Handling infeasibility
Topics covered in this section:
A problem is said to be infeasible if no solution exists which satisfies all the constraints. The problem status 'infeasible' generally is an undesirable outcome that should be avoided. In other terms, if an infeasibility arises you need suitable means to analyze what is going wrong and modeling techniques and tools to remedy or prevent this state from happening.
The following sections present different possibilities how to deal with infeasibility in FICO Xpress Optimization models.
Modeling for infeasibility
By 'modeling for infeasibility' we mean a model formulation that incorporates some extra freedom to make the problem feasible and minimizes the utilization of the added freedom. In mathematical terms this corresponds to introducing deviation variables in constraints to make them feasible and to penalize these deviations in the objective function. Adding deviation variables to a model formulation implies being able to modify the definition of variables or constraints after their creation, a feature well supported in Mosel and and the object-oriented solver APIs.
NB: deviation variables should only be added in constraints that use external data (to make up for infeasibility in data). Do not relax constraints that have no data, only variables, representing relationships that must hold, such as inventory balance constraints, physical processes, conversion rates or mass balance.
»Scenario 1 (Mosel)
The example file examples\getting_started\Mosel\folioinfeas.mos solves an LP problem. If the problem instance is found to be infeasible the model retrieves and displays the infeasible variables and constraints, it then adds deviation variables to certain constraints and re-solves the modified problem. The final solution display takes into account the values of the deviation variables, thus providing some insight on the type of constraint violations.
Analyzing infeasibility: IIS
A general technique to analyze infeasibility is to find a small portion of the matrix that is itself infeasible. Xpress Optimizer does this by finding irreducible infeasible sets (IISs). An IIS is a minimal set of constraints and variable bounds which is infeasible, but becomes feasible if any constraint or bound in it is removed.
»Scenario 1 (Mosel)
Take a look at the Mosel model in file examples\getting_started\Mosel\folioiis.mos. This example retrieves the IIS sets for an LP-infeasible problem and displays their contents.
»Scenario 2 (object-oriented APIs)
Similarly, you can use the IIS access functionality of the Optimizer to retrieve and display IIS (see file FolioIIS.[cs|java] in directory examples\optimizer\[csharp|java]\objects).
»Scenario 3 (Optimizer Python interface)
The Python script examples\python\example_infeasible.py showcases the usage of all functions for handling infeasibility in an optimization problem, specifically the functions that manage IIS.
Infeasibility repair
In some cases, identifying the cause of infeasibility, even if the search is based on IISs may prove very demanding and time consuming. In such cases, a solution that violates the constraints and bounds minimally can greatly assist modeling. This functionality is provided by the infeasibility repair utility of Xpress Optimizer. Based on preferences provided by the user, the Optimizer relaxes the constraints and bounds in the problem by introducing penalized deviation variables associated with selected rows and columns. The preference values reflect the modeler's will to relax the corresponding bound or constraint right-hand-side (the penalty value associated is the reciprocal of the preference), a zero preference means no relaxation.
»Scenario 1 (Mosel)
The infeasibility repair functionality in Mosel has two forms, the simpler one lets you define a preference per constraint type (=, ≤, ≥), with its detailed form you can state a preference for every single constraint. The latter is used in the example implementation in file examples\getting_started\Mosel\foliorep.mos. This example performs the infeasibility repair algorithm several times, each time with a different value for the parameter delta to analyze the effect of extra violations of the constraints and bounds to the underlying model.
Further information
- ``Xpress Optimizer Reference Manual'', 3.2 `Infeasibility'
- Examples of algorithms modifying constraint definitions in Mosel: ``Xpress Mosel User Guide'', Chapter 12: `Extensions to Linear Programming'
- Python: see examples in the ``Python interface manual'', Chapter 6
© 2001-2024 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.