0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ This question seems more appropriate for Stack Overflow, if you're asking what program or how to write code to do this. $\endgroup$
    – Charles Siegel
    Jan 17, 2010 at 2:31
  • $\begingroup$ 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. $\endgroup$
    – Mitch
    Jan 17, 2010 at 4:00
  • $\begingroup$ 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. $\endgroup$
    – Mitch
    Jan 17, 2010 at 4:05

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – freddy smith
    Jan 17, 2010 at 9:30
  • $\begingroup$ 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? $\endgroup$
    – freddy smith
    Jan 20, 2010 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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