×

Integer programming for classifying orthogonal arrays. (English) Zbl 1383.05031

Summary: Classifying orthogonal arrays (OAs) is a well-known important class of problems that asks for finding all non-isomorphic, non-negative integer solutions to a class of systems of constraints. Solved instances are scarce. We develop two new methods based on finding all non-isomorphic solutions of two novel integer linear programming formulations for classifying all non-isomorphic \(\mathrm{OA}(N,k,s,t)\) given a set of all non-isomorphic \(\mathrm{OA}(N,k-1,s,t)\). We also establish the concept of orthogonal design equivalence (OD-equivalence) of \(\mathrm{OA}(N,k,2,t)\) to reduce the number of integer linear programs (ILPs) all of whose non-isomorphic solutions need to be enumerated by our methods. For each ILP, we determine the largest group of permutations that can be exploited with the branch-and-bound (B&B) with isomorphism pruning algorithm of F. Margot [Discrete Optim. 4, No. 1, 40–62 (2007; Zbl 1169.90411)] without losing isomorphism classes of \(\mathrm{OA}(N,k,2,t)\). Our contributions bring the classifications of all non-isomorphic \(\mathrm{OA}(160,k,2,4)\) for \(k=9,10\) and \(\mathrm{OA}(176,k,2,4)\) for \(k=5,6,7,8,9,10\) within computational reach. These are the smallest \(s=2\), \(t=4\) cases for which classification results are not available in the literature.

MSC:

05B15 Orthogonal arrays, Latin squares, Room squares
90C10 Integer programming

Citations:

Zbl 1169.90411
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] G. Appa, D. Magos and I. Mourtos, Searching for mutually orthogonal Latin squares via integer and constraint programming, Europ. J. Oper. Res. 173 (2006), 519-530. · Zbl 1109.05027
[2] G. Appa, I. Mourtos and D. Magos, Integrating constraint and integer programming for the orthogonal Latin squares problem, In: Principles and Practice of Constraint Programming — CP 2002, Lec. Notes in Comp. Sci. 2470, (Ed. P. Van Hentenryck), Springer, Berlin, Heidelberg, Germany, (2002), 17-32. · Zbl 1109.05027
[3] M. Banciu, Dual simplex, In: Wiley Encyclopedia of Operations Research and Management Science, (Eds. J. J. Cochran, L. A. Cox, P. Keskinocak, J. P. Kharoufeh and C. J. Smith), John Wiley & Sons, Inc. Hoboken, NJ, USA, (2011).
[4] D. A. Bulutoglu and F. Margot, Classification of orthogonal arrays by integer programming, J. Statist. Plann. Inference 138 (2008), 654-666. · Zbl 1139.62041
[5] L. Y. Deng and B. Tang, Generalized resolution and minimum aberration criteria for Plackett-Burman and other nonregular factorial designs, Statist. Sinica 9 (1999), 1071-1082. · Zbl 0942.62084
[6] J. Egan and I. M. Wanless, Enumeration of MOLS of small order, Math. Comp. 85 (2016), 799-824. · Zbl 1332.05025
[7] Y. Fujii, T. Namikawa and S. Yamamoto, Classification of two-symbol orthogonal arrays of strength t, t + 3 constraints and index 4, II, Sut. J. Math. 25 (1989), 161-177. · Zbl 0732.62072
[8] The GAP Group, GAP-Groups, Algorithms, and Programming, Version 4.6.4, 2013. (http://www.gap-system.org)
[9] IBM ILOG CPLEX 12.6, CPLEX User’s Manual, 2014.
[10] A. Hedayat, N. J. A. Sloane and J. Stufken, Orthogonal arrays: Theory and applications, Springer-Verlag, New York, USA, 1999. · Zbl 0935.05001
[11] P. Kaski and P. R. J. ¨Osterg˚ard, Classification algorithms for codes and designs, Algorithms and Computation in Mathematics 15, Springer-Verlag, Berlin, Germany, 2006.
[12] J. I. Kokkala and P. R. J. ¨Osterg˚ard, Classification of Graeco-Latin cubes, J. Combin. Des. 23 (2015), 509-521. · Zbl 1331.05044
[13] B. Krishnamoorthy and G. Pataki, Column basis reduction and decomposable knapsack problems, Discrete Optim. 6 (2009), 242-270. · Zbl 1176.90418
[14] J. Linderoth, F. Margot and G. Thain, Improving bounds on the football pool problem via symmetry: Reduction and high-throughput computing, Informs J. Comput. 21 (2009), 445-457. · Zbl 1243.90006
[15] F. Margot, Pruning by isomorphism in branch-and-cut, Math. Program. Ser. A 94 (2002), 71-90. · Zbl 1023.90088
[16] F. Margot, Small covering designs by branch-and-cut, Math. Program. Ser. B 94 (2003), 207-220. · Zbl 1030.90144
[17] F. Margot, Exploiting orbits in symmetric ILP, Math. Program. Ser. B 98 (2003), 3-21. · Zbl 1082.90070
[18] F. Margot, Symmetric ILP: Coloring and small integers, Discrete Optim. 4 (2007), 40-62. · Zbl 1169.90411
[19] F. Margot, Symmetry in integer linear programming, In: 50 Years of Integer Programming 1958-2008, (Eds. M. Junger, T. Liebling, D. Naddef, G. L. Nemhauser, W. Pulleyblank, G. Reinelt, G. Rinaldi and L. Wolsey), SpringerVerlag, Berlin, Heidelberg, Germany, (2010), 647-686.
[20] B. D. McKay, Hadamard equivalence via graph isomorphism, Discrete Math. 27 (1979), 213-214. · Zbl 0401.05024
[21] B. D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998), 306-324. [Errata:http://users.ces.anu.edu.au/∼bdm/papers/orderly.pdf]. · Zbl 0894.68107
[22] B. D. McKay and A. Piperno, Practical graph isomorphism, II. J. Symbolic Comput. 60 (2014), 94-112. · Zbl 1394.05079
[23] B. D. McKay and A. Piperno, nauty Graph Isomorphism Software, Version 2.5, 2013. (http://cs.anu.edu.au/ bdm/nauty/ and http://pallini.di. uniroma1.it/).
[24] B. D. McKay and S. P. Radziszowski, The non-existence of 4-(12, 6, 6) designs, In: Computational and Constructive Design Theory, (Ed. W. D. Wallis), Kluwer Academic Publ., Dordrecht, Netherlands, (1996), 177-188. · Zbl 0851.05018
[25] M. Pfetsch and T. Rehn, Computational comparison of symmetry handling methods for mixed integer programs, Optimization Online (2015). · Zbl 1411.90233
[26] K. J. Ryan and D. A. Bulutoglu, Minimum aberration fractional factorial designs with large N , Technometrics 52 (2010), 250-255.
[27] E. D. Schoen, P. T. Eendebak and M. V. M. Nguyen, Complete enumeration of pure-level and mixed-level orthogonal arrays, J. Combin. Des. 18 (2010), 123- 140. · Zbl 1287.05017
[28] J. Stufken and B. Tang, Complete enumeration of two-level orthogonal arrays of strength d with d + 2 constraints, Ann. Statist. 35 (2007), 793-814. · Zbl 1117.62077
[29] J. H. Van Lint and R. M. Wilson, A course in combinatorics, Cambridge University Press, Cambridge, UK, 1992. · Zbl 0769.05001
[30] L. A. Wolsey, Integer programming, Wiley, New York, USA, 1998. · Zbl 0930.90072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.