# 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
)  # 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:

1. Integrating singleton constraints (constraints with one variable) into variable bounds.

2. Discarding inequalities that will always be slack.

3. 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];

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;

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.
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}

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:

1. The initial bounds declared on `final_awt` violate `numbuys` OR

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

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_awt`s 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'
;
```