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

Question

I am trying to apply linear programming for my problem using Apache commons Math library. I saw an example online to solve the following example

max.  3X + 5Y 

 s.t.

 2X + 8Y <= 13 

 5X - Y <= 11 

 X >= 0, Y >= 0 

The code is like

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");
 }

However, what if I want the value of X and Y can only be either 0 or 1? Is apache libs allow us do this? If no, any other libs I can use to achieve this?

Thanks in advance.

Answer 1

Well... no. Not within the bounds of linear programming. The reason is that in linear programming your constraints must be linear, and your solution space must be convex. The constraint of either 1 or 0 is not linear. The solution space {0, 1} in the real numbers is not convex (proof: the average of 0 and 1 is .5 and is not in the solution space).

The solver you're using in your code runs the Simplex algorithm, a very popular linear program solver, but it really only solves pure linear programs.

To get either 0 or 1 you need 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) albeit not a walk in the park to implement (they're generally the sorts of algorithms you want to let someone else implement, rather than roll your own).

If this makes you say "I need an integer linear program solver!" then you might be interested in this question and this question.

Answer 2

This is too late but in case people are still considering this, before going to the Branch and Bound algorithm try using a cut generation algorithm to reduce further the number of nodes the first needs to explore (reducing time). Like the Gomory's cut, if you are implementing it, I think this one is easier to make. But anyway, first reduce the number of variables needed to explore before the the Branch and Bound specially if you are working with a big number of variables and constraints.