[FEA] Incremental ("delta") C API for warm-started LP resolves — proposal + implementation (presolve-off only)

[spoorendonk]

Is your feature request related to a problem? Please describe.

Column-generation and cutting-plane loops re-solve a nearly identical LP many times. Today the C API offers only the cuOptCreate*Problem → cuOptSolve → cuOptDestroyProblem cycle, so every iteration rebuilds the problem host-side, re-uploads it to the GPU, and solves from scratch — even when the change is "append 50 columns" or "bump a handful of objective coefficients" and the previous optimal basis is one or two pivots away from the new optimum.

This is the ask in #725 (open since Dec 2025). In the Feb 2026 reply on that issue the maintainers noted that 26.02 added internal functions to append constraints and warm-start dual simplex from the previous basis, but that a public C API "might be a while". #1562 confirms the current user-facing answer for column generation is "transfer the entire problem into cuOpt for each solve."

This issue concretizes #725 into a specific C API with an implementation that is complete and tested, ready to open as a PR if the design is acceptable.

Describe the solution you'd like

A small companion header, cuopt_c_delta.h, next to cuopt_c.h, that mutates a persistent cuOptOptimizationProblem in place and re-solves it:

cuopt_int_t cuOptAddColumns(problem, num_columns,
                            objective_coefficients, variable_lower_bounds, variable_upper_bounds,
                            column_starts, row_indices, values,      /* CSC of the new columns */
                            variable_types /* NULL => CUOPT_CONTINUOUS */);

cuopt_int_t cuOptAddRows(problem, num_rows,
                         constraint_lower_bounds, constraint_upper_bounds,   /* ranged-problem convention */
                         row_starts, column_indices, values);               /* CSR of the new rows */

cuopt_int_t cuOptDeleteColumns(problem, num_indices, indices);  /* sorted, unique; survivors compact in order */
cuopt_int_t cuOptDeleteRows   (problem, num_indices, indices);

cuopt_int_t cuOptSetObjectiveCoefficients(problem, num_indices, indices, values);  /* one H2D copy + one scatter */

cuopt_int_t cuOptResolve(problem, settings, cuOptSolution* previous_solution_ptr);  /* in/out solution handle */

Semantics:

• Lazy rebuild. Mutators deep-copy their inputs into a host-side pending buffer and return without touching the GPU. cuOptResolve drains the buffer in arrival order against the persistent device problem, then solves. Getters (cuOptGetNumVariables, cuOptGetConstraintMatrix, …) reflect the last-resolved state; index validation in mutators is against the logical post-pending sizes, so a batch can cuOptAddColumns then cuOptAddRows referencing the new columns before a single resolve.
• Solution handle reuse. cuOptResolve takes cuOptSolution* in/out: NULL on first call, the previous handle afterwards. cuOpt reuses or replaces it; the caller never destroys a handle it passed in. On a non-success return the handle is untouched and still caller-owned.
• Per-method warm start. The solver keeps its own state consistent with the mutation:
  • Dual simplex: persists the converted (slack-augmented) LP and its optimal basis. A tail-only structural extension (appended columns enter nonbasic; appended <= rows enter as cuts through the existing internal add_cuts path) re-optimizes from the warm basis in a handful of pivots. A mixed/equality/ranged append, a delete, a coefficient edit, or the first solve falls back to a cold rebuild with a fresh basis capture. Objective is equivalent to a from-scratch solve either way.
  • PDLP: seeds the previous primal/dual iterate (padded/compacted in step with mutations; the stale scaled-space restart state is not reused).
  • Barrier: no warm start applicable; routes through solve_lp. Benefit is the persistent handle only.
• Settings untouched. cuOptResolve solves against a local copy of the settings; the caller's cuOptSolverSettings is never mutated.

⚠️ Scope: presolve OFF only

The delta path is a presolve-off feature by construction, and the API makes that explicit rather than trying to hide it:

1. Third-party presolve. If CUOPT_PRESOLVE explicitly selects PSLP or PaPILO, cuOptResolve returns CUOPT_INVALID_ARGUMENT on every method, with a log message. Default/None proceed and presolve is forced off on the local settings copy. Reason: the warm-start state (dual-simplex basis, PDLP iterate) lives in the unpresolved problem's coordinate space; a presolve that re-derives a different reduced problem each resolve would invalidate it, and barrier builds its problem directly from the device problem. Skipping solve_lp's presolve block also skips its sort_csr, which is why cuOptAddRows requires sorted column indices per row.
2. Internal simplex preprocessing. On the warm dual-simplex path, scale_columns, inner_presolve_optimizations, eliminate_singletons, and barrier_presolve are forced off so that presolve and scaling are the identity and the persisted basis stays in the converted LP's space. The basis is only persisted when its dimensions match that LP.

Trade-off, stated plainly: a problem that benefits heavily from presolve may resolve slower warm than cold-with-presolve. The feature targets the CG/cutting-plane regime, where the win is avoiding the rebuild/re-upload and re-optimizing from a near-optimal basis over many iterations, not the single-solve regime. Users who want presolve should keep using cuOptSolve.

Out of scope (relative to #725) / follow-ups

• Matrix-coefficient edits, variable-bound edits, and constraint-bound/RHS edits are not covered. [FEA] Adding constraints and variables to an existing LP problem (C/C++ API) #725 asked for those too; they are the natural next mutators but need their own warm-start treatment (a bound change can leave the basis primal-infeasible, which dual simplex handles naturally, but that path is not wired).
• LP only. cuOptAddColumns accepts variable_types for symmetry with cuOptCreateProblem, but cuOptResolve always issues an LP solve, i.e. it solves the continuous relaxation of any integer columns. There is no MIP resolve.
• QP: handles carrying a quadratic objective are untested on the delta path (the mutators and cuOptResolve have no Q-aware code and the test suite has no QP coverage). Treat as LP-only until that is added.
• No Python API. The Python modeling layer already has an "updation" API (tracked in [FEA] Python API Improvements Tracker #266, which superseded the original delta issue [FEA] Develop API for application of deltas to previous problems for LP #136), but it still re-uploads the full problem on solve; wiring it to this C path is separate work.
• Barrier and PDLP still reconstruct their internal GPU problem representation per resolve; eliminating that is a planned perf follow-up.
• Sizes/offsets are cuopt_int_t; a long-lived handle whose cumulative nonzeros exceed INT_MAX needs a 64-bit build (same limit as the base API).

Describe alternatives you've considered

• Rebuild via cuOptCreateRangedProblem each iteration — the status quo; pays full host build + H2D upload + cold solve per iteration.
• Expose the internal C++ mutators directly (the non-const get_constraint_matrix_values() references asked about in [FEA] Adding constraints and variables to an existing LP problem (C/C++ API) #725) — no lazy validation, no solver-state consistency, not a stable ABI for bindings (cf. [FEA] Expand cuopt_c.h with problem-model accessors for non-Python language bindings #1703's argument for a complete C surface).
• Session-level caching only (PR [DRAFT] Solver persistence pipeline #1518, "solver persistence pipeline") — reuses RAFT handle and barrier symbolic factorization across independent solves. Complementary, not overlapping: it does not mutate a problem or warm-start from a previous basis/iterate. The two compose (a delta resolve under a persistent session).
• Basis export/import ([FEA] Expose basis / variable status on the LP solution (companion to reduced costs) #1394) — would let users warm-start manually, but does not remove the rebuild/re-upload cost and pushes the basis-transplant logic to the caller.

Additional context

• Implementation: branch spoorendonk/cuopt@delta-api — compare against main (6 commits, 16 files; the branch is ~250 commits behind current main and will be rebased for the PR).
  • API: cuopt_c_delta.h / cuopt_c_delta.cpp / cuopt_c_delta_kernels.cu (~2.1k lines)
  • Warm core: solve_lp_dual_simplex_warm in solve.cu and dual_simplex_warm_state_t (~760 lines)
• Tests: delta_api_tests.cpp (DELTA_API_TEST, 20 tests). The load-bearing checks assert that the delta-path objective matches a from-scratch cuOptCreateRangedProblem solve of the same accumulated problem for barrier, PDLP, and dual simplex, including delete-then-resolve (host CSR compaction + warm-vector compaction), objective edits that flip the optimum, non-ranged cuOptCreateProblem handles, lazy replay/coalescing, invalid-argument handling, and the uniform PSLP/PaPILO rejection.
• Related: [FEA] Adding constraints and variables to an existing LP problem (C/C++ API) #725 (primary ask), [QST] Column Generation with NVIDIA CuOPT #1562 (column-generation demand), [FEA] Define and add Python API to use warmstart data when solving modified problems #353 (completed — Python warm-start API for modified problems), [FEA] Expose basis / variable status on the LP solution (companion to reduced costs) #1394 (basis status; natural companion), [FEA] Python API Improvements Tracker #266 / [FEA] Develop API for application of deltas to previous problems for LP #136 (Python-side delta tracker), PR [DRAFT] Solver persistence pipeline #1518 (session cache; complementary), PR Warm start barrier by taking PDLP solution, moving it to the interior, and doing PDHG on to find a point on the central path #955 (barrier warm start from PDLP; could later give barrier a warm path on resolve).
• Prior art: GRBaddvars/GRBaddconstrs/GRBdelvars/GRBoptimize (Gurobi), Highs_addCols/Highs_addRows/Highs_deleteColsBySet/Highs_run (HiGHS), CPXaddcols/CPXaddrows/CPXdelcols (CPLEX) — all of which keep the basis across the modification.

Happy to open the PR from the branch above (rebased onto current main and the mathematical_optimization/ header layout) if this shape is acceptable, or adjust the surface first.

[chris-maes]

Thanks for the feature request. We will consider it for future releases.