Elastic formulation of scheduling problems

When deploying optimization models in a production environment, the problem of dealing with infeasibilities is always a nasty complication. If the model is infeasible (either because the equations are really have no feasible solution, or we did not find a feasible solution in the allocated time), it is difficult to provide any useful feedback.

One way to handle this situation is to formulate an elastic model where we allow extra resources to be “purchased” at a price. This will make the model feasible so at least we can report something back. In addition this may give good feedback about a cheap way to alleviate resource bottlenecks in the system.

An additional advantage is that an elastic formulation may actually work better in practice in finding good solutions. MIP solvers often perform best when they produce good integer solutions early on during the search. Here is a example. In this scheduling problem using a standard formulation no solution was found in the first 1000 seconds. When we used an elastic formulation we found a number of good solutions in that time. In the beginning the solutions required extra resources, but within about a hundred seconds good solutions without penalties were produced.

So the irony is that we used an elastic formulation to be able to make some sense out of infeasible solutions, but while doing that actually were able to produce feasible solutions for the original problem.