Improving MIP performance by removing redundant binary variables: a real-life case

Introduction 

Removing redundant variables usually has no impact on the solving time because a solver like CPLEX will remove most of them during the presolve phase. However, in this post we will see that removing “non-trivial” redundant binary variables can have a positive impact. 

One of our users modeled a problem related to the unit commitment problem in AIMMS, and they ran into a performance issue with CPLEX. 

Model 

In the unit commitment problem we have a binary variable U(t) for each unit to model the commitment status of that unit for period t; U(t) = 1 if the unit is online in period t and U(t) = 0 if the unit is offline in period t. We also have a binary start-up variable SU(t) for each unit which is 1 if the unit starts up in period t and 0 otherwise, and a binary shut-down variable SD(t) ) for each unit which is 1 if the unit shuts down in period t and 0 otherwise. (Please note that in the AIMMS model the U, SU and SD variables are 2-dimensional but I omitted the index for the set of units.) 

An example might help. If a certain unit is up in periods 2 to 4 then we have the following values assigned to the variables: 

To model the relationship between U(t), SU(t) and SD(t) we can use the following constraints: 

1. SU(t) <= U(t) 

2. SD(t) <= 1 - U(t) 

3. U(t) – U(t-1) = SU(t) – SD(t) 

Usually the SU(t) and SD(t) variables are also used in other parts of the model but in the model of our user that was not the case; these variables were not used in any other constraint besides the three constraints shown above, and they were also not used in the objective. That means that the SU(t) and SD(t) variables have no impact on the solution because they do not even restrict the U(t) variables. In other words, the variables SU(t) and SD(t) are redundant and can be removed from the model, as well as the three constraints above. 

Note that if we solve the new model then CPLEX will not calculate solution values for SU(t) and SD(t), but if needed we can easily calculate them ourselves using the solution values of U(t). 

Experiment 

I did an experiment, using a fairly easy instance, in which I solved the old and new model 5 times, each time using a different value for the CPLEX option ‘Random seed’, to account for performance variability. For the old model the solving times with CPLEX were 160.1, 166.7, 183.4, 235.4 and 157.0 seconds. For the new model the solving times were 4.3, 4.3, 4.8, 4.4 and 4.4 seconds. So it seems that removing the redundant variables SU(t) and SD(t) has a big positive impact on the CPLEX performance for this particular model. A somewhat surprising outcome, at least to me. 

Conclusion 

These results indicate that the CPLEX presolver did not remove the variables SU(t) and SD(t). We can check this by letting AIMMS print the presolved model as created by CPLEX. To do so the CPLEX option ‘Write cuts’ should be set to ‘Presolved model plus cuts’, together with activating the option ‘Find fractional root solution’. I did so for the original model and observed that the variables SU(t) and SD(t) were still present in the presolved model, which means that the CPLEX presolver did indeed not remove them.