标签: integer-programming

是否有适用于Python的混合整数线性规划(MILP)求解器？

GLPK python可以解决MILP问题吗？我读到它可以解决混合整数问题.
我对线性编程问题很新.所以我很困惑,如果混合整数规划与混合整数线性规划(MILP)不同,则无法区分.

这个问题出现在一个挑战中,但由于它现在已经关闭,因此可以询问它.

问题(不是这个问题本身,这只是背景信息)可以像这样直观地描述,借用他们自己的图像:

我选择以最佳方式解决它.这可能(对于决策变量)是NP完全问题(它肯定在NP中,它闻起来像一个精确的封面,虽然我还没有证明一般的确切覆盖问题可以减少到它),但是没关系,它只需要在实践中快速,不一定在最坏的情况下.在这个问题的上下文中,我对任何近似算法都不感兴趣,除非它们提供削减.

有一个明显的ILP模型:生成所有可能的正方形(如果它只覆盖存在的网格单元格,则x_i可以使用正方形),为每个正方形引入一个二进制变量,指示我们是否使用它,然后

minimize sum x_i

subject to:
1) x_i is an integer
2) 0 ? x_i ? 1
3) for every cell c
       (sum[j | c ? square_j] x_j) = 1

约束3表示每个细胞只被覆盖一次.约束1和2使x_i成为二进制.最小解决方案为原始问题提供了最佳解决方案.

这种线性松弛(即忽略约束1)是不太合适的,但它做了这样的事情(这是一个6x6网格,左上角缺失):

这里有13个方块被选为"一半"(给出一个6.5的目标值),大小(所以你可以更容易找到它们)

• 1x of 4x4
• 3x3中的3
• 6x2x2
• 1x1中的3个

此实例的最佳解决方案的目标值为8,例如:

线性放松是一半体面,但我并不完全满意.差距有时超过10%,有时会导致非常缓慢的整数阶段.

那是实际问题的来源,是否有额外的限制,我可以添加(懒惰)作为削减,以改善分数解决方案？

我已经尝试了问题的替代配方来寻找切割,例如,而不是选择正方形,如果我们选择"左上角"和"右下角",然后匹配形成非重叠方块覆盖所有细胞？然后在每个"反斜杠状对角线"上,必须有匹配数量的左上角和右下角.但这没有用,因为如果我们选择正方形,那么无论如何,这种情况总是正确的,也是在分数解决方案中.

我还尝试了一些关于重叠的推理,例如,如果两个正方形明显重叠,它们的总和不得大于1,并且可以通过添加完全包含在重叠区域中的所有正方形来改善.但是这种约束不如所有细胞只被覆盖一次的约束力强.

我已经尝试过关于总面积的推理(例如,总覆盖面积必须等于单元格的数量),但是已经通过约束来保证,每个单元必须覆盖一次,并根据总面积来说明只允许更多的自由.

我也尝试用方形数字(每个方格的面积,正好,正方形)和方形数字的差异做一些事情,但这并没有以任何有用的方式结束.

我正在尝试解决整数编程问题.我试过使用SCIP和LPSolve

例如,给定A和B的最终值,我想在以下C#代码中求解valA:

Int32 a = 0, b = 0;
a = a*-6 + b + 0x74FA - valA;
b = b/3 + a + 0x81BE - valA;
a = a*-6 + b + 0x74FA - valA;
b = b/3 + a + 0x81BE - valA;
// a == -86561, b == -32299

我以lp格式实现了这个整数程序(截断分区导致一些复杂化):

min: ;
+valA >= 0;
+valA < 92;
remAA_sign >= 0;
remAA_sign <= 1;
remAA <= 2;
remAA >= -2;
remAA +2 remAA_sign >= …

我有一个优化问题,在目标函数2中有多个变量,使模型呈二次方.

我目前正在使用zimpl来解析模型,并使用glpk来解决它.由于它们不支持二次规划,我需要将其转换为MILP.

.第一个变量是实数,在[0,1]范围内,第二个变量是实数,范围从0到inf.这个可以没有问题是整数.

目标函数中的关键部分如下所示:

max ... + var1 * var2 + ...

我在约束中遇到了类似的问题,但它们很容易解决.

我怎样才能在目标函数中解决这类问题？

我有一组金属滑动件,它们以下列方式约束在x和y轴上:

我需要最大化由相同滑块约束的所有部件之间的水平距离以及滑动件和滑块本身之间的垂直距离.怎么解决这个问题？

任何能够解决这个问题的建议和建议都将不胜感激.

我首先看了一些非常强大的库,比如cassowary和jsLPSolver但是我在理解核心算法以及如何检查约束的可行性以及如何对可能的解决方案进行排序方面遇到了一些麻烦.

如何在JavaScript中实现一个(简单的)存根,用于二维几何约束求解器,解决上述问题？

编辑:

我有以下输入数据:

maxW = 300, maxH = 320

这些部分定义如下(不是强制性的,每个解决方案都被接受):

slidingPiece = [pX, pY, width, height, anchorPoint, loopDistance];

我将尝试解释"最大化"下的含义.

水平间距:

a0-b1,b1-b2,b2-b4,b4-b5和b5-maxX将是相同的,即max X除以最大垂直交叉片数+ 1(5).然后由可用的剩余空间确定b1-b3和b3-b5.

垂直间距:

b1-a3,a3-a4和a0-b5是相同的.理想地,a0-b3,b3-b4,a2-b2,b4-a3和b2-a4也将是相同的值.最大化a1-b4和b3-a2与最大化b3-b4相同.这同样适用于a2-b2和b4-a3:距离b2-b4将是最大负值.

因此,我需要最大化每个滑动件之间的距离以及他最近或低于Y约束的距离.

该问题的二维几何表示显示水平间距取决于锚的垂直距离(由于锚定件的垂直交叉),而这又取决于件本身的水平位置.比如说,b2比上面略短.在这种情况下,b1和b2不再相交,并且将成为相同的x值,即max X除以4.

在一些其他情况下,例如b2在上面的部分中要长得多 - 并且将穿过锚a2,然后它应该间隔为a1.这就是原因,因为会有一组解决方案,一些是可行的,另一些则不是,因为例如,全局最大Y约束将被打破.

考虑m乘n矩阵M,其所有条目都是0或1.对于给定的M,问题是是否存在非零向量v,其所有条目都是-1,0或1,其中Mv = 0.例如,

      [0 1 1 1]
M_1 = [1 0 1 1]
      [1 1 0 1]

在这个例子中,没有这样的向量v.

      [1 0 0 0]
M_2 = [0 1 0 0]
      [0 0 1 0]

在此示例中,向量(0,0,0,1)给出M_2v = 0.

给定m和n,我想找到是否存在这样的M,使得不存在非零v,使得Mv = 0.

如果m = 3和n = 4那么答案是肯定的,因为我们可以在上面看到.

我目前通过尝试所有不同的M和v来解决这个问题,这是非常昂贵的.

但是,是否可以将问题表达为整数编程问题或约束编程问题,因此我可以使用现有的软件包,例如SCIP,这可能更有效.

给定一个线性系统Ax = b,矩阵A和向量b具有整数值,我想找到解决这个方程的所有非负整数向量x.

到目前为止,我已经找到了一些技术,如Smith正规形式或Hermite正规形式的矩阵来找到整数解,我想我可以使用线性求解器来找到非负解.有没有一个可以让这更容易的图书馆？

Python解决方案是理想的,但如果一个库存在于另一种语言中我想知道它.

我正在使用PuLPPython中的模块来制定混合整数程序.我试图找出如何MIP start通过PuLP接口设置(即程序的可行解决方案).

这里MIP start给出了如何设置的详细信息

该PuLP软件包的开发人员声称您可以通过此处的PuLP界面访问完整的Gurobi模型

贴在下面是两个完整的模型.我已经使这些尽可能小,同时防止gurobi求解器使用启发式找到最佳值.

我试图在两个模型中设置初始解决方案(到最佳值),但在PuLP模型中它被忽略,但在gurobipy模型中它按预期工作.

如何通过PuLP接口为Gurobi解决方案设置初始解决方案？

from pulp import *

prob = LpProblem("min example",LpMinimize)

x1=LpVariable("x1",0,None,LpInteger)
x2=LpVariable("x2",0,None,LpInteger)
x3=LpVariable("x3",0,None,LpInteger)
x4=LpVariable("x4",0,None,LpInteger)

# Objective function
prob += 3*x1 + 5*x2 + 6*x3 + 9*x4

# A constraint
prob += -2*x1 + 6*x2 -3*x3 + 4*x4 >= 2, "Con1"
prob += -5*x1 + 3*x2 + x3 + 3*x4 >= -2, "Con2"
prob += …

我正在尝试创建最佳轮班时间表，在该时间表中将员工分配到轮班时间。输出应旨在花费最少的钱。棘手的部分是我需要考虑特定的约束。这些是：

1) At any given time period, you must meet the minimum staffing requirements
2) A person has a minimum and maximum amount of hours they can do
3) An employee can only be scheduled to work within their available hours
4) A person can only work one shift per day

在staff_availability df包含了员工的选择['Person']，可用最小-最大小时他们能够工作['MinHours']- ['MaxHours']，他们得到了多少钱['HourlyWage']，和可用性，表示小时['Availability_Hr']和15分钟片段['Availability_15min_Seg']。

注意：如果不需要，可以不必分配可用的员工轮班。他们只是可以这样做。

该staffing_requirements df包含一天中的时间['Time']和所需的工作人员['People']在这些时期。

该脚本返回df 'availability_per_member'，显示每个时间点有多少员工可用。因此， …

尝试在 Gurobi/Python 中添加以下约束：

代码

N_SERVERS = 5                             #number of servers
C_SERVER = [1]*N_SERVERS
N_NODES = 3                               #number of nodes
C_NODES = [2]*N_NODES    

#create model
m = Model("mip1")

#declare variables
x = m.addVars(len(C_SERVER), vtype=GRB.BINARY, name = "x")
y = m.addVars(len(C_NODES), vtype=GRB.BINARY, name = "y")
m.update()

m.addConstrs(quicksum(x[i]*C_SERVER[i] for i in range(len(x))) + quicksum(y[j]*C_NODES[j] for j in range(len(y))) == quicksum(C_SERVER)

我收到以下错误：KeyError: '缺少约束索引'。是什么原因？