In this post I consider the interaction between semi-continuous variables and the solution pool in Cplex and Gurobi. I received a question about this, and I had to try things about before I could give a definitive answer.
The solution pool can enumerate (some or all) different integer solutions. A difference in continuous variables is not recognized in the solution pool. A semi-continuous variable is somewhat of a hybrid (1): it is a continuous variables that can assume values: x=0 or between bounds x∈[ℓ,u]. How would the solution pool deal with this?
To test this out, we construct a tiny knapsack-like problem but with semi-continuous variables. I.e.:
min∑icixi∑ixi=bxi∈{0}∪[ℓi,ui] |
For this purpose I use a very small data set with just 4 variables. I used:
---- 19 PARAMETER c obj coefficients i1 1.000, i2 2.000, i3 3.000, i4 4.000
---- 19 PARAMETER xlo lower bounds i1 1.717, i2 8.433, i3 5.504, i4 3.011
i1 12.922, i2 12.241, i3 13.498, i4 18.563 |
The optimal solution can look like:
---- VAR x semi-continous variables LOWER LEVEL UPPER MARGINAL i1 1.7175 12.9221 12.9221 1.0000 LOWER LEVEL UPPER MARGINAL ---- VAR z -INF 84.9266 +INF . z objective |
Before running this model, I expected a few of the x variables to be zero.
All solutions
When we throw this into the solution pool and retrieve all solutions, we see:
---- 49 PARAMETER xp i1 i2 i3 i4 soln_m_p1 12.922 12.241 11.826 3.011
soln_m_p1 84.927, soln_m_p2 96.753, soln_m_p3 107.735, soln_m_p4 122.021 |
We see that besides the optimal solution (with objective 84.927), we find three other feasible solutions, where we have some variable xi=0.
Binary variable formulation
Basically Cplex and Gurobi consider a semi-continuous variable different, when they are zero or not. I think this is the correct interpretation. This corresponds directly to a binary variable formulation where we replace the semi-continuous variable xi by a pair of variables: a continuous variable xi and a binary variable δi:
min∑icixi∑ixi=bℓiδi≤xi≤uiδixi≥0δi∈{0,1} |
Indeed when we try this binary variable formulation with the solution pool we see:
---- 43 PARAMETER deltap i1 i2 i3 i4 soln_m_p1 1.000 1.000 1.000 1.000
i1 i2 i3 i4 soln_m_p1 12.922 12.241 11.826 3.011
soln_m_p1 84.927, soln_m_p2 96.753, soln_m_p3 107.735, soln_m_p4 122.021 |
References
- Semi-continuous variables, http://yetanothermathprogrammingconsultant.blogspot.com/2016/08/semi-continuous-variables.html
is it faster to use semicontinous variable vs combination of continuous variable and binary variable
ReplyDelete