Fix #417: Add ConsecutiveOnesSubmatrix model by GiggleLiu · Pull Request #667 · CodingThrust/problem-reductions

GiggleLiu · 2026-03-16T12:06:19Z

Summary

Add ConsecutiveOnesSubmatrix model — a satisfaction (decision) problem from Garey & Johnson A4 SR14. Given an m×n binary matrix and integer K, determines whether K columns can be selected and permuted so that each row's 1-entries are consecutive.

Fixes #417

codecov · 2026-03-16T12:08:29Z

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 97.31%. Comparing base (0b93e1e) to head (63a1591).
⚠️ Report is 9 commits behind head on main.

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #667      +/-   ##
==========================================
+ Coverage   97.28%   97.31%   +0.03%     
==========================================
  Files         322      324       +2     
  Lines       41598    41853     +255     
==========================================
+ Hits        40470    40731     +261     
+ Misses       1128     1122       -6

☔ 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 satisfaction problem for the Consecutive Ones Submatrix problem (Garey & Johnson A4 SR14): given an m×n binary matrix and bound K, decide if K columns can be selected and permuted so each row's 1-entries are consecutive (C1P). - Model in src/models/algebraic/ with Heap's algorithm for permutations - 14 unit tests including Tucker matrix examples - CLI support (pred create ConsecutiveOnesSubmatrix --matrix --k) - Paper entry with CeTZ figure and bibliography - Trait consistency and example_db registration Co-Authored-By: Claude Opus 4.6 <[email protected]>

GiggleLiu · 2026-03-16T12:25:57Z

Implementation Summary

Changes

src/models/algebraic/consecutive_ones_submatrix.rs — New satisfaction problem model (ConsecutiveOnesSubmatrix). Uses Heap's algorithm to enumerate all K! permutations of selected columns and check each row's 1-entries are contiguous (C1P).
src/unit_tests/models/algebraic/consecutive_ones_submatrix.rs — 14 unit tests covering evaluation, brute force solving, serialization, edge cases (K=0, wrong config length, invalid values), and panic tests.
src/models/algebraic/mod.rs / src/models/mod.rs — Module registration and re-export.
src/unit_tests/trait_consistency.rs — Added trait consistency check.
problemreductions-cli/src/commands/create.rs — CLI pred create support with --matrix and --k flags.
problemreductions-cli/src/cli.rs — Help text updated.
docs/paper/reductions.typ — Problem definition entry with formal definition, background (C1P, PQ-trees, Booth & Lueker), complexity note, Tucker matrix example, and CeTZ figure.
docs/paper/references.bib — Added Booth 1975 (PhD thesis) and Booth & Lueker 1976 bibliography entries.
src/example_db/fixtures/examples.json — Regenerated (33 model examples).
docs/src/reductions/problem_schemas.json — Regenerated (42 schemas).

Deviations from Plan

Tucker matrix paper example assertion corrected: only 2 of 4 three-column subsets have C1P (not 4 as initially assumed). Verified by manual analysis.

Open Questions

None

Copilot

Pull request overview

Adds a new algebraic satisfaction model, ConsecutiveOnesSubmatrix, to the core library, along with CLI support, examples/fixtures, tests, and regenerated schema/reduction-graph documentation.

Changes:

Implement ConsecutiveOnesSubmatrix model (schema registration, evaluation, variants, example-db spec).
Add unit tests and wire the model into trait-consistency checks and module re-exports.
Integrate with CLI pred create, example fixtures, and regenerate docs JSON / paper references & section.

Reviewed changes

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

Show a summary per file

File	Description
src/unit_tests/trait_consistency.rs	Adds trait/dims sanity check coverage for the new model.
src/unit_tests/models/algebraic/consecutive_ones_submatrix.rs	Introduces model-specific unit tests, brute-force solver checks, and serialization tests.
src/models/mod.rs	Re-exports `ConsecutiveOnesSubmatrix` from the `models` top-level module.
src/models/algebraic/mod.rs	Registers the new algebraic module and adds example-db spec wiring.
src/models/algebraic/consecutive_ones_submatrix.rs	Implements the model, registers schema metadata, declares variants, and adds example-db entry + tests module.
src/example_db/fixtures/examples.json	Adds a fixture instance + sample/optimal configs for the new model.
problemreductions-cli/src/commands/create.rs	Adds `pred create ConsecutiveOnesSubmatrix` instance construction via `--matrix` and `--k`.
problemreductions-cli/src/cli.rs	Documents the new problem’s CLI flags in the help text.
docs/src/reductions/reduction_graph.json	Adds the model node to the generated reduction graph docs (including shifted indices).
docs/src/reductions/problem_schemas.json	Adds the model schema to the generated schema docs.
docs/paper/references.bib	Adds Booth (1975) and Booth–Lueker (1976) references.
docs/paper/reductions.typ	Adds a paper definition + worked example/figure block for the model.

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

src/models/algebraic/consecutive_ones_submatrix.rs

+    /// Check if any permutation of the given columns has C1P.
+    fn any_permutation_has_c1p(&self, cols: &[usize]) -> bool {
+        let k = cols.len();
+        if k == 0 {
+            return true;
+        }
+        let mut perm: Vec<usize> = cols.to_vec();
+        // Generate all permutations using Heap's algorithm
+        let mut c = vec![0usize; k];
+        if self.has_c1p(&perm) {
+            return true;
+        }
+        let mut i = 0;
+        while i < k {
+            if c[i] < i {
+                if i % 2 == 0 {
+                    perm.swap(0, i);
+                } else {
+                    perm.swap(c[i], i);
+                }
+                if self.has_c1p(&perm) {
+                    return true;
+                }
+                c[i] += 1;
+                i = 0;
+            } else {
+                c[i] = 0;
+                i += 1;
+            }
+        }
+        false
+    }


src/models/algebraic/consecutive_ones_submatrix.rs

+impl SatisfactionProblem for ConsecutiveOnesSubmatrix {}
+
+crate::declare_variants! {
+    default sat ConsecutiveOnesSubmatrix => "2^(num_cols) * num_rows",


docs/paper/reductions.typ

+  let selected = cfg.enumerate().filter(((i, v)) => v == 1).map(((i, v)) => i)
+  [
+    #problem-def("ConsecutiveOnesSubmatrix")[
+      Given an $m times n$ binary matrix $A$ and a positive integer $K <= n$, determine whether there exists a subset of $K$ columns of $A$ whose columns can be permuted so that in each row all 1's occur consecutively (the _consecutive ones property_).


src/models/algebraic/consecutive_ones_submatrix.rs

+//! Given an m×n binary matrix A and a positive integer K ≤ n, determine whether
+//! there exists a subset of K columns whose columns can be permuted so that in
+//! each row all 1's occur consecutively. NP-complete (Booth, 1975) via
+//! transformation from Hamiltonian Path.


…17-consecutive-ones-submatrix # Conflicts: # docs/paper/reductions.typ # docs/src/reductions/problem_schemas.json # docs/src/reductions/reduction_graph.json # problemreductions-cli/src/commands/create.rs # src/example_db/fixtures/examples.json

GiggleLiu · 2026-03-18T01:06:40Z

Agentic Review Report

Note: This PR has merge conflicts with main. These must be resolved before merging (handled in final-review Step 1).

Structural Check

#	Check	Status
1	Model file exists (`src/models/algebraic/consecutive_ones_submatrix.rs`)	PASS
2	`inventory::submit!` present	PASS
3	`#[derive(...Serialize, Deserialize)]` on struct	PASS
4	`Problem` trait impl	PASS
5	`SatisfactionProblem` impl	PASS
6	`#[cfg(test)]` + `#[path = "..."]` test link	PASS
7	Test file exists (`src/unit_tests/models/algebraic/consecutive_ones_submatrix.rs`)	PASS
8	Test file has >= 3 test functions	PASS — 19 test functions
9	Registered in `algebraic/mod.rs`	PASS
10	Re-exported in `models/mod.rs`	PASS
11	`declare_variants!` entry exists	PASS
12	CLI `resolve_alias` entry	PASS
13	CLI `create` support	PASS
14	Canonical model example registered	PASS
15	Paper `display-name` entry	PASS
16	Paper `problem-def` block	PASS

16/16 structural checks passed.

Build: make test PASS, make clippy PASS

Whitelist violations: 6 files flagged — all justified and standard for a model PR (references.bib, cli.rs, create.rs, cli_tests.rs, examples.json, trait_consistency.rs).

Issue compliance (vs #417): 9/10 passed. One justified deviation: complexity string "2^(num_cols) * factorial(bound_k) * num_rows" is more precise than issue's "2^(num_cols) * num_rows" — accurately reflects the brute-force evaluator's permutation enumeration cost.

Semantic review highlights:

evaluate() correctness: OK — validates config length, variable values, column count, then checks all permutations via Heap's algorithm
has_c1p() correctness: OK — first/last/count approach correctly checks consecutiveness
Constructor validation: OK — asserts bound_k <= n and consistent row lengths
Canonical example (Tucker 3×4 matrix, K=3): verified correct — both solutions [1,1,0,1] and [1,0,1,1] manually confirmed
Paper entry: OK — clear definition, historical context (Booth 1975, PQ-trees), data-driven CeTZ figure

Suggestions (nice to have):

src/models/algebraic/mod.rs lines 3-7: module docstring lists 4 problems but omits ConsecutiveOnesSubmatrix

Quality Check

Design principles: DRY OK, KISS OK, HC/LC OK

HCI (CLI changed):

Error messages: OK — actionable messages with usage examples
Discoverability: OK — listed in help text
Consistency: OK — follows BMF/SetBasis patterns (--matrix, --k)
Least surprise: OK — JSON uses bound_k matching struct field

Test quality: OK — 19 tests with strong coverage:

Exhaustive combinatorial count verification (paper example: exactly 2 of C(4,3)=4 subsets have C1P)
Negative case (Tucker matrix with K=4, known to lack C1P)
Boundary cases (K=0, empty matrix, single column)
Constructor panic tests (#[should_panic])
Serialization round-trip
All evaluate guard clauses covered

Issues: None critical or important.

Minor: Module doc in src/models/algebraic/mod.rs does not list ConsecutiveOnesSubmatrix alongside the other four problems (lines 3-7).

Agentic Feature Tests

#	Test	Command	Result
1	Catalog listing	`pred list`	PASS — `ConsecutiveOnesSubmatrix *` appears with correct complexity
2	Problem details	`pred show ConsecutiveOnesSubmatrix`	PASS — correct fields, 0 reductions
3	Example creation	`pred create --example ConsecutiveOnesSubmatrix`	PASS — valid 3×4 Tucker matrix
4	Solve (ILP)	`pred solve <instance>`	PASS (expected) — "No reduction path to ILP"
5	Solve (brute-force)	`pred solve --solver brute-force`	PASS — returns `[1,0,1,1]`, verified correct
6	JSON list output	`pred list --json`	PASS
7	JSON show output	`pred show --json`	PASS
8	Trivial instance (k=1)	Custom JSON	PASS
9	Full C1P matrix (k=3)	Custom 3×3 JSON	PASS
10	Unsatisfiable (Tucker forbidden submatrix)	Custom 3×3 JSON	PASS — "No solution found"
11	Empty matrix (k=0)	Custom JSON	PASS — vacuous true
12	Invalid instance (k > n via JSON)	Custom JSON	PASS — correctly rejects all configs
13	k=0 with non-empty matrix	Custom JSON	PASS
14	Minimal 1×1	Custom JSON	PASS
15	Round-trip serialization	create → file → solve	PASS
16	Canonical example verification	Manual check	PASS — both solutions verified

16/16 feature tests passed. Full test suite: 2,223 tests pass, 0 failures, 0 clippy warnings.

Observations (informational):

size_fields empty in pred show --json — expected for isolated problem with no reductions
Serde deserialization bypasses constructor validation (e.g., bound_k > n accepted via JSON) — evaluate() correctly rejects all configs, consistent with other models

Generated by review-pipeline

GiggleLiu · 2026-03-18T16:59:23Z

Agentic Review Report

Structural Check

Structural Completeness

#	Check	Status
1	Model file exists (`src/models/algebraic/consecutive_ones_submatrix.rs`)	PASS
2	`inventory::submit!` present	PASS
3	`#[derive(...Serialize, Deserialize)]` on struct	PASS
4	`Problem` trait impl	PASS
5	`SatisfactionProblem` impl	PASS
6	`#[cfg(test)]` + `#[path = "..."]` test link	PASS
7	Test file exists (`src/unit_tests/models/algebraic/consecutive_ones_submatrix.rs`)	PASS
8	Test file has >= 3 test functions	PASS — 19 test functions
9	Registered in `algebraic/mod.rs`	PASS
10	Re-exported in `models/mod.rs`	PASS
11	`declare_variants!` entry exists	PASS
12	CLI `resolve_alias` entry	PASS
13	CLI `create` support	PASS
14	Canonical model example registered	PASS
15	Paper `display-name` entry	PASS
16	Paper `problem-def` block	PASS

16/16 structural checks passed.

Build Status

Check	Result
`cargo test`	PASS — 2104 passed, 0 failed
`cargo clippy`	PASS — no warnings
`cargo fmt --check`	PASS

Semantic Review

evaluate() correctness: OK — Correctly validates config length, binary values, exact K selection count, then checks all permutations of selected columns for C1P. Returns false for all infeasible configurations. The C1P check in has_c1p() correctly counts ones and verifies contiguity via span == count.
dims() correctness: OK — Returns vec![2; num_cols()], correctly modeling n binary variables.
Edge cases: OK — Empty matrix, K=0, inconsistent row lengths, bound_k > n all handled correctly.
Paper entry: OK — Clear mathematical definition, historical context, worked example with CeTZ figure, proper citations.

Issue Compliance (#417)

#	Check	Status
1	Problem name matches	OK
2	Mathematical definition matches	OK
3	Problem type (sat) matches	OK
4	Type parameters match	OK
5	Configuration space matches	OK
6	Feasibility check matches	OK
7	Objective function matches	OK
8	Complexity matches	ISSUE — see below

Issues Found

Important — Complexity string overstated (src/models/algebraic/consecutive_ones_submatrix.rs:210): The declared complexity "2^(num_cols) * factorial(bound_k) * num_rows" includes a spurious factorial(bound_k) factor. The best known algorithm enumerates all C(n,K) subsets (bounded by 2^n) and tests each for C1P in O(m+n) time using PQ-tree (Booth & Lueker, 1976). The factorial(bound_k) reflects the implementation's permutation enumeration, not the best known algorithm. Should be "2^(num_cols) * (num_rows + num_cols)" or at minimum "2^(num_cols) * num_rows" as specified in issue [Model] ConsecutiveOnesSubmatrix #417.
Suggestion — Module docstring not updated (src/models/algebraic/mod.rs:1-7): The algebraic/mod.rs module doc comment lists QUBO, ILP, CVP, and BMF but omits ConsecutiveOnesSubmatrix.

Quality Check

Design Principles

DRY: OK — Reuses parse_bool_matrix helper from BMF for CLI parsing. cli_flag_name table properly extended.
KISS: OK — Implementation is straightforward. Heap's algorithm for permutation generation is standard. Clean early returns in evaluate.
HC/LC: OK — Proper module structure. One minor gap: module docstring (see structural review).

HCI (CLI)

Error messages: OK — Actionable error: "ConsecutiveOnesSubmatrix requires --matrix and --k" with usage example.
Discoverability: OK — after_help text includes ConsecutiveOnesSubmatrix --matrix (0/1), --k.
Consistency: OK — Follows BMF pattern (reuses --matrix for boolean matrix, --k for bound).
Output format: OK — Standard {"type": "ConsecutiveOnesSubmatrix", "data": {...}} JSON.

Test Quality

19 test functions with excellent coverage:
- Creation, evaluation (satisfying/unsatisfying), wrong config lengths, wrong selection counts, invalid variable values
- Brute-force solving (single + all solutions), unsatisfiable instances
- Trivial C1P, single-column edge case, K=0 vacuous case, empty matrix
- Serialization round-trip, paper example verification with exact solution count (2 of 4)
- Two #[should_panic] tests for constructor validation
- CLI tests: negative (no-flags help) and positive (create with correct JSON)

Issues Found

Important — Complexity string overstated (src/models/algebraic/consecutive_ones_submatrix.rs:210): Same as structural review finding. The factorial(bound_k) factor is spurious for the best known algorithm — PQ-tree testing is O(m+n) per subset, not O(K! * m). Should be "2^(num_cols) * (num_rows + num_cols)".
Suggestion — Module docstring (src/models/algebraic/mod.rs:1-7): Same as structural review.
Minor — Inline column-count duplication (src/models/algebraic/consecutive_ones_submatrix.rs:73-77, 105-109): The pattern if matrix.is_empty() { 0 } else { matrix[0].len() } appears in both new() and num_cols(). Matches existing patterns (e.g., BMF), so low priority.
Minor — Paper example hardcodes permutation (docs/paper/reductions.typ): The column permutation [1, 0, 3] is stated as prose rather than derived from data. Low risk since the example is unlikely to change.

Agentic Feature Tests

#	Test	Result	Details
1	`cargo build -p problemreductions-cli`	PASS	Compiled without errors or warnings
2	`pred list`	PASS	`ConsecutiveOnesSubmatrix *` appears in catalog
3	`pred show ConsecutiveOnesSubmatrix`	PASS	Shows description, complexity, 2 fields (`matrix`, `bound_k`), 0 reductions
4	`pred create --example ConsecutiveOnesSubmatrix`	PASS	Valid JSON: 3x4 binary matrix with `bound_k: 3`
5	`pred solve <instance>` (ILP)	PASS (expected)	Correctly reports no reduction path, suggests `--solver brute-force`
6	`pred solve --solver brute-force <instance>`	PASS	Returns satisfying solution `[1, 0, 1, 1]` with `evaluation: "true"`
7	`cargo test --lib consecutive_ones`	PASS	19/19 tests passed

All 7 tests PASS. No failures detected.

The model is fully functional end-to-end: catalog registration, display, example creation, serialization, and brute-force solving all work correctly.

Consolidated Findings

#	Severity	Finding	Location
1	Important	Complexity string includes spurious `factorial(bound_k)` — should reflect best known algorithm (PQ-tree O(m+n) per subset), not implementation's permutation enumeration. Recommend `"2^(num_cols) * (num_rows + num_cols)"`.	`src/models/algebraic/consecutive_ones_submatrix.rs:210`
2	Suggestion	Module docstring in `algebraic/mod.rs` does not list `ConsecutiveOnesSubmatrix`.	`src/models/algebraic/mod.rs:1-7`
3	Minor	Inline column-count duplication between `new()` and `num_cols()`.	`src/models/algebraic/consecutive_ones_submatrix.rs:73-77, 105-109`
4	Minor	Paper example hardcodes column permutation as prose.	`docs/paper/reductions.typ`

Generated by review-pipeline

Resolve conflicts with QuadraticAssignment, PrimeAttributeName, PrecedenceConstrainedScheduling and other models added to main. Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

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

- Change complexity from implementation cost (factorial permutation enumeration) to best-known algorithm bound (PQ-tree C1P testing) - Add ConsecutiveOnesSubmatrix to algebraic module docstring Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

Add plan for #417: ConsecutiveOnesSubmatrix model

46eb20d

GiggleLiu and others added 2 commits March 16, 2026 20:25

chore: remove plan file after implementation

bebe0f0

GiggleLiu requested a review from Copilot March 16, 2026 12:26

Copilot started reviewing on behalf of GiggleLiu March 16, 2026 12:28 View session

Copilot AI reviewed Mar 16, 2026

View reviewed changes

GiggleLiu added 2 commits March 16, 2026 23:10

fix: align consecutive ones metadata and CLI help

d7f6f58

GiggleLiu added this to Good issues Mar 18, 2026

GiggleLiu moved this to Under review in Good issues Mar 18, 2026

GiggleLiu moved this from Under review to Final review in Good issues Mar 18, 2026

zazabap and others added 3 commits March 18, 2026 17:41

Merge branch 'main' into issue-417-consecutive-ones-submatrix

9882ef2

Resolve conflicts with QuadraticAssignment, PrimeAttributeName, PrecedenceConstrainedScheduling and other models added to main. Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

fix: rustfmt line wrap in models/mod.rs after merge

f6eec5f

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

zazabap approved these changes Mar 18, 2026

View reviewed changes

zazabap mentioned this pull request Mar 18, 2026

[Model] ConsecutiveOnesSubmatrix #417

Closed

3 tasks

zazabap merged commit 0ef0b87 into main Mar 18, 2026
5 checks passed

isPANN moved this from Final review to Done in Good issues Mar 19, 2026

GiggleLiu deleted the issue-417-consecutive-ones-submatrix branch April 12, 2026 00:53

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fix #417: Add ConsecutiveOnesSubmatrix model#667

Fix #417: Add ConsecutiveOnesSubmatrix model#667
zazabap merged 8 commits intomainfrom
issue-417-consecutive-ones-submatrix

GiggleLiu commented Mar 16, 2026

Uh oh!

codecov bot commented Mar 16, 2026 •

edited

Loading

Uh oh!

GiggleLiu commented Mar 16, 2026

Uh oh!

Copilot AI left a comment

Uh oh!

GiggleLiu commented Mar 18, 2026

Uh oh!

GiggleLiu commented Mar 18, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Conversation

GiggleLiu commented Mar 16, 2026

Summary

Uh oh!

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

Uh oh!

Codecov Report

Uh oh!

GiggleLiu commented Mar 16, 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!

GiggleLiu commented Mar 18, 2026

Agentic Review Report

Structural Check

Quality Check

Agentic Feature Tests

Uh oh!

GiggleLiu commented Mar 18, 2026

Agentic Review Report

Structural Check

Structural Completeness

Build Status

Semantic Review

Issue Compliance (#417)

Issues Found

Quality Check

Design Principles

HCI (CLI)

Test Quality

Issues Found

Agentic Feature Tests

Consolidated Findings

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

codecov bot commented Mar 16, 2026 •

edited

Loading