Description: This notebook offers a concise guide on troubleshooting model infeasibility using AMPL’s presolve feature and other language capabilities.
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:
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""")
.
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.
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.
The output indicates a violation in the final_awt
variable bounds.
Next, we perform a similar check for the buy_comp
variable.
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:
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
:
# 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_awt
s were tightened by checking if there is a difference between .lb0
and .lb
:
'bound tightened' [*] :=
AAPL 'bound tightened'
MSFT 'bound tightened'
;