Diagnosis and Resolution of Conflicts
In optimization, encountering infeasible models – where no solution satisfies all constraints – is a common challenge. So, let's explore effective strategies to diagnose and resolve infeasibility in optimization models.
Verifying Inputs and Model Correctness
Accuracy of Input Data
Before diving into complex solutions, ensure your input data is accurate. This seemingly obvious step is crucial for every model, not just when facing infeasibility. Perform thorough sanity checks to confirm the integrity of your data. For instance, if a constraint in your model limits commitment to a client based on production capacity, overpromising beyond this capacity can lead to infeasibility. Thorough data validation can prevent such issues and save time, especially in scenarios where model creation and solving are time-intensive.
Model Accuracy
Make sure that your model’s variables and constraints are correctly defined. A common pitfall involves simple coding errors, such as:
Incorrectly defining variable types
Making indexing mistakes (like creating x_{i,k} rather than x_{i,j,k})
Setting incorrect bounds
Incorrectly using equality instead of less-than-equality
Reviewing the “.lp” file - the human-readable algebraic representation of your code - can highlight these discrepancies. It’s important to remember that the presence of numerous individual constraints doesn’t necessitate reviewing each one. Often, these constraints are generated through iterations over indices. So, verifying a representative sample is usually sufficient.
Tip: Algebraic Formulation First
Always start with the algebraic formulation of your model before coding. This practice aids in verifying the formulation’s correctness and simplifies the process of sharing the model with team members, support teams, or online communities.
If your input data and model structure appear correct, troubleshooting the model is the next course of action.
Model Troubleshooting Techniques
Review IIS
Solvers like Gurobi, XPRESS, or CPLEX offer advanced features to identify conflicting constraints, one of which is computing the Irreducible Inconsistent Subsystem (IIS) or Irreducible Infeasible Set. An IIS is a subset of constraints and variable bounds that is infeasible on its own but becomes feasible if any single constraint or bound is removed.
While not unique and potentially resource-intensive to calculate in large mixed-integer programming (MIP) models, analyzing the IIS generated by the solver can shed light on the types of conflicting constraints and bounds, aiding in resolving issues.
Using Slack Variables
Adding slack variables to constraints and penalizing their violations in the objective function is a powerful technique for preventing or managing infeasibility. This approach offers several advantages:
It is particularly useful in models with a large number of constraints, where pinpointing conflicting constraints can be challenging.
By implementing this approach, hard constraints are transformed into soft ones, which often align better with the economic realities of a problem. For instance:
A violation of labor resources could indicate the need for additional temporary workers.
Exceeding capacity constraints could indicate the need to rent extra space.
Violation of production constraints could mean the need to outsource some of the production.
Minor time violations might be acceptable by the business, and penalizing the violation can mean offering coupons and discounts to the customers.
As shown in the image below, in some rare cases, a MIP problem might be infeasible, while its LP relaxation is feasible. Adding slack variables to all constraints might be the easiest way to identify the issue.
The region is feasible for LP relaxation but has no integer points for the MIP model
Adding slack variables can be a proactive measure to avoid infeasibilities. This is especially beneficial in complex models, or those with many conditional constraints, or in many real-life problems where the stakeholders may provide some rules as hard constraints, but they do not need to be.
When penalizing slack variables in the objective function, penalties should be reasonably and relatively large but not too large, to avoid introducing numerical issues in the model. Be aware that numerical issues themselves can also become a source of infeasibility in some models.
So, review the solver’s log file to check the range of coefficients in your model and spot warnings about numerical instability.
If relaxing some constraints or bounds are allowed, you may also use features available in the solvers that allow an infeasible model to be relaxed. I reference this feature in Gurobi, XPRESS, and CPLEX but be sure to check the documentation of the solver you use to learn more about a similar feature.
General Tips
If a known feasible solution exists, input its values into your model and solve it. After getting an infeasible solution, employ troubleshooting techniques such as accessing the IIS or introducing slack variables.
Note that the existing feasible solution can be any trivial solution. Most likely, your model is a representation of a real-life problem. So, think about that problem and whether, for instance, setting all the variables to zero (or to their lower bounds) results in a feasible solution. If so, do you obtain the same result from your formulated model? How about your coded model?
So, as part of your development process, always test your model against a small dataset, and ideally, against a known correct benchmark or baseline. This also facilitates discussions about any violated constraints with the users to evaluate the feasibility of converting some hard constraints into soft ones. Or potential exceptions in the data and the model that are usually handled by the users and are overlooked in the mathematical model.
Incremental Activation of Constraints
If none of the techniques mentioned so far could help reveal the source of infeasibility, start with a constraint-free model, and add constraints incrementally. This can be done one set of constraints at a time or in blocks, depending on your problem’s structure. We usually have an idea of what each set of constraints should do. For example, some are capacity constraints, some are flow constraints, some are assignment constraints, and so on. This incremental approach can help isolate and pinpoint the source of conflict. Note that there is no one right way to start adding the constraints. The infeasibility may rise after adding the last set of constraints. So, next time, you can start from that constraint. This can be a last resort approach and you may never need it. But it’s good to know in case it helps you solve your problem.
Takeaway
While this is not an exhaustive list, these techniques for tackling infeasibility have proven effective over the years. Incorporating slack variables as a safeguard might be the best choice, but if not possible, you’re now equipped with several techniques to address infeasibility in your models.