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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Jan 20, 2010 at 4:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .