"""``BilevelMethod`` -- "bilevel solution".
- Implements the method of Turan, Moret & Bardow, "ORACLE: A rigorous
metric and method to explore all near-optimal designs for energy
systems", Computers & Chemical Engineering (2026).
- Only ``norm='linf'`` is supported; L1/L2 aren't implemented (use
:class:`~mga_surveyor.methods.cdd.CddMethod` instead).
- Requires ``gurobipy`` and a Gurobi license; no open-source backend.
- Reformulates the max-min bilevel LP into a single-level MILP via KKT +
Big-M (Fortuny-Amat/McCarl) linearization of the complementarity
conditions.
"""
import numpy as np
try:
import gurobipy as gp
from gurobipy import GRB
except ImportError:
gp = None
GRB = None
from ..common import Halfspace, Norm, check_norm
from .base import Method
[docs]
def compute_safe_big_m(
A_O: np.ndarray, b_O: np.ndarray, inner_points: np.ndarray, margin: float = 1.0,
) -> tuple[float, float]:
"""Derive provably-valid ``(M_P, M_D)`` directly from this problem's own
data, instead of guessing fixed constants -- see
:func:`solve_farthest_outer_point_milp`'s own docstring for what each
bounds. Both constants follow from the KKT system's own structure:
- ``M_P`` bounds ``w[i]`` and the two slacks
``slack_plus[j] = t - zO[j] + (Iw)[j]``,
``slack_minus[j] = t + zO[j] - (Iw)[j]``. ``w[i] <= 1`` always
(convex weights). For the slacks: let ``lo[j]``/``hi[j]`` be the min/
max of ``zO[j]`` over ``O`` (found here via ``2*nz`` tiny LPs on
``A_O``/``b_O``), and ``L[j]``/``U[j]`` the min/max of
``inner_points[:, j]`` (a plain array reduction -- any convex
combination's ``j``-th coordinate is provably within
``[L[j], U[j]]``). Then ``t* = max_zO min_w ||zO - Iw||_inf <= T_MAX
:= max_j max(hi[j]-L[j], U[j]-lo[j])`` (how far ``O`` can possibly
get from ``conv(inner_points)`` on any single axis), and each slack
is at most ``t* + T_MAX <= 2*T_MAX``.
- ``M_D`` bounds ``a_plus[j]``, ``a_minus[j]``, ``b_dual[i]``. The
stationarity constraint ``sum(a_plus[j]+a_minus[j]) == 1`` (all
terms >= 0) already forces ``a_plus[j] <= 1`` and ``a_minus[j] <=
1`` on its own. At the complementary-slackness-active ``i`` (some
``w[i] > 0`` always exists, and ``b_dual[i] = 0`` there), the
stationarity-in-``w`` equation pins ``eta`` to
``sum_j inner_points[i,j]*(a_plus[j]-a_minus[j])``, bounded by
``R_IN := max_{i,j} |inner_points[i,j]|`` since the ``a`` terms sum
to 1 in absolute value. Propagating back through that same equation
for every ``i`` gives ``b_dual[i] <= 2*R_IN``.
Both are LOWER bounds on what's actually needed (exact at the true
optimum) -- ``margin`` (default ``1.0``, i.e. no slack) inflates them
for extra numerical headroom at the cost of a proportionally weaker
relaxation; pass e.g. ``1.05`` if solves ever come back infeasible due
to floating-point roundoff at the boundary.
:param A_O: Outer polytope constraint matrix, with ``O`` given by
``A_O @ z <= b_O``.
:param b_O: Outer polytope right-hand side.
:param inner_points: Points whose convex hull is the inner
approximation.
:param margin: Multiplicative safety factor applied to both bounds.
:returns: ``(M_P, M_D)``, ready to pass straight into
:func:`solve_farthest_outer_point_milp`/:class:`BilevelMethod`.
:rtype: tuple
:raises ImportError: If ``gurobipy`` is not installed.
"""
if gp is None:
raise ImportError(
"compute_safe_big_m requires the `gurobipy` package and a valid "
"Gurobi license, same as solve_farthest_outer_point_milp itself."
)
inner_points = np.asarray(inner_points, dtype=float)
nz = inner_points.shape[1]
L = inner_points.min(axis=0)
U = inner_points.max(axis=0)
R_IN = float(np.max(np.abs(inner_points)))
box_model = gp.Model()
box_model.Params.OutputFlag = 0
z = box_model.addVars(nz, lb=-GRB.INFINITY, name="z")
for r in range(A_O.shape[0]):
box_model.addConstr(gp.quicksum(A_O[r, j] * z[j] for j in range(nz)) <= b_O[r])
lo = np.empty(nz)
hi = np.empty(nz)
for j in range(nz):
box_model.setObjective(z[j], GRB.MAXIMIZE)
box_model.optimize()
hi[j] = z[j].X
box_model.setObjective(z[j], GRB.MINIMIZE)
box_model.optimize()
lo[j] = z[j].X
t_max = float(np.max(np.maximum(hi - L, U - lo)))
M_P = max(1.0, 2.0 * t_max) * margin
M_D = max(1.0, 2.0 * R_IN) * margin
return M_P, M_D
[docs]
def solve_farthest_outer_point_milp(
A_O: np.ndarray, b_O: np.ndarray, inner_points: np.ndarray, time_limit: float | None,
M_P: float | None = None, M_D: float | None = None, verbose: bool = False,
diagnostics: dict | None = None,
mip_gap: float = 1e-7, mip_gap_abs: float | None = None,
) -> tuple[np.ndarray, float, np.ndarray]:
"""Solve ``max_{zO in O} min_{zI in conv(inner_points)} ||zO - zI||_inf``
via the KKT-based single-level MILP reformulation. ``O`` is given as
``A_O @ z <= b_O``.
:param A_O: Outer polytope constraint matrix, with ``O`` given by
``A_O @ z <= b_O``.
:param b_O: Outer polytope right-hand side, with ``O`` given by
``A_O @ z <= b_O``.
:param inner_points: Points whose convex hull is the inner
approximation.
:param time_limit: Seconds, forwarded to Gurobi's own ``TimeLimit``
param -- no default, an explicit choice is required every call
(``None`` for unbounded/exact-only, matching the original
behavior before this parameter existed). ``None`` requires
``GRB.OPTIMAL``, raising on anything else. When set, a solve
that hits the time limit with at least one feasible incumbent
(``GRB.TIME_LIMIT``, ``model.SolCount > 0``) is ALSO accepted --
the returned ``t_star`` is then a valid lower bound on the true
max-min distance, not necessarily the exact value (the Big-M
reformulation's usual exactness caveat, now compounded by not
having actually proven optimality either). Pass ``diagnostics``
to tell which case happened. A time-limited solve with NO
incumbent at all still raises, same as any other failure status.
:param M_P: Big-M constant bounding the primal solution
(Fortuny-Amat/McCarl linearization of the complementarity
conditions); must be a valid (large enough) bound for the specific
problem, or the reformulation is not exact -- there is no automatic
way to check this from inside the MILP itself. ``None`` (default)
computes a provably-valid bound via :func:`compute_safe_big_m` on
this exact call's own ``A_O``/``b_O``/``inner_points`` instead of
guessing a fixed constant.
:param M_D: Big-M constant bounding the dual solution; same caveat --
and same ``None`` default -- as ``M_P``.
:param verbose: If True, let Gurobi print its own solve log.
:param diagnostics: If given, populated in place with ``solve_time``,
``status`` (Gurobi's own status code), ``is_optimal`` (``True``
only for ``GRB.OPTIMAL``), ``mip_gap`` (``model.MIPGap`` --
meaningless/``inf``-ish if no incumbent, which can't happen here
since that case raises instead), and ``node_count``. Doesn't
change the return value; purely for a caller that wants to log
solve quality without re-deriving it.
:param mip_gap: Forwarded to Gurobi's own ``MIPGap`` (relative
optimality gap) convergence parameter.
:param mip_gap_abs: Forwarded to Gurobi's own ``MIPGapAbs`` (absolute
optimality gap) convergence parameter. ``None`` (default) leaves
Gurobi's own default in place -- unlike ``mip_gap``, this isn't
set unconditionally, since ``0`` is itself a meaningful value
(require an EXACT proof, not just within some absolute tolerance)
that shouldn't be silently equivalent to "unset".
:returns: ``(z_O_star, t_star, w_star)`` -- the worst point, the max-min
L_inf distance (exact iff ``diagnostics["is_optimal"]``, when
given), and the convex-combination weights of its closest inner
point (``z_I_star = w_star @ inner_points``).
:rtype: tuple
:raises ImportError: If ``gurobipy`` is not installed.
:raises RuntimeError: If the solve ends in any status other than
``GRB.OPTIMAL``, or (only when ``time_limit`` is set)
``GRB.TIME_LIMIT`` with at least one feasible incumbent.
"""
if gp is None:
raise ImportError(
"BilevelMethod requires the `gurobipy` package and a valid "
"Gurobi license -- its MILP reformulation is Gurobi-specific, with no "
"backend option (unlike CddMethod's own projection_backend; see module "
"docstring). Install gurobipy, or use CddMethod instead "
"(projection_backend='highs' needs no Gurobi at all, for norm in "
"('l1', 'linf'))."
)
inner_points = np.asarray(inner_points, dtype=float)
m, nz = inner_points.shape
n_rows = A_O.shape[0]
if M_P is None or M_D is None:
computed_M_P, computed_M_D = compute_safe_big_m(A_O, b_O, inner_points)
if M_P is None:
M_P = computed_M_P
if M_D is None:
M_D = computed_M_D
model = gp.Model()
if not verbose:
model.Params.OutputFlag = 0
model.Params.MIPGap = mip_gap
if mip_gap_abs is not None:
model.Params.MIPGapAbs = mip_gap_abs
if time_limit is not None:
model.Params.TimeLimit = time_limit
zO = model.addVars(nz, lb=-GRB.INFINITY, name="zO")
t = model.addVar(lb=0.0, name="t")
w = model.addVars(m, lb=0.0, name="w")
a_plus = model.addVars(nz, lb=0.0, name="a_plus")
a_minus = model.addVars(nz, lb=0.0, name="a_minus")
b_dual = model.addVars(m, lb=0.0, name="b_dual")
eta = model.addVar(lb=-GRB.INFINITY, name="eta")
u_plus = model.addVars(nz, vtype=GRB.BINARY, name="u_plus")
u_minus = model.addVars(nz, vtype=GRB.BINARY, name="u_minus")
v_bin = model.addVars(m, vtype=GRB.BINARY, name="v")
for r in range(n_rows):
model.addConstr(gp.quicksum(A_O[r, j] * zO[j] for j in range(nz)) <= b_O[r])
slack_plus, slack_minus = {}, {}
for j in range(nz):
model.addConstr(zO[j] - gp.quicksum(inner_points[i, j] * w[i] for i in range(m)) - t <= 0)
slack_plus[j] = t - zO[j] + gp.quicksum(inner_points[i, j] * w[i] for i in range(m))
model.addConstr(-zO[j] + gp.quicksum(inner_points[i, j] * w[i] for i in range(m)) - t <= 0)
slack_minus[j] = t + zO[j] - gp.quicksum(inner_points[i, j] * w[i] for i in range(m))
model.addConstr(gp.quicksum(w[i] for i in range(m)) == 1, name="sum_to_one")
model.addConstr(gp.quicksum(a_plus[j] + a_minus[j] for j in range(nz)) == 1, name="stat_t")
for i in range(m):
model.addConstr(
eta - b_dual[i] - gp.quicksum(inner_points[i, j] * (a_plus[j] - a_minus[j]) for j in range(nz)) == 0,
name=f"stat_w_{i}",
)
for j in range(nz):
model.addConstr(a_plus[j] <= u_plus[j] * M_D)
model.addConstr(slack_plus[j] <= (1 - u_plus[j]) * M_P)
model.addConstr(a_minus[j] <= u_minus[j] * M_D)
model.addConstr(slack_minus[j] <= (1 - u_minus[j]) * M_P)
for i in range(m):
model.addConstr(b_dual[i] <= v_bin[i] * M_D)
model.addConstr(w[i] <= (1 - v_bin[i]) * M_P)
# tightening from Caratheodory + L_inf structure (optional but cheap)
model.addConstr(gp.quicksum(1 - v_bin[i] for i in range(m)) <= nz + 1)
model.addConstr(gp.quicksum(1 - v_bin[i] for i in range(m)) >= 1)
model.addConstr(gp.quicksum(u_plus[j] + u_minus[j] for j in range(nz)) >= 1)
model.addConstr(gp.quicksum(u_plus[j] + u_minus[j] for j in range(nz)) <= nz)
model.setObjective(t, GRB.MAXIMIZE)
model.optimize()
timed_out_with_incumbent = (
time_limit is not None and model.Status == GRB.TIME_LIMIT and model.SolCount > 0
)
if model.Status != GRB.OPTIMAL and not timed_out_with_incumbent:
raise RuntimeError(f"MILP failed: status {model.Status}")
if diagnostics is not None:
diagnostics["solve_time"] = model.Runtime # Gurobi's own wall-clock solve time, no need to time it ourselves
diagnostics["status"] = model.Status
diagnostics["is_optimal"] = model.Status == GRB.OPTIMAL
diagnostics["mip_gap"] = model.MIPGap
diagnostics["node_count"] = model.NodeCount
z_O_star = np.array([zO[j].X for j in range(nz)])
t_star = t.X
w_star = np.array([w[i].X for i in range(m)])
return z_O_star, t_star, w_star
[docs]
class BilevelMethod(Method):
"""See module docstring.
:param k: Dimension of the exploratory variables.
:param norm: Must be ``'linf'`` -- see module docstring for why.
:type norm: str
:param time_limit: Forwarded to :func:`solve_farthest_outer_point_milp`
on every call -- see its own docstring. No default -- an explicit
choice is required (``None`` for unbounded/exact-only, matching
the original behavior before this parameter existed); set a real
limit to accept a possibly-non-exact (but time-bounded) gap
instead of risking an unboundedly long single solve -- see
:attr:`stats`' ``is_optimal`` for whether a given call's result
was actually exact.
:param M_P: Big-M primal bound, forwarded to
:func:`solve_farthest_outer_point_milp` on every call -- ``None``
(default) computes a fresh, provably-valid bound via
:func:`compute_safe_big_m` on every solve instead of a fixed
constant (cheap relative to the MILP solve itself -- see that
function's own docstring).
:param M_D: Big-M dual bound, forwarded to
:func:`solve_farthest_outer_point_milp` on every call -- same
``None`` default as ``M_P``.
:param verbose: If True, let Gurobi print its own solve log.
:param mip_gap: Forwarded to :func:`solve_farthest_outer_point_milp`
on every call -- see its own docstring.
:param mip_gap_abs: Forwarded to :func:`solve_farthest_outer_point_milp`
on every call -- see its own docstring.
:raises NotImplementedError: If ``norm`` is not ``'linf'``.
"""
def __init__(
self, k: int, norm: Norm, time_limit: float | None,
M_P: float | None = None, M_D: float | None = None, verbose: bool = False,
mip_gap: float = 1e-7, mip_gap_abs: float | None = None,
) -> None:
check_norm(norm)
if norm != "linf":
raise NotImplementedError(
"BilevelMethod only supports norm='linf' -- L1/L2 would each need a "
"different reformulation, not implemented. "
"Use CddMethod or BBMethod for other norms."
)
super().__init__(k, norm)
self.M_P = M_P
self.M_D = M_D
self.verbose = verbose
self.time_limit = time_limit
self.mip_gap = mip_gap
self.mip_gap_abs = mip_gap_abs
self.inner_vertices = None
self.outer_halfspaces = []
self._dirty = True
self._trial_point = None
self._gap = 0.0
self.stats: dict[str, float | int | bool | None] = {}
self.reset_stats()
[docs]
def reset_stats(self) -> None:
"""Zero :attr:`stats` -- mirrors :meth:`CddMethod.reset_stats`'s
role for a caller that wants to scope solve diagnostics to one
logical iteration, though here there's at most one solve per
:meth:`find_trial_point`/:meth:`max_gap` call to begin with (no
cross-call accumulation needed), so this just resets to defaults.
Populated from :func:`solve_farthest_outer_point_milp`'s own
``diagnostics`` out-param after any call that actually solved
(an unchanged/no-op ``find_trial_point`` call, or one with no
halfspaces yet, leaves the previous values in place instead of
clearing them).
"""
self.stats = {
"solve_time": 0.0,
"status": None,
"is_optimal": None,
"mip_gap": None,
"node_count": None,
}
[docs]
def bootstrap(self, initial_points: list[np.ndarray], initial_halfspaces: list[Halfspace]) -> None:
self.inner_vertices = np.array(initial_points, dtype=float)
self.outer_halfspaces = list(initial_halfspaces)
self._dirty = True
[docs]
def add_point(self, point: np.ndarray) -> bool:
point = np.asarray(point, dtype=float)
is_new = np.linalg.norm(self.inner_vertices - point, axis=1).min() > 1e-6
if is_new:
self.inner_vertices = np.vstack([self.inner_vertices, point])
self._dirty = True
return is_new
[docs]
def add_cut(self, direction: np.ndarray, point: np.ndarray) -> None:
direction = np.asarray(direction, dtype=float)
point = np.asarray(point, dtype=float)
self.outer_halfspaces = self.outer_halfspaces + [(direction, point)]
self._dirty = True
def _matrices(self) -> tuple[np.ndarray, np.ndarray]:
"""Assemble ``(A_O, b_O)`` from ``self.outer_halfspaces`` for
:func:`solve_farthest_outer_point_milp`.
:returns: ``(A_O, b_O)`` such that ``O`` is ``A_O @ z <= b_O``.
:rtype: tuple
"""
A_O = np.array([direction for direction, _ in self.outer_halfspaces])
b_O = np.array([direction @ point for direction, point in self.outer_halfspaces])
return A_O, b_O
[docs]
def find_trial_point(self) -> tuple[np.ndarray | None, float]:
"""Cached: recomputes only if ``self._dirty`` is set (by
:meth:`bootstrap`, :meth:`add_point`, or :meth:`add_cut` since the
last call); a repeat call in between -- notably from
:meth:`max_gap` -- skips the MILP solve and reuses the cached
result.
"""
if not self._dirty:
return self._trial_point, self._gap
if not self.outer_halfspaces:
self._trial_point, self._gap = None, 0.0
else:
A_O, b_O = self._matrices()
diagnostics = {}
z_O_star, t_star, _w_star = solve_farthest_outer_point_milp(
A_O, b_O, self.inner_vertices, M_P=self.M_P, M_D=self.M_D, verbose=self.verbose,
time_limit=self.time_limit, diagnostics=diagnostics,
mip_gap=self.mip_gap, mip_gap_abs=self.mip_gap_abs,
)
self.stats.update(diagnostics)
self._trial_point, self._gap = z_O_star, float(t_star)
self._dirty = False
return self._trial_point, self._gap
[docs]
def max_gap(self) -> float:
_point, gap = self.find_trial_point()
return gap