Sunday, May 7, 2017

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