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 \in [\ell,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.:

\[\bbox[lightcyan,10px,border:3px solid darkblue]{ \begin{align} \min & \sum_ i c_i x_i \\ & \sum_i x_i = b\\ & x_i \in \{0\} \cup [\ell_i,u_i] \end{align} }\] |

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 \(x_i=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 \(x_i\) by a pair of variables: a continuous variable \(x_i\) and a binary variable \(\delta_i\):

\[\bbox[lightcyan,10px,border:3px solid darkblue]{ \begin{align} \min & \sum_ i c_i x_i \\ & \sum_i x_i = b\\ & \ell_i \delta_i \le x_i \le u_i \delta_i\\ & x_i \ge 0\\ & \delta_i \in \{0,1\} \end{align} }\] |

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

## No comments:

## Post a Comment