Fix #399: Add MinSumMulticenter model#635
Merged
Conversation
Codecov Report✅ All modified and coverable lines are covered by tests. Additional details and impacted files@@ Coverage Diff @@
## main #635 +/- ##
==========================================
+ Coverage 96.79% 96.82% +0.03%
==========================================
Files 234 236 +2
Lines 30743 31002 +259
==========================================
+ Hits 29757 30017 +260
+ Misses 986 985 -1 ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
Add the MinSumMulticenter problem — a facility location optimization problem that minimizes total weighted distance from vertices to K selected centers. Includes graph + vertex weights + edge lengths input, Bellman-Ford shortest path computation, CLI support, and comprehensive unit tests (19 tests including solver, serialization, edge cases). Co-Authored-By: Claude Opus 4.6 <[email protected]>
Collaborator
Author
Implementation SummaryChanges
Deviations from Plan
Open Questions
|
There was a problem hiding this comment.
Pull request overview
Adds a new graph optimization model, MinSumMulticenter (p-median), and wires it into the library exports and CLI so instances can be created/serialized and solved (e.g., via BruteForce).
Changes:
- Introduces
MinSumMulticentermodel with schema registration, evaluation, and variant declaration. - Exposes the model via
modelsmodules + crateprelude, and adds CLI alias/dispatch/create support. - Adds a dedicated unit test suite covering creation, evaluation, solver behavior, and serialization.
Reviewed changes
Copilot reviewed 8 out of 8 changed files in this pull request and generated 5 comments.
Show a summary per file
| File | Description |
|---|---|
src/models/graph/min_sum_multicenter.rs |
New p-median model implementation, schema registration, and variant declaration |
src/models/graph/mod.rs |
Registers the new graph model module and re-export |
src/models/mod.rs |
Re-exports MinSumMulticenter at the top-level models module |
src/lib.rs |
Adds MinSumMulticenter to the crate prelude exports |
src/unit_tests/models/graph/min_sum_multicenter.rs |
Adds unit tests for evaluation logic, solver integration, and serde roundtrip |
problemreductions-cli/src/problem_name.rs |
Adds pmedian alias and canonical name resolution |
problemreductions-cli/src/dispatch.rs |
Enables load/serialize dispatch for MinSumMulticenter<SimpleGraph, i32> |
problemreductions-cli/src/commands/create.rs |
Adds pred create MinSumMulticenter ... support and CLI example string |
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
Comment on lines
+132
to
+160
| /// Compute shortest distances from each vertex to the nearest center. | ||
| /// | ||
| /// Uses multi-source Dijkstra: initializes all centers at distance 0 | ||
| /// and relaxes edges using edge lengths. | ||
| /// | ||
| /// Returns `None` if any vertex is unreachable from all centers. | ||
| fn shortest_distances(&self, config: &[usize]) -> Option<Vec<W::Sum>> { | ||
| let n = self.graph.num_vertices(); | ||
| let edges = self.graph.edges(); | ||
|
|
||
| // Build adjacency list: for each vertex, list of (neighbor, edge_length) | ||
| let mut adj: Vec<Vec<(usize, W::Sum)>> = vec![Vec::new(); n]; | ||
| for (idx, &(u, v)) in edges.iter().enumerate() { | ||
| let len = self.edge_lengths[idx].to_sum(); | ||
| adj[u].push((v, len.clone())); | ||
| adj[v].push((u, len)); | ||
| } | ||
|
|
||
| // Multi-source Bellman-Ford: initialize all centers at distance 0 | ||
| let mut dist: Vec<Option<W::Sum>> = vec![None; n]; | ||
| for (v, &selected) in config.iter().enumerate() { | ||
| if selected == 1 { | ||
| dist[v] = Some(W::Sum::zero()); | ||
| } | ||
| } | ||
|
|
||
| // Repeated relaxation until convergence (Bellman-Ford style) | ||
| let mut changed = true; | ||
| while changed { |
Comment on lines
+158
to
+179
| // Repeated relaxation until convergence (Bellman-Ford style) | ||
| let mut changed = true; | ||
| while changed { | ||
| changed = false; | ||
| for v in 0..n { | ||
| let dv = match &dist[v] { | ||
| Some(d) => d.clone(), | ||
| None => continue, | ||
| }; | ||
| for &(u, ref len) in &adj[v] { | ||
| let new_dist = dv.clone() + len.clone(); | ||
| let update = match &dist[u] { | ||
| None => true, | ||
| Some(du) => new_dist < *du, | ||
| }; | ||
| if update { | ||
| dist[u] = Some(new_dist); | ||
| changed = true; | ||
| } | ||
| } | ||
| } | ||
| } |
Comment on lines
+237
to
+239
| crate::declare_variants! { | ||
| MinSumMulticenter<SimpleGraph, i32> => "2^num_vertices", | ||
| } |
Comment on lines
+506
to
+530
| // MinSumMulticenter (p-median) | ||
| "MinSumMulticenter" => { | ||
| let (graph, n) = parse_graph(args).map_err(|e| { | ||
| anyhow::anyhow!( | ||
| "{e}\n\nUsage: pred create MinSumMulticenter --graph 0-1,1-2,2-3 [--weights 1,1,1,1] [--edge-weights 1,1,1] --k 2" | ||
| ) | ||
| })?; | ||
| let vertex_weights = parse_vertex_weights(args, n)?; | ||
| let edge_lengths = parse_edge_weights(args, graph.num_edges())?; | ||
| let k = args.k.ok_or_else(|| { | ||
| anyhow::anyhow!( | ||
| "MinSumMulticenter requires --k (number of centers)\n\n\ | ||
| Usage: pred create MinSumMulticenter --graph 0-1,1-2,2-3 --k 2" | ||
| ) | ||
| })?; | ||
| ( | ||
| ser(MinSumMulticenter::new( | ||
| graph, | ||
| vertex_weights, | ||
| edge_lengths, | ||
| k, | ||
| ))?, | ||
| resolved_variant.clone(), | ||
| ) | ||
| } |
| let new_dist = dv.clone() + len.clone(); | ||
| let update = match &dist[u] { | ||
| None => true, | ||
| Some(du) => new_dist < *du, |
Resolve conflicts in module registrations by keeping both MinSumMulticenter (this PR) and new models from main (PartitionIntoTriangles, RuralPostman, SubgraphIsomorphism). Co-Authored-By: Claude Opus 4.6 <[email protected]>
- Fix docstring: "multi-source Dijkstra" → "multi-source Bellman-Ford" - Add iteration cap (n-1) to prevent non-termination with negative edges - Fix potential borrow issue: clone du instead of dereferencing - Add MCP tools support (create_problem_inner + create_random_inner) - Regenerate problem_schemas.json to include MinSumMulticenter Co-Authored-By: Claude Opus 4.6 <[email protected]>
Per issue #399 and human review comment, the naming convention requires the full "Minimum" prefix (matching MinimumVertexCover, MinimumDominatingSet, etc.). Rename struct, files, module paths, CLI aliases, and regenerate schemas. Co-Authored-By: Claude Opus 4.6 <[email protected]>
Collaborator
Author
Review Pipeline Report
🤖 Generated by review-pipeline |
Resolve merge conflicts to include both MinimumSumMulticenter (from this PR branch) and MinimumFeedbackArcSet (from main) in shared files: src/models/graph/mod.rs, src/models/mod.rs, src/lib.rs, problemreductions-cli/src/problem_name.rs, and problemreductions-cli/src/commands/create.rs. Co-Authored-By: Claude Opus 4.6 <[email protected]>
Co-Authored-By: Claude Opus 4.6 <[email protected]>
There was a problem hiding this comment.
Pull request overview
Adds a new graph optimization model, MinimumSumMulticenter (p-median), and wires it through the library exports, CLI/MCP creation, and documentation schema so it can be instantiated/serialized and solved (e.g., via brute force).
Changes:
- Introduces
MinimumSumMulticentermodel with evaluation logic and variant declaration. - Adds unit tests covering creation, evaluation, edge cases, brute-force solving, and serde round-trip.
- Integrates the model into CLI/MCP (aliases, dispatch, create) and updates docs schema/paper.
Reviewed changes
Copilot reviewed 11 out of 11 changed files in this pull request and generated 8 comments.
Show a summary per file
| File | Description |
|---|---|
| src/models/graph/minimum_sum_multicenter.rs | New p-median model implementation + schema registration + variants. |
| src/unit_tests/models/graph/minimum_sum_multicenter.rs | Unit tests for correctness, edge cases, solver integration, and serialization. |
| src/models/graph/mod.rs | Registers the new graph model module and re-export. |
| src/models/mod.rs | Re-exports the new model at the top-level models module. |
| src/lib.rs | Adds the new model to the public prelude. |
| problemreductions-cli/src/problem_name.rs | Adds pmedian alias + alias resolution for the canonical name. |
| problemreductions-cli/src/dispatch.rs | Enables load/serialize dispatch for the new problem type. |
| problemreductions-cli/src/commands/create.rs | Adds pred create MinimumSumMulticenter ... support. |
| problemreductions-cli/src/mcp/tools.rs | Adds MCP create + random generation support and edge-length parsing helper. |
| docs/src/reductions/problem_schemas.json | Adds schema entry for MinimumSumMulticenter (and includes PartitionIntoTriangles). |
| docs/paper/reductions.typ | Adds paper definition + display-name entry for MinimumSumMulticenter. |
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
Comment on lines
+139
to
+149
| fn shortest_distances(&self, config: &[usize]) -> Option<Vec<W::Sum>> { | ||
| let n = self.graph.num_vertices(); | ||
| let edges = self.graph.edges(); | ||
|
|
||
| // Build adjacency list: for each vertex, list of (neighbor, edge_length) | ||
| let mut adj: Vec<Vec<(usize, W::Sum)>> = vec![Vec::new(); n]; | ||
| for (idx, &(u, v)) in edges.iter().enumerate() { | ||
| let len = self.edge_lengths[idx].to_sum(); | ||
| adj[u].push((v, len.clone())); | ||
| adj[v].push((u, len)); | ||
| } |
| "MinimumSumMulticenter requires --k (number of centers)\n\n\ | ||
| Usage: pred create MinimumSumMulticenter --graph 0-1,1-2,2-3 --k 2" | ||
| ) | ||
| })?; |
| .map(|v| v as usize) | ||
| .ok_or_else(|| { | ||
| anyhow::anyhow!("MinimumSumMulticenter requires 'k' (number of centers)") | ||
| })?; |
Comment on lines
+668
to
+672
| let k = params | ||
| .get("k") | ||
| .and_then(|v| v.as_u64()) | ||
| .map(|v| v as usize) | ||
| .unwrap_or(1.max(num_vertices / 3)); |
Comment on lines
+359
to
+361
| "name": "MinimumSumMulticenter", | ||
| "description": "Find K centers minimizing total weighted distance (p-median problem)", | ||
| "fields": [ |
| "MinimumFeedbackVertexSet": [Minimum Feedback Vertex Set], | ||
| "MinimumSumMulticenter": [Minimum Sum Multicenter], | ||
| "SubgraphIsomorphism": [Subgraph Isomorphism], | ||
| "SubsetSum": [Subset Sum], |
| // MinimumSumMulticenter (p-median) | ||
| "MinimumSumMulticenter" => { | ||
| let (graph, n) = parse_graph_from_params(params)?; | ||
| let vertex_weights = parse_vertex_weights_from_params(params, n)?; |
Comment on lines
+206
to
+207
| // Check exactly K centers are selected | ||
| let num_selected: usize = config.iter().sum(); |
Co-Authored-By: Claude Opus 4.6 <[email protected]>
…/problem-reductions into issue-399-minsummulticenter
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Add the MinSumMulticenter (p-median) problem model — a classical NP-complete facility location problem that minimizes total weighted distance from vertices to K selected centers.
Fixes #399