Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer
    
thanks that solution worked well. I also found in the lp solve documentation that a decision var can be declared as "semi-continuous", in this case the result is the same so underneath it might be doing the same modelling trick. –  freddy smith Jan 17 '10 at 9:30
    
now suppose in addition to a Q1 (Q1=0 or a <= Q1 <= b) and Q2 (Q2 = 0 or c <= Q2 <= d), how would I formulate the same thing for an additional constraint using those 2 vars, i.e. (Q1 + Q2) = 0, or e <= Q1 + Q2 <= f ? Do I need to introduce a 3rd binary for this or use some combination of the existing two binary vars for Q1 and Q2? –  freddy smith Jan 20 '10 at 4:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.