# linear program with zeros

Hi, I want to be able to solve a linear program that has constraints that are either zero or a range. An example below in LP_Solve-like syntax shows what I want to do. This doesnt work. In general all the decision variables Qx can be 0 or a <= Qx <= b where a > 0 and b > a. All decision variables must be integers.

 max: 0.2 Q1 + 0.4 Q2 + 0.6 Q3 + 0.8 Q4 + 0.4 Q5 + 0.6 Q6 + 0.6 Q7 + 0.7 Q8;

 

Q1 = 0 or Q1 >= 5; Q2 = 0 or Q2 >= 1; Q3 = 0 or Q3 >= 1; Q4 = 0 or Q4 >= 1; Q5 = 0 or Q5 >= 1; Q6 = 0 or Q6 >= 1; Q7 = 0 or Q7 >= 9; Q8 = 0 or Q8 >= 1; Q4 <= 30; Q1 + Q2 + Q3 + Q4 + Q5 + Q6 + Q7 + Q8 <= 50; 

How would I rewrite this to work? Is there a particular solver that should be used for this kind of task?

-
This question seems more appropriate for Stack Overflow, if you're asking what program or how to write code to do this. –  Charles Siegel Jan 17 '10 at 2:31
looks more like a quadratic program than a linear program, since you can express that a variable is either zero or one. You can't hope to solve this efficiently in general. Look for integer linear programming solvers on the web. –  Mitch Jan 17 '10 at 4:00
I guess, appropriately rephrased this could be a somewhat interesting math overflow question. Like, what algorithms/heuristics are known to solve mixed integer linear programs, which instances are easy etc. –  Mitch Jan 17 '10 at 4:05

You can use the following modelling trick to transform you problem in a integer linear program: for each constraint of the type $$Q_i = 0 \text{ or } L_i \le Q_i \le M_i$$ (on an integer variable $Q_i$) introduce a new binary variable $B_i$ and write $$L_i B_i \le Q_i \le M_i B_i$$ If, as in your example, you have no explicit value for $M_i$, simply use a large upper bound on the values of $Q_i$ (for example $50$ in your situation). Also, the constraint $Q_i = 0 \text{ or } Q_i \ge 1$ is redundant. You can then solve the resulting program with any integer programming solver, such as lp_solve or glpk.
By the way, the solution to your example is easily seen to be obtained with $Q_4=30$ and $Q_8=20$.