GDP Algorithms: LOA, GLOA, RIC, Enumerate, LBB and LD-SDA

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

gdp_method

algorithm

what it certifies

"loa"

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

"gloa"

global logic-based OA [Lee and Grossmann, 2001]

a global optimum (cuts come from discopt’s relaxations, valid on the disjunct’s box)

"ric"

relaxation with integer cuts

a global optimum (the master is a relaxation for any model)

"enumerate"

every configuration, each solved globally

a global optimum, once every configuration is certified

"lbb"

logic-based branch and bound [Lee and Grossmann, 2000]

a global optimum

"ldsda"

logic-based discrete-steepest descent [Ovalle et al., 2025]

nothing: a local method; never reports optimal

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-m and the five global algorithms certify 4.460368, and each bound is one a solver proved.

  • hull does not certify within 60 s. Its node NLPs break down on the perspective of the exp rows, and the last section shows the fix.

  • ldsda finds the optimum but reports feasible with no bound. It is a local method.

  • loa certifies 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

DISCOPT_GDP_BOUND_PRETRANSFORM

big-M / mbigm: a SELECT_ONE disjunction’s univariate bounds become sum_k L_k y_k <= x <= sum_k U_k y_k

DISCOPT_GDP_ENUMERATE_CUTOFF

enumerate: each configuration is bounded against the incumbent before its NLP is solved

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 ldsda is a global method with a stated certificate rule. Each publishes a bound only when it has proved one, and optimal only when nothing is left unresolved.

  • gdp_options follows 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).