使用 Python 中的 cvxpy 库解决整数编程问题
最编程
2024-04-20 11:10:42
...
Python的scipy库中提供了解简单线性或非线性规划问题,但是不能求解如背包问题的0-1规划问题,或整数规划问题,混合整数规划问题,CVXPY库可以求解以上类型的问题。本文将使用cvxpy库求解整数规划问题。如果你需要使用cvxpy求解背包 问题或混合整数规划问题可以直接在cvxpy的官方文档上查询相关的例子。
Cvxpy库官方提供算例
本文求解的整数规划问题如下:
Objective: \(\text{min: }Z = \sum_{i=0}^5x_i\)
Constrains:
\[\begin{aligned} 0 \leq x_1 \le 25\\ 0 \leq x_2 \le 12\\ 0 \leq x_3 \le 12.5\\0 \leq x_4 \le 2\\0 \leq x_5 \le 0 \\ x_1 \le 10\\x_2 \le 40 \\x_3 \le 90\\x_4 \le 80\\x_5 \le 0\\-1*x_1 \le 40\\-0.9*x_1-x_2 \le 2\\-0.8x_1-(5/6)*x_2-x_3 \le -30\\-0.3x_1-(5/8)*x_2-0.8*x_3-x_4 \le 38\end{aligned}
\]
import cvxpy as cp
import numpy as np
# Create two scalar optimization variables.
n = 5
x = cp.Variable(n, integer=True)#cvxpy使用cp.Variable(n,intger = True) 中的intger参数来规定x变量为整数
# # Create two constraints.
A1 = np.ones((5,5))
for i in range(A1.shape[0]):
for j in range(A1.shape[1]):
if i == j:
pass
else:
A1[i,j] = A1[i,j]*0
A2 = A1 * (-1)
A3 = np.array([[-1,0,0,0,0],[-0.9,-1,0,0,0],[-0.8,-(40/48),-1,0,0],[-0.3,-(5/8),-0.8,-1,0]])
B = np.array([0,0,0,0,0,25,12,12.5,2,0,10,40,90,80,0,40,2,-30,32])
A = np.vstack((A2,A1,A1,A3))
constraints = [A @ x <= B]
objects = cp.Minimize(cp.sum(x))
# Define and solve the CVXPY problem.
prob = cp.Problem(objects,constraints)
prob.solve(solver=cp.CPLEX)#此处使用IBM商业求解器CPLEX作为求解器,对于没有安装CPLEX的同学可以通过pip install cplex安装该求解器,亦可将此处更改为solver = cp.ECOS_BB使用convexpy自带求解器对该问题进行求解
# Print result.
print("\nThe optimal value is", prob.value)
print("A solution x is")
print(x.value)
# print(help(prob))
# print (cp.installed_solvers())
'''结果如下:
The optimal value is 34.00000013019109
A solution x is
[ 1.00000000e+01 1.20000000e+01 1.20000000e+01 1.11983366e-07
-6.64682255e-09]
'''
有同学反映在prob.solve(solver=cp.CPLEX)一行报错,此处我的代码使用IBM商业求解器CPLEX作为求解器,对于没有安装CPLEX的同学可以通过pip install cplex安装该求解器,亦可将此处更改为solver = cp.ECOS_BB使用convexpy自带求解器对该问题进行求解。
原文地址:https://www.cnblogs.com/the-therma/p/16260195.html
上一篇: 匹配数字的正则表达式(附代码)
下一篇: 整数编程 第五章--分隔符
推荐阅读
-
[推荐阅读 - 优化中的 R 语言]使用 Rglpk 软件包解决线性规划和整数规划问题
-
使用 Python 中的 cvxpy 库解决整数编程问题
-
[姿势估计] 实践记录:使用 Dlib 和 mediapipe 进行人脸姿势估计 - 本文重点介绍方法 2):方法 1:基于深度学习的方法:。 基于深度学习的方法:基于深度学习的方法利用深度学习模型,如卷积神经网络(CNN)或递归神经网络(RNN),直接从人脸图像中学习姿势估计。这些方法能够学习更复杂的特征表征,并在大规模数据集上取得优异的性能。方法二:基于二维校准信息估计三维姿态信息(计算机视觉 PnP 问题)。 特征点定位:人脸姿态估计的第一步是通过特征点定位来检测和定位人脸的关键点,如眼睛、鼻子和嘴巴。这些关键点提供了人脸的局部结构信息,可用于后续的姿势估计。 旋转表示:常见的旋转表示方法包括欧拉角和旋转矩阵。欧拉角通过三个旋转角度(通常是俯仰、偏航和滚动)描述头部的旋转姿态。旋转矩阵是一个 3x3 矩阵,表示头部从一个坐标系到另一个坐标系的变换。 三维模型重建:根据特征点的定位结果,三维人脸模型可用于姿势估计。通过将人脸的二维图像映射到三维模型上,可以估算出人脸的旋转和平移信息。这就需要建立人脸的三维模型,然后通过优化方法将模型与特征点对齐,从而获得姿势估计结果。 特征点定位 特征点定位是用于检测人脸关键部位的五官基础部分,还有其他更多的特征点表示方法,大家可以参考我上一篇文章中介绍的特征点检测方案实践:人脸校正二次定位操作来解决人脸校正的问题,客户在检测关键点的代码上略有修改,坐标转换部分客户见上图 def get_face_info(image). img_copy = image.copy image.flags.writeable = False image = cv2.cvtColor(image, cv2.COLOR_BGR2RGB) results = face_detection.process(image) # 在图像上绘制人脸检测注释。 image.flags.writeable = True image = cv2.cvtColor(image, cv2.COLOR_RGB2BGR) box_info, facial = None, None if results.detections: for detection in results. for detection in results.detections: mp_drawing.Drawing.detection = 无 mp_drawing.draw_detection(image, detection) 面部 = detection.location_data.relative_keypoints 返回面部 在上述代码中,返回的数据是五官(6 个关键点的坐标),这是用 mediapipe 库实现的,下面我们可以尝试用另一个库:dlib 来实现。 使用 dlib 使用 Dlib 库在 Python 中实现人脸关键点检测的步骤如下: 确保已安装 Dlib 库,可使用以下命令: pip install dlib 导入必要的库: 加载 Dlib 的人脸检测器和关键点检测器模型: 读取图像并将其灰度化: 使用人脸检测器检测图像中的人脸: 对检测到的人脸进行遍历,并使用关键点检测器检测人脸关键点: 显示绘制了关键点的图像: 以下代码将参数 landmarks_part 添加到要返回的关键点坐标中。
-
趣谈留言队列,搞清楚留言队列到底是什么!-说到消息队列,洪觉大概能猜到人们听到消息队列的反应,大致可以分为以下几类人。 第一类人,懵懵懂懂,刚上大学接触编程,还没用过消息队列,甚至还以为消息队列就是代码里面要新建一个List之类的;第二类人,听过消息队列,了解消息队列,但具体是什么还不是太明白,只知道一说到消息队列,脑海里马上出现了三组词,削峰、异步、解耦;第三类人,用过消息队列,对它有一定了解,但不知道为什么要这样设计,消息队列有什么样的前世今生,是如何演化到现在的模式的?**第四类人,已经对消息队列有了足够的了解,可以阅读本帖作为复习和温习。**你属于哪一类?无论你对消息队列了解多少,读完这篇文章后,我相信你都会有所收获。 什么是消息队列?我们为什么要使用消息队列?真的只是因为它看起来很勉强、很常用吗?当然不是,一项技术的出现往往是为了解决某种痛点,我们就从这个痛点出发,看看消息队列到底是为了解决什么问题而诞生的。 相信大家在工作之前,或者工作中接触单片机的次数会多一点,不管什么业务都一股脑塞进一个系统里,这种情况下接触消息队列的场景会比较少。但随着业务的增长,量上去了,单机系统就很难维护了,也扛不住并发量的增长,就需要把原来的单体应用拆分成多个服务。例如,牛奇网采用分布式架构,将原来的单体系统拆分成用户服务、题库服务、求职服务、论坛服务等,每个分布式节点都有一个集群,保证高可用性。 那虽然在这样的微服务架构下,如果某个核心业务并发量过大,系统就扛不住了。比如淘宝、淘票票、拼多多、京东等电商场景中的支付场景,你在某宝下单并支付后,调用支付服务,完成支付后,还需要更新订单的状态,这个时候就需要调用订单服务,那我们平时也下单,除了简单完成这些操作外,还会给你相应的积分;商家也会收到订单消息,并给您发送旺旺消息,确认订单无误;同时,也会给您发送消息,确认订单无误。确认订单无误;同时您还可以查看您的物流状态;还有系统为了给您推荐更适合您的商品,会根据您的订单做类似的推荐等等,我说的这些都是当我们下单后,肉眼可以感知到系统所做的动作。 **一个支付动作如果还需要调用那么多服务,等他们响应成功,最后再告诉用户你支付成功了,用户在系统中的整个体验会非常糟糕。**设想一下,假设请求服务+处理请求+响应总共需要 50ms,我们上面列出的场景:支付服务、订单服务、积分服务、商家服务、物流服务、推荐服务,总共需要 300ms。
-
解决使用 POI 库生成的 word 文件中的表格无法在 python-docx 中解析的问题。
-
Python 输入整数 a(1~9) 和 n( Python 输入整数 a(1~9)和 n(<9),求 a+aa+aaa+...+a...a(最后一项为 n 位数,每一位数为 a) I.问题描述 给定两个整数 a 和 n,其中 a 的取值范围为 1 到 9,n 的取值范围为小于 9。+ a....a(最后一项是 n 个数字,每个数字都是 a)的值。 二、解题思路 要解决这个问题,我们可以按照下面的步骤进行: 步骤 说明 1 定义两个变量 a 和 n,分别存储输入整数 a 和 n 的值 2 使用循环生成一个从 1 到 n 的数组。 3 使用循环生成一个从 1 到 n 的数组,每个数组的值为
-
阿里味 "的《Redis核心实践全彩手册》给你,还学不会转行--Redis基本是必考点。在 "阿里味 "的《Redis核心实战全彩手册》里,你还是学不会转行--Redis基本是必考点: - Redis 常见的性能问题有哪些?Redis 最常见的性能问题有哪些,如何解决?--性能相关 - Redis 缓存的雪崩、击落和穿透到底意味着什么?如何处理?--缓存相关 - Redis 主从集群有哪些常见问题?如何解决?--可用性 - 现有的 Redis 实例有 6GB 的存储空间,预计将来会扩展到 32GB,你能提供解决方案并分析其优势和潜在问题吗?--可扩展性相关 毕竟,10 家公司中至少有 8 家的架构系统中都有 Redis,基本上可以说是 IT 基础架构的必备系统。 因此,Redis 的开发和运维是很多大厂的重要工作,也是我们必须掌握的技术栈。 不过,Redis 毕竟是一个复杂的键值数据库,在实际使用中,有非常多的技术点需要注意,比如:各种数据结构、数据持久化机制、分片集群、主从集群等等。 一不小心,性能就会每况愈下,失去 "快 "的最大特点!
-
windows下进程间通信的(13种方法)-摘 要 本文讨论了进程间通信与应用程序间通信的含义及相应的实现技术,并对这些技术的原理、特性等进行了深入的分析和比较。 ---- 关键词 信号 管道 消息队列 共享存储段 信号灯 远程过程调用 Socket套接字 MQSeries 1 引言 ---- 进程间通信的主要目的是实现同一计算机系统内部的相互协作的进程之间的数据共享与信息交换,由于这些进程处于同一软件和硬件环境下,利用操作系统提供的的编程接口,用户可以方便地在程序中实现这种通信;应用程序间通信的主要目的是实现不同计算机系统中的相互协作的应用程序之间的数据共享与信息交换,由于应用程序分别运行在不同计算机系统中,它们之间要通过网络之间的协议才能实现数据共享与信息交换。进程间通信和应用程序间通信及相应的实现技术有许多相同之处,也各有自己的特色。即使是同一类型的通信也有多种的实现方法,以适应不同情况的需要。 ---- 为了充分认识和掌握这两种通信及相应的实现技术,本文将就以下几个方面对这两种通信进行深入的讨论:问题的由来、解决问题的策略和方法、每种方法的工作原理和实现、每种实现方法的特点和适用的范围等。 2 进程间的通信及其实现技术 ---- 用户提交给计算机的任务最终都是通过一个个的进程来完成的。在一组并发进程中的任何两个进程之间,如果都不存在公共变量,则称该组进程为不相交的。在不相交的进程组中,每个进程都独立于其它进程,它的运行环境与顺序程序一样,而且它的运行环境也不为别的进程所改变。运行的结果是确定的,不会发生与时间相关的错误。 ---- 但是,在实际中,并发进程的各个进程之间并不是完全互相独立的,它们之间往往存在着相互制约的关系。进程之间的相互制约关系表现为两种方式: ---- (1) 间接相互制约:共享CPU ---- (2) 直接相互制约:竞争和协作 ---- 竞争——进程对共享资源的竞争。为保证进程互斥地访问共享资源,各进程必须互斥地进入各自的临界段。 ---- 协作——进程之间交换数据。为完成一个共同任务而同时运行的一组进程称为同组进程,它们之间必须交换数据,以达到协作完成任务的目的,交换数据可以通知对方可以做某事或者委托对方做某事。 ---- 共享CPU问题由操作系统的进程调度来实现,进程间的竞争和协作由进程间的通信来完成。进程间的通信一般由操作系统提供编程接口,由程序员在程序中实现。UNIX在这个方面可以说最具特色,它提供了一整套进程间的数据共享与信息交换的处理方法——进程通信机制(IPC)。因此,我们就以UNIX为例来分析进程间通信的各种实现技术。 ---- 在UNIX中,文件(File)、信号(Signal)、无名管道(Unnamed Pipes)、有名管道(FIFOs)是传统IPC功能;新的IPC功能包括消息队列(Message queues)、共享存储段(Shared memory segment)和信号灯(Semapores)。 ---- (1) 信号 ---- 信号机制是UNIX为进程中断处理而设置的。它只是一组预定义的值,因此不能用于信息交换,仅用于进程中断控制。例如在发生浮点错、非法内存访问、执行无效指令、某些按键(如ctrl-c、del等)等都会产生一个信号,操作系统就会调用有关的系统调用或用户定义的处理过程来处理。 ---- 信号处理的系统调用是signal,调用形式是: ---- signal(signalno,action) ---- 其中,signalno是规定信号编号的值,action指明当特定的信号发生时所执行的动作。 ---- (2) 无名管道和有名管道 ---- 无名管道实际上是内存中的一个临时存储区,它由系统安全控制,并且独立于创建它的进程的内存区。管道对数据采用先进先出方式管理,并严格按顺序操作,例如不能对管道进行搜索,管道中的信息只能读一次。 ---- 无名管道只能用于两个相互协作的进程之间的通信,并且访问无名管道的进程必须有共同的祖先。 ---- 系统提供了许多标准管道库函数,如: pipe——打开一个可以读写的管道; close——关闭相应的管道; read——从管道中读取字符; write——向管道中写入字符; ---- 有名管道的操作和无名管道类似,不同的地方在于使用有名管道的进程不需要具有共同的祖先,其它进程,只要知道该管道的名字,就可以访问它。管道非常适合进程之间快速交换信息。 ---- (3) 消息队列(MQ) ---- 消息队列是内存中独立于生成它的进程的一段存储区,一旦创建消息队列,任何进程,只要具有正确的的访问权限,都可以访问消息队列,消息队列非常适合于在进程间交换短信息。 ---- 消息队列的每条消息由类型编号来分类,这样接收进程可以选择读取特定的消息类型——这一点与管道不同。消息队列在创建后将一直存在,直到使用msgctl系统调用或iqcrm -q命令删除它为止。 ---- 系统提供了许多有关创建、使用和管理消息队列的系统调用,如: ---- int msgget(key,flag)——创建一个具有flag权限的MQ及其相应的结构,并返回一个唯一的正整数msqid(MQ的标识符); ---- int msgsnd(msqid,msgp,msgsz,msgtyp,flag)——向队列中发送信息; ---- int msgrcv(msqid,cmd,buf)——从队列中接收信息; ---- int msgctl(msqid,cmd,buf)——对MQ的控制操作; ---- (4) 共享存储段(SM) ---- 共享存储段是主存的一部分,它由一个或多个独立的进程共享。各进程的数据段与共享存储段相关联,对每个进程来说,共享存储段有不同的虚拟地址。系统提供的有关SM的系统调用有: ---- int shmget(key,size,flag)——创建大小为size的SM段,其相应的数据结构名为key,并返回共享内存区的标识符shmid; ---- char shmat(shmid,address,flag)——将当前进程数据段的地址赋给shmget所返回的名为shmid的SM段; ---- int shmdr(address)——从进程地址空间删除SM段; ---- int shmctl (shmid,cmd,buf)——对SM的控制操作; ---- SM的大小只受主存限制,SM段的访问及进程间的信息交换可以通过同步读写来完成。同步通常由信号灯来实现。SM非常适合进程之间大量数据的共享。 ---- (5) 信号灯 ---- 在UNIX中,信号灯是一组进程共享的数据结构,当几个进程竞争同一资源时(文件、共享内存或消息队列等),它们的操作便由信号灯来同步,以防止互相干扰。 ---- 信号灯保证了某一时刻只有一个进程访问某一临界资源,所有请求该资源的其它进程都将被挂起,一旦该资源得到释放,系统才允许其它进程访问该资源。信号灯通常配对使用,以便实现资源的加锁和解锁。 ---- 进程间通信的实现技术的特点是:操作系统提供实现机制和编程接口,由用户在程序中实现,保证进程间可以进行快速的信息交换和大量数据的共享。但是,上述方式主要适合在同一台计算机系统内部的进程之间的通信。 3 应用程序间的通信及其实现技术 ---- 同进程之间的相互制约一样,不同的应用程序之间也存在竞争和协作的关系。UNIX操作系统也提供一些可用于应用程序之间实现数据共享与信息交换的编程接口,程序员可以通过自己编程来实现。如远程过程调用和基于TCP/IP协议的套接字(Socket)编程。但是,相对普通程序员来说,它们涉及的技术比较深,编程也比较复杂,实现起来困难较大。 ---- 于是,一种新的技术应运而生——通过将有关通信的细节完全掩盖在某个独立软件内部,即底层的通讯工作和相应的维护管理工作由该软件内部来实现,用户只需要将通信任务提交给该软件去完成,而不必理会它的具体工作过程——这就是所谓的中间件技术。 ---- 我们在这里分别讨论这三种常用的应用程序间通信的实现技术——远程过程调用、会话编程技术和MQSeries消息队列技术。其中远程过程调用和会话编程属于比较低级的方式,程序员参与的程度较深,而MQSeries消息队列则属于比较高级的方式,即中间件方式,程序员参与的程度较浅。 ---- 4.1 远程过程调用(RPC)
-
南邮OJ Web任务大揭秘:层层挑战剖析 1. 挑战一:迷宫般的目录探索 题目作者似乎穷举了所有可能的目录组合,最终在404.php中的