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:

  1. Making some mistakes when modeling or inputting data (e.g., an empty left-hand side in a constraint).

  2. 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):

  1. Compute IIS: Identify the key constraints and variable bounds causing infeasibility.

  2. 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:

  1. The subsystem is still infeasible.

  2. 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:

(48)\[\begin{split}\max\quad &z=12x_{1}+8x_{2}\\ \text{s.t.}\quad &5 x_{1} + 2 x_{2} \geq 140\\ &2 x_{1} + 3 x_{2} \leq 90\\ &4 x_{1} + 2 x_{2} \leq 100\\ &x_{1}, x_{2}\geq0\end{split}\]

The feasible region of the model is shown below:

_images/copt-iisexample.png

From the figure, the conflicting constraints can be clearly seen:

(49)\[\begin{split}&c1:5 x_{1} + 2x_{2} \geq 140\\ &c3:4 x_{1} + 2x_{2} \leq 100\end{split}\]

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:

Table 39 Functions for Computing IIS of Infeasible Models

API

Compute IIS

Write IIS to File

C

COPT_ComputeIIS

COPT_WriteIIS

C++

Model::ComputeIIS()

Model::WriteIIS()

C#

Model.ComputeIIS()

Model.WriteIIS()

Java

Model.computeIIS()

Model.writeIIS()

Python

Model.computeIIS()

Model.writeIIS()

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:

Table 40 Functions for Getting Variable IIS Status

API

Lower Bound IIS Status

Upper Bound IIS Status

C

COPT_GetColLowerIIS

COPT_GetColUpperIIS

C++

Model::GetVarLowerIIS()

Model::GetVarUpperIIS()

C#

Model.GetVarLowerIIS()

Model.GetVarUpperIIS()

Java

Model.getVarLowerIIS()

Model.getVarUpperIIS()

Python

Model.getVarLowerIIS()

Model.getVarUpperIIS()

Notes:

  • The above functions accept either a single variable (Var object) or a set of variables (VarArray or tupledict 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() and Var.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:

Table 41 Functions for Getting Constraint IIS Status

API

Lower Bound IIS Status

Upper Bound IIS Status

C

COPT_GetRowLowerIIS

COPT_GetRowUpperIIS

C++

Model::GetConstrLowerIIS()

Model::GetConstrUpperIIS()

C#

Model.GetConstrLowerIIS()

Model.GetConstrUpperIIS()

Java

Model.getConstrLowerIIS()

Model.getConstrUpperIIS()

Python

Model.getConstrLowerIIS()

Model.getConstrUpperIIS()

Notes:

  • The above functions accept either a single constraint (Constraint object) or a set of constraints (Constraint or ConstrArray 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() and Constraint.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:

Table 42 Functions for Getting IIS Status of Special Constraints

API

SOS Constraint

Indicator Constraint

C

COPT_GetSOSIIS

COPT_GetIndicatorIIS

C++

Model::GetSOSIIS()

Model::GetIndicatorIIS()

C#

Model.GetSOSIIS()

Model.GetIndicatorIIS()

Java

Model.getSOSIIS()

Model.getIndicatorIIS()

Python

Model.getSOSIIS()

Model.getIndicatorIIS()

For details on the usage of the above functions, please refer to the API reference manual for each programming interface:

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:

Table 44 Functions for Computing Feasibility Relaxation

API

Compute FeasRelax

Write Relaxed Model to File

C

COPT_FeasRelax

COPT_WriteRelax

C++

Model::FeasRelax()

Model::WriteRelax()

C#

Model.FeasRelax()

Model.WriteRelax()

Java

Model.feasRelax()

Model.writeRelax()

Python

Model.feasRelax()

Model.writeRelax()

COPT supports two approaches for computing feasibility relaxation. In interfaces other than Python, users can use different function arguments:

  1. 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)

  2. Full version: Accepts more parameters (specify variables/constraints, set penalty factors for bounds).

    • vars: variables to relax

    • cons: constraints to relax

    • colLowPen: penalty factor for variable lower bounds

    • colUppPen: penalty factor for variable upper bounds

    • rowBndPen: penalty factor for constraint bounds

    • rowUppPen: penalty factor for constraint upper bounds (for double-sided constraints)

    Note: In most cases, set rowUppPen as NULL.

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:

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)