Infeasibility Diagnostics
There are two closely related tools for infeasibility diagnosis:
The first simply provides a conduit for solvers that compute an
infeasible irreducible system (e.g., Cplex, Gurobi, or Xpress). The
second provides similar functionality, but uses the mis
package
contributed to Pyomo.
Infeasible Irreducible System (IIS) Tool
This module contains functions for computing an irreducible infeasible set for a Pyomo MILP or LP using a specified commercial solver, one of CPLEX, Gurobi, or Xpress.
- pyomo.contrib.iis.write_iis(pyomo_model, iis_file_name, solver=None, logger=<Logger pyomo.contrib.iis (INFO)>)[source]
Write an irreducible infeasible set for a Pyomo MILP or LP using the specified commercial solver.
- Parameters:
pyomo_model – A Pyomo Block or ConcreteModel
iis_file_name (str) – A file name to write the IIS to, e.g., infeasible_model.ilp
solver (str) – Specify the solver to use, one of “cplex”, “gurobi”, or “xpress”. If None, the tool will use the first solver available.
logger (logging.Logger) – A logger for messages. Uses pyomo.contrib.iis logger by default.
- Returns:
iis_file_name – The file containing the IIS.
- Return type:
Minimal Intractable System finder (MIS) Tool
The file mis.py
finds sets of actions that each, independently,
would result in feasibility. The zero-tolerance is whatever the
solver uses, so users may want to post-process output if it is going
to be used for analysis. It also computes a minimal intractable system
(which is not guaranteed to be unique). It was written by Ben Knueven
as part of the watertap project (https://github.com/watertap-org/watertap)
and is therefore governed by a license shown
at the top of mis.py
.
The algorithms come from John Chinneck’s slides, see: https://www.sce.carleton.ca/faculty/chinneck/docs/CPAIOR07InfeasibilityTutorial.pdf
Solver
At the time of this writing, you need to use IPopt even for LPs.
Quick Start
The file trivial_mis.py
is a tiny example listed at the bottom of
this help file, which references a Pyomo model with the Python variable
m and has these lines:
from pyomo.contrib.mis import compute_infeasibility_explanation
ipopt = pyo.SolverFactory("ipopt")
compute_infeasibility_explanation(m, solver=ipopt)
Note
This is done instead of solving the problem.
Note
IDAES users can pass get_solver()
imported from ideas.core.solvers
as the solver.
Interpreting the Output
Assuming the dependencies are installed, running trivial_mis.py
(shown below) will
produce a lot of warnings from IPopt and then meaningful output (using a logger).
Repair Options
This output for the trivial example shows three independent ways that the model could be rendered feasible:
Model Trivial Quad may be infeasible. A feasible solution was found with only the following variable bounds relaxed:
ub of var x[1] by 4.464126126706818e-05
lb of var x[2] by 0.9999553410114216
Another feasible solution was found with only the following variable bounds relaxed:
lb of var x[1] by 0.7071067726864677
ub of var x[2] by 0.41421355687130673
ub of var y by 0.7071067651855212
Another feasible solution was found with only the following inequality constraints, equality constraints, and/or variable bounds relaxed:
constraint: c by 0.9999999861866736
Minimal Intractable System (MIS)
This output shows a minimal intractable system:
Computed Minimal Intractable System (MIS)!
Constraints / bounds in MIS:
lb of var x[2]
lb of var x[1]
constraint: c
Constraints / bounds in guards for stability
This part of the report is for nonlinear programs (NLPs).
When we’re trying to reduce the constraint set, for an NLP there may be constraints that when missing cause the solver to fail in some catastrophic fashion. In this implementation this is interpreted as failing to get a results object back from the call to solve. In these cases we keep the constraint in the problem but it’s in the set of “guard” constraints – we can’t really be sure they’re a source of infeasibility or not, just that “bad things” happen when they’re not included.
Perhaps ideally we would put a constraint in the “guard” set if IPopt failed to converge, and only put it in the MIS if IPopt converged to a point of local infeasibility. However, right now the code generally makes the assumption that if IPopt fails to converge the subproblem is infeasible, though obviously that is far from the truth. Hence for difficult NLPs even the “Phase 1” may “fail” – in that when finished the subproblem containing just the constraints in the elastic filter may be feasible – because IPopt failed to converge and we assumed that meant the subproblem was not feasible.
Dealing with NLPs is far from clean, but that doesn’t mean the tool can’t return useful results even when its assumptions are not satisfied.
trivial_mis.py
import pyomo.environ as pyo
m = pyo.ConcreteModel("Trivial Quad")
m.x = pyo.Var([1,2], bounds=(0,1))
m.y = pyo.Var(bounds=(0, 1))
m.c = pyo.Constraint(expr=m.x[1] * m.x[2] == -1)
m.d = pyo.Constraint(expr=m.x[1] + m.y >= 1)
from pyomo.contrib.mis import compute_infeasibility_explanation
ipopt = pyo.SolverFactory("ipopt")
compute_infeasibility_explanation(m, solver=ipopt)