Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triple systems
作者： D. R. Fulkerson , G. L. Nemhauser , L. E. Trotter
DOI: 10.1007/BFB0120689
关键词:
摘要: Two minimum cardinality set covering problems of similar structure are presented as difficult test for evaluating the computational efficiency integer programming and algorithms. The smaller problem has 117 constraints 27 variables, larger one, constructed by H.J. Ryser, 330 45 variables. constraint matrices two incidence Steiner triple systems. An optimal solution to that we were able solve (the one) gives some new information on 1-widths members this class (0,1)-matrices.
springer.com
springerlink.com参考文章(17)
C. E. Lemke, H. M. Salkin, K. Spielberg, Set Covering by Single-Branch Enumeration with Linear-Programming Subproblems Operations Research. ,vol. 19, pp. 998- 1022 ,(1971) , 10.1287/OPRE.19.4.998
G. Anthony Gorry, William D. Northup, Jeremy F. Shapiro, Computational experience with a group theoretic integer programming algorithm Mathematical Programming. ,vol. 4, pp. 171- 192 ,(1973) , 10.1007/BF01584659
Jeremy F. Shapiro, G. Anthony Gorry, An Adaptive Group Theoretic Algorithm for Integer Programming Problems ,(2015)
S. Vajda, Robert L. Graves, Philip Wolfe, RECENT ADVANCES IN MATHEMATICAL PROGRAMMING ,(2011)
Ralph E. Gomory, Outline of an algorithm for integer solutions to linear programs Bulletin of the American Mathematical Society. ,vol. 64, pp. 275- 278 ,(1958) , 10.1090/S0002-9904-1958-10224-4
D. R. Fulkerson, H. J. Ryser, Widths and heights of (0,1)-matrices. Canadian Journal of Mathematics. ,vol. 13, pp. 239- 255 ,(1961) , 10.4153/CJM-1961-020-3
A. M. Geoffrion, An Improved Implicit Enumeration Approach for Integer Programming Operations Research. ,vol. 17, pp. 437- 454 ,(1969) , 10.1287/OPRE.17.3.437
D. R. Fulkerson, H. J. Ryser, Multiplicities and minimal widths for (0,1)-matrices. Canadian Journal of Mathematics. ,vol. 14, pp. 498- 508 ,(1962) , 10.4153/CJM-1962-041-9
L. E. Trotter, C. M. Shetty, An Algorithm for the Bounded Variable Integer Programming Problem Journal of the ACM. ,vol. 21, pp. 505- 513 ,(1974) , 10.1145/321832.321848
D. R. Fulkerson, H. J. Ryser, Width sequences for special classes of (0,1)-matrices.: Canadian Journal of Mathematics. ,vol. 15, pp. 371- 396 ,(1963) , 10.4153/CJM-1963-042-1