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.