mgrettondann/partridge-cpp
1
0
Fork 0
Code Issues 4 Pull Requests Activity

solver: benchmark candidate ordering and portfolio search #12

New Issue
Closed
opened 2026-07-30 16:23:34 +01:00 by mcp · 2 comments
mcp commented 2026-07-30 16:23:34 +01:00
Collaborator
Copy Link
Copy Source

Background

Candidate ordering has an enormous effect on time to the first solution. The current solver tries sizes in descending order, while published smallest-valley implementations found ascending order effective.

Parallel workers may also benefit from complementary orderings rather than identical traversal.

Proposed work

  • Make candidate ordering a search policy.
  • Compare ascending, descending and justified best-fit policies.
  • Optionally add seeded deterministic randomized ordering.
  • Evaluate a multi-worker portfolio with complementary policies.
  • Keep reproducible seeds in benchmark reports.

Acceptance criteria

  • Search completeness is independent of policy.
  • Benchmarks report distributions over repeated runs where randomness is used.
  • Select a stable default based on time-to-first-solution, not solution enumeration.
  • Record node counts as well as elapsed time.

References

## Background Candidate ordering has an enormous effect on time to the first solution. The current solver tries sizes in descending order, while published smallest-valley implementations found ascending order effective. Parallel workers may also benefit from complementary orderings rather than identical traversal. ## Proposed work - Make candidate ordering a search policy. - Compare ascending, descending and justified best-fit policies. - Optionally add seeded deterministic randomized ordering. - Evaluate a multi-worker portfolio with complementary policies. - Keep reproducible seeds in benchmark reports. ## Acceptance criteria - Search completeness is independent of policy. - Benchmarks report distributions over repeated runs where randomness is used. - Select a stable default based on time-to-first-solution, not solution enumeration. - Record node counts as well as elapsed time. ## References - https://www.or.uni-bonn.de/~hougardy/paper/PerfectRectanglePacking.pdf - https://github.com/lightln2/partridge-solver
mgrettondann commented 2026-07-30 17:54:40 +01:00
Owner
Copy Link
Copy Source

Does a single policy apply across multiple sizes?

Does a single policy apply across multiple sizes?
mcp commented 2026-07-30 18:07:20 +01:00
Author
Collaborator
Copy Link
Copy Source

Implementation/review decision before merge:

  • Introduce an explicit deterministic search policy with ascending, descending, and best-fit choices.
  • Define best-fit as trying an available square exactly matching the selected valley width first, then the remaining candidates in ascending order. This closes the valley without a shelf remainder when possible while still trying every fitting candidate.
  • Preserve benchmark schema-v1 and --candidate-order compatibility; best-fit is an additional field value, not a wire-format rename.
  • Do not add seeded randomization or a worker portfolio: measured deterministic policies already identify a default, ascending/best-fit have little search-tree diversity, descending is consistently slower, and shared-frontier parallelism belongs to #11.

Repeated single-worker Release measurements (Apple Clang 21, arm64, -O3 -DNDEBUG), with independent validation and stable counters:

order policy counted median counter-free median nodes
8 ascending 0.808 s 0.794 s 7,735,369
8 descending 1.310 s 1.268 s 12,186,125
8 best-fit 0.817 s 0.823 s 7,679,349
9 direct ascending 5.522 s not measured 45,840,266
9 direct best-fit 5.651 s not measured 45,746,016

Ascending remains the stable single-thread default because it has the lowest measured time to first solution for orders 8 and direct 9. Best-fit's slightly smaller trees do not offset its policy checks. Exhaustive order-5 searches visit identical node counts under all three policies, confirming ordering does not affect completeness.

10x10/11x11 assessment: issue #4 established that public/direct order 10 exceeds a 20-second exploratory cap, and public order 11 first performs the same order-10 search. Best-fit changes direct order-9 nodes by only about 0.2%, so there is no evidence to repeat a long order-10 probe. Both stay opt-in benchmarks; automated route-boundary coverage still verifies order 11 chooses construction.

Review and verification:

  • independent diff review found no correctness issue;
  • Release CTest: 10/10 passed (10.46 s);
  • Debug CTest: 10/10 passed (63.71 s);
  • benchmark emitted valid schema-v1 best-fit output;
  • git diff --check passed.

References: issue #12, issue #4's merged skyline measurements, and Hougardy's observation that candidate order strongly changes feasible-instance time to first solution.

Implementation/review decision before merge: - Introduce an explicit deterministic search policy with `ascending`, `descending`, and `best-fit` choices. - Define best-fit as trying an available square exactly matching the selected valley width first, then the remaining candidates in ascending order. This closes the valley without a shelf remainder when possible while still trying every fitting candidate. - Preserve benchmark schema-v1 and `--candidate-order` compatibility; `best-fit` is an additional field value, not a wire-format rename. - Do not add seeded randomization or a worker portfolio: measured deterministic policies already identify a default, ascending/best-fit have little search-tree diversity, descending is consistently slower, and shared-frontier parallelism belongs to #11. Repeated single-worker Release measurements (Apple Clang 21, arm64, -O3 -DNDEBUG), with independent validation and stable counters: | order | policy | counted median | counter-free median | nodes | | --- | --- | ---: | ---: | ---: | | 8 | ascending | 0.808 s | 0.794 s | 7,735,369 | | 8 | descending | 1.310 s | 1.268 s | 12,186,125 | | 8 | best-fit | 0.817 s | 0.823 s | 7,679,349 | | 9 direct | ascending | 5.522 s | not measured | 45,840,266 | | 9 direct | best-fit | 5.651 s | not measured | 45,746,016 | Ascending remains the stable single-thread default because it has the lowest measured time to first solution for orders 8 and direct 9. Best-fit's slightly smaller trees do not offset its policy checks. Exhaustive order-5 searches visit identical node counts under all three policies, confirming ordering does not affect completeness. 10x10/11x11 assessment: issue #4 established that public/direct order 10 exceeds a 20-second exploratory cap, and public order 11 first performs the same order-10 search. Best-fit changes direct order-9 nodes by only about 0.2%, so there is no evidence to repeat a long order-10 probe. Both stay opt-in benchmarks; automated route-boundary coverage still verifies order 11 chooses construction. Review and verification: - independent diff review found no correctness issue; - Release CTest: 10/10 passed (10.46 s); - Debug CTest: 10/10 passed (63.71 s); - benchmark emitted valid schema-v1 best-fit output; - `git diff --check` passed. References: issue #12, issue #4's merged skyline measurements, and Hougardy's observation that candidate order strongly changes feasible-instance time to first solution.
mcp closed this issue 2026-07-30 18:08:07 +01:00
Sign in to join this conversation.
No Branch/Tag Specified
Branches Tags
Labels
No items
No labels
Milestone
No items
No Milestone
Assignees
Clear assignees
mcp mgrettondann (Matthew Gretton-Dann)
No Assignees
2 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: mgrettondann/partridge-cpp#12