|
Gecode 6.4.0
|
Work is on codex/solver-parity in the independent checkout at implementation/gecode. The original solver checkout, branch, uncommitted source and benchmark binaries remain untouched. The enhanced source/test/input snapshot is e10562fd9; source-snapshot.json records 2,963 input hashes. All 2,963 original files matched when checked after integration.
This ledger covers the implemented slices of the ongoing W0–W14 roadmap. The validation record identifies the exact source used for each completed gate. They provide numerical LP/MILP modeling and workflows, persistent numerical sessions, typed native globals, weighted feasibility repair, C/Python bindings, an explicit bounded integer compiler to native Gecode search, ranked solution pools, checked integer LP deductions, exact integer presolve/reconstruction, interruption-safe native frontier bounds, bounded reliability branching, verified root covers, continuous weighted-square QP and an owning FlatZinc capture/compiler with a separate command-line solver. Commercial-solver parity and the larger native search improvements remain incomplete. The algorithm checkpoint adds bounded native binary capacity optimization after the ninth checkpoint. Further roadmap implementation is on hold. Each report identifies its own tested source, artifacts and prior-version comparison.
| Area | Delivered behavior | Where to start |
|---|---|---|
| Native binary capacity optimization | Bounded exact dynamic programming supplies a checked witness preference and objective bound for one-row Binary capacity models; other search defaults are preserved | Algorithm checkpoint |
| Isolation and dependencies | Independent clone/branch, separate agent worktrees/build directories, preserved enhanced baseline, pinned HiGHS source | source-snapshot.json, dependencies.json |
| Sparse owning model | Five explicit variable domains; ranged linear rows; min/max/offsets; canonical sparse terms; stable model-aware handles, tombstones, revisions and snapshots | gecode/optimize/model.hpp |
| Bulk construction | Atomic variable/row batches and explicit CSR input, strong allocation-failure guarantee, geometric growth and no dense matrix allocation | Bulk API |
| Result and budget contract | Status separate from incumbent; backend/version attribution; numerical guarantee; missing-bound semantics; normalized/native gaps; shared time/cancellation and node budget primitives | gecode/optimize/result.hpp |
| Numerical backend | Optional HiGHS LP/MILP route, explicit unsupported classes/guarantees/scales, deadline-aware candidate capture, one worker per solve | gecode/optimize/solve.hpp |
| Independent checking | Structural trust boundary; original bounds, rows, integrality, objective and logical indicators; original-slot solution mapping | gecode/optimize/validate.hpp |
| Starts and edits | Numerical partial/complete starts; native exact complete starts with live indicator gate completion and strict improvement search; model edits and historical result ownership | SolveOptions::primal_start, Model |
| Persistent sessions | Compatible cost/bound/RHS edits retain LP bases; structural/type/owner changes reload; MIP witnesses are revalidated before reuse; fresh options, budgets and callback lifetime per solve | Sessions |
| Explicit LP basis starts | Immutable original-model basis records, precise compatibility rejection and accepted/repaired submission reporting, with C/Python ownership | Basis API, Bindings |
| Serial scenario batches | Sparse coefficient, offset, variable-bound and row-side overrides; independent historical results, shared time/cancellation and optional private HiGHS session reuse, with C/Python ownership | Scenarios, Bindings |
| Numerical LP evidence | Explicit private auxiliary solves recover checked original feasible bases/improving rays or signed Farkas contradictions; separate availability and raw stage history, with C/Python ownership | LP evidence, Bindings |
| Selected-basis LP sensitivity | Numerical objective-coefficient and equality-RHS intervals, private checked basis factorization without optimization runs, owning results and C/Python lifetime/cancellation behavior | Sensitivity, Bindings |
| Local Python wheel | Self-contained macOS arm64 C ABI, automatic package-relative loading, pinned notices and RECORD checks; isolated Python 3.12/3.14 installation tests | Wheels |
| Continuous LP observations | Owning original activities, two-sided slacks, duals, reduced costs and basis export with independent numerical KKT checking and C/Python access | LP observations |
| Native integer route | Explicit Backend::Native, actual Space/IntVarArray and branch-and-bound, native reified indicators, exact original-integer witness checking within documented activity limits | Native bridge |
| Native global registry | Typed all-different, element, table, cumulative, circuit and Regular records; aliases/index bases retained; independent predicates and native compiler; automatic native dispatch for active globals | Globals |
| Sparse checked integer LP | Binary and bounded-integer CSR storage, exact dual bounds and interval reductions, sibling-bound restoration and explicit native hybrid API; dense compatibility retained | Sparse LP, Native LP |
| Native search frontier | Explicit best-bound or depth-first coordinator; exact interrupted global bounds, retained incumbents and bounded live regions, optional checked LP and opt-in bounded binary reliability probes | Native search |
| Native incumbent neighborhood | Explicit C++ BinaryHamming attempt after a checked incumbent, original-model improvement validation and shared bounded frontier accounting | Neighborhoods |
| Verified root covers | Budgeted binary cover separation, independent exact cut validation and explicit handoff to native LP/frontier search; separate cut and LP accounting | Root covers |
| Continuous quadratic models | Distinct owning weighted-affine-square model, bounded convex min/concave max through HiGHS QP, original primal/KKT checks and outward tangent bound; C/Python bindings | Quadratic API |
| FlatZinc pipeline | Owning capture, strict whole-model integer/Boolean compiler, supported implications/reifications, all-different/element, table/holey domains, explicit-offset circuit fixed-data cumulative and literal deterministic Regular; independent raw-source witness validation and explicit fzn-gecode-optimize CLI | Compiler, Driver |
| Experimental MiniZinc route | Opt-in separate solver identity and dedicated library, explicit millisecond protocol, relocatable build/install registration and real pinned compiler/output checks | MiniZinc |
| Exact presolve/postsolve | Signed interval implications, fixed substitution, redundant rows and immutable original/reduced mappings; explicit utility with exact historical witness reconstruction | Presolve |
| Solution pools | Ranked representatives over finite discrete projections, continuous recourse, original witness validation and separate RequestedLimit/Exhausted evidence | Pools |
| Feasibility repair | Explicit weighted L1 row/bound relaxation on a distinct private model; optional ordered original-objective refinement; original residual reporting and separate proof/completion fields | Repair |
| C and Python | Versioned C99 owning-handle boundary, immutable results, cancellation, sessions and model I/O; Python ctypes package; installed C consumer and backend-enabled/disabled conformance | Bindings |
| Conflict diagnostics | Numerical deletion-minimal groups for rows, bounds, integrality and domains; original attribution and optional deletion witnesses; interruption cannot promote an incomplete conflict | Diagnostics |
| Fast regression gate | Required native CP and numerical cases, plus sessions, diagnostics and exact native bridge; a 28-second whole-command budget and explicit incomplete-case failures | Fast gate |
| Bounded indicators | Conservative domain-derived M, separate binary inactivity gate, preserved original logic, atomic posting, mutation/domain guards and checked removal | Constraint helpers |
| Boolean helpers | AND/OR equality, empty/single/multiple inputs, aliases and duplicates; atomic posting | Constraint helpers |
| Multiple objectives | Ordered linear stages, explicit degradation, one outer deadline, retained original-model feasible result, no false completion after interrupted stages | Workflows |
| Model exchange | Strict numerical LP/free-MPS readers; 17-digit output; checked round trips; atomic replacement; explicit unsupported dialects | I/O |
| Distribution and CLI | Standalone or opt-in native CMake component; installed package aliases; umbrella header; JSON file solver; isolated exact-check benchmark harness | Build and API guide |
| Verification and CI | Independent component tests, full-source sanitizers, cross-feature integration, native regressions, installed consumers, five existing MIPLIB models; added platform CI workflow | Validation |
The backend's search, presolve, cuts and heuristics in this new route are HiGHS capabilities. Native Gecode CP and the checked sparse relaxation remain available through their original interfaces. The explicit native hybrid adds certificate-checked LP deductions to native propagation; its results identify both engines. Ordinary numerical solves continue to use HiGHS search and ordinary native routing is unchanged.
These gates describe unfinished scope; they are not authorization to start a new batch after the current integration checkpoint.
| Work package | Status after this batch | Next completion gate |
|---|---|---|
| W0 reproducible foundation | Source isolation/pin, correctness harness and bounded fast regression gate implemented; comprehensive performance baseline still outstanding | Freeze cold/warm tracks, machine/environment accounting and untouched holdout inputs; execute Windows containment CI and full timing gate before enabling that platform |
| W1 original-model IR | Linear numerical model, lifecycle, indicator metadata, six native globals and scoped owning FlatZinc capture/reconstruction implemented; broad capture admission remains | Expand native global registry and capture; measure original-model construction memory |
| W2 result/session contract | Results, budgets, capability query, persistent HiGHS sessions and owning continuous LP dual/basis observations and owning explicit basis submission implemented; cumulative backend usage remains | Interrupted-workflow accounting and action callback contracts; native persistent state |
| W3 usable LP/MILP route | First vertical slice implemented and tested; supported I/O dialect is explicit | Broader LP/numerical/general-integer panels, backend-alone comparisons and unsupported-format fixtures |
| W4 native and FlatZinc integration | Bounded integer linear/indicator native bridge and six typed globals; owning FlatZinc capture with explicit CLI and opt-in MiniZinc registration implemented; broader predicates remain | Broader preserved globals with exact raw-source checks and external CP panels |
| W5 native sparse relaxation | CSR binary and bounded-integer certificates/interval cuts, native propagation and explicit public hybrid bridge implemented and independently tested | Measure root/whole-solve benefit across families before changing defaults; expand exact arithmetic portability |
| W6 presolve/postsolve | Exact bounded-integer interval reductions and fixed substitution with owning reconstruction implemented; numerical route also uses HiGHS presolve | Expand mapped constraints and reductions, budgeted solve composition and measured default selection |
| W7 native branch-and-cut | Proof-carrying scoped pool, binary cover separator, verified root loop and explicit native LP/frontier handoff implemented; dynamic local cuts and broader separation remain | Broader separators, dynamic local-cut lifecycle and measurable root/whole-solve benefit |
| W8 native branching/global bounds | Explicit frontier/global bounds and opt-in bounded binary reliability probes implemented; broader branching and measured default selection remain | General integer/LP-informed scoring and whole-solve benefit across families with protected regressions |
| W9 primal portfolio | Numerical starts, exact complete native starts and one explicit bounded binary incumbent neighborhood implemented; partial native completion and repair/diving/RINS/LNS scheduling remain | Cold-start first-feasible gains, broader neighborhood policies and measured benefit with original-model checking |
| W10 learning/explanations | Architecture/source investigation, isolated pinned SAT protocol experiment and private uncompiled reason-contract header retained; 29,160 experiment queries pass normally and with full dependency sanitizers; no product learning runtime | Checked original-row conditional reason kernel; clone/recompute versus trailed learning pilot; representative benefit before defaults |
| W11 application workflows | Edits, starts, bounded logic, ordered objectives, numerical grouped conflicts, weighted repair, ranked pools, serial scenarios and selected-basis coefficient/equality sensitivity implemented; fine-grained indicator IIS, broader sensitivity and action callbacks remain | Workflow-by-workflow conformance and a backend/feature support matrix |
| W12 distribution/Python | C++ packaging, CLI and CI configuration implemented; versioned C ABI/Python including native globals, workflows and LP evidence; local macOS arm64 wheel implemented; other platforms and executed cross-platform CI remain | Expand typed/workflow binding surface, clean platform builds and installed consumers |
| W13 quadratic/nonlinear | Bounded weighted-square continuous QP with C/Python APIs and independent primal/KKT/bound checking implemented; general Hessians, QCP, MIQP and nonlinear support remain | Broader numerical QP panels and carefully scoped convex quadratic constraints before mixed-integer/nonconvex expansion |
| W14 native parallel hybrid | Not started | Worker-local state, sound shared bounds/cuts, race/lifecycle testing and uncontended scaling measurements |
The seventh integrated checkpoint covers basis submission, Regular and C++ scenario execution, including sanitizer, installed-consumer and wheel checks. Its FAST gate passed 32 cases in 5.69 seconds external wall time. The eighth checkpoint adds LP evidence, scenario C/Python bindings and MiniZinc registration, with full sanitizer, installed-consumer and wheel gates. Its FAST gate passes all 33 cases in 5.73 seconds external wall time, including analytic ray and Farkas checks. Exact source and artifacts are listed in the validation record. The ninth checkpoint integrates selected-basis LP sensitivity with C/Python bindings and bounded native incumbent neighborhoods. It passes the enlarged 35-case FAST gate in 5.7852 seconds, all three CTest configurations, full native sanitizers and fresh installed consumers. Its bounded old/new comparison finds no repeated material case regression among five complete common-workload pairs; one additional unchanged native case hits its existing deadline. Full results and the timing limitation are in the checkpoint report. The separate learning investigation has a checked external-propagation interface experiment; it is not yet a native learning engine. Default performance selection remains outstanding. Broad capture, cold-start primal portfolios, LCG, quadratic constraints/nonlinear support, fine-grained application workflows and native parallel hybrid search remain substantial unfinished work. This ledger does not declare parity from surface API availability.
The full research/source comparison and work-package acceptance criteria remain in the workspace's planning/solver-parity-plan.md, feature-matrix.md, and research-agenda.md. This ledger records implemented scope rather than marking those larger packages complete on the strength of a few successful fixtures.
Model, result/budget and validation work first ran in independent worktrees. The next independent pieces were indicators/Boolean logic, multiobjective coordination and I/O. Each passed its own checks before cherry-picking into this branch. Reviewers then checked one another's work; concrete defects became regression tests before the integrated suite was rerun.
No compilation or solver tests started until the preexisting size-scaling run reported all 3,240 rows complete and its processes exited. Later builds used bounded parallelism. All new outputs live under the isolated implementation build directories; the existing benchmark suite was only read by the new correctness harness. The five-model checks are explicitly not performance measurements or evidence of native/commercial speed parity.