Semi-Continuous Variables and the Solution Pool

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 b                    =       40.000  rhs ----     19 PARAMETER xlo  lower bounds i1 1.717,    i2 8.433,    i3 5.504,    i4 3.011 ----     19 PARAMETER xup  upper bounds 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      i2         8.4327        12.2405        12.2405         2.0000      i3         5.5038        11.8260        13.4983         3.0000      i4         3.0114         3.0114        18.5627         4.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_p2      12.922      12.241                  14.837 soln_m_p3      12.922                  13.498      13.580 soln_m_p4 -1.7764E-15      12.241      13.498      14.261 ----     49 PARAMETER objs  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 soln_m_p2       1.000       1.000                   1.000 soln_m_p3       1.000                   1.000       1.000 soln_m_p4                   1.000       1.000       1.000 ----     43 PARAMETER xp                     i1          i2          i3          i4 soln_m_p1      12.922      12.241      11.826       3.011 soln_m_p2      12.922      12.241                  14.837 soln_m_p3      12.922                  13.498      13.580 soln_m_p4 1.77636E-15      12.241      13.498      14.261 ----     43 PARAMETER objs  soln_m_p1  84.927,    soln_m_p2  96.753,    soln_m_p3 107.735,    soln_m_p4 122.021

References

1. Semi-continuous variables, http://yetanothermathprogrammingconsultant.blogspot.com/2016/08/semi-continuous-variables.html