Abstract

A functionality within the modeling language to relax a constraint and/or variable bound and re-solve will save development time as well as provide control to the decision-maker(s) when a particular instance of a math programming model is infeasible. One candidate solution is to introduce a suffix for constraints that allows for this functionality.

Motivation

An instance of a math programming model can be infeasible due to a particular set of parameter values. It may be that not all parameters are certain or that not all constraints and/or variable bounds are hard. Tools like Irreducible Infeasible Set (IIS) in MIP solvers help the expert understand and debug the model formulation. They do not necessarily offer a practical way to parse the information and report the finding to the end-user/decision-maker. In practice, adding a set of slack variables (note: for a lack of better terminology, using the term slack here to denote the slack required in a constraint to make it feasible; not to be confused with slack variables in linear programming) to constraints and setting up a feasibility problem (to minimize total slack required or other appropriate measure) is more approachable to provide control to the end-user. However, this requires the following.

1. Slack variables are declared and added to the relevant constraints.
2. Identifiers are declared and used as bounds for variables.
3. An appropriate objective is defined to setup the feasibility problem.
4. Math program is setup to exclude the variables while solving for the original objective and include the variables while solving for the feasibility problem either by
   • manipulating the definition of a subset of AllVariables (corresponding to the slacks) that defines the math program, or
   • fixing the slack variables to zero and relaxing them.

All the information required to define the feasibility problem may not be available at the time developing the first math programming model and during subsequent iterations. It can be time-consuming during development or lead to errors while manually updating the model. Further, it may destroy the structure of the problem to develop advanced algorithms later on (at least when using the approach of fixing the slack variables to zero and then relaxing them later).

Solution Candidate

• Add a functionality in the AIMMS modeling language to relax a constraint or variable bound by introducing a new suffix for constraints and variables.
• Maintain a one-to-one feasibility model behind the scenes and solve it when requested. MIP solvers like CPLEX and Gurobi already support this natively (GRBModel.FeasRelax() - Gurobi Optimization and IBM Documentation - IBM Documentation).
• Alternatively, generate a model with slacks as a runtime library somehow and generalize it for other types of math programs.
• The suffix denoting the relaxation could consider non-binary values to also represent a priority order or even the objective function coefficient corresponding to the constraint/variable bound for the feasibility problem.