## Sunday, May 7, 2017

### Semi-Continuous Variables and the Solution Pool

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.011soln_m_p2      12.922      12.241                  14.837soln_m_p3      12.922                  13.498      13.580soln_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.000soln_m_p2       1.000       1.000                   1.000soln_m_p3       1.000                   1.000       1.000soln_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.011soln_m_p2      12.922      12.241                  14.837soln_m_p3      12.922                  13.498      13.580soln_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