Handling Infeasible Models
This chapter introduces two approaches supported by COPT for handling infeasible problems:
In real-world problems, it is common to encounter infeasible models, which correspond to the solution status
code COPT.INFEASIBLE
. The main reasons for infeasibility are usually:
Making some mistakes when modeling or inputting data (e.g., an empty left-hand side in a constraint).
The problem itself is infeasible, meaning some constraints or variable bounds are conflicting.
COPT provides two methods for analyzing and handling infeasible models, which are supported for both Linear Programming (LP) and Mixed-Integer linear programming (MILP):
Compute IIS: Identify the key constraints and variable bounds causing infeasibility.
Feasibility Relaxation (FeasRelax): Quantitatively compute the conflicts in constraints or variable bounds (violations) that lead to infeasibility.
IIS for Infeasible Models
IIS (Irreducible Inconsistent Subsystem) refers to a minimal conflicting set in the model that causes infeasibility, and has the following properties:
The subsystem is still infeasible.
Removing any single constraint or variable bound from the IIS will make the subsystem feasible.
Note: The IIS computed by COPT may not be minimal or unique. It may require several iterations of modifying constraints and recomputing the IIS before the model becomes feasible.
Below is an example of an infeasible Linear Programming model:
The feasible region of the model is shown below:
From the figure, the conflicting constraints can be clearly seen:
After computing the IIS for the above model and writing it to a file (.iis
format),
the file content is as follows, consistent with the figure:
\Generated by Cardinal Operations
Maximize
12 x[1] + 8 x[2]
Subject To
c1: 5 x[1] + 2 x[2] >= 140
c3: 4 x[1] + 2 x[2] <= 100
END
Computing IIS
COPT provides functions in various Programming API to compute the IIS of an infeasible model, returning a set of conflicting
constraints and variable bounds. The IIS can also be written to a file by specifying the file name suffix as .iis
(e.g., example.iis
).
Related function names are shown in Table 39:
API |
Compute IIS |
Write IIS to File |
---|---|---|
C |
|
|
C++ |
|
|
C# |
|
|
Java |
|
|
Python |
|
|
Getting IIS status of variables and constraints
Functions for variable’s IIS status
After computing the IIS, the IIS status of variables (lower/upper bound) can be obtained. The status indicates whether the bound is in the IIS:
1: The specified variable bound (lower/upper) is in the IIS
0: The specified variable bound (lower/upper) is not in the IIS
Supported functions for different interfaces are shown in Table 40:
API |
Lower Bound IIS Status |
Upper Bound IIS Status |
---|---|---|
C |
|
|
C++ |
|
|
C# |
|
|
Java |
|
|
Python |
|
|
Notes:
The above functions accept either a single variable (
Var
object) or a set of variables (VarArray
ortupledict
objects).Except for the C API, other interfaces provide member functions in the
Var
class to get the IIS status for a single variable. For example, in Python:Var.getLowerIIS()
andVar.getUpperIIS()
.In the Python API, you can also directly access the IIS status as member attributes of the
Var
object:Var.iislb
for the lower bound IIS status,Var.iisub
for the upper bound IIS status.
Functions for constraint’s IIS status
After computing the IIS, COPT also supports querying the IIS status of constraint bounds (lower/upper). The status indicates whether the bound is in the IIS:
1: The specified constraint bound (lower/upper) is in the IIS
0: The specified constraint bound (lower/upper) is not in the IIS
Supported functions for different interfaces are shown in Table 41:
API |
Lower Bound IIS Status |
Upper Bound IIS Status |
---|---|---|
C |
|
|
C++ |
|
|
C# |
|
|
Java |
|
|
Python |
|
|
Notes:
The above functions accept either a single constraint (
Constraint
object) or a set of constraints (Constraint
orConstrArray
objects).Except for the C API, other interfaces provide member functions in the
Constraint
class to get the IIS status for a single constraint. For example, in Python:Constraint.getLowerIIS()
andConstraint.getUpperIIS()
.In the Python API, you can also directly access the IIS status as member attributes of the
Constraint
object:Constraint.iislb
for the lower bound IIS status,Constraint.iisub
for the upper bound IIS status.
Functions for special constraints
COPT also provides functions, as shown in Table 42, for getting the IIS status of SOS and Indicator constraints:
API |
SOS Constraint |
Indicator Constraint |
---|---|---|
C |
|
|
C++ |
|
|
C# |
|
|
Java |
|
|
Python |
|
|
For details on the usage of the above functions, please refer to the API reference manual for each programming interface:
C API: IIS computation functions
C++ API: Model class, Var class, Constraint class
C# API: Model class, Var class, Constraint class
Java API: Model class, Var class, Constraint class
Python API: Model class, Var class, Constraint class
Feasibility Relaxation for infeasible models
Feasibility relaxation is the process of minimizing the conflicts in the bounds of variables and constraints in the original infeasible model. Users can use the quantitative results from feasibility relaxation to adjust constraints or variable bounds, thus making the model feasible.
Computing Feasibility Relaxation
COPT provides functions in different interfaces for computing feasibility relaxation, and also allows writing the relaxed
model to a file with the suffix .relax
(e.g., example.relax
). Related function names are listed in Table 44:
API |
Compute FeasRelax |
Write Relaxed Model to File |
---|---|---|
C |
|
|
C++ |
|
|
C# |
|
|
Java |
|
|
Python |
|
|
COPT supports two approaches for computing feasibility relaxation. In interfaces other than Python, users can use different function arguments:
Simplified version: Relax all variables and/or constraints in the model, only requiring two parameters to specify whether to relax all variables or all constraints.
ifRelaxVars
: whether to relax variables (default:True
)ifRelaxCons
: whether to relax constraints (default:True
)
Full version: Accepts more parameters (specify variables/constraints, set penalty factors for bounds).
vars
: variables to relaxcons
: constraints to relaxcolLowPen
: penalty factor for variable lower boundscolUppPen
: penalty factor for variable upper boundsrowBndPen
: penalty factor for constraint boundsrowUppPen
: penalty factor for constraint upper bounds (for double-sided constraints)
Note: In most cases, set
rowUppPen
asNULL
.
The function names and argument conventions differ slightly across APIs, but the functionality and meaning are consistent. See each interface’s API manual for details:
C++ API: Model class
C# API: Model class
Java API: Model class
Python API: Model class
Notes:
For the simplified feasibility relaxation approach, the Python API additionally provides the function
Model.feasrelaxS(vrelax, crelax)
, requiring only two arguments:vrelax
: whether to relax variables (default:True
)crelax
: whether to relax constraints (default:True
)