Skip to content

5 satisfaction problems missing find_all_satisfying tests #701

@isPANN

Description

@isPANN

Problem

5 SatisfactionProblem models have test files but do not use find_all_satisfying to enumerate all feasible solutions, unlike the other 33 satisfaction models which all include such tests.

Additionally, 7 problems were missing canonical_model_example_specs registration (no auto-exported JSON for the paper), and their paper entries used hardcoded examples instead of load-model-example.

Affected models (find_all_satisfying)

Model Test file Issue example Search space Solutions
SequencingWithinIntervals src/unit_tests/models/misc/sequencing_within_intervals.rs #219 (5 tasks, overlapping windows) 5280 41
ShortestCommonSupersequence src/unit_tests/models/misc/shortest_common_supersequence.rs #412 instance 1 (3 strings, ternary, K=7) 2187 42
MultiprocessorScheduling src/unit_tests/models/misc/multiprocessor_scheduling.rs #212 (5 tasks, 2 processors, D=10) 32 2
FlowShopScheduling src/unit_tests/models/misc/flow_shop_scheduling.rs #507 (5 jobs, 3 machines, D=25) 120 99
RuralPostman src/unit_tests/models/graph/rural_postman.rs #248 instance 1 (hexagon, 8 edges, B=6) 6561 1

Affected models (missing canonical_model_example_specs + hardcoded paper)

Model Category
BinPacking misc / optimization
GraphPartitioning graph / optimization
Knapsack misc / optimization
MinimumFeedbackArcSet graph / optimization
OptimalLinearArrangement graph / satisfaction
SubgraphIsomorphism graph / satisfaction
SubsetSum misc / satisfaction

Changes made

  1. Added find_all_satisfying + empty tests for all 5 satisfaction models, using issue examples with exact solution counts verified by brute force
  2. Updated canonical examples for SequencingWithinIntervals ([Model] SequencingWithinIntervals #219) and ShortestCommonSupersequence ([Model] ShortestCommonSupersequence #412) to use more natural instances matching their issues
  3. Registered canonical_model_example_specs for all 7 missing models (total: 70/70 problems now registered)
  4. Converted all 7 paper entries from hardcoded to data-driven (load-model-example)
  5. Made FlowShopScheduling and RuralPostman paper entries fully data-driven with auto-computed Gantt charts / graph figures

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    Status

    Done

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions