Source code for mga_surveyor.gurobi_projection

"""Gurobi (via gurobipy) implementation of the closest-point-on-hull
projection query -- `(point, points, norm) -> (c, normal)` -- the one
solver-backed operation `common.py` deliberately does not contain. Peer
module to `highs_projection.py`: same contract, different backend. Use this
one for all three norms, including L2 (a quadratic objective, which HiGHS
cannot solve); use `highs_projection.closest_point_on_hull` for an
open-source, license-free alternative when your norm is 'l1' or 'linf'.

`gurobipy` is imported at module import time but optionally (`gp = None`
if it isn't installed, raising only on first use), and the licensed Gurobi
environment is opened lazily, on the first call to `closest_point_on_hull`
-- so `import mga_surveyor` (and picking `projection_backend='highs'`
throughout) never requires gurobipy, nor pays for a Gurobi environment it's
never going to use.
"""
import threading

import numpy as np

from .common import Norm, check_norm

try:
    import gurobipy as gp
    from gurobipy import GRB
except ImportError:
    gp = None
    GRB = None

_thread_local = threading.local()
_gurobi_env = None
_gurobi_env_lock = threading.Lock()


def _require_gurobipy():
    if gp is None:
        raise ImportError(
            "projection_backend='gurobi' requires the `gurobipy` package and a valid "
            "Gurobi license, neither of which is available here (pip install "
            "gurobipy). Use projection_backend='highs' instead for a free, open-source "
            "alternative -- supports norm in ('l1', 'linf') only, see "
            "highs_projection.closest_point_on_hull."
        )


def _get_gurobi_env():
    global _gurobi_env
    if _gurobi_env is None:
        with _gurobi_env_lock:
            if _gurobi_env is None:
                env = gp.Env(empty=True)
                env.setParam("OutputFlag", 0)
                env.start()
                _gurobi_env = env
    return _gurobi_env


[docs] def closest_point_on_hull(point: np.ndarray, points: np.ndarray, norm: Norm) -> tuple[np.ndarray, np.ndarray]: """Project `point` onto conv(points) under `norm` ('l1', 'l2', or 'linf'), formulated as a convex combination of `points` -- no ConvexHull/facet enumeration needed, so this scales to the point counts that accumulate over an exploration run. Solved with a persistent, per-(thread, norm) Gurobi model built once and only ever updated: the query point enters only via the RHS of k residual constraints (O(k) per query), and new inner points are folded in with O(k) work each via `gp.Column` rather than a full rebuild. That reuse assumes every call from one thread passes the same growing `points` array (new rows only appended), as one Method's own executor does; a different point set in the same thread would silently reuse the old columns. `Threads=1` since many of these are typically solved concurrently from a thread pool -- letting each individual model also spawn worker threads would oversubscribe the machine. Returns `(c, normal)`: - `c`: the closest point itself. - `normal`: a valid separating-hyperplane normal at `c`, i.e. every point `x` in the hull satisfies `normal @ (x - c) <= 0`, taken from the (sign-corrected) dual values of the residual constraints. For L2 this is `2 * (point - c)` -- the residual's direction, scaled by the squared objective's gradient (L2 is self-dual); for L1/Linf the residual is *not* generally a valid normal, so the dual is required in general -- using the dual uniformly is what makes this function correct for all three norms with one code path. """ _require_gurobipy() check_norm(norm) point = np.asarray(point, dtype=float) points = np.asarray(points, dtype=float) m_target, k = points.shape attr = f"qp_state_{norm}" state = getattr(_thread_local, attr, None) if state is None: model = gp.Model(env=_get_gurobi_env()) model.Params.OutputFlag = 0 model.Params.OptimalityTol = 1e-9 model.Params.FeasibilityTol = 1e-9 model.Params.NumericFocus = 3 model.Params.Threads = 1 sum_constr = model.addConstr(gp.LinExpr() == 1.0, name="sum_to_one") r_vars = [model.addVar(lb=-GRB.INFINITY, name=f"r{j}") for j in range(k)] resid_constrs = [model.addConstr(r_vars[j] == 0.0, name=f"resid{j}") for j in range(k)] if norm == "l2": model.Params.BarConvTol = 1e-12 model.setObjective(gp.quicksum(r_vars[j] * r_vars[j] for j in range(k)), GRB.MINIMIZE) elif norm == "l1": s_vars = [model.addVar(lb=0.0, name=f"s{j}") for j in range(k)] for j in range(k): model.addConstr(s_vars[j] >= r_vars[j]) model.addConstr(s_vars[j] >= -r_vars[j]) model.setObjective(gp.quicksum(s_vars), GRB.MINIMIZE) else: # linf t_var = model.addVar(lb=0.0, name="t") for j in range(k): model.addConstr(t_var >= r_vars[j]) model.addConstr(t_var >= -r_vars[j]) model.setObjective(t_var, GRB.MINIMIZE) model.update() state = { "model": model, "w_vars": [], "sum_constr": sum_constr, "resid_constrs": resid_constrs, "m_known": 0, } setattr(_thread_local, attr, state) model = state["model"] w_vars = state["w_vars"] sum_constr = state["sum_constr"] resid_constrs = state["resid_constrs"] m_known = state["m_known"] if m_target > m_known: new_points = points[m_known:m_target] for offset, p_new in enumerate(new_points): col = gp.Column([1.0], [sum_constr]) var = model.addVar(lb=0.0, column=col, name=f"w{m_known + offset}") model.update() for j in range(k): model.chgCoeff(resid_constrs[j], var, -float(p_new[j])) w_vars.append(var) state["m_known"] = m_target model.update() # bulk RHS update -- one C API call for all k constraints, instead of # k individual .RHS = ... assignments (see project notes: this and the # bulk result reads below were added specifically to isolate whether an # observed HiGHS speed edge was a genuine solver-algorithm difference or # just an artifact of per-element vs bulk Python attribute access). model.setAttr("RHS", resid_constrs, [-float(point[j]) for j in range(k)]) model.optimize() if model.Status != GRB.OPTIMAL: raise RuntimeError(f"Gurobi solve failed: status {model.Status}") # bulk result reads -- one C API call each for all m variables / all k # constraints, instead of m + k individual .X / .Pi attribute accesses. w = np.array(model.getAttr("X", w_vars)) c = w @ points[:m_target] normal = -np.array(model.getAttr("Pi", resid_constrs)) return c, normal