|
When is it beneficial to use semi-continous variables in commercial MILP solvers? For example, if I have a variable a that can be written like $$a\geq0x_0+3x_1+3x_2+4x_3$$ where all x are binary and \(x_0+x_1+x_2+x_3=1\), will there be any advantage in declaring a as a semi-continous variable. Can the solver in this case somehow remove the relaxed solutions where a would be between 0 and 3? If not then when can the semi-continous variables be useful? EDIT: Ah sorry, I tried to make the example as easy as possible and therefore removed some information from the problem. In my problem I have other constraints that will make a as low as possible (but in the example the \(\geq\) could be replaced by =). However I have a lot of constraints of this type in my real problem. When I solve it normally I get relaxed LP solutions in the B-and-B where a is between 0 and 3. for example when \(x_0=0.5,x_1=0.5\) would semi-continous variables somehow give different relaxed values? with other words, would a semi-continous variable force the \(x_0\) to be either 1 or zero in the relaxed solutions?
showing 5 of 8
show all
|
|
The advantage of a semi-continuous variable is significant when the semi-continuous variable has no fixed upper bound. Suppose the range of x is $${0} \cup [1000,\infty)$$ Using an auxiliary binary variable, it's not difficult to force the x variable to the continuous range (greater or equal to 1000 in this example), but it's not easy to force the x variable to zero. In contrast, if a solver implements semi-continuous variables, then it will explicitly branch on the two different ranges for the variable. Even if the variable has a fixed upper bound, a semi-continuous variable is also helpful in reducing the potential for numerical issues that can arise if the upper bound is large. 2
I agree with Greg +if+ the solver's branching logic recognizes semi-continuous variables as such. If the solver converts a semi-continuous variable to a continuous/binary variable pair, you're probably better off modeling such a pair explicitly (you're liable to have a better sense of a valid upper bound than the solver will). As far as unbounded variables go, all things are bounded; it's just that the bounds are not always readily known.
(Apr 27 '11 at 12:19)
Paul Rubin ♦
@Paul That's exactly what I'm wondering.. Can the solver leave out all relaxed solutions where the semi-continous variable is between zero and it's lower bound or will it get relaxed as well. If it's the latter case I am pretty sure I won't get anything out of using SC variables in my model. If the solver can branch on all the semi-continous variables in my problem without relaxing any of them I could reduce the search space significantly...
(Apr 28 '11 at 04:12)
Buxley
1
At the heart, you're solving an LP relaxation, which may still produce a solution that violates the integrality (or semicontinuous) restrictions. The branch-and-cut process is necessary to ensure a feasible solution.
(Apr 28 '11 at 11:21)
Greg Glockner
|
|
Well it's hard to say exactly what goes on under the hood of the good MIP solvers. Regarding semi-continous variables, I am quite sure it's not straight forward and very solver dependent. In your case using a semi-continous sounds reasonable, and in theory it would allow for performance improvements through better branching. You might not see any speed up though, since the formulation is likely to be identified in presolve. |
|
On a more general level about using semi-continous variable, Tobias's comment address part of your question.
He's the lead MIP developer at CPLEX, so I take his word :-) Thanks! This was pretty much the conclusion I made as well after Gregs answer and comments!
(May 04 '11 at 03:09)
Buxley
|
|
For example, there is a model below: IloC0 and IloC1 are not positive semi-definite. So we prefer to re-formulate the model to LP. Because all variables are non-negative, the quadratic constraints -2x + x^2 >= 0 are equivalent to (x >= 2 or x = 0). So, instead of writing quadratic constraints you can specify IloX0 and IloX1 to be semi-continuous variables with domain [2,5]. Then the QCP will be converted to LP. |
Your example is not sufficient to make the variable a semi-continuous: if x0=1 then a could be any value greater than or equal to 0, including values between 0 and 3.
I assumed the zero at x0 was a typo ?
Not sure it's that simple. Hopefully the OP will elaborate.
I edited to make it clearer (...I hope)
If your goal is to use auxiliary variables to ensure that a is zero or in the range [3,4], then the way to model this is to introduce a single binary variable (call it z) along with the constraint: 3z <= a <= 4z.
@Greg My goal is to get the relaxed solution to be zero or between [3,4]. In the example above z could still take the value 0.5 in the LP solutions and thus a would be 1.5...
In my example, z should be a binary (0-1 integer) variable. Of course it may take a non-integer value in the LP relaxation, but that's not the point - you will get an integer value for z once you solve the MIP.
@Greg thanks, think of a as $$a=0x_0+3x_1+3x_2+4x_3$$ I don't have a problem when the MIP is solved but I would like to make the relaxations tighter, and that's why I was wondering about the SC variables. My MIP is enourmous and I would like to speed it up, and basically my guess is that a tighter value in the relaxation would give a faster solution...