Problem
Graph and set representations do not consistently express the mathematical domains assumed by models and reductions. Establish those domains before changing loop, parallel-edge, or duplicate-element handling. This is separate from making existing model construction checks apply consistently to Rust, CLI/MCP creation, and persisted JSON.
Audit baseline: branch refactor/native-ilp-adapter, commit 597ba9fc3741ad8d65367759276774fcccf93465; related work: #1147 and #1145. Recheck the current implementation before changing it.
Concrete failures and conflicting requirements
-
SimpleGraph permits loops and parallel edges. A one-vertex looped MaximumIndependentSet instance has only the empty independent set. The MaximumIndependentSet -> MaximumClique complement construction loses the loop; the target's optimal singleton maps to an invalid source independent set. The simple-graph creation schema rejects loops, while direct construction accepts them.
-
MaximumSetPacking accepts an inner vector [0, 0]. Model evaluation treats it as one selected set with value 1 for unit weight. The ILP construction counts both occurrences, produces 2*x <= 1, and excludes that selection. The model and reduction disagree about whether an inner vector represents a mathematical set or a multiset.
-
A blanket prohibition or deduplication is not a safe repair: TravelingSalesman currently represents a one-vertex tour with a loop and a two-vertex tour with two parallel edges. Its QUBO reduction explicitly handles these cases. Removing parallel edges can also change weights and edge-index witnesses.
-
PlanarGraph currently checks only the necessary Euler edge bound, not planarity. For example, K3,3 passes that bound but is nonplanar. Decide whether this type promises actual planarity, then use an established planarity implementation if that promise is retained; constructor/Serde consistency alone cannot establish the mathematical property.
Relevant implementation paths: src/topology/graph.rs, src/models/graph/maximum_independent_set.rs, src/rules/maximumindependentset_maximumclique.rs, src/models/set/maximum_set_packing.rs, src/rules/maximumsetpacking_ilp.rs, and src/rules/travelingsalesman_qubo.rs.
Work
- Inventory the graph/set contracts actually used by model evaluation, constructors, and outgoing reductions. State where loops, parallel edges, and repeated inner-set elements are permitted, rejected, or canonically represented. Distinguish repeated elements inside a set from distinct selectable entries in a set family.
- Resolve conflicting mathematical definitions with the maintainer before changing accepted instances. Document each affected model's domain and each reduction's applicability assumptions.
- Enforce the agreed conditions in the owning topology/model construction paths; update affected rules to satisfy their declared domain. Use existing Rust types and dependency facilities where they preserve the chosen semantics. Do not introduce a generic validation framework or solver-output repair gate.
- Update callers and mathematical documentation together. Preserve edge/entry identity and weights wherever they are part of a witness; do not silently deduplicate or drop input.
Acceptance
- The looped independent-set and repeated-element set-packing examples are either explicitly rejected at construction under the agreed domain, or handled correctly by every applicable reduction.
- Small exhaustive tests compare source optima with target optima and check extraction for every tied qualifying target witness on affected boundary cases.
- Rust construction, CLI/MCP creation, and persisted JSON agree on the chosen domain.
- Existing one-/two-vertex tour semantics are explicitly retained or deliberately replaced with corresponding documentation and tests.
- No solver-specific tolerances, extraction-time feasibility patches, verifier infrastructure, or unrelated numerical refactors are included.
Problem
Graph and set representations do not consistently express the mathematical domains assumed by models and reductions. Establish those domains before changing loop, parallel-edge, or duplicate-element handling. This is separate from making existing model construction checks apply consistently to Rust, CLI/MCP creation, and persisted JSON.
Audit baseline: branch
refactor/native-ilp-adapter, commit597ba9fc3741ad8d65367759276774fcccf93465; related work: #1147 and #1145. Recheck the current implementation before changing it.Concrete failures and conflicting requirements
SimpleGraphpermits loops and parallel edges. A one-vertex looped MaximumIndependentSet instance has only the empty independent set. The MaximumIndependentSet -> MaximumClique complement construction loses the loop; the target's optimal singleton maps to an invalid source independent set. The simple-graph creation schema rejects loops, while direct construction accepts them.MaximumSetPacking accepts an inner vector
[0, 0]. Model evaluation treats it as one selected set with value 1 for unit weight. The ILP construction counts both occurrences, produces2*x <= 1, and excludes that selection. The model and reduction disagree about whether an inner vector represents a mathematical set or a multiset.A blanket prohibition or deduplication is not a safe repair: TravelingSalesman currently represents a one-vertex tour with a loop and a two-vertex tour with two parallel edges. Its QUBO reduction explicitly handles these cases. Removing parallel edges can also change weights and edge-index witnesses.
PlanarGraphcurrently checks only the necessary Euler edge bound, not planarity. For example, K3,3 passes that bound but is nonplanar. Decide whether this type promises actual planarity, then use an established planarity implementation if that promise is retained; constructor/Serde consistency alone cannot establish the mathematical property.Relevant implementation paths:
src/topology/graph.rs,src/models/graph/maximum_independent_set.rs,src/rules/maximumindependentset_maximumclique.rs,src/models/set/maximum_set_packing.rs,src/rules/maximumsetpacking_ilp.rs, andsrc/rules/travelingsalesman_qubo.rs.Work
Acceptance