17 May 2021 (280 words)
BCG Gamma have an interesting article that describes Five strategies for debugging MIP models.
There are many situations in which a MIP model must be debugged. The most common is when you run your model and get a message saying that it is infeasible or unbounded. Debugging can also be helpful when the model is feasible, but its solution does not behave as expected.
Five model debugging strategies:
- Inspect the .lp file. Mistakes in building the model can result in a failure to create the variables and constraints you intended. Review the .lp file to see what the solver is actually solving.
- Keep a small model instance. The .lp file size can grow very quickly. To keep the file readable, make toy models that are small enough that you can inspect the file while not being so simplistic that you lose important aspects of the real-sized model.
- Selectively remove families of constraints. The idea is to find a smaller, but still infeasible, version of your model. This allows you to identify which groups of constraints are causing infeasibility.
- Compute the irreducible inconsistent subsystem (IIS). Some solvers have an automatic method for computing which constraints cause infeasibility. The product is the smallest subset of constraints causing your model to be infeasible. Fixing the infeasibility is still a manual process.
- Use penalized artificial variables to relax constraints. An artificial variable allows a constraint to be violated, if necessary, at a cost. The relaxed system of inequalities will always have a solution, enabling you to identify which constraints are causing infeasibility.
These strategies can be combined to help you debug your model.