MP2NL: logical and complementarity constraints with any NL solver#
Description: Using the MP2NL meta-driver from amplpy: which options go where, what the subsolver receives, why the subsolver must handle the problem class MP produces, how to choose a complementarity reformulation, and how to check the returned solution
Tags: mp2nl, mp, minlp, complementarity, solution-check, nonlinear, amplpy, modeling-tips
Notebook author: Gleb Belov <gleb@ampl.com>
References:
MP modeling guide, Meta-driver MP2NL: https://mp.ampl.com/modeling-tools.html#meta-driver-mp2nl
MP modeling guide, Automatic solution check: https://mp.ampl.com/modeling-tools.html#automatic-solution-check
# Install dependencies
%pip install -q amplpy pandas
# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook
ampl = ampl_notebook(
modules=["coin"], # modules to install
license_uuid="default", # license to use
) # instantiate AMPL object and register magics
SOLVER_MINLP = "couenne" # an NL solver for mixed-integer nonlinear models: couenne, bonmin, knitro, baron, ...
SOLVER_NLP = "ipopt" # a continuous NLP solver: ipopt, knitro, conopt, ...
What MP2NL is for#
MP-based drivers (HiGHS, Gurobi, Xpress, CPLEX, COPT, SCIP, …) understand
MP’s extended expressions: ==>, or, atmost, count, alldiff,
complements, set membership, piecewise-linear terms and more. Solvers that
read the classic NL format do not. MP2NL sits between AMPL and such a
solver: it applies MP’s reformulations, writes a new NL file the solver can read,
runs the solver on it, and maps the solution back to your model.
Some drivers include the bridge and accept an option mp2nl=1 (see the MP
documentation for the current list). For any other NL solver, call MP2NL as the
solver and name the real solver inside it, as below.
A small model with logic and complementarity#
Four variables \(x_i\) want to be close to \(i\), at most two of them may be at least 1, and each \(y_i\) is complementary to \(y_i - x_i + 2 \ge 0\).
import pandas as pd
MODEL = r"""
set I := 1..4;
param target {i in I} := i;
var x {I} >= 0, <= 10;
var y {I} >= 0, <= 10;
minimize Deviation: sum {i in I} ((x[i] - target[i])^2 + y[i]);
subject to Pick: atmost 2 {i in I} (x[i] >= 1);
subject to Compl {i in I}: 0 <= y[i] complements y[i] - x[i] + 2 >= 0;
"""
def fresh():
ampl = AMPL()
ampl.eval(MODEL)
return ampl
def violated_logic(ampl):
"""Names of logical constraints (atmost, or, ==>, ...) that the returned point violates."""
if ampl.get_value("_nlogcons") == 0:
return []
return [
name
for _, name in ampl.get_data(
"{i in 1.._nlogcons: !_logcon[i].val} _logconname[i]"
).to_list()
]
Where the options go#
mp2nl_optionstakes MP’s options:solver=(the real solver), the reformulation optionscvt:..., the acceptance optionsacc:..., the solution checksol:chk:..., and the genericlim:time,outlev,mip:gap.<solver>_options, e.g.ipopt_options, takes the real solver’s own keywords. An MP keyword placed there is usually rejected by the solver, and the solve fails.lim:timeinmp2nl_optionsis translated into the subsolver’s own time keyword where MP2NL knows it, as the log below shows (“subsolver options …”).
With outlev=1, MP2NL also prints the model before and after reformulation:
here the atmost and the complementarity turn into binary variables and extra
constraints.
ampl = fresh()
ampl.solve(
solver="mp2nl",
mp2nl_options=f"solver={SOLVER_MINLP} outlev=1 lim:time=60",
verbose=True,
)
print(
"\nsolve_result:",
ampl.solve_result,
" objective:",
round(ampl.obj["Deviation"].value(), 4),
" violated logical constraints:",
violated_logic(ampl),
)
[WARNING]
Nonsquare complementarity system:
8 complementarities including 4 equations
12 variables
MP2NL 0.1:
nl:solver = couenne
tech:outlev = 1
lim:time = 60
AMPL MP initial flat model has 12 variables (0 integer, 0 binary);
Objectives: 1 linear;
Constraints: 9 linear;
Algebraic expressions: 1 count; 4 powc;
Logical expressions: 4 conditional (in)equalitie(s); 4 compl;
AMPL MP final model has 51 variables (0 integer, 4 binary);
Objectives: 1 nonlinear;
Constraints: 26 linear; 4 nonlinear;
Algebraic expressions: 16 powc;
MP2NL: subsolver options 'bonmin.time_limit=60'
Couenne 0.5.8 -- an Open-Source solver for Mixed Integer Nonlinear Optimization
Mailing list: [email protected]
Instructions: http://www.coin-or.org/Couenne
couenne: bonmin.time_limit=60
ANALYSIS TEST:
NLP0012I
Num Status Obj It time Location
NLP0014I 1 OPT 2.5000019 52 0.047222
NLP0014I 2 INFEAS 0.99999998 27 0.042061
Loaded instance "<temporary directory>/model.nl"
Constraints: 17
Variables: 51 (4 integer)
Auxiliaries: 29 (0 integer)
Coin0506I Presolve 105 (-5) rows, 36 (-44) columns and 224 (-17) elements
Clp0006I 0 Obj 0 Primal inf 27.428578 (14)
Clp0006I 21 Obj 2
Clp0000I Optimal - objective value 2
Clp0032I Optimal objective 2 - 21 iterations time 0.002, Presolve 0.00
Clp0000I Optimal - objective value 2
NLP Heuristic:
time limit reached.
Clp0000I Optimal - objective value 2
Optimality Based BT:
6 improved bounds
Probing:
0 improved bounds
NLP Heuristic:
Couenne: new cutoff value 1.4001199924e+01 (0.257718 seconds)
solution found, obj. 14.0012
Cbc0012I Integer solution of 14.0012 found by Couenne Rounding NLP after 71 iterations and 0 nodes (0.11 seconds)
Cbc0031I 8 added rows had average density of 2
Cbc0013I At root node, 8 cuts changed objective from 2 to 2.5 in 10 passes
Cbc0014I Cut generator 0 (Couenne convexifier cuts) - 88 row cuts average 2.0 elements, 42 column cuts (42 active)
Cbc0010I After 0 nodes, 1 on tree, 14.0012 best solution, best possible 2.5 (0.11 seconds)
Optimality Based BT:
5 improved bounds
Optimality Based BT:
3 improved bounds
Couenne: new cutoff value 6.7505999739e+00 (0.444657 seconds)
Cbc0012I Integer solution of 6.7506 found by Couenne Rounding NLP after 100 iterations and 2 nodes (0.29 seconds)
Optimality Based BT:
3 improved bounds
Couenne: new cutoff value 3.5679871593e+00 (0.569332 seconds)
Optimality Based BT:
0 improved bounds
Couenne: new cutoff value 3.5202916081e+00 (0.650081 seconds)
Couenne: new cutoff value 3.5058551398e+00 (0.65078 seconds)
Couenne: new cutoff value 3.5002000228e+00 (0.683039 seconds)
Cbc0012I Integer solution of 3.5002 found by Couenne Rounding NLP after 129 iterations and 4 nodes (0.53 seconds)
Cbc0001I Search completed - best objective 3.500200022781402, took 129 iterations and 4 nodes (0.53 seconds)
Cbc0035I Maximum depth 2, 0 variables fixed on reduced cost
"Finished"
Linearization cuts added at root node: 110
Linearization cuts added in total: 110 (separation time: 0.000471s)
Total solve time: 0.533962s (0.533962s in branch-and-bound)
Lower bound: 3.5002
Upper bound: 3.5002 (gap: 0.00%)
Branch-and-bound nodes: 4
Performance of FBBT: 0.001385s, 21 runs. fix: 0 shrnk: 0.0191772 ubd: 0.761905 2ubd: 4 infeas: 0
Performance of OBBT: 0.017184s, 5 runs. fix: 0 shrnk: 6.69393 ubd: 0 2ubd: 4 infeas: 0
MP2NL 0.1:
couenne: Optimal
solve_result: solved objective: 3.5002 violated logical constraints: []
The subsolver must handle the class MP produces#
MP linearizes logic with binary variables. If the subsolver is a continuous NLP
solver, it relaxes them, and the answer can violate the logic, while the
subsolver still reports success. (print_level=0 is an Ipopt keyword, so it goes
into ipopt_options, not mp2nl_options.)
ampl = fresh()
ampl.solve(
solver="mp2nl",
mp2nl_options=f"solver={SOLVER_NLP}",
verbose=True,
**{SOLVER_NLP + "_options": "print_level=0" if SOLVER_NLP == "ipopt" else ""},
)
print(
"\nsolve_result:",
ampl.solve_result,
" objective:",
round(ampl.obj["Deviation"].value(), 4),
" violated logical constraints:",
violated_logic(ampl),
)
[WARNING]
Nonsquare complementarity system:
8 complementarities including 4 equations
12 variables
MP2NL 0.1:
nl:solver = ipopt
Ipopt 3.12.13: print_level=0
==> Warning: Treating 4 binary and 0 integer variables as continous.
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
MP2NL 0.1:
Ipopt 3.12.13: Optimal Solution Found
------------ WARNINGS ------------
WARNING: "Tolerance violations"
Type MaxAbs [Name] MaxRel [Name]
* aux var integrality 4E-01 -
* expr '_compl' - -
* expr '_condlinge' - -
*: Using the solver's aux variable values.
Documentation: mp.ampl.com/modeling-tools.html#automatic-solution-check.
suffix ipopt_zL_out OUT;
suffix ipopt_zU_out OUT;
solve_result: solved objective: 2.5 violated logical constraints: ['Pick']
The status is solved and the objective is better than the MINLP solver’s,
because the point violates Pick. Two things catch it, and both should be routine:
MP’s automatic solution check prints a “Tolerance violations” warning after the solve. MP2NL checks the solution against your original model, not only against the reformulated one.
Reading the violated logical constraints (
violated_logicabove, using AMPL’s_logconset).
So: choose a subsolver for the problem class after reformulation. Logic needs a solver for integer variables; complementarity alone does not.
Complementarity with a continuous NLP solver#
Without the atmost, the model is a mathematical program with complementarity
constraints (MPCC), which a continuous NLP solver can take after reformulation.
cvt:compl selects the reformulation:
|
reformulation of \(a \ge 0,\ b \ge 0,\ a \perp b\) |
|---|---|
0 |
disjunction \(a \le 0 \lor b \le 0\) (needs binaries) |
1 |
product \(a \cdot b = \varepsilon\) |
2 |
Fischer-Burmeister \(\sqrt{a^2+b^2+2\varepsilon} = a+b\) |
3 |
\(\min(a, b) = 0\) |
\(\varepsilon\) is cvt:compl:tol. Each MP2NL subsolver configuration sets a
default that suits the solver; override it to compare.
rows = []
for mode in (1, 2, 3):
ampl = fresh()
ampl.eval("drop Pick;")
ampl.solve(
solver="mp2nl",
verbose=False,
mp2nl_options=f"solver={SOLVER_NLP} cvt:compl={mode} cvt:compl:tol=1e-8",
)
y = ampl.var["y"].to_dict()
slack = {i: y[i] - ampl.var["x"][i].value() + 2 for i in y}
rows.append(
dict(
cvt_compl=mode,
status=ampl.solve_result,
objective=round(ampl.obj["Deviation"].value(), 6),
max_violation=max(min(y[i], slack[i]) for i in y),
)
)
pd.DataFrame(rows).set_index("cvt_compl")
| status | objective | max_violation | |
|---|---|---|---|
| cvt_compl | |||
| 1 | solved | 2.500009 | 0.000006 |
| 2 | solved | 2.500009 | 0.000006 |
| 3 | failure | 30.000000 | 0.000000 |
max_violation is \(\max_i \min(y_i, \text{slack}_i)\), which is zero when every
pair is complementary. The reformulations behave differently: \(\min(a,b) = 0\)
is nonsmooth, and a smooth local solver can fail on it, as here, while the
product and Fischer-Burmeister forms reach the same point. Compare them on your
model rather than relying on one.
AMPL’s warning “Nonsquare complementarity system” at each solve is expected here: the model has an objective, so it is an optimization problem with complementarity constraints, not a square complementarity system.
What else to know#
See the subsolver’s configuration:
mp2nl_options="printconfigs"lists, per known subsolver, which constructs MP2NL linearizes for it. If your solver binary has another name, pick a configuration withconfig=<name>.Keep the reformulated NL file:
stub=<path>writes it as<path>.nl, useful for inspecting what the subsolver received or for a support request.Statuses come from the subsolver. A local solver’s
solvedon a nonconvex model means locally optimal. Check the solution-check warnings and, where it matters, compare with a global solver.
Related notebooks: https://colab.ampl.com/tags/mp2nl.html.