HiGHS Implementation

Purpose

This spec provides implementation guidance specific to HiGHS integration as the first open-source LP solver reference implementation for Cobre. It complements the Solver Abstraction Layer with HiGHS-specific patterns for the C API, batch bound operations for row and column bound updates, retry strategy, basis management, memory footprint, and optimization-tuned configuration. For thread-local workspace management, see Solver Workspaces.

HiGHS and CLP are both first-class reference implementations — the solver abstraction interface is designed and validated against both (see Solver Abstraction, Decision 5).

1. Architecture Alignment

1.1 HiGHS API Layer

HiGHS exposes a pure C API through Highs_c_api.h that is directly callable from Rust via extern "C" FFI. Unlike CLP, there is no need for a C++ wrapper — all required operations are available through the C API.

2. Solver Interface Mapping

This section maps each operation from the Solver Abstraction SS4 to the specific HiGHS API calls.

2.1 Load Model

Highs_passLp loads a complete LP in a single call:

Highs_passLp(highs, num_col, num_row, num_nz,
             a_format, sense, offset,
             col_cost, col_lower, col_upper,
             row_lower, row_upper,
             a_start, a_index, a_value)

Format flexibility: Unlike CLP (which requires column-major only), HiGHS accepts both formats via the a_format parameter:

Since the stage LP templates (Solver Abstraction SS11) store the structural matrix in CSC form, the HiGHS implementation passes them with a_format = kHighsMatrixFormatColwise. This avoids per-stage-transition transposition overhead — HiGHS internally stores the LP matrix in column-major (CSC) format, so passing CSC directly skips the internal ensureColwise() transposition that would occur if CSR were passed.

2.2 Add Rows

Highs_addRows adds multiple rows in a single batch call:

Highs_addRows(highs, num_new_row,
              lower, upper,
              num_new_nz, starts, index, value)

The starts/index/value arrays follow the standard CSR (row-major) format. This matches the cut pool’s CSR-friendly storage layout (see Binary Formats SS3.4).

2.3 Set Row Bounds

HiGHS provides batch bound modification via index-set APIs. Unlike CLP’s mutable pointer access (zero-copy direct writes), HiGHS requires function calls for each batch of updates.

Performance implication: Row and column bound updates should be assembled into a single batch call rather than individual per-row calls. In SDDP, the ~2,240 RHS updates per solve (incoming storage, AR lag fixing, noise fixing) are the primary use case. The index array (set) identifies which rows to update; the lower/upper arrays provide the new bounds. Pre-allocating these batch buffers in the thread-local workspace (see Solver Workspaces) eliminates allocation overhead on the hot path.

The LP layout convention (Solver Abstraction SS2) places state-linking constraints at the top, so the row indices for scenario patching form a contiguous range starting at 0 — enabling efficient sequential index generation.

Comparison with CLP: CLP’s mutable double* pointers enable zero-copy in-place writes with no function call overhead per element. HiGHS’s batch API is slightly higher overhead but provides bounds checking and maintains solver-internal invariants. For the ~2,240 updates typical in SDDP, the difference is expected to be negligible relative to solve time.

2.4 Solve

HiGHS uses a single entry point for all solve operations:

HiGHS determines its solve strategy internally based on:

• Whether a basis has been set (via Highs_setBasis) → warm-start
• The configured algorithm (simplex_strategy option) → dual or primal simplex
• Whether presolve is enabled → full preprocessing or direct solve

Status interpretation after solve:

For status 9 (UnboundedOrInfeasible), use Highs_getDualRay and Highs_getPrimalRay to disambiguate.

2.5 Solution Extraction

HiGHS copies solution values into caller-provided arrays:

Key difference from CLP: HiGHS copies values into pre-allocated caller-owned arrays, while CLP returns mutable pointers into solver-internal memory. The HiGHS approach is safer (no pointer invalidation risk) but requires pre-allocated buffers. These buffers should be part of the thread-local workspace (see Solver Workspaces).

Dual normalization: HiGHS’s dual sign convention must be verified against the canonical sign convention defined in Solver Abstraction SS8. If HiGHS reports duals with a different sign for $\ge$ constraints, the HiGHS implementation must negate the appropriate dual values before returning them to the SDDP algorithm. This is a critical correctness requirement — sign errors in duals produce divergent cuts.

2.6 Basis Management

HiGHS uses separate arrays for column and row basis status:

Highs_setBasis(highs, col_status, row_status)
Highs_getBasis(highs, col_status, row_status)

Both arrays are HighsInt[] (one integer per variable/constraint).

Status codes:

Key difference from CLP: HiGHS uses separate column and row status arrays (HighsInt[]), while CLP uses a combined unsigned char[] array (status[0..numcols-1] = columns, status[numcols..numcols+numrows-1] = rows). The HiGHS representation is more natural for the basis management described in Solver Abstraction SS2.3.

Interaction with LP layout convention: Per Solver Abstraction SS2.3, the structural portion of the basis is position-stable across iterations. When warm-starting after adding cuts, the implementation:

1. Prepares the column status array (unchanged from cached basis)
2. Prepares the row status array: cached structural rows + new dynamic constraint rows set to kHighsBasisStatusBasic (1)
3. Calls Highs_setBasis with both arrays
4. Calls Highs_run for warm-start solve

2.7 Reset

Highs_clearSolver(highs) clears all solver state (basis, factorization, solution) while keeping the model loaded. This is useful for retry strategies that need to discard the current basis without reloading the LP.

For a full reset (discard everything): Highs_destroy(highs) + Highs_create(). This is only needed at shutdown or in extreme recovery scenarios.

2.8 Infeasibility Diagnostics

3. Retry Strategy

The retry strategy follows the behavioral contract defined in Solver Abstraction SS7. HiGHS-specific retry escalation:

The retry strategy uses a 2-phase escalation with 12 levels and wall-clock time budgets:

Phase 1 — Quick recovery (levels 0–5): Low-cost parameter adjustments with tight time budgets.

Phase 2 — Aggressive recovery (levels 6–11): More expensive strategies with extended time budgets.

Each level has an associated wall-clock budget controlled by the retry_time_budget_seconds configuration parameter. After each successful retry, the implementation restores default settings for the next solve. After all levels are exhausted, return a terminal error with the best partial solution if available (call Highs_getSolution — HiGHS may have a feasible but suboptimal solution).

4. Configuration

4.1 SDDP-Tuned Settings

4.2 Scaling Note

HiGHS manages scaling internally. The relevant options are:

The scaling strategy interacts with the open point in Solver Abstraction SS3 (single-phase vs two-phase scaling). If Cobre manages its own scaling (applied at the template level), HiGHS internal scaling should be set to 0 to avoid double-scaling. If Cobre delegates scaling to the solver, HiGHS’s default strategy is a reasonable starting point.

5. Memory Footprint

This is within acceptable bounds for production HPC nodes (256+ GB RAM). The memory footprint is comparable to CLP (~15 MB without cloning).

Note on basis storage: HiGHS uses HighsInt (4 bytes) per basis status entry, vs CLP’s unsigned char (1 byte). This increases basis storage by ~4x but is negligible relative to the LP matrix and factorization.

6. HiGHS-Specific Considerations

6.1 Format Flexibility

HiGHS’s Highs_passLp accepts both CSR (kHighsMatrixFormatRowwise = 2) and CSC (kHighsMatrixFormatColwise = 1) formats. However, HiGHS internally stores the LP matrix in column-major (CSC) format — when CSR is passed, Highs_passLp internally calls ensureColwise() to transpose it (see Highs.cpp:353). Since stage LP templates are stored in CSC form, the HiGHS implementation passes them directly with a_format = kHighsMatrixFormatColwise, avoiding this per-stage-transition transposition overhead. Both solvers (HiGHS and CLP) use CSC internally, so using CSC templates is the common format that works natively with both.

Highs_addRows for dynamic constraint addition uses CSR format (row starts, column indices, values), which is the same for both solvers.

6.2 Dual Sign Convention

HiGHS’s dual sign convention must be verified against the canonical sign convention defined in Solver Abstraction SS8. If HiGHS reports duals with a different sign for $\ge$ constraints, the HiGHS implementation must negate the appropriate dual values before returning them to the SDDD algorithm. This is a critical correctness requirement — sign errors in duals produce divergent cuts.

6.3 Thread Safety

Each void* HiGHS instance is not thread-safe — it must be exclusively owned by one thread. This aligns with the solver abstraction’s thread-safety requirement (Solver Abstraction SS4.2). Each OpenMP thread creates its own instance via Highs_create() at initialization and destroys it at shutdown via Highs_destroy.

6.4 Solution Copy Semantics

Unlike CLP (which returns mutable pointers into solver internals), HiGHS copies solution values into caller-provided arrays via Highs_getSolution. This is inherently safer — no pointer invalidation risk — but requires pre-allocated buffers in the thread-local workspace. The buffers are sized once at initialization (to num_col and num_row of the largest stage LP) and reused for all solves.

6.5 StageLpCache Stage Transition

Stage transitions load the complete StageLpCache[t] via Highs_passLp — which includes structural constraints plus all active cuts in CSC format. Since the StageLpCache CSC is in HiGHS’s native internal format, Highs_passLp is a fast bulk memory operation with no format conversion overhead. Highs_addRows is used during StageLpCache assembly between iterations.

Cross-References

• Solver Abstraction — Interface contract (SS4), LP layout convention (SS2), cut pool design (SS5), error categories (SS6), retry contract (SS7), dual normalization (SS8), basis storage (SS9), stage templates (SS11)
• Solver Abstraction — Decision 5 (dual-solver validation) that established HiGHS as a first-class reference implementation
• CLP Implementation — Companion solver implementation for cross-validation
• Solver Workspaces & LP Scaling — Thread-local workspace infrastructure that owns the HiGHS instance
• LP Formulation — Constraint structure that HiGHS operates on
• Cut Management — How cuts are generated; this spec handles how they are loaded via Highs_addRows
• Training Loop — Forward/backward pass orchestration driving solver invocations
• Binary Formats — Cut pool CSR layout (SS3.4)
• Hybrid Parallelism — OpenMP threading model requiring one HiGHS instance per thread
• Memory Architecture — NUMA-aware allocation for solver workspaces
• Configuration Reference — Solver configuration parameters