Improving Bounds on the Football Pool Problem by Integer Programming and High-Throughput Computing

References

• Anstreicher K., Brixius N., Goux J.-P., Linderoth J. T. Solving large quadratic assignment problems on computational grids. Math. Programming Ser. B (2002) 91(3):563–588Crossref, Google Scholar
• Applegate D. L., Bixby R. E., Chvátal V., Cook W. J.The Trav- eling Salesman Problem (2006) (Princeton University Press, Princeton, NJ) Google Scholar
• Barnhart C., Johnson E. L., Nemhauser G. L., Savelsbergh M. W. P., Vance P. H. Branch-and-price: Column generation for solving huge integer programs. Oper. Res. (1998) 46(3):316–329Link, Google Scholar
• Bazaraa M. S., Kirca O. A branch-and-bound-based heuristic for solving the quadratic assignment problem. Naval Res. Logist. Quart. (1983) 30(2):287–304Crossref, Google Scholar
• Bradley D. Schedd on the side. (2006) Presentation, Condor Week 2006April 25(University of Wisconsin–Madison, Madison) Google Scholar
• Butler G., Lam C. W. H. A general backtrack algorithm for the isomorphism problem of combinatorial objects. J. Symbolic Comput. (1985) 1(4):363–381Crossref, Google Scholar
• Chen Q., Ferris M. C., Linderoth J. T. FATCOP 2.0: Advanced features in an opportunistic mixed integer programming solver. Ann. Oper. Res. (2001) 103:17–32Crossref, Google Scholar
• Epema D. H. J., Livny M., van Dantzig R., Evers X., Pruyne J. A worldwide flock of Condors: Load sharing among workstation clusters. J. Future Generation Comput. Systems (1996) 12(1):53–65Crossref, Google Scholar
• Foster I., Kesselman C. Globus: A metacomputing infrastructure toolkit. Internat. J. Supercomputer Appl. (1997) 11(2):115–128Crossref, Google Scholar
• Foster I., Kesselman C., Foster I., Kesselman C. Computational grids. The Grid: Blueprint for a New Computing Infrastructure (1999) (Morgan Kaufmann, San Francisco) 15–52Chapter 2Google Scholar
• Frey J., Tannenbaum T., Livny M., Foster I., Tuecke S. Condor-G: A computation management agent for multi-institutional grids. Cluster Comput. (2002) 5(3):237–246Crossref, Google Scholar
• Glankwamdee W., Linderoth J., Talbi E. MW: A software framework for combinatorial optimization on computational grids. Parallel Combinatorial Optimization (2006) (John Wiley & Sons, New York) 239–261Crossref, Google Scholar
• Goux J.-P., Leyffer S. Solving large MINLPs on computational grids. Optim. Engrg. (2003) 3(3):327–346Crossref, Google Scholar
• Goux J.-P., Kulkarni S., Yoder M., Linderoth J. T. Master-worker: An enabling framework for master-worker applications on the computational grid. Cluster Comput. (2001) 4(1):63–70Crossref, Google Scholar
• Hämäläinen H., Honkala I., Litsyn S., Östergård P. Football pools–A game for mathematicians. Amer. Math. Monthly (1995) 102(7):579–588Crossref, Google Scholar
• Holm S., Sørensen M. M. The optimal graph partitioning problem: Solution method based on reducing symmetric nature and combinatorial cuts. OR Spectrum (1993) 15(1):1–8Crossref, Google Scholar
• Ivanov A. V. Constructive enumeration of incidence systems. Ann. Discrete Math. (1985) 114(26):227–246Google Scholar
• Kaibel V., Pfetsch M. Packing and partitioning orbitopes. Math. Programming (2008) 114(1):1–36Crossref, Google Scholar
• Kreher D. L., Stinson D. R.Combinatorial Algorithms, Generation, Enumeration, and Search (1999) (CRC Press, Boca Raton, FL) Google Scholar
• Lenstra A. K., Lenstra H. W., Lovász L. Factoring polynomials with rational coefficients. Mathematische Annalen (1982) 261(4):515–534Crossref, Google Scholar
• Linderoth J., Thain G., Wright S. J.User's Guide to MW (2007) (University of Wisconsin–Madison, Madison) . http://www.cs.wisc.edu/condor/mwGoogle Scholar
• Litzkow M. J., Livny M., Mutka M. W. Condor—A hunter of idle workstations. Proc. 8th Internat. Conf. Distributed Comput. Systems (1998) San Jose, CA(IEEE Press, Los Alamitos, CA) 104–111Google Scholar
• Macambira E. M., Maculan N., de Souza C. C. Reducing symmetry of the SONET ring assignment problem using hierarchical inequalities. (2004) . Technical Report ES-636/04, Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, BrazilGoogle Scholar
• Margot F. Pruning by isomorphism in branch-and-cut. Math. Programming (2002) 94(1):71–90Crossref, Google Scholar
• Margot F. Small covering designs by branch-and-cut. Math. Programming (2003) 94(2–3):207–220Crossref, Google Scholar
• McKay B. autoson—A distributed batch system for UNIX workstation networks (version 1.3). (1996) . Technical report, Computer Sciences Department, Australian National University, Canberra, ACT, AustraliaGoogle Scholar
• McKay B. D. Isomorph-free exhaustive generation. J. Algorithms (1998) 26(2):306–324Crossref, Google Scholar
• Méndez-Díaz I., Zabala P. A branch-and-cut algorithm for graph coloring. Discrete Appl. Math. (2006) 154(5):826–847Crossref, Google Scholar
• Mezmaz M., Melab N., Talbi E.-G. A grid-enabled branch and bound algorithm for solving challenging combinatorial optimization problems. (2006) . Research Report 5945, INRIA, Lille, FranceGoogle Scholar
• Östergård P. R. J., Blass W. On the size of optimal binary codes of length 9 and covering radius 1. IEEE Trans. Inform. Theory (2001) 47(6):2556–2557Crossref, Google Scholar
• Östergård P. R. J., Wassermann A. A new lower bound for the football pool problem for six matches. J. Combinatorial Theory Ser. A (2002) 99(1):175–179Crossref, Google Scholar
• Ostrowski J., Linderoth J., Rossi F., Smriglio S. Constraint orbital branching. IPCO 2008: 13th Conf. Integer Programming and Combinatorial Optim. (2008) 5035(Springer, Berlin) 225–239Lecture Notes in Computer ScienceCrossref, Google Scholar
• Read R. C., Alspach B., Hell P., Miller D. J. Every one a winner, or how to avoid isomorphism search when cataloguing combinatorial configurations. Algorithmic Aspects of Combinatorics. Annals of Discrete Mathematics (1978) 2(North-Holland, Amsterdam) 107–120Crossref, Google Scholar
• Sherali H. D., Smith J. C. Improving zero-one model representations via symmetry considerations. Management Sci. (2001) 47(10):1396–1407Link, Google Scholar
• Wille L. T. The football pool problem for 6 matches: A new upper bound obtained by simulated annealing. J. Combinatorial Theory Ser. A (1987) 45(2):171–177Crossref, Google Scholar
• Xu Y., Ralphs T. K., Ladányi L., Saltzman M. J. ALPS: A framework for implementing parallel search algorithms. Proc. Ninth INFORMS Comput. Soc. Conf. (2005) Annapolis, MD(INFORMS, Hanover, MD) 319–334Crossref, Google Scholar