Infeasibility Analysis

Infeasibility analysis

One of the more daunting tasks in mathematical programming is to find the cause of an infeasible mathematical program. Such infeasibilities may occur

  • either when you are developing a new model due to modeling errors,

  • or in a complete (and well-tested), model-based, end-user application employed by your customers due to inconsistencies in the model data.

Infeasibilities due to modeling errors

There are several types of modeling errors that you can make during the development of a mathematical program that can lead to hard-to-explain infeasibilities. The most common are:

  • simple typing errors, leading, for instance, to a wrong variable being referenced in a constraint,

  • a logical flaw in the model formulation, i.e. the formulation of one or more constraints just makes no sense,

  • the domain restriction of a constraint is not restrictive enough, i.e. constraints are generated that should not be generated,

  • the domain restriction of a variable is wrong, leading to too many or too few terms being generated in constraints referring to such a variable, or

  • the restriction in iterative operators (such as SUM or PROD) in the definition of constraints or defined variables is wrong, leading to too many or too little terms being generated in that particular constraint.

In general, trying to find infeasibilities that occur during model development may force you to generate a constraint listing of your mathematical program and carefully examine the generated constraints in order to find the modeling error.

Infeasibilities due to data inconsistencies

Even when the formulation of a mathematical program is internally consistent, and shipped as an end-user application to your customers, infeasibilities may occur due to inconsistencies in the model data. The most common data errors are:

  • inconsistencies in the structural data defining the topology of a model, e.g. in a network model a demand node may have been added for which no incoming arcs have been specified, or

  • inconsistencies in the quantitive model data, e.g. to total demand exceeds the total supply.

While most data inconsistencies may be detected by methodically checking the consistency all input data prior to actually solving the mathematical program (for example, by using Assertions, see also Assertions), it is often hard to cover all possible data inconsistencies.

Adding excess variables

A commonly used approach to try and deal with infeasibilities, is to add explicit excess variables to all or some constraints in a model, along with a penalty term in the objective that will keep all excess variables equal to 0 if the model is feasible. If this procedure is executed properly, the modified mathematical program will always be feasible, while the original mathematical program is feasible if and only if the excess variables are all equal to 0. In the case of an infeasibility, an examination of the excess variables may provide useful information about the cause of infeasibility.

Laborious procedure

While adding excess variables to your model may certainly help you to resolve any infeasibilities, the process of manually adding these excess variables to a mathematical program is laborious and error-prone:

  • you have to add the declarations of the excess variables for all (or some) constraints in your model,

  • the selected constraints have to be modified to include these excess variables, and

  • the objective has to be modified to include the excess-related penalty terms.

In addition, adding excess variables may considerably increase the size of the generated matrix, so you may want to write supporting code to exclude the excess variables from your mathematical program unless you encounter an infeasibility.

Adding Infeasibility Analysis to Your Model

The ViolationPenalty attribute

To ease the manual process described above, AIMMS offers support to automatically extend your mathematical program with excess variables during the generation of the matrix for the solver. You enable this feature through the ViolationPenalty attribute of a MathematicalProgram declaration. The value of the ViolationPenalty attribute must be either a

The predefined set AllVariablesConstraints is a subset of the set AllIdentifiers and contains the names of all the variables and constraints in your model. Through one of these two types of parameters you can specify for which variables and constraints in your mathematical program AIMMS must generate excess variables, as well as the penalty coefficient of these excess variables in the modified objective.

The set AllViolationTypes

The predefined set AllViolationTypes is a fixed set containing the three types of possible violations for which AIMMS can generate excess variables. The elements in the set AllViolationTypes are

  • Lower: generate excess variables for the violation of a lower bound,

  • Upper: generate excess variables for the violation of an upper bound, and

  • Definition: generate excess variables for the violation of the equality between a defined variable and its definition.

Interpretation of ViolationPenalty attribute

If a parameter you entered in the ViolationPenalty attribute contains no data, AIMMS will generate the mathematical program without any generated excess variables. If you specify a 2-dimensional parameter which is not empty, all values must be nonnegative or assume the special value ZERO (see also Real Values and Arithmetic Extensions), and AIMMS will interpret its contents as follows.

Penalty for objective variable

The modified objective will include the original objective, unless a value of ZERO has been assigned to Definition violation type for the original objective variable. AIMMS will treat any other penalty value than ZERO assigned to the objective variable as 1.0! Note that by including the original objective the penalized mathematical program may become unbounded.

Penalty for constraints

AIMMS will add nonnegative excess variables for the violation of a (finite) lower and/or upper bound of every constraint for which a penalty value other than 0.0 has been specified for the Lower and/or Upper violation type, respectively. If a bound is infinite, no corresponding excess variable will be generated. A penalty term will be added to the modified objective consisting of the product of the specified (nonnegative) penalty coefficient times the excess variable associated with the constraint, unless a penalty of ZERO has been specified in which case the corresponding term will not be added to the modified objective.

Penalty for variables

AIMMS will add nonnegative excess variables for the violation of a (finite) lower and/or upper bound of every variable for which a penalty value other than 0.0 has been specified for the Lower and/or Upper violation type, respectively. If a bound is infinite, no corresponding excess variable will be generated. A penalty term will be added to the modified objective consisting of the product of the specified (nonnegative) penalty coefficient times the excess variable associated with the variable, unless a penalty of ZERO has been specified in which case the corresponding term will not be added to the modified objective. The effect of using Lower and/or Upper violations is that the variable can assume values outside their bounds throughout the mathematical program.

Penalty for variable definitions

AIMMS will add nonnegative excess variables for the violation of the equality between a defined variable and its definition for every defined variable for which a penalty value other than 0.0 has been specified for the Definition violation type. A penalty term will be added to the modified objective consisting of the product of the specified (nonnegative) penalty times the excess variable(s) associated with the constraint expressing the equality, unless a penalty of ZERO has been specified in which case the corresponding term(s) will not be added to the modified objective.

Definition versus lower/upper violations

You can both use the Lower and/or Upper violation types and Definition violation type to compensate for a violation between the value of the defined variable and its definition. However, when you use the Definition violation type, the value of the variable will remain within its specified bounds throughout the mathematical program. It is up to you to decide which violation type suits your needs best for a particular defined variable.

Interpretation of 1-dimensional parameter

If you specify a 1-dimensional parameter for the ViolationPenalty attribute, AIMMS will interpret this parameter as if it were a 2-dimensional parameter, with the same value for all three violation types Lower, Upper and Definition.

FeasOpt and FeasRelax

Gurobi and CPLEX offer functionality to extend the method of Violation Penalties described in this section. If the option Feasibility relaxation is set to advanced, AIMMS will call FeasOpt (CPLEX) or FeasRelax (Gurobi). Note that this option is only available for these two solvers.

As before, AIMMS will still automatically generate the violation variables. However, there are some differences.

For the default method of handling Violation Penalties, AIMMS will add the penalty term to the original objective function (unless a value of ZERO has been assigned to Definition violation type for the original objective variable). In contrast, for FeasOpt and FeasRelax the objective will only consist of violation variables and their respective penalty terms. This allows the user to compute a minimum cost relaxation.

Additionally, the user can choose between several objective metrics for the computation of the minimum cost relaxation. The objective metric can be set in the option Feasibility relaxation objective. The values are:

  • weighted sum of violations,

  • weighted sum of squared violations,

  • weighed number of violations.

Optionally, after the first phase of computing a minimum cost relaxation, the user can choose to activate a second phase. In the second phase, the original objective is optimized among all minimum cost relaxations. The second phase can be activated by using the option Feasibility relaxation optimize original objective.

There are some other differences, that is, if the option Feasibility relaxation is set to advanced then:

  • A penalty value of ZERO specifies that the corresponding constraint or variable bound cannot be violated, and

  • The Lower violation type will be ignored for equality constraints and, in case of Gurobi, for ranged constraints.

Inspecting Your Model for Infeasibilities

Finding violations

After you have let AIMMS extend your model with excess variables to find an infeasibility, you must inspect the variables and constraints in your model to find the violations. AIMMS allows you to do this through the use of two suffices, the .Violation suffix and the .DefinitionViolation suffix.

The .Violation suffix…

The .Violation suffix denotes the amount by which a variable or constraint violates its lower or upper bound. If you have specified a nonzero violation penalty for the Upper violation type, the .Violation suffix can assume positive values, while it can assume negative values whenever you have specified a nonzero violation penalty for the Lower violation type.

… for variables

For variables the .Violation suffix denotes the amount by which the variable violates its

  • upper bound (if the suffix assumes a positive value), or

  • lower bound (if the suffix assumes a negative value).

… for constraints

For constraints the .Violation suffix denotes the amount by which the constraint violates its

  • upper bound (if the suffix assumes a positive value),

  • lower bound (if the suffix assumes a negative value, for ranged constraints).

If the constraint is an equality constraint, the .Violation suffix denotes the (positive or negative) amount by which the left hand side differs from the (constant) right hand side.

The .DefinitionViolation suffix

With the .DefinitionViolation suffix, you can locate violations in the definitions of defined variables for which you have specified a positive penalty for the Definition violation type. The value of the suffix denotes the (positive or negative) amount by which the defined variable differs from its definition. Note that a defined variable may violate both its bounds and its definition, depending on the type of allowed violations you have specified.

Locating violations

To locate violations in a model which was extended by AIMMS with excess variables, you may use the Card function to locate variables and constraints with nonzero .Violations suffices. The following example shows how to proceed, where v is assumed to be an index in AllVariables.

for ( v | Card(v, 'Violation') ) do

    ! Take any action that you want to perform on this violated variable

endfor;

Application to Goal Programming

Goal programming …

In goal programming a distinction is made between hard constraints that cannot be violated and soft constraints, which represent goals or targets one would like to achieve. The objective function in goal programming is to minimize the weighted sum of deviations from the goals set by the soft constraints.

…interpreted as violations

In AIMMS, goal programming can be easily implemented using the ViolationPenalty attribute of a mathematical program, without the need to modify the formulation of all soft constraints. For each soft constraint in your goal programming model, you can assign the appropriate weight to the ViolationPenalty attribute to penalize deviations from the set target for that constraint.

Inspecting deviations

Through the .Violation suffix of constraints and variables you can inspect the deviations from the goals of the soft constraints in your goal programming model.