pith. sign in

arxiv: 2604.16271 · v1 · submitted 2026-04-17 · 💻 cs.DS · math.CO

Parallelizing the branch-and-bound with isomorphism pruning algorithm for classifying orthogonal arrays

Dursun Bulutoglu This is my paper

Pith reviewed 2026-05-10 07:13 UTC · model grok-4.3

classification 💻 cs.DS math.CO
keywords orthogonal arraysisomorphism pruningbranch-and-boundparallel algorithmscombinatorial classificationOA(192, k, 2, 4)strength-4 designs
0
0 comments X

The pith

A method to parallelize branch-and-bound isomorphism pruning delivers linear speedups and first classifications of OA(192, k, 2, 4) for k=9,10,11.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives a concrete way to distribute the search steps of the branch-and-bound algorithm that uses isomorphism pruning when classifying orthogonal arrays. The distribution produces linear speedups on the known cases of all non-OD-equivalent OA(128, 9, 2, 4) and OA(144, 9, 2, 4). The same method also produces the first complete lists of non-OD-equivalent OA(192, k, 2, 4) for nine, ten, and eleven columns. A reader cares because these lists describe the distinct combinatorial designs available for statistical experiments and coding applications, and the parallel version makes larger instances feasible on ordinary clusters.

Core claim

Distributing the nodes of the branch-and-bound search tree while preserving the isomorphism-pruning decisions yields linear speedups and allows the first enumeration of all non-OD-equivalent orthogonal arrays OA(192, 9, 2, 4), OA(192, 10, 2, 4), and OA(192, 11, 2, 4).

What carries the argument

Parallel distribution of the branch-and-bound search tree with synchronized isomorphism pruning that avoids both omissions and duplicate arrays.

Load-bearing premise

Distributing the search tree keeps the original pruning rules intact so that every valid orthogonal array is found exactly once.

What would settle it

Recompute the complete set of non-OD-equivalent OA(192, 9, 2, 4) on a single processor and obtain either a different count or an array absent from the parallel run's output.

read the original abstract

We provide a method for parallelizing the branch-and-bound with isomorphism pruning algorithm developed by Margot [Symmetric ILP: Coloring and small integers, Discrete Optimization (4) (2007), 40-62]. We apply our method to classify orthogonal arrays. For classifying all non-OD- equivalent OA(128, 9, 2, 4) and OA(144, 9, 2, 4) our method results in linear speedups. Finally, our method enables classifying all non-OD-equivalent OA(192, k, 2, 4) for k = 9, 10, 11 for the first time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript presents a parallelization of Margot's branch-and-bound algorithm with isomorphism pruning, applies it to the enumeration of orthogonal arrays, reports linear speedups on the known instances OA(128,9,2,4) and OA(144,9,2,4), and obtains the first complete classifications of all non-OD-equivalent OA(192,k,2,4) for k=9,10,11.

Significance. If the parallel implementation is shown to preserve correctness and completeness, the work extends the reach of an established exact algorithm to previously intractable instances in combinatorial design theory. Reproduction of known counts on smaller cases provides a concrete check on the distributed search, and the new enumerations constitute verifiable, falsifiable contributions to the OA literature.

minor comments (2)
  1. The description of the parallelization strategy (how the search tree is partitioned and how isomorphism pruning is synchronized across processes) should be expanded with pseudocode or a clear algorithmic outline to support independent re-implementation.
  2. Results tables for the new OA(192,k,2,4) classifications should report not only the final counts but also the number of nodes explored, wall-clock times, and processor counts so that the claimed linear speedups can be directly inspected.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the accurate summary of our contributions, and the recommendation for minor revision. We are pleased that the significance of extending the exact algorithm to new OA instances is recognized.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents a parallelization technique for Margot's 2007 branch-and-bound algorithm with isomorphism pruning, applied to orthogonal array classification. It validates correctness by reproducing known results on OA(128,9,2,4) and OA(144,9,2,4) instances before extending to new OA(192,k,2,4) cases for k=9,10,11. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation. The claims rely on direct algorithmic extension and reproducible computation, not reduction to the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the un-reproven correctness of Margot's 2007 branch-and-bound with isomorphism pruning algorithm and on standard assumptions about parallel search tree distribution preserving pruning invariants.

axioms (1)
  • domain assumption Margot's branch-and-bound with isomorphism pruning algorithm is correct and complete for the orthogonal array classification problem.
    The paper extends this algorithm without providing an independent proof of its base properties.

pith-pipeline@v0.9.0 · 5403 in / 1275 out tokens · 77463 ms · 2026-05-10T07:13:33.741113+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    Classification of orthogonal arrays by integer programming

    Bulutoglu, D.A., Margot, F., 2008. Classification of orthogonal arrays by integer programming. Journal of Statistical Planning and Inference 138, 654–666

    work page 2008

  2. [2]

    Integer programming for classifying orthogonal arrays

    Bulutoglu, D.A., Ryan, K.J., 2018. Integer programming for classifying orthogonal arrays. Australasian Journal of Combinatorics 70, 362–385

    work page 2018

  3. [3]

    Early estimates of the size of branch-and-bound trees

    Cornu´ ejols, G., Karamanov, M., Li, Y., 2006. Early estimates of the size of branch-and-bound trees. Informs Journal on Computing 18, 86–96. doi:https://doi.org/10.1287/ijoc.1040. 0107

    work page doi:10.1287/ijoc.1040 2006

  4. [4]

    Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays

    Geyer, A.J., Bulutoglu, D.A., Ryan, K.J., 2019. Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays. Discrete Optimization 32, 93–119

    work page 2019

  5. [5]

    Gemini advanced (3.0) for code generation

    Google, 2025. Gemini advanced (3.0) for code generation. URL:https://gemini.google.com. Assisted with generating and debuggingPerlcode

    work page 2025

  6. [6]

    Column basis reduction and decomposable knapsack problems

    Krishnamoorthy, B., Pataki, G., 2009. Column basis reduction and decomposable knapsack problems. Discrete Optimization 6, 242–270

    work page 2009

  7. [7]

    A computational study of search strategies for mixed integer programming

    Linderoth, J., Savelsbergh, M., 1999. A computational study of search strategies for mixed integer programming. INFORMS Journal on Computing 11, 173–187

    work page 1999

  8. [8]

    Symmetric ILP: Coloring and small integers

    Margot, F., 2007. Symmetric ILP: Coloring and small integers. Discrete Optimization 4, 40–62

    work page 2007

  9. [9]

    Mathematical Programming , year =

    Scavuzzo, L., Aardal, K., Lodi, A., Yorke-Smith, N., 2024. Machine learning augmented branch and bound for mixed integer linear programming. Mathematical Programming Series B doi:10.1007/s10107-024-02130-y. 8

    work page doi:10.1007/s10107-024-02130-y 2024