java - 线性规划-如何将变量设置为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 libs 允许我们这样做吗？如果没有，我可以使用其他库来实现此目的吗？

提前致谢。

Answer 1

嗯...不。不在 linear programming 的范围内。原因是在线性规划中，您的约束必须是线性的，并且解决方案空间必须是凸的。 1 或 0 的约束不是线性的。实数中的解空间{0, 1}不是凸的(证明:0和1的平均值是0.5并且不在解空间中)。

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

要获得 0 或 1，您需要 integer linear programming ，这有点不同。基本上，它是线性规划，但所有(或一些，在混合整数线性规划的情况下)值被迫为整数。具体细节有点超出了 Stack Overflow 的范围(查看 Math Stack Exchange! )；可以说它不是线性编程，但它是可行的，并且有一些库可以让您做到这一点。甚至有一些相当容易理解的算法( e.g. branch and bound )，尽管实现起来并不容易(它们通常是您想让别人实现的算法，而不是您自己实现的算法)。

如果这让您说“我需要一个整数线性程序求解器!”那么您可能会对 this question 感兴趣和 this question .