Source code for mga_surveyor.highs_projection

"""HiGHS (via raw highspy, no AML abstraction layer) reimplementation of
gurobi_projection.closest_point_on_hull -- same name, same contract
(point, points, norm) -> (c, normal), just this module's backend instead of
that one's; the two are never imported side by side under the same bare
name (pick one backend per solve), so there's no reason for one of them to
carry a `_highs` suffix the other doesn't. Mirrors the raw-gurobipy design
as closely as HiGHS's native
Python API allows: one persistent Highs() instance per (thread, norm),
extended with a new `w` column per new inner point via addCol, and the
query point folded into the bounds of two per-dimension rows (one per side
of the abs-value linearization) updated in place via changeRowBounds -- no
file export, no AML abstraction layer, matching the persistent-model
pattern that makes the Gurobi version fast (see project notes: an earlier
attempt through Pyomo's AML layer over the same persistent Gurobi backend
cost ~15-50x versus this, and linopy -- which has no persistent-solve path
at all -- cost 3,000-7,000x).

L1 and Linf only: HiGHS is an LP/MIP solver, no quadratic objective
support (confirmed separately: Pyomo's appsi_highs interface raises
DegreeError on a quadratic objective) -- no L2 branch here. Use
gurobi_projection.closest_point_on_hull for L2.

Tolerances are tightened to 1e-9 (HiGHS's default is 1e-7 for both primal
and dual feasibility), matching the Gurobi version's OptimalityTol/
FeasibilityTol=1e-9 -- important for iteration-by-iteration agreement with
the Gurobi backend over long runs, where looser tolerances would let small
per-call differences accumulate.

`highspy` is imported at module import time but optionally (`highspy =
None` if it isn't installed, raising only on first use) -- so `import
mga_surveyor` (and picking `projection_backend='gurobi'` throughout) never
requires highspy to be installed.

As in `gurobi_projection`, the persistent per-(thread, norm) model assumes
every call from one thread passes the same growing `points` array (new rows
only appended), as one Method's own executor does.
"""
import threading
from typing import Literal

import numpy as np

try:
    import highspy
except ImportError:
    highspy = None

VALID_NORMS_HIGHS = ("l1", "linf")
NormHighs = Literal["l1", "linf"]

_thread_local = threading.local()


def _require_highspy():
    if highspy is None:
        raise ImportError(
            "projection_backend='highs' requires the `highspy` package, which is not "
            "installed here (pip install highspy). Use projection_backend='gurobi' "
            "instead if you have a Gurobi license (see gurobi_projection."
            "closest_point_on_hull), or install highspy for a free, "
            "open-source alternative -- norm in ('l1', 'linf') only."
        )


def _build(norm: NormHighs, k: int, first_points: np.ndarray) -> dict:
    m0, k0 = first_points.shape
    assert k0 == k

    model = highspy.Highs()
    model.setOptionValue("output_flag", False)
    model.setOptionValue("primal_feasibility_tolerance", 1e-9)
    model.setOptionValue("dual_feasibility_tolerance", 1e-9)

    for i in range(m0):
        model.addCol(0.0, 0.0, highspy.kHighsInf, 0, np.array([], dtype=np.int32), np.array([], dtype=np.float64))
    n_w = m0

    if norm == "linf":
        model.addCol(1.0, 0.0, highspy.kHighsInf, 0, np.array([], dtype=np.int32), np.array([], dtype=np.float64))
        aux_cols = [n_w]
    else:  # l1
        for j in range(k):
            model.addCol(1.0, 0.0, highspy.kHighsInf, 0, np.array([], dtype=np.int32), np.array([], dtype=np.float64))
        aux_cols = list(range(n_w, n_w + k))

    idx = np.arange(n_w, dtype=np.int32)
    val = np.ones(n_w, dtype=np.float64)
    model.addRow(1.0, 1.0, n_w, idx, val)
    sum_row = 0

    upper_rows, lower_rows = [], []
    row_idx = 1
    for j in range(k):
        aux = aux_cols[0] if norm == "linf" else aux_cols[j]
        cols = np.concatenate([np.arange(n_w, dtype=np.int32), [aux]]).astype(np.int32)
        vals_u = np.concatenate([first_points[:, j].astype(np.float64), [-1.0]])
        model.addRow(-highspy.kHighsInf, 0.0, len(cols), cols, vals_u)
        upper_rows.append(row_idx); row_idx += 1
        vals_l = np.concatenate([first_points[:, j].astype(np.float64), [1.0]])
        model.addRow(0.0, highspy.kHighsInf, len(cols), cols, vals_l)
        lower_rows.append(row_idx); row_idx += 1

    return {
        "model": model, "w_cols": list(range(n_w)), "aux_cols": aux_cols,
        "upper_rows": upper_rows, "lower_rows": lower_rows, "sum_row": sum_row,
        "m_known": m0, "n_cols": n_w + len(aux_cols),
    }


[docs] def closest_point_on_hull(point: np.ndarray, points: np.ndarray, norm: NormHighs) -> tuple[np.ndarray, np.ndarray]: _require_highspy() if norm not in VALID_NORMS_HIGHS: raise NotImplementedError( f"HiGHS backend is LP-only (no quadratic objective) -- norm must be one of " f"{VALID_NORMS_HIGHS}, got {norm!r}. Use gurobi_projection.closest_point_on_hull for L2." ) point = np.asarray(point, dtype=float) points = np.asarray(points, dtype=float) m_target, k = points.shape attr = f"highs_state_{norm}" state = getattr(_thread_local, attr, None) if state is None: state = _build(norm, k, points[:m_target]) setattr(_thread_local, attr, state) model = state["model"] w_cols, upper_rows, lower_rows = state["w_cols"], state["upper_rows"], state["lower_rows"] m_known = state["m_known"] if m_target > m_known: for p_new in points[m_known:m_target]: row_idx = np.array([state["sum_row"]] + upper_rows + lower_rows, dtype=np.int32) row_val = np.concatenate([[1.0], p_new.astype(np.float64), p_new.astype(np.float64)]).astype(np.float64) model.addCol(0.0, 0.0, highspy.kHighsInf, len(row_idx), row_idx, row_val) w_cols.append(state["n_cols"]) state["n_cols"] += 1 state["m_known"] = m_target for j in range(k): model.changeRowBounds(upper_rows[j], -highspy.kHighsInf, float(point[j])) model.changeRowBounds(lower_rows[j], float(point[j]), highspy.kHighsInf) status = model.run() model_status = model.getModelStatus() # run() returns kOk even when it stops at a limit or proves infeasibility, # so also require an optimal model -- the same contract as the Gurobi backend. if status != highspy.HighsStatus.kOk or model_status != highspy.HighsModelStatus.kOptimal: raise RuntimeError(f"HiGHS solve failed: status {status}, model status {model.modelStatusToString(model_status)}") sol = model.getSolution() all_col_values = np.array(sol.col_value) w_val = all_col_values[w_cols] c_point = w_val @ points[:m_target] duals = model.allConstrDuals() normal = np.array([duals[upper_rows[j]] + duals[lower_rows[j]] for j in range(k)]) return c_point, normal