When solving optimization models, certain scenarios may arise where the defined constraints cannot be fulfilled, leading to what is known as an infeasible model. Such situations can occur either during the initial formulation of the model or when there are updates in the data, modifications to limits, or the introduction of new constraints. In such cases, it becomes necessary to either identify and rectify the underlying cause of the infeasibility or, alternatively, identify a subset of constraints that can be relaxed to achieve a feasible model. In this article, we discuss how to identify, diagnose, and cope with infeasibility then we offer some tips and best practices.
How to tell if your model is infeasible?
You can determine the status of a solved Gurobi model by querying the Optimization Status Code or by reviewing the log file. If the model is proven to be infeasible, the status code will be INFEASIBLE and the log file message will be "Infeasible model". If the model is proven to be either infeasible or unbounded, then status code will be INF_OR_UNBD and the log file message will be "Model is infeasible or unbounded". For more information on this status, please see How do I resolve the error "Model is infeasible or unbounded"?
Diagnosing and coping with infeasibility
To determine the set of model constraints that cause infeasibility, there are two questions that you can ask the solver:
- What subset of model constraints is responsible for making the model infeasible?
- What changes do I need to make to the model to recover feasibility?
To answer the first question, you can compute an Irreducible Infeasible Subsystem (IIS). This is a minimal subset of constraints and variable bounds that is still infeasible if isolated from the rest of the model. However, if any single constraint or bound from this subsystem is removed, the resulting subsystem is feasible. In Python, you can compute an IIS using the Model.computeIIS() method.
Note that an infeasible model may have multiple IISs. The one returned by Gurobi is not necessarily the one with minimum cardinality; others with fewer constraints or bounds may exist.
To answer the second question, you can compute the smallest (with respect to some specified metric) perturbation that would need to be made to the model in order to recover feasibility. You can do this in Python with the Model.feasRelax() and Model.feasRelaxS() methods. The latter is a simplified version, hence the "S" suffix.
For instructions and examples on how to use these two features,
- For compute IIS, see How do I use 'compute IIS' to find a subset of constraints that are causing model infeasibility?
- For feasibility relaxation, see How do I change variable and/or constraint bounds to make an infeasible model feasible using feasRelax?
For more details, see the Diagnose and cope with infeasibility section in the documentation.
Tips and Best Practices
Prescreen constraints and limits that are more likely to be causing the issue
To reduce the problem size and improve the interpretability of the results, it is helpful to define a list of potentially problematic constraints and limits before running either compute IIS routine or a feasibility relaxation. When expanding the list of potentially problematic constraints and limits, there are several criteria to take into account:
- constraints and limits that are influenced by changing data,
- constraints and limits that are defined based on user inputs,
- constraints and limits that have been recently modified during model development.
Once you have this list of potentially problematic constraints and limits, you can specify that
- for 'compute IIS', constraints and limits that are not on the list are not eligible for inclusion in the IIS using the ISConstrForce, IISLBForce, IISUBForce, IISSOSForce, IISQConstrForce, and IISGenConstrForce attributes,
- for feasibility relaxation, only the constraints and limits on the list are eligible for relaxation when using Model.feasRelax() by using the vars and constrs arguments. These two arguments control which variables whose bounds are allowed to be violated and which linear constraints are allowed to be violated, respectively. For feasibility relaxation, you can also use the IIS results to get the list of constraints and limits that are potentially problematic.
Compute IIS can be computationally expensive for larger models
In terms of computational complexity, calculating an IIS is relatively inexpensive for linear programming (LP) problems, but can be much more computationally expensive for mixed-integer programming (MIP) problems. Additionally, the resulting IIS may be large and hard to interpret.
For larger models, particularly MIP models, we recommend using a feasibility relaxation with the objective of minimizing the number of violations. To do this, you need to set the first argument of Model.feasRelaxS() and Model.feasRelax() to relaxobjtype=2. This is less computationally expensive and, depending on the end goal, can be viewed as an alternative to 'compute IIS'.
Caveat: check that the lower bounds on variables are what you intended
Gurobi automatically adds a lower bound of 0 to variables. This can cause an infeasibility, if this is not what was intended.
Further information
- How does Gurobi compute the IIS for infeasible models?
- Why does Gurobi sometimes return non-integral values for integer variables?
- Feasibility relaxations of multi-objective models in Gurobi v9.0.x
Comments
0 comments
Article is closed for comments.