Fix #406: Add OptimalLinearArrangement satisfaction problem by zazabap · Pull Request #616 · CodingThrust/problem-reductions

zazabap · 2026-03-12T15:36:13Z

Summary

Add OptimalLinearArrangement<G> as a SatisfactionProblem with Metric = bool, following the Garey & Johnson GT42 decision formulation
Fields: graph: G and bound: usize (upper bound K on total edge length)
evaluate() checks if config is a valid permutation AND total edge length <= bound
Includes total_edge_length(), is_valid_solution(), num_vertices(), num_edges(), bound() getters
declare_variants! with complexity "2^num_vertices" (Held-Karp-style DP)
CLI dispatch registered with deser_sat, alias OLA added
Paper definition updated to satisfaction formulation
16 unit tests covering YES/NO instances, solver, serialization, edge cases

Fixes #406

Test plan

All 16 unit tests pass (cargo test optimal_linear_arrangement)
Full test suite passes (cargo test)
Clippy clean (cargo clippy --all-targets)
Formatting clean (cargo fmt -- --check)
Schemas regenerated (make export-schemas)
CI passes

Co-Authored-By: Claude Opus 4.6 <[email protected]>

- Add OptimalLinearArrangement<G> optimization problem (minimize total edge length) - Register in graph module, lib.rs prelude, CLI dispatch, alias, create command - Add 16 unit tests covering creation, evaluation, solver, serialization - Add problem-def entry in paper with display-name and references - Regenerate problem schemas JSON Co-Authored-By: Claude Opus 4.6 <[email protected]>

Co-Authored-By: Claude Opus 4.6 <[email protected]>

- Paper definition now uses {0, ..., |V|-1} to match code implementation - Removed OLA from ALIASES array (not established enough in literature) - Keep "ola" as lowercase alias in resolve_alias for convenience Co-Authored-By: Claude Opus 4.6 <[email protected]>

Co-Authored-By: Claude Opus 4.6 <[email protected]>

…nd K The issue specifies this as a decision problem (Garey & Johnson GT42): given graph G and bound K, is there a permutation f with total edge length <= K? This converts from OptimizationProblem to SatisfactionProblem with Metric = bool, adding the `bound` field as specified. Co-Authored-By: Claude Opus 4.6 <[email protected]>

zazabap · 2026-03-12T15:36:30Z

Implementation Summary

Changes

src/models/graph/optimal_linear_arrangement.rs — New model file implementing OptimalLinearArrangement<G> as a SatisfactionProblem with bound field
src/unit_tests/models/graph/optimal_linear_arrangement.rs — 16 unit tests covering basic evaluation, YES/NO instances, solver, serialization, edge cases
src/models/graph/mod.rs — Module registration and re-export
src/models/mod.rs — Re-export at models level
src/lib.rs — Added to prelude
problemreductions-cli/src/dispatch.rs — CLI dispatch with deser_sat
problemreductions-cli/src/problem_name.rs — Added OLA alias
docs/paper/reductions.typ — Updated problem definition to satisfaction formulation
docs/src/reductions/problem_schemas.json — Regenerated schemas

Deviations from Plan

The branch previously had an optimization variant (no bound field, Metric = SolutionSize<usize>). Rewrote to satisfaction formulation per issue spec (Garey & Johnson GT42 decision problem with bound K).

Open Questions

None

Copilot

Pull request overview

Adds Optimal Linear Arrangement (GT42) as a new graph satisfaction (decision) problem to the problemreductions model suite, with corresponding CLI integration, documentation/schema updates, and unit tests.

Changes:

Introduces OptimalLinearArrangement<G> as a SatisfactionProblem (boolean metric) with permutation validation and bound-check evaluation.
Registers the new problem across model exports, CLI alias/dispatch, and generated schema documentation.
Adds a dedicated unit test suite for correctness, solver behavior, and serialization.

Reviewed changes

Copilot reviewed 12 out of 12 changed files in this pull request and generated 5 comments.

Show a summary per file

File	Description
`src/models/graph/optimal_linear_arrangement.rs`	New satisfaction-problem model implementation (evaluation, helpers, schema registration, variants, tests module).
`src/unit_tests/models/graph/optimal_linear_arrangement.rs`	New unit tests covering evaluation/edge cases/solver/serde round-trip.
`src/models/graph/mod.rs`	Exposes the new model module and re-exports it.
`src/models/mod.rs`	Re-exports `OptimalLinearArrangement` at the top-level models module.
`src/lib.rs`	Adds `OptimalLinearArrangement` to the crate `prelude`.
`problemreductions-cli/src/dispatch.rs`	Adds load/serialize dispatch support for the new problem.
`problemreductions-cli/src/problem_name.rs`	Adds `OLA` alias and alias resolution.
`problemreductions-cli/src/commands/create.rs`	Adds `pred create` and `--random` support hooks for the new problem.
`problemreductions-cli/src/cli.rs`	Updates CLI help text to mention the new problem.
`docs/src/reductions/problem_schemas.json`	Adds generated schema entry for the new problem.
`docs/paper/reductions.typ`	Adds/updates paper definition text for the decision formulation.
`docs/paper/references.bib`	Adds a supporting reference for NP-completeness discussion.

💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.

Copilot · 2026-03-12T16:11:02Z

problemreductions-cli/src/commands/create.rs

+                    "{e}\n\nUsage: pred create OptimalLinearArrangement --graph 0-1,1-2,2-3"
+                )
+            })?;
+            (
+                ser(OptimalLinearArrangement::new(graph))?,


OptimalLinearArrangement::new is called with only graph, but the model constructor requires (graph, bound). This won’t compile, and even if a default were intended, the CLI needs a way to supply the decision bound K (likely via --bound or reusing --k).

Suggested change

"{e}\n\nUsage: pred create OptimalLinearArrangement --graph 0-1,1-2,2-3"

)

})?;

(

ser(OptimalLinearArrangement::new(graph))?,

"{e}\n\nUsage: pred create OptimalLinearArrangement --graph 0-1,1-2,2-3 --k K"

)

})?;

let bound = args.k.ok_or_else(|| {

anyhow::anyhow!(

"OptimalLinearArrangement requires --k (decision bound K)\n\n\

Usage: pred create OptimalLinearArrangement --graph 0-1,1-2,2-3 --k K"

)

})?;

(

ser(OptimalLinearArrangement::new(graph, bound))?,

Copilot · 2026-03-12T16:11:03Z

problemreductions-cli/src/commands/create.rs

+            let variant = variant_map(&[("graph", "SimpleGraph")]);
+            (ser(OptimalLinearArrangement::new(graph))?, variant)


Random instance generation for OptimalLinearArrangement also calls OptimalLinearArrangement::new(graph) without providing the required bound K. Decide how K should be chosen for --random (e.g., require --k/--bound, or derive a default like num_edges * (num_vertices-1)), and pass it to the constructor.

Suggested change

let variant = variant_map(&[("graph", "SimpleGraph")]);

(ser(OptimalLinearArrangement::new(graph))?, variant)

// Use a safe upper bound K = m * (n - 1), where m is the number of edges

let num_edges = graph.num_edges();

let k_bound = num_edges * num_vertices.saturating_sub(1);

let variant = variant_map(&[("graph", "SimpleGraph")]);

(ser(OptimalLinearArrangement::new(graph, k_bound))?, variant)

Copilot · 2026-03-12T16:11:03Z

problemreductions-cli/src/commands/create.rs

        "SpinGlass" => "--graph 0-1,1-2 --couplings 1,1",
        "KColoring" => "--graph 0-1,1-2,2-0 --k 3",
        "Factoring" => "--target 15 --m 4 --n 4",
+        "OptimalLinearArrangement" => "--graph 0-1,1-2,2-3",


The help/example for OptimalLinearArrangement only shows --graph, but the schema includes a bound field and the model requires a bound K. Update the example to include the bound flag you support (e.g., --bound <K> or --k <K>), and ensure the CLI args actually define that flag so pred create help matches what clap accepts.

Suggested change

"OptimalLinearArrangement" => "--graph 0-1,1-2,2-3",

"OptimalLinearArrangement" => "--graph 0-1,1-2,2-3 --bounds 3",

Copilot · 2026-03-12T16:11:04Z

problemreductions-cli/src/cli.rs

  BicliqueCover                   --left, --right, --biedges, --k
  BMF                             --matrix (0/1), --rank
  CVP                             --basis, --target-vec [--bounds]
+  OptimalLinearArrangement        --graph


This flag list says OptimalLinearArrangement --graph, but the model/schema require a bound K as well. Also, CreateArgs currently has no bound field, so if you intend --bound (as printed from schema) clap will reject it. Either add --bound: Option<usize> to CreateArgs and use it in create, or explicitly document and reuse the existing --k flag for the bound.

Suggested change

OptimalLinearArrangement --graph

OptimalLinearArrangement --graph, --k

Copilot · 2026-03-12T16:11:04Z

src/models/graph/mod.rs

 //! - [`TravelingSalesman`]: Traveling Salesman (minimum weight Hamiltonian cycle)
 //! - [`SpinGlass`]: Ising model Hamiltonian
 //! - [`BicliqueCover`]: Biclique cover on bipartite graphs
+//! - [`OptimalLinearArrangement`]: Optimal linear arrangement (minimum total edge length)


The module-level docs describe OptimalLinearArrangement as “minimum total edge length”, but this model is implemented as a decision/satisfaction problem with an explicit bound K. Consider rewording this bullet to reflect the decision formulation (e.g., “total edge length at most K”) to avoid misleading users skimming the module docs.

Suggested change

//! - [`OptimalLinearArrangement`]: Optimal linear arrangement (minimum total edge length)

//! - [`OptimalLinearArrangement`]: Optimal linear arrangement (linear arrangement with total edge length at most K)

…gration - CLI create/random now requires --bound for OptimalLinearArrangement - Updated help text and examples to include --bound - Fixed module doc to reflect decision formulation (at most K) Co-Authored-By: Claude Opus 4.6 <[email protected]>

codecov · 2026-03-14T01:16:28Z

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 96.83%. Comparing base (31ed79e) to head (4fae43c).
⚠️ Report is 3 commits behind head on main.

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #616      +/-   ##
==========================================
+ Coverage   96.81%   96.83%   +0.01%     
==========================================
  Files         244      246       +2     
  Lines       31650    31855     +205     
==========================================
+ Hits        30642    30846     +204     
- Misses       1008     1009       +1

☔ 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 OptimalLinearArrangement to trait_consistency checks - Strengthen NO instance test with brute-force verification - Fix random generation default bound formula (n-1)*num_edges Co-Authored-By: Claude Opus 4.6 <[email protected]>

GiggleLiu · 2026-03-14T01:34:29Z

Review Pipeline Report

Check	Result
Merge with main	Resolved 8 additive conflicts
Copilot comments	5 addressed (missing --bound param in CLI)
Issue/human comments	1 checked (quality check — no action needed)
Structural review	17/17 passed (trait_consistency added)
Code quality	OK (DRY, KISS, HC/LC all clean)
CI	green (all 5 checks pass)
Agentic test	passed (library API + CLI all functional)
Board	review-agentic → In Review

Fixes Applied

Merged origin/main, resolved additive conflicts in 8 files
Added --bound parameter to CLI create/random for OLA (was missing)
Updated CLI help text and examples to include --bound
Fixed module doc to reflect decision formulation ("at most K")
Added trait_consistency entry for OLA
Strengthened NO instance test with brute-force verification
Fixed random generation default bound formula ((n-1)*num_edges)

Notes

OLA is isolated in reduction graph (no incoming/outgoing reductions)
Naming follows G&J canonical name (GT42), acceptable for satisfaction problem
O*(2^n) complexity claim plausible but lacks specific OLA citation

🤖 Generated by review-pipeline

zazabap and others added 6 commits March 12, 2026 14:33

Add plan for #406: OptimalLinearArrangement

6b6cfa2

Co-Authored-By: Claude Opus 4.6 <[email protected]>

chore: remove plan file after implementation

3a4da26

Co-Authored-By: Claude Opus 4.6 <[email protected]>

fix: add OLA to ALIASES const for shell completion

12eb3ae

Co-Authored-By: Claude Opus 4.6 <[email protected]>

zazabap requested a review from Copilot March 12, 2026 16:07

Copilot started reviewing on behalf of zazabap March 12, 2026 16:08 View session

Copilot AI reviewed Mar 12, 2026

View reviewed changes

GiggleLiu and others added 2 commits March 14, 2026 08:35

Merge origin/main into PR branch, resolve additive conflicts

fa06804

GiggleLiu merged commit e73796d into main Mar 14, 2026
5 checks passed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fix #406: Add OptimalLinearArrangement satisfaction problem#616

Fix #406: Add OptimalLinearArrangement satisfaction problem#616
GiggleLiu merged 9 commits intomainfrom
issue-406-optimal-linear-arrangement

zazabap commented Mar 12, 2026

Uh oh!

zazabap commented Mar 12, 2026

Uh oh!

Copilot AI left a comment

Uh oh!

Copilot AI Mar 12, 2026

Uh oh!

Copilot AI Mar 12, 2026

Uh oh!

Copilot AI Mar 12, 2026

Uh oh!

Copilot AI Mar 12, 2026

Uh oh!

Copilot AI Mar 12, 2026

Uh oh!

codecov bot commented Mar 14, 2026 •

edited

Loading

Uh oh!

GiggleLiu commented Mar 14, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

-                    "{e}\n\nUsage: pred create OptimalLinearArrangement --graph 0-1,1-2,2-3"
-                )
-            })?;
-            (
-                ser(OptimalLinearArrangement::new(graph))?,
+                    "{e}\n\nUsage: pred create OptimalLinearArrangement --graph 0-1,1-2,2-3 --k K"
+                )
+            })?;
+            let bound = args.k.ok_or_else(|| {
+                anyhow::anyhow!(
+                    "OptimalLinearArrangement requires --k (decision bound K)\n\n\
+                     Usage: pred create OptimalLinearArrangement --graph 0-1,1-2,2-3 --k K"
+                )
+            })?;
+            (
+                ser(OptimalLinearArrangement::new(graph, bound))?,

		let variant = variant_map(&[("graph", "SimpleGraph")]);
		(ser(OptimalLinearArrangement::new(graph))?, variant)

-            let variant = variant_map(&[("graph", "SimpleGraph")]);
-            (ser(OptimalLinearArrangement::new(graph))?, variant)
+            // Use a safe upper bound K = m * (n - 1), where m is the number of edges
+            let num_edges = graph.num_edges();
+            let k_bound = num_edges * num_vertices.saturating_sub(1);
+            let variant = variant_map(&[("graph", "SimpleGraph")]);
+            (ser(OptimalLinearArrangement::new(graph, k_bound))?, variant)

	"OptimalLinearArrangement" => "--graph 0-1,1-2,2-3",
	"OptimalLinearArrangement" => "--graph 0-1,1-2,2-3 --bounds 3",

	OptimalLinearArrangement --graph
	OptimalLinearArrangement --graph, --k

	//! - [`OptimalLinearArrangement`]: Optimal linear arrangement (minimum total edge length)
	//! - [`OptimalLinearArrangement`]: Optimal linear arrangement (linear arrangement with total edge length at most K)

Conversation

zazabap commented Mar 12, 2026

Summary

Test plan

Uh oh!

zazabap commented Mar 12, 2026

Implementation Summary

Changes

Deviations from Plan

Open Questions

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Reviewed changes

Uh oh!

Copilot AI Mar 12, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Mar 12, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Mar 12, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Mar 12, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Mar 12, 2026

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Codecov Report

Uh oh!

GiggleLiu commented Mar 14, 2026

Review Pipeline Report

Fixes Applied

Notes

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

codecov bot commented Mar 14, 2026 •

edited

Loading