标签: integer-programming

我试图在MIP中建模以下约束:

x_1 +x_2 + ... +x_n != d

我的想法是引入一个变量z,即1,如果x_1 + x_2 + ... + x_n = d并添加约束

z <= 0.

但我无法弄清楚如何建模约束

(x_1 +x_2 + ... +x_n = d) ==> z=1 

在整数程序中.

我正在尝试解决背包问题,这也是整数编程问题.我已经研究了几种近似解决方案,如动态编程,贪婪算法,分支定界算法,遗传算法.你能告诉我一个库(用任何语言)来帮助实现任何/所有这些算法吗？

提前致谢.

我正在尝试使用 Apache commons Math 库对我的问题应用线性编程。我在网上看到一个例子，解决了下面的例子

max.  3X + 5Y 

 s.t.

 2X + 8Y <= 13 

 5X - Y <= 11 

 X >= 0, Y >= 0 

代码就像

LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 3, 5}, 0);

 Collection constraints = new ArrayList();
 constraints.add(new LinearConstraint(new double[] { 2, 8}, Relationship.LEQ, 13));
 constraints.add(new LinearConstraint(new double[] { 5, -1}, Relationship.LEQ, 11));

 constraints.add(new LinearConstraint(new double[] { 1, 0}, Relationship.GEQ, 0));
 constraints.add(new LinearConstraint(new double[] { 0, 1}, Relationship.GEQ, 0));

 //create and run solver
 RealPointValuePair solution …

我用c ++编写代码并调用CPLEX来解决它.它很快找到了一个非常好的解决方案,但需要很长时间才能改进它.所以我想将间隙设置为更大的值来终止代码,这就是我使用的:

    cplex_model.setParam(EpGap, 0.01);

但编译器给我一个错误,说EpGap是一个未声明的标识符.相对差距的默认名称是什么？

我正在尝试使用Python 2.7上的CVXOPT库解决https://en.wikipedia.org/wiki/Integer_programming#Example中找到的简单示例；最佳答案是（1,2）或（2,2）。我得到（0.0，0.0）。我在下面的代码中做错了什么？谢谢 ！

import numpy as np
import cvxopt
from cvxopt import glpk

c=cvxopt.matrix([0,-1]) #-1 since we're maximising the 2nd variable
G=cvxopt.matrix([[-1,1],[3,2],[2,3],[-1,0],[0,-1]],tc='d')
h=cvxopt.matrix([1,12,12,0,0],tc='d')
(status, x)=glpk.ilp(c,G.T,h,B=set([0,1]))
print status
print x[0],x[1]    #should be (1,2) or (2,2)
print sum(c.T*x)

我正在学习用于自动分组用户的优化算法.但是,我对这些算法完全陌生,我在回顾相关文献时听说过它们.而且,不同的是,在其中一篇文章中,作者使用整数编程实现了他们自己的算法(基于他们自己的逻辑)(这就是我所知道的IP).

我想知道是否需要使用混合整数线性编程实现遗传/粒子群(或任何其他优化)算法,或者这只是其中一个选项.最后,我需要构建一个基于Web的系统,自动对用户进行分组.我感谢任何帮助.

我需要从这个 if-else 语句构建一个 MILP（混合整数线性规划）约束：其中 beta 是一个常量。

if (a > b) then c = beta else c = 0

如何构建 MILP 约束的语句。有没有什么技术可以解决这个问题。谢谢。

我一直在研究可以建模为整数线性规划的组合优化问题。我在 Visual Studio 2017 和 CPLEX1271 中将它实现为一个 C++ 项目。由于有成倍数的约束，我通过 IloCplex::LazyConstraintCallbackI 实现了惰性约束。在我看来，以下过程是如何产生最优解的：每次确定一个整数解时，LazyConstraintCallbackI 将检查它并向模型添加一些违反约束，直到获得最优整数解。

但是，我对不同输入的实现给出的目标值并不总是正确的。经过将近一年的间歇性调试和测试，我终于找到了原因，这与问题非常相关，但可以通过以下小示例来解释（希望如此）：涉及四个布尔变量 x1、x2、x3 和 x4 的整数线性规划

minimize x1
subject to: 
x1  ?  x2
x1  ?  x3
x1  ?  x4
x2  + x3  ? 1
x1, x2, x3 and x4  ? {0, 1}?

cplex给出的结果是：

Solution status = Optimal
Objective value = 1
x1 = 1
x2 = 1
x3 = 1
x4 = 1?

毫无疑问，目标值是正确的。奇怪的是cplex设置x4 = 1。虽然x4等于1或0对这个编程中的目标值没有影响。但是，当使用惰性约束回调时，这可能会通过添加一些不正确的约束而导致问题，并且整数编程可以通过迭代添加违反约束来解决。我想知道：

1. 为什么 cplex 将“无关”变量 x4 设置为 1，而不是 0？
2. 我应该怎么做才能告诉 CPLEX 我想将这种“无关”变量保留为 0？