线性规划 - 如何将变量设置为 0 或 1？

Question

我正在尝试使用 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 = null;
 try {
 solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, false);
 }
 catch (OptimizationException e) {
 e.printStackTrace();
 }

 if (solution != null) {
 //get solution
 double max = solution.getValue();
 System.out.println("Opt: " + max);

 //print decision variables
 for (int i = 0; i < 2; i++) {
 System.out.print(solution.getPoint()[i] + "\t");
 }

但是，如果我希望X和Y的值只能是0或1怎么办？ apache 库允许我们这样做吗？如果不是，我可以使用任何其他库来实现此目的吗？

提前致谢。

Answer 1

嗯...不。不在 linear programming 的范围内。原因是在线性规划中，您的约束必须是线性，而您的解决方案 space 必须是凸的。 1 或 0 的约束不是线性的。 space{0, 1}在实数中的解不是凸的（证明：0和1的平均值为0.5，不在解space中）。

您在代码中使用的求解器运行 Simplex algorithm，一种非常流行的线性程序求解器，但它实际上只求解纯线性程序。

要获得 0 或 1，您需要 integer linear programming, which is a little different. Basically, it's linear programming but with all (or some, in the case of mixed integer linear programming) values forced to be integers. The specifics are a bit out of scope for Stack Overflow (check out the Math Stack Exchange!); suffice it to say it's not linear programming but it is doable, and there are libraries that let you do it. There are even algorithms for it that are fairly easy to understand (e.g. branch and bound) 尽管不是在公园里散步来实现（它们通常是您想让其他人实现的算法，而不是自己实现).

如果这让你说 "I need an integer linear program solver!" 那么你可能会对 and this question.

感兴趣

Answer 2

这为时已晚，但如果人们仍在考虑这一点，请在使用分支定界算法之前尝试使用切割生成算法来进一步减少首先需要探索的节点数量（减少时间）。就像 Gomory 的剪辑一样，如果你正在实施它，我认为这个更容易制作。但无论如何，如果您正在处理大量变量和约束，请先减少在分支定界之前需要探索的变量数量。

线性规划 - 如何将变量设置为 0 或 1？

linear programming - how to set variable to be 0 or 1?

java

linear-programming

apache-commons-math

integer-programming