crossover:v0; first simple version for feedback by charles-vzf · Pull Request #56 · JuliaDecisionFocusedLearning/CoolPDLP.jl

charles-vzf · 2026-06-04T03:51:06Z

Add V1 post-solve crossover (threshold snap + implied bounds) Refs #13

Post-OPTIMAL crossover for PDLP: snap primal coordinates near finite box bounds, tighten implied bounds from equality rows, rollback if KKT residuals regress. Controlled by CrossoverParameters on Algorithm (enabled by default).

V1 is not a basic-vertex crossover (unlike cuOpt): it helps near-bound / implied-bound cases (e.g. toy_lp) but is usually a no-op when variables stay strictly interior. Lightweight first step toward MIP-ready solutions.

Also realized a small bench compared to cuopt:

I am planning a more advanced version cuopt-like after feedbacks

codecov · 2026-06-07T14:36:11Z

Codecov Report

❌ Patch coverage is 94.53125% with 7 lines in your changes missing coverage. Please review.

Files with missing lines	Patch %	Lines
src/components/crossover.jl	93.54%	6 Missing ⚠️
src/algorithms/common.jl	96.55%	1 Missing ⚠️

Files with missing lines	Coverage Δ
src/CoolPDLP.jl	`100.00% <ø> (ø)`
src/components/termination.jl	`80.00% <100.00%> (+15.00%)`	⬆️
src/algorithms/common.jl	`96.10% <96.55%> (+2.22%)`	⬆️
src/components/crossover.jl	`93.54% <93.54%> (ø)`

... and 2 files with indirect coverage changes

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

gdalle

Thank you for giving this a shot! Of course there are lots of comments, but as you'll learn if you continue to contribute to open-source, this is rather a good sign :) If you ever get a review of a 500-LOC PR with a single comment, the maintainer didn't read your code.
My main doubts are related to the algorithm you picked: is it even called a crossover? Why not go for the full Megiddo approach with simplex pivot steps?

gdalle · 2026-07-01T16:36:21Z

+        crossover_threshold = 1.0e-6,
+        crossover_fixed_tol = 1.0e-8,
+        crossover_rollback_on_kkt_regression = true,
+        crossover_kkt_rtol = 0.0,
+        crossover_use_effective_bounds = true,


Where do these default values come from?

Pragmatic V1 knobs, not from a single paper constant:

1e-6 / 1e-8: absolute snap tolerances (same order as PDLP residual scales and cuPDLPx-style "near bound" heuristics).

rollback_on_kkt_regression = true, kkt_rtol = 0: conservative default —
keep crossover only if KKT does not worsen.

use_effective_bounds = true: enables the equality-row implied-bound pass before snapping.
These are defaults only; the user can override them via PDLP / PDHG kwargs

gdalle · 2026-07-01T16:36:30Z

+    reltol_T = _T(termination_reltol)
+    crossover_params = CrossoverParameters(;
+        enabled = crossover,
+        threshold = max(_T(crossover_threshold), reltol_T / 20),


Where does this / 20 come from?

Heuristic floor: effective snap threshold = max(crossover_threshold, termination_reltol / 20).

With a loose reltol (e.g. 1e-3), PDLP can stop as OPTIMAL while some coords are still O(reltol) from bounds; the default 1e-6 snap would barely fire. The floor raises the snap radius to at least reltol/20 (here 5e-5)
so near-bound coords at the solve-tolerance scale actually get snapped.
Factor 20 is arbitrary, i can remove this coupling entirely and just use crossover_threshold as
given (user sets it explicitly if they want a looser snap), or expose it as a named parameter (crossover_reltol_fraction) if you prefer to keep the link.

gdalle · 2026-07-01T16:38:22Z

+    end
+    (; termination_reltol) = algo.termination
+    err_before = stats.err
+    x_backup = copy(state.sol.x)


We might be able to overwrite some field from the scratch space to avoid allocating? It doesn't matter much though, since we only apply crossover once

We cannot reuse scratch.x / y / z for the backup:
kkt_errors! overwrites all three when checking post-crossover residuals.

gdalle · 2026-07-01T16:42:18Z

+    "revert to the pre-crossover primal if KKT errors regress beyond tolerances"
+    rollback_on_kkt_regression::Bool = true


Is this boolean parameter necessary? To simulate rollback_on_kkt_regression = false, one could also set kkt_rtol = Inf?

Not completely equivalent :)
rollback_on_kkt_regression = false skips all rollback checks
(crossover_kkt_acceptable returns true immediately). kkt_rtol = Inf only disables the relative increase test; we still reject if relative(err_after) > termination_reltol. Tests rely on rollback=false accepting a worsened iterate. Keeping the bool for clarity, but it is still possible to remove it and have +inf instead, as you want.

gdalle · 2026-07-01T16:47:42Z

+    elseif crossover_applied
+        "crossover applied ($crossover_n_snapped coords)"
+    else
+        "crossover not applied"


What does this case mean?

That else branch is the catch-all message when crossover did not stick:
disabled (crossover=false), enabled but nothing snapped (n_changed == 0),
or we never kept a post-crossover primal. show only has three strings total
— rolled back / applied / not applied — and this is the third.

gdalle · 2026-07-01T17:06:39Z

+                push!(free, j)
+            end
+        end
+        length(free) == 1 || continue


How often do we have length(free) = 1 on realistic cases, e.g. from MathOptBenchmarkInstances.jl?

The pass only tightens when an equality has exactly one free (not-at-box) variable — if that is rare on realistic LPs, the feature buys little.
Local tests (unit + toy LPs) show that case does occur and enables snaps
when PDLP already puts vars on bounds; on larger/random MOBI-style
instances it is often a no-op, and cheap (continue).

gdalle · 2026-07-01T17:08:06Z

+end
+
+function crossover_n_changed(x_after, x_before)
+    return sum(x_after .!= x_before)


This version is non-allocating:

count(!=, x_after, x_before)

count(!=, a, b) is not defined for two AbstractVectors
on Julia 1.10–1.12 (MethodError). CPU path: explicit loop (non-allocating);
GPU path: sum(x_after .!= x_before) (broadcast).

gdalle · 2026-07-01T17:09:21Z

+            if at_box_cpu[j]
+                slack -= aij * x_cpu[j]
+            else
+                push!(free, j)


Judging by what comes below, this loop might be interrupted early as soon as we find two free variables. Thus, the free vector might not even be necessary?

INdeed - replaced free::Vector{Int} with (n_free, free_j, free_aij) counters
and break when n_free > 1.

gdalle · 2026-07-01T17:10:08Z

+            if !isfinite(uv_cpu[j])
+                uv_cpu[j] = implied
+            else
+                uv_cpu[j] = min(uv_cpu[j], implied)
+            end


The else actually works for both cases

Merci - simplified to uv_cpu[j] = min(uv_cpu[j], slack/aij) and
lv_cpu[j] = max(lv_cpu[j], slack/aij) (min/max with ±Inf handle both
cases).

gdalle · 2026-07-01T17:11:32Z

+end
+
+"""
+    fraction_at_bounds(x, milp; atol=1e-12)


What is this used for?

Needed for the apply/rollback gate (n_changed > 0), not only display. The
exact integer is also stored as stats.crossover_n_snapped and shown in
ConvergenceStats — useful for tests/debug, optional for end users. Happy to
keep only the bools (applied / rolled_back) and drop the count from the
public stats if you prefer a thinner API.

After OPTIMAL termination, optionally snap primal coordinates near finite box bounds, tighten implied bounds from equality rows, and roll back if KKT errors regress. Controlled by CrossoverParameters on Algorithm (on by default). Effective bounds run on CPU once per solve and copy back to device. Not a basic-vertex crossover (unlike cuOpt): useful when PDLP stops near bounds, usually a no-op for strictly interior solutions. Refs JuliaDecisionFocusedLearning#13

@ref

Enum values are not separate doc bindings; use inline code instead of @ref.

…er fixes. Document V1 vs Megiddo, parametrize bound/eq atol, traverse At via nzrange, drop @inbounds/free vector, simplify implied bounds, and cover ConvergenceStats show.

Mutate effective bounds in place after the caller materializes CPU vectors, clarify the implied-bounds docstring, and remove review-only comments.

charles-vzf · 2026-07-11T10:47:41Z

Thank you for your review and all the comments that were very instructive.
This PR is intentionally a V1 post-PDLP rounding step (threshold snap + implied
equality bounds + KKT rollback), not a Megiddo-style crossover with simplex
pivots.
I plan to use this V1 as a baseline while designing the basis-based version.
Happy to rename to postprocess / rounding in the API if you prefer less
loaded terminology before merge (if merge?) — I'll wait for your preference before renaming.

charles-vzf force-pushed the crossover-13 branch from a4e3058 to 4b82353 Compare June 7, 2026 23:54

gdalle marked this pull request as draft June 8, 2026 08:40

gdalle self-requested a review June 8, 2026 08:40

charles-vzf force-pushed the crossover-13 branch 2 times, most recently from b89002c to af49ead Compare June 22, 2026 07:56

gdalle requested changes Jul 1, 2026

View reviewed changes

Charles Vielzeuf added 2 commits July 5, 2026 16:40

Fix Documenter cross-references to TerminationStatus.OPTIMAL.

c777379

Enum values are not separate doc bindings; use inline code instead of @ref.

charles-vzf force-pushed the crossover-13 branch from 2b6731c to c777379 Compare July 5, 2026 07:41

Charles Vielzeuf added 2 commits July 11, 2026 16:09

Address PR JuliaDecisionFocusedLearning#56 review: compact V1 crossov…

c4dac0d

…er fixes. Document V1 vs Megiddo, parametrize bound/eq atol, traverse At via nzrange, drop @inbounds/free vector, simplify implied bounds, and cover ConvergenceStats show.

Trim crossover review polish: drop redundant Vector copies.

23fbbee

Mutate effective bounds in place after the caller materializes CPU vectors, clarify the implied-bounds docstring, and remove review-only comments.

		"revert to the pre-crossover primal if KKT errors regress beyond tolerances"
		rollback_on_kkt_regression::Bool = true

Uh oh!

Conversation

charles-vzf commented Jun 4, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

codecov Bot commented Jun 7, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

gdalle left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

charles-vzf commented Jul 11, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

charles-vzf commented Jun 4, 2026 •

edited

Loading

codecov Bot commented Jun 7, 2026 •

edited

Loading