标签: linear-programming

我正在研究一些非常大规模的线性规划问题。（矩阵目前大约为 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] …

这可能是一个烦人的问题。但我希望有人能为我提供有关如何在 Windows 计算机上启动并运行 GLPK 的分步说明。我有 Windows 7 64 位。

我尝试查看各个网站上的一些说明，但不断遇到问题。我不太熟悉创建目录、使用二进制文件（例如什么是二进制文件）等......甚至运行命令对我来说也有点陌生。

为了了解我在说明中需要什么样的详细信息，以下是我尝试过（但失败了）使用的一些信息：

http://winglpk.sourceforge.net/

http://en.wikibooks.org/wiki/GLPK/Windows

正如你所看到的，我需要一些相当详细的东西。我已经阅读了 GLPK 程序的实际示例，我相信一旦我启动并运行该程序，我应该能够编写代码来使用它。

谁能帮我？我将非常感激。

编辑：作为一个并行问题，我也对其他程序的建议感兴趣，这些程序将执行与 GLPK 类似的操作，但安装和使用更简单。

我想对现有模型中的系数进行更改。目前（使用 Python API）我正在遍历约束并调用，model.chgCoeff但速度很慢。在 Python 和/或 C API 中，是否有更快的方法，也许可以直接访问约束矩阵？

下面的示例代码。它缓慢的原因似乎主要是因为循环本身；用chgCoeff任何其他操作替换仍然很慢。通常我会通过使用向量运算而不是 for 循环来解决这个问题，但如果无法访问约束矩阵，我认为我无法做到这一点。

from __future__ import division
import gurobipy as gp
import numpy as np
import time
N = 300
M = 2000
m = gp.Model()
m.setParam('OutputFlag', False)

masks = [np.random.rand(N) for i in range(M)]
p = 1/np.random.rand(N)
rets = [p * masks[i] - 1 for i in range(M)]
v = np.random.rand(N)*10000 * np.round(np.random.rand(N))

t = m.addVar()
x = [m.addVar(vtype=gp.GRB.SEMICONT, lb=1000, ub=v[i]) for i in range(N)]
m.update()
cons …

我需要找到线性程序的精确实数解（其中所有输入都是整数）。重要的是，求解器还将解输出为有理数，理想情况下无需使用浮点数执行任何中间步骤。

GLPK 可以进行精确算术，但无法将解显示为有理数（即 1/3 得到 0.3333）。我可能可以尝试猜测这意味着哪个数字，但这似乎非常脆弱。

我无法找到可以做这种事情的 LP 求解器。有吗？性能并不是一个大问题；我的问题很小。（我确实考虑过使用像 Z3 这样的 SMT 求解器；它们可以解决此类问题并提供精确的有理解，但它们采用量词消除，而不是使用更适合线性规划（如 Simplex）的算法）

我正在尝试解决或实现 R 中的集合覆盖问题的近似值。给定这样的数据框。

  sets n
1   s1 1
2   s1 2
3   s1 3
4   s2 2
5   s2 4
6   s3 3
7   s3 4
8   s4 4
9   s4 5

列中元素的唯一数量n是：

unique(d$n)
[1] 1 2 3 4 5

我想计算sets覆盖 n （宇宙）中所有独特元素的较小数量的集合（列）。在此示例中，有两个集合：s1 {1, 2, 3} 和 s4 {4, 5}。我在维基百科和互联网上读过相关内容，并且我知道可以应用贪婪算法来找到近似值。我也检查了这个链接，其中他们提到了两个包来解决此类问题，LPsolve并且Rsymphony，但我什至不知道如何开始。在我现实生活中的例子中，我有超过 40,000 个集合，每个集合有 1,000 到 10,000 个元素，而无生命或独特的元素有 80,000 个。

任何有关如何开始或继续的帮助或指导将非常感激。

数据

d <- structure(list(sets = structure(c(1L, 1L, 1L, 2L, 2L, …

我会尽量让我的问题简短明了。如果您需要任何进一步的信息，请告诉我。

我有一个 MIP，用 Python 包 PuLP 实现。（大约 100 个变量和约束）问题的数学表述来自一篇研究论文。本文还包括一项数值研究。然而，我的结果与作者的结果不同。

我的问题变量叫做prob

prob = LpProblem("Replenishment_Policy", LpMinimize)

prob.solve() LpStatus我通过退货解决问题Optimal

当我添加一些最佳（论文）结果作为约束时，我得到了稍微更好的客观值。将目标函数限制为稍低的值也是如此。LpStatus 保持不变Optimal。

original objective value: total = 1704.20
decision variable: stock[1] = 370

adding constraints: prob += stock[1] == 379
new objective value: 1704.09

adding constraints: prob += prob.objective <= 1704
new objective value: 1702.81

我的假设是 PuLP 的求解器近似解。计算速度很快，但显然不太准确。有没有办法可以提高 PuLP 所使用的求解器的精度？我正在寻找类似的内容：prob.solve(accuracy=100%).我查看了文档，但不知道该怎么做。有什么想法可能是什么问题吗？

任何帮助表示赞赏。谢谢。

我目前正在使用 Gurobi Python API 来解决大型 LP。我发现添加变量的过程花费了太多时间，在某些情况下甚至超过优化时间。我的代码大致是这样的（我删除了读取数据的部分，让它更简单）：

from gurobipy import *
import numpy as np
import time

height = 32
width = 32
size = height * width

# set dummy data
supply = [1.0] * size
demand = [1.0] * size

# compute cost
costs = ((np.arange(size) // height  - 
             np.arange(size).reshape(size,1) // height) ** 2 + \
             (np.arange(size) % width - 
              np.arange(size).reshape(size,1) % width) ** 2).ravel().tolist()

# now build up the model
model = Model("model")
model.Params.Threads = 8

# add …