3
1

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?

asked 26 Apr '11, 07:20

Buxley's gravatar image

Buxley
5641614
accept rate: 9%

edited 14 Nov '13, 05:56

fbahr's gravatar image

fbahr ♦
4.6k716

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.

(26 Apr '11, 13:23) Greg Glockner

I assumed the zero at x0 was a typo ?

(26 Apr '11, 13:34) Bo Jensen ♦

Not sure it's that simple. Hopefully the OP will elaborate.

(26 Apr '11, 15:31) Greg Glockner
1

I edited to make it clearer (...I hope)

(27 Apr '11, 02:28) Buxley
2

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.

(27 Apr '11, 02:36) Greg Glockner

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

(27 Apr '11, 02:51) Buxley

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.

(27 Apr '11, 02:55) Greg Glockner

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

(27 Apr '11, 03:19) Buxley
showing 5 of 8 show 3 more comments

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.

link

answered 26 Apr '11, 09:27

Greg%20Glockner's gravatar image

Greg Glockner
43716
accept rate: 20%

edited 14 Nov '13, 05:56

fbahr's gravatar image

fbahr ♦
4.6k716

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.

(27 Apr '11, 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...

(28 Apr '11, 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.

(28 Apr '11, 11:21) Greg Glockner

On a more general level about using semi-continous variable, Tobias's comment address part of your question.

Alternatively, you can just model the semi-continuous variables as pairs of continuous and binary variables yourself. There is no magic in the CPLEX automatic reformulation, so doing it yourself should not cost performance. And if you do it yourself, you can of course branch on the binary variable as you like.

He's the lead MIP developer at CPLEX, so I take his word :-)

link

answered 03 May '11, 10:37

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

Thanks! This was pretty much the conclusion I made as well after Gregs answer and comments!

(04 May '11, 03:09) Buxley

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.

link

answered 26 Apr '11, 07:41

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

For example, there is a model below:

Minimize
obj: IloX2
Subject To
IloC0: IloX0 + IloX1  = 5
IloC1: IloX0 - IloX2 + IloX3 <= 0
IloC0: - 2 IloX0 + [ IloX0 ^2 ] >= 0
IloC1: - 2 IloX1 + [ IloX1 ^2 ] >= 0
Bounds
0 <= IloX0 <= 5
0 <= IloX1 <= 5
0 <= IloX2 <= 100
0 <= IloX3 <= 100
End

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.

link

answered 27 Apr '11, 09:27

John%20Cui's gravatar image

John Cui
15917
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×191
×71
×22
×1

Asked: 26 Apr '11, 07:20

Seen: 4,989 times

Last updated: 14 Nov '13, 05:56

OR-Exchange! Your site for questions, answers, and announcements about operations research.