标签: linear-programming

这个伟大的SO答案指向一个好的稀疏求解器Ax=b,但是我已经有了约束,x因此每个元素x都是>=0一个<=N.

此外,A是巨大的(约2e6x2e6),但<=4每行元素非常稀疏.

有什么想法/建议吗？我正在寻找像MATLAB这样的东西,lsqlin但是有很大的稀疏矩阵.

我基本上试图解决稀疏矩阵上的大规模有界变量最小二乘问题:

编辑: 在CVX中:

cvx_begin
    variable x(n)
    minimize( norm(A*x-b) );
    subject to 
        x <= N;
        x >= 0;
cvx_end

我有一个整数线性优化问题,我对可行的,好的解决方案感兴趣.据我所知,例如Gnu线性编程工具包只返回最优解(假设存在).这需要无休止的时间,并不是我正在寻找的东西:我会对任何好的解决方案感到满意,而不仅仅是最优的解决方案.

因此,一个LP解算器,例如在一段时间后停止并返回他到目前为止找到的最佳解决方案,将完成这项工作.

有没有这样的软件？如果该软件是开源的,或者至少像啤酒一样免费,那将是很棒的.

或者:有没有其他方法通常可以加速整数LP问题？这是正确的地方吗？

很长一段时间的听众第一次打电话给SO ..我问的问题之前有过非常相似的问题,但我不相信我足够聪明地破译如何实施解决方案,为此我道歉.以下是我发现的问题的链接: R多重整数线性规划中的约束

我的预计幻想点数(FPTS_PREDICT_RF)最高,受到50,000工资上限的限制,同时最大限度地减少了我提出的"风险"计算.

现在,问题在于"弹性"位置.该团队需要由9个职位组成,1个QB 2 RB 3 WR 1 TE 1 DEF 1 FLEX

flex可以是RB,WR或TE.
那么,我们可以得到:1 QB 2-3 RB 3-4 WR 1-2 TE 1 DEF

我正在尝试实现#RB + #WR + #TE == 7的约束.

这是相关代码:

library(Rglpk)



# number of variables
num.players <- length(final$PLAYER)
# objective:
obj <- final$FPTS_PREDICT_RF
# the vars are represented as booleans
var.types <- rep("B", num.players)
# the constraints
matrix <- rbind(as.numeric(final$position == "QB"), # num QB
           as.numeric(final$position == "RB"), # num RB
           as.numeric(final$position == "WR"), # num …

在Python PuLP中,线性编程约束可以变成弹性子问题.

http://www.coin-or.org/PuLP/pulp.html?highlight=lpsum#elastic-constraints

解决子问题可以优化距目标值的距离.

当然,目标值是这个子问题的最佳解决方案,但弹性化的全部意义在于我们认为这种解决方案可能是不可行的.

如何将子问题纳入整体问题？我尝试按照添加约束的方式将其添加到问题中,这会引发类型错误.我尝试将它放在目标函数中,这也不起作用.

我在上面的文档或此处托管的示例中找不到任何内容:

https://code.google.com/p/pulp-or/wiki/OptimisationWithPuLP?tm=6

这是我制定的子问题:

capacity = LpConstraint(e=lpSum([ x[m][n] * len(n.items) for n in N ]),
    sense=-1, rhs=30, name=str(random.random()))
stretch_proportion = 30/50
elasticCapacity = capacity.makeElasticSubProblem(penalty=50,
    proportionFreeBoundList=[1,stretch_proportion])

以下是我认为必须将其纳入LP目标的最接近的事情:

def sub(m):
    capacity = LpConstraint(e=lpSum([ x[m][n] * len(n.items) for n in N ]),
        sense=-1, rhs=30, name=str(random.random()))
    stretch_proportion = 30/50
    elasticCapacity = capacity.makeElasticSubProblem(penalty=50,
        proportionFreeBoundList=[1,stretch_proportion])
    elasticCapacity.solve()
    return elasticCapacity.isViolated()

...

prob += lpSum( [ x[m][n] * reduce(op.add, map(D2, [i.l for i in n.items], [j.l for j in n.items]))\
    for n in N …

我正在为C#寻找线性编程求解器.换句话说,我正在寻找一个解决线性编程问题的C#库.

我需要一个易于使用的库(所以我可以学习如何快速使用它),但如果它支持一些功能作为自动绝对值转换(因此我不必自己编程转换)会很好.图书馆应该是免费的(不一定是开源的)是很重要的.

好的文档对我来说是个巨大的优势.性能下降10%-20%对我的项目来说并不重要.

谢谢你的回答

我需要解决一个欠定的线性方程组和约束系统,然后找到最小化成本函数的特定解决方案.这需要在纯粹可移植的托管代码中完成,该代码将在.NET和Mono中运行.我可以使用哪些免费的库来实现它？

我发现免费库提供的所有优化算法都只支持单个变量的区间约束,例如0 < x < 1,不支持约束x + 2y < 4.我还发现通常线性方程求解器仅支持具有一个解的线性系统.

到目前为止我发现的最接近的是DotNumerics,其中包括用于求解欠定线性系统的奇异值分解,但其优化算法仅支持单变量约束(据我所知).

还有其他一些问题涉及线性规划,但我的关键要求是多变量约束和解决欠定系统.我还没有找到一个支持多变量约束的免费库.

3天后，我无法将python程序打包成.exe文件。我试过 py2exe（它不断错过模块）和 PyInstaller。

这是复杂的部分。我的程序使用了许多额外安装的模块（coopr、pyomo、openpyxl、glpk、cbc、pyutilib、numpy 等）。这些反过来又导入了各种其他东西，我无法追踪它（PyInstaller 警告日志列出了 676 行丢失或可能不需要的模块。）

但是，我得到了（通过将“缺失”模块的导入添加到我的程序中）一个 .exe 版本，它通过双击或从命令行运行，没有打印任何错误。

问题是，程序什么都不做。我有一个包含在构建中的输入文件，我的程序读入该文件，进行一些（密集）计算，然后在同一目录中创建一个 .csv 输出文件。它作为 .py 文件工作。我的 .exe 什么也不做。

所以，如果你能告诉我出了什么问题，请继续。如果没有，我想知道任何有用的步骤或想法可以尝试。在这一点上，我已经用尽了可以从程序和文档中找到的反馈。

我试图通过使用apache-commons的Simplex解算器解决以下线性问题:org.apache.commons.math3.optim.linear.SimplexSolver.

n行
m数是列数
L是每行总和的全局限制

这是我到目前为止:

List<LinearConstraint> constraints = new ArrayList<>();

double[][] A = calculateAValues();
// m = count of columns
// constraint 1: the sum of values in all column must be <= 1
for(int i = 0; i < m; i++) {
    double[] v = new double[n];
    for(int j=0; j < n; j++) {
        v[j] = 1;
    }
    constraints.add(new LinearConstraint(v, Relationship.LEQ, 1));
}
// n = count of rows
// constraint 2: sum of …

我使用web.py来创建Python Web服务器.调用此服务器以解决线性编程问题,并使用库CBC来执行此操作.

每隔一段时间,服务器就会崩溃,并显示如下所示的日志:

78.243.184.3:56271 - - [03/Jun/2016 04:35:54] "HTTP/1.1 GET /optimization" - 200 OK
Aborted (core dumped)

我相信"Aborted(core dumped)"是一个C错误,所以它来自web.py或CBC.

有没有办法追溯错误的来源？

我一直在使用PuLP来解决我感兴趣的特定混合整数线性程序 (MIP)。但是，随着问题规模的增长，PuLP 花费的时间太长。我希望能够运行求解器一段时间，并在需要很长时间的情况下提前终止它，并获得迄今为止计算出的最佳可行解决方案。我尝试过用信号手动对求解器进行计时，但变量都是“无”。

我查看了文档，PuLP 似乎不支持这一点，尽管据我了解，它调用的大多数求解器例程都支持这一点。有没有办法对 PuLP 施加时间限制？