Debugging Model Infeasibility#

Description: This notebook offers a concise guide on troubleshooting model infeasibility using AMPL’s presolve feature and other language capabilities.

Tags: amplpy, ampl, debug, infeasibility

Notebook author: Gyorgy Matyasfalvi <gyorgy@ampl.com>

References:

AMPL a Modeling Language for Mathematical Programming – Robert Fourer et al.

# Install dependencies
%pip install -q amplpy

# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
    modules=["open"],  # modules to install
    license_uuid="default",  # license to use
)  # instantiate AMPL object and register magics

Introduction#

Understanding what causes the infeasibility is crucial, regardless of whether you’re using the solver, AMPL, or both. This notebook offers some insight that might streamline this process. A clear understanding of how presolve works can guide one in devising a method to pinpoint the cause of infeasibility.

Overview of presolve#

Presolve recursively executes the following tasks:

Integrating singleton constraints (constraints with one variable) into variable bounds.
Discarding inequalities that will always be slack.
Inferring bounds from constraints that involve multiple bounded variables.

In light of this, an ‘infeasible’ constraint is identified in step 3 of the above process, and arises when the deduced bounds violate the model’s bounds. These bounds are inferred by examining the variables’ bounds that form part of the constraint. For instance, a constraint’s upper bound could be violated by the lower bounds on some variables present in the constraint with positive constants.

Identifying the cause of infeasibility#

A sensible first step in identifying the cause of infeasibility is to scrutinize the variable bounds of the infeasible constraint. Try to determine which variables’ bounds contribute to the infeasibility and, if any, find the constraints that led to the tightening of those bounds.

Let’s walk through a specific example to illustrate the process:

%%writefile infeas.run

# Declare sets
set COMP1;
set COMP2;

# Variables
var final_awt{COMP1} >= 0;
var buy_comp{COMP2} >= 0;

# Parameters
param final_awt_lb{COMP1};
param final_awt_ub{COMP1};
param maxbuys >= 0;

# Constraints
subject to finalbounds {c in {'MSFT','AAPL'} inter COMP1}:
    final_awt_lb[c] <= final_awt[c] <= final_awt_ub[c];

subject to numbuys:
    sum{c1 in COMP1} final_awt[c1] + sum{c2 in COMP2} buy_comp[c2] <= maxbuys;

# Enter data mode and specify data
data;
param maxbuys := 4;
set COMP2 := META;

param: COMP1: final_awt_lb :=
MSFT 3 AAPL 2 NVDA 0 AMZN 0 TSLA 0;

param final_awt_ub :=
MSFT 4 AAPL 3 NVDA 2 AMZN 2 TSLA 2;

# Return to model mode
model;

Writing infeas.run

Running `infeas.mod`#

In the following sections, we’ll utilize %%ampl_eval magic cells, enabling us to execute AMPL code directly from the notebook’s code cells. %%ampl_eval cells are equivalent to invoking ampl.eval("""cell content""").

%%ampl_eval

include infeas.run;
option solver highs, show_stats 1;
solve;

Presolve eliminates 2 constraints.
Adjusted problem:
6 variables, all linear
1 constraint, all linear; 6 nonzeros
	1 inequality constraint
0 objectives.

Warning:
	presolve: constraint numbuys cannot hold:
		body <= 4 cannot be >= 5; difference = -1

The above output indicates that the constraint numbuys cannot hold due to the violation in bounds.

Investigating the `numbuys` constraint#

To delve deeper, we can use the show or expand command in AMPL to investigate the numbuys constraint further.

%%ampl_eval

show numbuys; # Will display the constraint as it is in the model.
print; # Used for newline
expand numbuys; # This will expand the constraint and display the expanded form.

subject to numbuys: sum{c1 in COMP1} final_awt[c1] + sum{c2 in COMP2}
  buy_comp[c2] <= maxbuys;

subject to numbuys:
	final_awt['MSFT'] + final_awt['AAPL'] + final_awt['NVDA'] + 
	final_awt['AMZN'] + final_awt['TSLA'] + buy_comp['META'] <= 4;

This reveals the variables involved in the numbuys constraint and its upper bound. The next step is to check if the sum of the lower bounds of these variables exceeds the constraint’s upper bound.

%%ampl_eval

if sum {c1 in COMP1} final_awt[c1].lb >= numbuys.ub then print "final_awt: Violation"; else print "final_awt: No violation";

final_awt: Violation

The output indicates a violation in the final_awt variable bounds. Next, we perform a similar check for the buy_comp variable.

%%ampl_eval

if sum {c2 in COMP2} buy_comp[c2].lb >= numbuys.ub then print "buy_comp: Violation"; else print "buy_comp: No violation";

buy_comp: No violation

Investigating variable bounds#

At this point we know that lower bounds on final_awt violate the constraint numbuys. There are two scenarios that could have lead to this violation:

The initial bounds declared on final_awt violate numbuys OR
presolve tightened the bounds, which then led to the violation.

Modifying the above AMPL command to use suffix .lb0 (initial lower bounds) will help determining this:

%%ampl_eval

if sum {c1 in COMP1} final_awt[c1].lb0 >= numbuys.ub then print "final_awt.lb0: Violation"; else print "final_awt.lb0: No violation";

final_awt.lb0: No violation

This means that presolve tightened the bounds, meaning the infeasibility is related to another constraint. We can use the xref command to check, which constraints depend on final_awt:

%%ampl_eval

xref final_awt;

# 3 entities depend on final_awt:
Initial
finalbounds
numbuys

We can ignore Initial as that’s the default environment AMPL starts in. This leaves us with finalbounds, which is indeed a constraint. Revealing the other constraint that causes the infeasibility.

For this example all constraints in finalbounds cause a bound tightening that leads to the infeasibility. But we could further analyze the case by looking at which final_awts were tightened by checking if there is a difference between .lb0 and .lb:

%%ampl_eval

display {c1 in COMP1: final_awt[c1].lb > final_awt[c1].lb0} 'bound tightened';

'bound tightened' [*] :=
AAPL  'bound tightened'
MSFT  'bound tightened'
;