标签: linear-programming

我有一个很大的MIP问题，我使用GLPK中的GLPSOL来解决它。然而，求解LP松弛问题需要多次迭代，并且每次迭代的obj和infeas值都是相同的。我认为它已经找到了最优解，但它不会停止，并且持续运行了好几个小时。每个大规模 MIP/LP 问题都会发生这种情况吗？遇到这样的情况我该如何处理？有人可以给我任何关于这个的建议吗？谢谢！

我想表达一个线性程序，其变量只能大于或等于常数 c 或等于 0。范围 ]0; c[ 是不允许的。

您是否知道一种在线性程序中表达此约束的方法，并且可以使用未经修改的单纯形实现来解决该约束？

例如此约束：x1 >= 4 或 x1 = 0。

线性程序中所有约束之间的典型关系是 AND。这是两个约束之间的或。

注意：我需要以计算有效的方式解决具有多个变量的问题。

我使用 CBC 来解决不同的整数线性规划问题。对于其中一些，约束集是没有解决方案的。在这种情况下，我得到如下信息：

Problem is infeasible - 0.30 seconds
Infeasible - objective value -6832.50000000

CBC 有什么办法可以告诉我“为什么”这个问题不可行？例如，我很乐意拥有一组不兼容的最小约束。

在我用 python 中的 PuLP 求解的 LP 模型中，我有两组决策变量，例如

#Variables x 
x = LpVariable.dicts("Decision_x",(range(3),range(3)),0,1,LpInteger)
#Variables y 
y = LpVariable.dicts("Decision_y",(range(3),range(3)),0,1,LpInteger)

求解模型后，我只对 x[i][j] 取值为 1 的变量感兴趣。我知道

for v in prob.variables():
    if v.varValue == 1:
        print(v)

我可以打印所有值等于 1 的变量。因此，所有值等于 1 的 x 和所有 y 变量都会被打印。如何设法仅访问 x 变量，以便不打印 y 变量？我尝试过prob.variables(x)，prob.variables()[x]但到目前为止没有任何效果。

然后在下一步中，我想提取 x 等于 1 的 x 变量的索引。例如，如果x[1][3] == 1我想找到索引 1 和 3。PuLP 中有什么聪明的方法来实现这一点吗？

我正在尝试使用 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 …

我对纸浆完全陌生，想知道是否需要优化以下内容：

x = pulp.LpVariable.dicts("Volume", range(0, 7), cat='Binary')

其中只要有 0，则至少需要有 3 个。

所以解可以是 [0,0,0,0,0,0,1], [0,0,0,1,0,0,0], [1,1,1,0,0,0, 1] 但不是 [1,0,1,0,1,0,0]。

我尝试添加一个约束，如下所示：

prob += min([len(list(g)) for k, g in itertools.groupby(x.values()) if k == 0]) >= 3

但没有成功。

我该如何表述呢？

我读到 scipy 中的 linprog 返回最小解决方案，并且可以通过将目标函数乘以 -1 来获得最佳解决方案。

我在这里读到它： https: //realpython.com/linear-programming-python/ 我已经测试了他们提供的示例，看看我是否也能得到最小的解决方案——我可以。


关于我试图解决的问题，我希望解决方案是：

opt_sol1.x = [0.61538462 0.38461538]
opt_sol2.x = [0.0, 1.0]

但在两种情况下我都得到相同的结果 [0.61538462 0.38461538] 为什么？-- 我的猜测是它与我的目标函数中的值相互接近有关，但只是猜测有没有一种方法可以得到我正在寻找的第二个解决方案？

from scipy.optimize import linprog

obj_fct1 = [0.5, 0.5]
obj_fct2 = [-0.5, -0.5]
lhs_ineq = [[1.5, 0.2]]
rhs_ineq = [1]
lhs_eq = [[1,1]]
rhs_eq = [1]
bnds = [(0, 1),
          (0, 1)]

opt_sol1 = linprog(c=obj_fct1,
                  A_ub=lhs_ineq,
                  b_ub=rhs_ineq,
                  A_eq=lhs_eq,
                  b_eq=rhs_eq,
                  bounds=bnds)
print(opt_sol1.x)
print("------------------------------------------")
opt_sol2 = linprog(c=obj_fct2,
                  A_ub=lhs_ineq,
                  b_ub=rhs_ineq,
                  A_eq=lhs_eq,
                  b_eq=rhs_eq,
                  bounds=bnds)
print(opt_sol2.x)


>>> [0.61538462 0.38461538]
>>> ------------------------------------------ …

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

    cplex_model.setParam(EpGap, 0.01);

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

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

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

我必须解决纸浆的整数线性优化问题。我解决了问题，并获得了等于42的优化值。但是，当我编写更通用的代码时，例如在循环内声明变量，在循环内定义约束以及使用lpSum函数定义优化，我没有解决方案。我认为我的问题是定义下一个约束。

for a in itemset_dict.keys():
    for b in itemset_dict[a][0]:
        my_lp_program +=b  >=  a, "2Constraint"

我收到以下警告：

C:\Program Files\Python36\lib\site-packages\pulp\pulp.py:1353: UserWarning: Overwriting previously set objective.
  warnings.warn("Overwriting previously set objective.")
Status: Optimal
Total Optimum= None
__dummy = None
products_beer = 0.0
products_cheese = 0.0
products_cola = 0.0
products_peanuts = 0.0
The thread 'MainThread' (0xb30) has exited with code 0 (0x0).
The program '[10140] python.exe' has exited with code 0 (0x0).

谢谢。

      from pulp import *

# defining list of products
products = ['cola','peanuts', 'cheese', …