标签: glpk

我正在研究一些非常大规模的线性规划问题。（矩阵目前大约为 1000x1000，这些是“迷你”矩阵。）

我以为我的程序运行成功了，但我才意识到我得到了一些非常不直观的答案。例如，假设我要在一组约束 x+y<10 和 y+z <5 下最大化 x+y+z。我运行它并获得最佳解决方案。然后，我运行相同的方程，但有不同的约束：x+y<20 和 y+z<5。然而在第二次迭代中，我的最大化减少了！

我已经煞费苦心地经历了，并向自己保证约束加载正确。

有谁知道问题可能是什么？

我在关于 lpx_check_kkt 的文档中找到了一些东西，它似乎告诉你你的解决方案何时可能是正确的或高可信度（或低可信度），但我不知道如何使用它。

我尝试并收到错误消息 lpx_check_kkt 未定义。

我正在添加一些代码作为附录，希望有人能找到错误。这样做的结果是它声称已经找到了一个最佳解决方案。然而，每次我提高上限时，它都会变得不太理想。
我已经确认我的界限是上升而不是下降。

    size = 10000000+1
    ia = intArray(size)
    ja = intArray(size)
    ar = doubleArray(size)
    prob = glp_create_prob()

    glp_set_prob_name(prob, "sample")
    glp_set_obj_dir(prob, GLP_MAX)
    glp_add_rows(prob, Num_constraints)
    for x in range(Num_constraints):
            Variables.add_variables(Constraints_for_simplex)
            glp_set_row_name(prob, x+1, Variables.variers[x])
            glp_set_row_bnds(prob, x+1, GLP_UP, 0, Constraints_for_simplex[x][1])
            print 'we set the row_bnd for', x+1,' to ',Constraints_for_simplex[x][1]
    glp_add_cols(prob, len(All_Loops))
    for x in range(len(All_Loops)):
            glp_set_col_name(prob, x+1, "".join(["x",str(x)]))
            glp_set_col_bnds(prob,x+1,GLP_LO,0,0)
            glp_set_obj_coef(prob,x+1,1)
    for x in range(1,len(All_Loops)+1):
            z=Constraints_for_simplex[0][0][x-1] …

这是我的完整问题:

信息:

*最大.总投资:125美元

*支付是购买的单位x支付/单位的总和

*每次投资成本:购买成本+成本/单位x如果您购买至少一个单位的单位数量

*费用是每笔投资的总和

约束:

*您可能不会同时投资2和5.

*只有投资2和3中的至少一个,您才可以投资1.

*您必须至少投资3,4,5中的两个.

*您的投资额不得超过最大单位数.

问题:最大化利润:支付 - 成本

 xi: # of units i ? {1,2,3,4,5}
 yi=1 if xi>0 else yi=0
 cost = sum{i in I} buyInCost_i * yi + cost-unit_i*xi
 pay-off = sum{i in I} (pay-off/unit)_i*xi
 profit = pay-off - cost

 Maximize profit

 Subject to

 y2+y5 <= 1
 y1<= y2+y3
 y3+y4+y5 >= 2
 x1<=5, x2<=4, x3<=5, x4<=7, x5<=3
 cost<=125

这是我的问题:

例如,我有这个二进制变量y

 yi=1 if xi>0 else yi=0  and i ? {1,2,3,4,5}

我宣称我是一个数据集

 set I;

 data; …

我正在尝试使用PuLP,但是需要50秒才能添加4000个约束(67个变量).解决问题只需要几分之一秒.

我们希望使用PuLP轻松测试一大堆问题上的几个求解器.

它应该花这么长时间服用PuLP吗？直接使用PyGLPK只需要一小部分时间,包括设置和求解,所以我希望不会.我该怎么做才能提高PuLP中这一步骤的效率？

更新

我的约束矩阵非常稀疏,并且通过仅包括非零系数,我能够将该特定问题的建立时间减少到4或5秒.我仍然能够编写自己的.lp或.mps格式的文件,用cbc或glpsol子进程解决问题,并且比PuLP更有效地解析解决方案,因为我可以在几毫秒内编写输入文件PuLP需要几秒钟.我仍然不确定为什么会这样.

我必须找到一些微小的线性编程问题的所有基本解决方案。

这是一个示例（采用lp_solve格式）：

max: x1 + x2;
x1 + x2 <= 1;
x1 <= 0.8;
x2 <= 0.8;

所有2种基本解决方案：

• x1 = 0.2，x2 = 0.8
• x1 = 0.8，x2 = 0.2

当然，有一种寻找替代解决方案的方法，但是我真的更喜欢使用现有的库，而不是精心设计自己的单纯形代码。

我使用Python作为编程语言，希望lp_solve或GLPK的C API中有某种方法可以做到这一点。

谢谢。

我正在使用 cvxpy，自从更新到 1.0.6 以来，我在调用 GLPK 时得到了不需要的输出。

import cvxpy as cvx
x = cvx.Variable(2)
p = cvx.Problem(cvx.Minimize(x[0]), [x[0] + x[1] == 1, x[0] - x[1] >= 1])
p.solve(solver = cvx.GLPK)

在 IPython3 中，这会创建输出

GLPK Simplex Optimizer, v4.61
2 rows, 2 columns, 4 non-zeros
      0: obj =   0.000000000e+00 inf =   2.000e+00 (2)
      1: obj =   1.000000000e+00 inf =   0.000e+00 (0)
*     2: obj =   1.000000000e+00 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Out[5]: 1.0

在 0.4.11 中，我只得到了1.0打印，我想恢复这种行为。对于其他求解器，有该verbose选项，但对于 …

我在 Python 2.7.8、Windows 32 位上运行 PuLP 编程库。我使用 GLPK 作为混合整数线性规划问题的求解器。求解器收敛到大约。1% 的最优解很快，但是计算精确最优解的时间很长。有没有办法使用 PuLP 为 GLPK 求解器指定百分比容差？我搜索了https://pythonhosted.org/PuLP/solvers.html但它没有为 GLPK 求解器提供任何答案。

我是python和优化的新手。我遇到一些错误，请帮助我解决它。我尝试在运行Anaconda 3的PyCharm中运行以下代码

from pulp import *
x = LpVariable("x", 0, 3)
y = LpVariable("y", 0, 1)
prob = LpProblem("myProblem", LpMinimize)

prob += x + y <= 2

prob += -4*x + y

status = prob.solve(GLPK(msg = 0))

value(x)

我有一个错误

追溯（最近一次通话最近）：文件“ D：/ Projects / RH Analytics / RNN / TestPulp.py”，第10行，状态= prob.solve（GLPK（msg = 0）），文件“ C：\ Users \ rahul “ .bajaj \ AppData \ Local \ Continuum \ Anaconda3 \ lib \ site-packages \ pulp \ pulp.py”，行1643，处于解决状态= resolver.actualSolve（self，** kwargs）文件“ C：\ Users \ rahul。 …

我正在尝试使用 Python 上的 GLPK 求解器在 PuLP 上使用混合整数线性规划来解决优化问题。到目前为止，我已经成功地解决了具有约束的基本优化问题，例如：

prob = LpProblem("MILP", LpMinimize)
x1 = LpVariable("x1",lowBound=0, cat = 'Binary')
x2 = LpVariable("x2", cat = 'Continuous')
prob += 4*x1 + x2, "Objective Function"
prob += x2 - 4*x1 <= 0
prob += x2 - 2*x1 >= 0
status = prob.solve()
LpStatus[status]
value(x1), value(x2), value(prob.objective)

这给出了最佳结果，其中 x1 = 1.0、x2 = 3.0 和目标函数 = 7.0

我想弄清楚的是如何解决具有if条件的优化问题，例如，以下约束：

x1 > 0 IF x2 > 2

或类似的东西：

x1 > 0 IF x2 == 3

基本上，如何将 if …

我想在学习中使用“ pyomo”。我通过easy_install coopr安装说明安装了pyomo ，Pyomo需要一个求解器才能工作，因此我想安装（GNU Linear Programming Kit）glpk_webpage，pyomo似乎安装正确，因为我可以在spyder中将其导入（我正在使用WinPython-64bit- 2.7.5.3） import coopr.pyomo

但是，我想如果没有glpk我什么也做不了...

我从ftp服务器上下载了glpk-4.52（最新版本），但是我不知道该如何处理在“ w64”文件夹中找到的批处理文件，我应该根据“ 安装GLPK ” 使用（？）

我没有安装Visual Studio-如果没有它，是否可以工作？

我想知道如何在纸浆、Python 上逐步添加 GLPK 求解器。我已经安装了python（v=3.6.5）、pulp（v=1.6.8）。

我执行时得到的结果如下pulp.pulpTestAll()。

 Testing zero subtraction
 Testing inconsistant lp solution
 Testing continuous LP solution
 Testing maximize continuous LP solution
 Testing unbounded continuous LP solution
 Testing Long Names
 Testing repeated Names
 Testing zero constraint
 Testing zero objective
 Testing LpVariable (not LpAffineExpression) objective
 Testing Long lines in LP
 Testing LpAffineExpression divide
 Testing MIP solution
 Testing MIP solution with floats in objective
 Testing MIP relaxation
 Testing feasibility problem (no objective)
 Testing an infeasible problem
 Testing an integer infeasible problem …