In linear and mixed integer programming, constraints often have a bad reputation. If a model is a family, then the constraints are the parents – making sure everyone does their homework, brushes their teeth, and in general obeys the rules. Parents can be a pain though, making us eat fruit when we want to eat candy and go to bed early when we want to stay up all night. And all of this parental guidance can hurt performance.
A modeler who has developed a large-scale MIP with many different types of constraints probably knows the anxiety that can accompany the addition of each constraint. Will this next constraint be the one that kills the model’s run time; the straw that breaks the model’s back? Even seemingly innocuous constraints can cause problems when added to an already complicated MIP. This can lead to a fear of adding a new constraint to a functioning model.
But just like good parents nurture their children and help them become more than they could be by themselves, constraints not only improve a model by adding realism to the model, they can even improve performance under certain circumstances. Let me give you an example that I ran into just last week while working on a large-scale MIP that already has 10-12 different types of constraints. One of these constraint types attempts to bring balance to the model by distributing a resource to a group of parties based on each party’s stake in the overall system. For instance, consider a long-term assignment problem where workers are assigned to shifts, including a limited number of prime shifts. To make sure the prime shifts are fairly distributed, workers with longer tenure in the company should receive more prime shifts.
Let pi be the number of prime shifts that worker i has the right to based on his/her tenure and let sij equal 1 if prime shift j is assigned to worker i. Then let xi be the cost (i.e. penalty) for not assigning enough prime shifts to worker i. The constraint to set xi is then xi≥pi-∑jsij. If at least the “fair” amount of prime shifts have been assigned to worker i, then the penalty variable xi has to be greater than or equal to 0. Otherwise, if worker i does not have enough prime shifts, the penalty variable xi has to be greater than or equal to the gap between the fair number of prime shifts and the actual number of prime shifts. Adding xi to the objective of minimizing the total cost of the schedule will guide the model towards a more fair schedule in terms of prime shift allocation since a more fair schedule will decrease the values of xi‘s and thus the total cost of the model.
You will notice that in the constraint above, we’ve only set the minimum value of xi. Since there is a cost associated with the value of this variable, the solver (in our case Cplex) should always choose the smallest value possible for the variable, thus providing the upper bound on the variable. But when we started to test the model after adding this constraint we realized that while it was obvious to us that the value of xi should always be either zero or exactly equal to pi-∑jsij, it was not so obvious to Cplex. The penalty variables were often set higher than “necessary” until the optimality gap got fairly small towards the end of the model solve. Now this in theory is not an issue since the optimal solution will always have the penalty variables set as low as they can be set. However, our model is large and has a 30 minute run time limit, so there may be times when the model run ends with a large optimality gap and thus those variables are set higher than necessary. Also, this adds to the complexity of the model and is one more thing Cplex has to try to optimize when, in fact, we know the exact value that each of these variables should be.
So we decided to try adding another constraint to provide the upper bound for these penalty variables (either zero or pi-∑jsij depending on whether or not worker i has his/her fair number of shifts). The two constraints combine as xi≥pi-∑jsij and xi≤pi-∑jsij when pi≥∑jsij; effectively xi=pi-∑jsij. Once we added this new constraint, Cplex is no longer able to set the value of the xi‘s higher than “necessary”, reducing the search space. The solve starts with a lower optimality gap right away and the model solves faster.
In many cases, adding new constraints can negatively affect performance, but when the current set of constraints allow the solver more latitude than necessary, as in our case, adding a constraint or two to provide more guidance to the solver can improve performance and reduce run time. Sometimes having strict parents can be a good thing.