Fix #185: [Rule] MinimumMultiwayCut to ILP by GiggleLiu · Pull Request #693 · CodingThrust/problem-reductions

GiggleLiu · 2026-03-17T17:22:47Z

Summary

Add reduction rule from MinimumMultiwayCut to ILP using the standard vertex-assignment + edge-cut indicator formulation (Chopra & Owen 1996). The ILP uses kn + m binary variables and n + 2km constraints.

Fixes #185

codecov · 2026-03-17T17:24:40Z

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 97.22%. Comparing base (90977d7) to head (019be17).
⚠️ Report is 1 commits behind head on main.

Additional details and impacted files

@@           Coverage Diff            @@
##             main     #693    +/-   ##
========================================
  Coverage   97.21%   97.22%            
========================================
  Files         312      314     +2     
  Lines       40734    40877   +143     
========================================
+ Hits        39600    39743   +143     
  Misses       1134     1134

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

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

Add vertex-assignment + edge-cut indicator ILP formulation (Chopra & Owen 1996) with kn+m binary variables and n+2km+k^2 constraints. Includes 6 unit tests (closed-loop, triangle, 2-terminal, extraction, solve_reduced), canonical example-db entry, paper documentation, and bib reference.

GiggleLiu · 2026-03-17T17:44:35Z

Implementation Summary

Changes

src/rules/minimummultiwaycut_ilp.rs — Reduction from MinimumMultiwayCut<SimpleGraph, i32> to ILP using vertex-assignment + edge-cut indicator formulation (Chopra & Owen 1996)
src/unit_tests/rules/minimummultiwaycut_ilp.rs — 6 unit tests (structure validation, closed-loop, triangle, 2-terminal, manual extraction, solve_reduced)
src/rules/mod.rs — Module registration and example-db integration
src/example_db/fixtures/examples.json — Regenerated with new canonical example
docs/src/reductions/reduction_graph.json — Updated graph export
docs/paper/reductions.typ — Added reduction-rule entry with construction, correctness, and solution extraction
docs/paper/references.bib — Added Chopra & Owen (1996) citation

Deviations from Plan

Terminal fixing uses equality constraints (k² extra) instead of variable bounds, since the ILP model doesn't support per-variable bounds directly. Overhead formula updated to n + 2km + k² (issue says n + 2km assuming bounds).

Open Questions

None

GiggleLiu · 2026-03-17T19:31:51Z

Agentic Review Report

Structural Check

Item	Status	Details
`mod.rs` registration	PASS	`pub(crate) mod minimummultiwaycut_ilp;` under `#[cfg(feature = "ilp-solver")]`
Reduction trait impl	PASS	`impl ReduceTo<ILP<bool>> for MinimumMultiwayCut<SimpleGraph, i32>` with `type Result = ReductionMMCToILP`
Overhead annotation	PASS	`num_vars = "num_terminals * num_vertices + num_edges"`, `num_constraints = "num_vertices + 2 * num_terminals * num_edges + num_terminals * num_terminals"` — matches code
Test file	PASS	6 tests covering structure, closed-loop, triangle, 2-terminal, extraction, solve_reduced
Paper entry	PASS	`#reduction-rule("MinimumMultiwayCut", "ILP")` with citation `@chopra1996`
example_db entry	PASS	`canonical_rule_example_specs()` defined and registered
`#[path]` test link	PASS	Correct path annotation
reduction_graph.json	PASS	Edge source=47 → target=16 with correct overhead formulas
examples.json fixture	PASS	21 vars, 50 constraints; solution extraction verified
Whitelist check	FAIL (expected)	Supporting files outside rule whitelist — all legitimate

Build: make build PASS, make clippy PASS

Semantic Review — Mathematical Correctness:

Variable layout (y_{iv} at i·n+v, x_e at kn+e): correct
Partition constraints (n): correct
Terminal fixing via explicit Eq constraints (k²): correct — ILP struct has no bounds field, so uses constraints instead of variable bounds
Edge-cut linking (2km): correct — forces x_e=1 for cross-component edges
Objective (minimize Σ w_e · x_e): correct
extract_solution: correctly extracts target_solution[kn..kn+m]
Overhead formulas: verified against actual constructed sizes (k² + n + 2km = 50 for canonical example)

Issue Compliance:

Spec item	Issue #185	Implementation	Status
Source	MinimumMultiwayCut<SimpleGraph, i32>	Same	PASS
Target	ILP<bool>	Same	PASS
Variables	kn + m = 21	21	PASS
Constraint count	n + 2km = 41 (terminal fixing via bounds)	n + 2km + k² = 50 (terminal fixing via constraints)	MINOR DEVIATION
Formulation	Chopra & Owen (1996)	Same	PASS
Example optimal cost	8	8	PASS

Issues:

Severity	Location	Description
MEDIUM	`src/rules/minimummultiwaycut_ilp.rs`	`num_constraints` overhead is n + 2km + k² but issue #185 specifies n + 2km. Implementation is self-consistent and correct — divergence is because ILP struct lacks variable bounds, so terminals are fixed via explicit equality constraints. Paper correctly states k² + n + 2km.
MINOR	`docs/paper/reductions.typ:3345`	Extra closing parenthesis in `x^_(k n + "idx"))` — should be `x^_(k n + "idx")`
INFO	`problemreductions-cli/src/commands/create.rs`	Unrelated blank-line removal. Harmless.

Quality Check

Design Principles:

DRY: OK — canonical instance duplication between test helper and example_db builder is tolerable (different concerns)
KISS: OK — two sequential terminal-fixing loops could be merged into one (style only)
Cohesion/Coupling: Good — ReductionMMCToILP stores exactly the 3 fields needed (n, m, k); file is self-contained

Overhead Consistency: PASS — formulas verified against actual output

Test Quality: 6 tests covering structure, closed-loop, triangle (k=3=n), 2-terminal (degenerate), manual extraction, solve_reduced. Missing: no test for objective coefficient structure (weights → ILP objective variable indices). Compare with test_reduction_weighted in other ILP reductions.

Issues:

Severity	Location	Description
style	`src/rules/minimummultiwaycut_ilp.rs:77-88`	Two sequential terminal-fixing loops can be merged into one
style	`docs/paper/reductions.typ:3345`	Extra closing parenthesis in Typst math
minor	`src/unit_tests/rules/minimummultiwaycut_ilp.rs`	No test for objective coefficient structure

Overall: Good. Correct, well-commented, follows project conventions. Nothing blocks merge.

Agentic Feature Tests

#	Test	Command	Status	Notes
1	Catalog presence	`pred list \| grep -i multiway`	PASS	Listed with correct complexity
2	Show details	`pred show MinimumMultiwayCut`	PASS	Variants, reductions display correctly
3	ILP incoming	`pred show ILP`	PASS	MinimumMultiwayCut appears in incoming reductions
4	Example creation	`pred create --example MinimumMultiwayCut`	PASS	Valid 5-vertex, 6-edge, 3-terminal instance
5	Direct solve	`pred solve instance.json`	PASS	Returns Valid(8), solution [1,0,0,1,1,0]
6	Reduce to ILP	`pred reduce instance.json --to ILP`	PASS	21 variables, 50 constraints
7	Solve reduced	`pred solve reduced.json`	PASS	ILP objective Valid(8.0), extracted [1,0,0,1,1,0]
8	Closed-loop	Compare steps 5 & 7	PASS	Identical values and solutions
9	Overhead verification	Formula vs actual	PASS	Both formulas exact
10	Unit tests (model)	`cargo test minimum_multiway_cut`	PASS	16/16 pass
11	Unit tests (rule)	`cargo test minimummultiwaycut_to_ilp`	PASS	All pass

Issues found: None. Feature works end-to-end.

Generated by review-pipeline

Resolve conflicts in references.bib, rules/mod.rs, and examples.json. Regenerated fixtures with all rule examples. Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

Add plan for #185: MinimumMultiwayCut to ILP

1059193

zazabap and others added 2 commits March 18, 2026 12:26

Merge origin/main into issue-185

5d070df

Resolve conflicts in references.bib, rules/mod.rs, and examples.json. Regenerated fixtures with all rule examples. Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

fix: remove extra closing parenthesis in paper reduction-rule entry

019be17

Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

zazabap approved these changes Mar 18, 2026

View reviewed changes

zazabap merged commit 3b71c18 into main Mar 18, 2026
3 checks passed

GiggleLiu deleted the issue-185 branch April 12, 2026 00:51

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fix #185: [Rule] MinimumMultiwayCut to ILP#693

Fix #185: [Rule] MinimumMultiwayCut to ILP#693
zazabap merged 4 commits intomainfrom
issue-185

GiggleLiu commented Mar 17, 2026

Uh oh!

codecov bot commented Mar 17, 2026 •

edited

Loading

Uh oh!

GiggleLiu commented Mar 17, 2026

Uh oh!

GiggleLiu commented Mar 17, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Conversation

GiggleLiu commented Mar 17, 2026

Summary

Uh oh!

codecov bot commented Mar 17, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

GiggleLiu commented Mar 17, 2026

Implementation Summary

Changes

Deviations from Plan

Open Questions

Uh oh!

GiggleLiu commented Mar 17, 2026

Agentic Review Report

Structural Check

Quality Check

Agentic Feature Tests

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

codecov bot commented Mar 17, 2026 •

edited

Loading