MP2NL: logical and complementarity constraints with any NL solver#

mp2nl_logic_and_complementarity.ipynb Open In Colab Open In Deepnote Open In Kaggle Open In Gradient Open In SageMaker Studio Lab Powered by AMPL

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:

  1. MP modeling guide, Meta-driver MP2NL: https://mp.ampl.com/modeling-tools.html#meta-driver-mp2nl

  2. 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_options takes MP’s options: solver= (the real solver), the reformulation options cvt:..., the acceptance options acc:..., the solution check sol:chk:..., and the generic lim: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:time in mp2nl_options is 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:

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

  2. Reading the violated logical constraints (violated_logic above, using AMPL’s _logcon set).

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:

cvt:compl

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 with config=<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 solved on 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.