GDP Algorithms: LOA, GLOA, RIC, Enumerate, LBB and LD-SDA#
The GDP tutorial solves a disjunctive model by reformulating it, with big-M, hull or multiple big-M, and handing the result to discopt’s branch and bound. This notebook covers the other family: algorithms that keep the disjunctions and work on them directly, the logic-based methods of Pyomo’s GDPopt [Chen et al., 2022], built on discopt’s own global solver [Grossmann, 2002].
|
algorithm |
what it certifies |
|---|---|---|
|
logic-based outer approximation [Türkay and Grossmann, 1996] |
a global optimum when every row that receives OA cuts, and the objective, are certified convex |
|
global logic-based OA [Lee and Grossmann, 2001] |
a global optimum (cuts come from discopt’s relaxations, valid on the disjunct’s box) |
|
relaxation with integer cuts |
a global optimum (the master is a relaxation for any model) |
|
every configuration, each solved globally |
a global optimum, once every configuration is certified |
|
logic-based branch and bound [Lee and Grossmann, 2000] |
a global optimum |
|
logic-based discrete-steepest descent [Ovalle et al., 2025] |
nothing: a local method; never reports |
Every algorithm verifies its incumbent against the declared GDP, so a point is never reported unless it satisfies the original disjunctions.
import time
import warnings
import discopt.modeling as dm
from discopt.solver_tuning import SolverTuning
warnings.simplefilter("ignore", UserWarning)
A small nonconvex GDP#
Trespalacios’ analytical example [Trespalacios and Grossmann, 2015]: two disjunctions with two disjuncts
each, nonconvex rows (exp, a shifted quadratic, a reciprocal), optimum 4.46 at
\((x_1, x_2) = (1.467, 0.833)\).
def trespalacios():
m = dm.Model("ex_633")
x1 = m.continuous("x1", lb=0, ub=5)
x2 = m.continuous("x2", lb=0, ub=3)
m.minimize(5 + 0.2 * x1 - x2)
m.either_or(
[
[x2 <= 0.4 * dm.exp(x1 / 2.0), x2 <= 0.5 * (x1 - 2.5) ** 2 + 0.3,
x2 <= 6.5 / (x1 / 0.3 + 2.0) + 1.0],
[x2 <= 0.3 * dm.exp(x1 / 1.8), x2 <= 0.7 * (x1 / 1.2 - 2.1) ** 2 + 0.3,
x2 <= 6.5 / (x1 / 0.8 + 1.1)],
],
name="d1",
)
m.either_or(
[
[x2 <= 0.9 * dm.exp(x1 / 2.1), x2 <= 1.3 * (x1 / 1.5 - 1.8) ** 2 + 0.3,
x2 <= 6.5 / (x1 / 0.8 + 1.1)],
[x2 <= 0.4 * dm.exp(x1 / 1.5), x2 <= 1.2 * (x1 - 2.5) ** 2 + 0.3,
x2 <= 6.0 / (x1 / 0.6 + 1.0) + 0.5],
],
name="d2",
)
return m
def report(method, r, wall):
bound = "-" if r.bound is None else f"{r.bound:.6f}"
obj = "-" if r.objective is None else f"{r.objective:.6f}"
print(f"{method:10s} {r.status:9s} objective {obj:>10s} bound {bound:>10s} {wall:5.1f} s")
for method in ["big-m", "hull", "loa", "gloa", "ric", "enumerate", "lbb", "ldsda"]:
t = time.perf_counter()
r = trespalacios().solve(gdp_method=method, time_limit=60)
report(method, r, time.perf_counter() - t)
big-m optimal objective 4.460368 bound 4.460096 1.4 s
/Users/jkitchin/projects/discopt/python/discopt/_relax/gdp_reformulate.py:2087: RuntimeWarning: overflow encountered in exp
hi = np.exp(arg_hi) if np.isfinite(arg_hi) else np.inf
INFO pounce_algorithm::conv_check::opt_error: certifying with a dual infeasibility above dual_inf_tol: it is within the scale-relative floor set by the terms the Lagrangian gradient is built from (dual_inf_scale_kappa=0 disables) dual_inf=948510.75 dual_scale=382376211734796.25 dual_inf_tol=1.0 bound=3823762.1173479627
INFO pounce::linesearch: theta_max raised 2.759e6 -> 2.759e8 (raise 1 of 4): 3 consecutive line searches had every trial rejected at the theta_max gate (pounce#546)
INFO pounce::linesearch: theta_max raised 2.759e6 -> 2.759e8 (raise 1 of 4): 3 consecutive line searches had every trial rejected at the theta_max gate (pounce#546)
INFO pounce::linesearch: theta_max raised 2.759e6 -> 2.759e8 (raise 1 of 4): 3 consecutive line searches had every trial rejected at the theta_max gate (pounce#546)
INFO pounce::linesearch: theta_max raised 2.759e6 -> 2.759e8 (raise 1 of 4): 3 consecutive line searches had every trial rejected at the theta_max gate (pounce#546)
INFO pounce_algorithm::conv_check::opt_error: certifying with a dual infeasibility above dual_inf_tol: it is within the scale-relative floor set by the terms the Lagrangian gradient is built from (dual_inf_scale_kappa=0 disables) dual_inf=948510.75 dual_scale=382376211734796.25 dual_inf_tol=1.0 bound=3823762.1173479627
INFO pounce::linesearch: theta_max raised 4.510e4 -> 4.510e6 (raise 1 of 4): 3 consecutive line searches had every trial rejected at the theta_max gate (pounce#546)
INFO pounce::linesearch: theta_max raised 1.803e7 -> 1.803e9 (raise 1 of 4): 3 consecutive line searches had every trial rejected at the theta_max gate (pounce#546)
INFO pounce::linesearch: theta_max raised 1.803e9 -> 1.803e11 (raise 2 of 4): 3 consecutive line searches had every trial rejected at the theta_max gate (pounce#546)
INFO pounce::linesearch: theta_max raised 1.803e7 -> 1.803e9 (raise 1 of 4): 3 consecutive line searches had every trial rejected at the theta_max gate (pounce#546)
INFO pounce::linesearch: theta_max raised 1.803e9 -> 1.803e11 (raise 2 of 4): 3 consecutive line searches had every trial rejected at the theta_max gate (pounce#546)
INFO pounce::linesearch: theta_max raised 1.803e11 -> 1.803e13 (raise 3 of 4): 3 consecutive line searches had every trial rejected at the theta_max gate (pounce#546)
hull optimal objective 4.460368 bound 4.460055 30.8 s
loa optimal objective 4.460368 bound 4.460368 0.7 s
gloa optimal objective 4.460368 bound 4.460368 0.7 s
ric optimal objective 4.460368 bound 4.460368 0.6 s
enumerate optimal objective 4.460368 bound 4.460144 7.2 s
No valid dual bound was produced for model 'ex_633': the relaxation layer could not bound this objective (status=feasible). The result cannot be certified globally optimal. A nonlinear term with no envelope is the usual cause; an epigraph reformulation (minimize z subject to f(x) <= z) often gives the relaxation something to bound.
lbb optimal objective 4.460368 bound 4.460368 0.6 s
ldsda feasible objective 4.460368 bound - 0.0 s
Read the table row by row:
big-mand the five global algorithms certify 4.460368, and each bound is one a solver proved.hulldoes not certify within 60 s. Its node NLPs break down on the perspective of theexprows, and the last section shows the fix.ldsdafinds the optimum but reportsfeasiblewith no bound. It is a local method.loacertifies even though the rows are not convex. Its outer approximation is not a relaxation here, so its master bound is not used. Instead each configuration’s subproblem is solved globally (subproblem="global", the default) and leaves the master once it is proved.
An algorithm that has proved nothing reports no bound.
Options#
gdp_options takes Pyomo GDPopt’s names where the meaning is the same (iterlim,
init_algorithm, set_cover_iterlim, check_sat, …) plus discopt’s own
(subproblem, subproblem_time_limit, max_configurations). An unknown key is refused,
and so is a known key the chosen method does not read: it is never silently ignored.
r = trespalacios().solve(
gdp_method="loa",
gdp_options={"init_algorithm": "set_covering", "subproblem_time_limit": 5.0},
time_limit=60,
)
print(r.status, r.objective, r.solver_stats["iterations"], "iterations")
try:
trespalacios().solve(gdp_method="enumerate", gdp_options={"init_algorithm": "set_covering"})
except ValueError as exc:
print("refused:", str(exc)[:120], "...")
optimal 4.460367630368564 3 iterations
refused: gdp_method='enumerate' does not read gdp_options ['init_algorithm'] yet; it reads ['max_configurations']. ...
enumerate counts the configurations that survive logic propagation before solving
anything, and refuses above max_configurations (default 104) instead of
truncating. A truncated enumeration would be a heuristic that looks like a proof.
try:
trespalacios().solve(gdp_method="enumerate", gdp_options={"max_configurations": 2})
except ValueError as exc:
print("refused:", str(exc)[:160], "...")
refused: enumerate: the GDP has more than max_configurations=2 configurations (4 before logic propagation); raise the limit or use gdp_method='ric', 'gloa' or 'loa' (enu ...
Flags that passed or failed their panels#
Changes that alter bounds or formulations ship off until a corpus-wide panel shows they are
both sound and net-positive. Each is a field of SolverTuning, and so an environment variable,
and can be switched per solve with tuning=.
Two GDP flags passed their panels and are now on by default; set either to 0 to restore the
previous route:
flag |
what it does |
|---|---|
|
big-M / mbigm: a SELECT_ONE disjunction’s univariate bounds become |
|
|
DISCOPT_HULL_CONIC_QUADRATIC (hull: a convex quadratic disjunct lowered as a rotated cone)
remains opt-in.
Summary#
Reformulations (
big-m,hull,mbigm, …) turn the GDP into a MINLP; the algorithms above keep its logic and solve configurations.Every one but
ldsdais a global method with a stated certificate rule. Each publishes a bound only when it has proved one, andoptimalonly when nothing is left unresolved.gdp_optionsfollows Pyomo’s GDPopt names and refuses what it does not read.The default-off flags are where discopt is still being measured against Pyomo.GDP (#1917).