Abstract
Two minimum cardinality set covering problems of similar structure are presented as difficult test problems for evaluating the computational efficiency of integer programming and set covering algorithms. The smaller problem has 117 constraints and 27 variables, and the larger one, constructed by H.J. Ryser, has 330 constraints and 45 variables. The constraint matrices of the two set covering problems are incidence matrices of Steiner triple systems. An optimal solution to the problem that we were able to solve (the smaller one) gives some new information on the 1-widths of members of this class of (0,1)-matrices.
This research was supported, in part, by National Science Foundation Grants GK-32282X and GP-32316X and Office of Naval Research Contract No. N00014-67-A-0077-0028 to Cornell University. A substantial amount of the computer time was provided by the Mathematics Research Center of the University of Wisconsin under U.S. Army Contract No. DA-31-124-ARO-D-462.
Preview
Unable to display preview. Download preview PDF.
References
M. Bellmore and H.D. Ratliff, “Set covering and involutory bases”, Management Science 18 (1971) 194–206.
G.H. Bradley and P.N. Wahi, “An algorithm for integer linear programming: A combined algebraic and enumeration approach”, Operations Research 21 (1973) 45–60.
D.R. Fulkerson and H.J. Ryser, “Widths and heights of (0,1)-matrices”, Canadian Journal of Mathematics 13 (1961) 239–255.
D.R. Fulkerson and H.J. Ryser, “Multiplicities and minimal widths for (0,1)-matrices”, Canadian Journal of Mathematics 14 (1962) 498–508.
D.R. Fulkerson and H.J. Ryser, “Width sequences for special classes of (0,1)-matrices”, Canadian Journal of Mathematics 15 (1963) 371–396.
A.M. Geoffrion, “An improved implicit enumeration approach for integer programming”, Operations Research 17 (1969) 437–454.
R.E. Gomory, “An algorithm for integer solutions to linear programs”, in: R.L. Graves and P. Wolfe, eds., Recent advances in mathematical programming (McGraw-Hill, New York, 1963) pp. 269–302.
R.E. Gomory, “On the relation between integer and non-integer solutions to linear programs”, Proceedings of the National Academy of Sciences 53 (1965) 260–265.
G.A. Gorry and J.F. Shapiro, “An adaptive group theoretic algorithm for integer programming problems”, Management Science 17 (1971) 285–306.
G.A. Gorry, W.D. Northrup and J.F. Shapiro, “Computational experience with a group theoretic integer programming algorithm”, Mathematical Programming 4 (1973) 171–192.
R.W. House, L.D. Nelson and J. Rado, “Computer studies of a certain class of linear integer problems”, in: A. Lavi and T. Vogl, eds., Recent advances in optimization techniques (Wiley, New York, 1966) pp. 241–280.
R.G. Jeroslow, “Trivial integer programs unsolvable by branch-and-bound”, Mathematical Programming 6 (1974) 105–109.
C.E. Lemke, H.M. Salkin and K. Spielberg, “Set covering by single branch enumeration with linear programming subproblems”, Operations Research 19 (1971) 998–1022.
H.J. Ryser, Combinatorial mathematics, Carus Mathematical Monograph No. 14 (Wiley, New York, 1963).
J.F. Shapiro, Private communication (September 1973).
H. Thiriez, “The set covering problem: A group theoretic approach”, Revue Francaise d’Informatique et de Recherche Operationelle V3 (1971) 83–104.
L.E. Trotter, Jr. and C.M. Shetty, “An algorithm for the bounded variable integer programming problem”, Journal of the Association for Computing Machinery 21 (1974) 505–513.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1974 The Mathematical Programming Society
About this chapter
Cite this chapter
Fulkerson, D.R., Nemhauser, G.L., Trotter, L.E. (1974). Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triple systems. In: Balinski, M.L. (eds) Approaches to Integer Programming. Mathematical Programming Studies, vol 2. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0120689
Download citation
DOI: https://doi.org/10.1007/BFb0120689
Received:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00739-2
Online ISBN: 978-3-642-00740-8
eBook Packages: Springer Book Archive