A Class of Hard Small 0-1 Programs

References

• Ahn S., Cooper C., Cornuéjols G., Frieze A. Probabilistic analysis of a relaxation for the k-median problem. Math. Oper. Res. (1988) 13:1–31Link, Google Scholar
• Balas E., Ceria S., Cornuéjols G. Mixed 0-1 programming by lift-and-project in a branch-and-cut framework. Management Sci. (1996) 42:1229–1246Link, Google Scholar
• Charnes A., Cooper W. W.Management Models and Industrial Applications of Linear Programming (1961) (Wiley, New York) Google Scholar
• Chvátal V. Hard knapsack problems. Oper. Res. (1980) 28:1402–1411Link, Google Scholar
• Cook W., Rutherford T., Scarf H. E., Shallcross D. An implementation of the generalized basis reduction algorithm for integer programming. ORSA J. Comput. (1993) 3:206–212Link, Google Scholar
• Crowder H. P., Johnson E. L., Hu T. C., Robinson S. M. Use of cyclic group methods in branch-and-bound. Mathematical Programming (1973) (Academic Press, New York, T.C.) 213–216Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (Freeman, San Francisco) 223Google Scholar
• Gomory R. E. On the relation between integer and non-integer solutions to linear programs. Proc. National Acad. Sci. (1965) 53:260–265Crossref, Google Scholar
• Gorry G. A., Northup W. D., Shapiro J. F. Computational experience with a group theoretic integer programming algorithm. Math. Programming (1973) 4:171–192Crossref, Google Scholar
• Gorry G. A., Shapiro J. F. An adaptive group theoretic algorithm for integer programming problems. Management Sci. (1971) 7:285–306Link, Google Scholar
• Gorry G. A., Shapiro J. F., Wolsey L. A. Relaxation methods for pure and mixed integer programming problems. Management Sci. (1972) 18:229–239Link, Google Scholar
• Lenstra H. W. Integer programming with a fixed number of variables. Math. Oper. Res. (1983) 8:538–547Link, Google Scholar
• Loávasz L., Scarf H. The generalized basis reduction algorithm. Math. Oper. Res. (1992) 17:751–763Link, Google Scholar
• Martello S., Toth P.Knapsack Problems: Algorithms and Computer Implementations (1990) (Wiley, Chichester, UK) 108–109Google Scholar
• Martello S., Toth P. A mixture of dynamic programming and branch-and-bound for the subset sum problem. Management Sci. (1984) 30:765–771Link, Google Scholar
• Minoux M.Mathematical Programming: Theory and Algorithms (1986) (Wiley, NY) Google Scholar
• Wang X. A new implementation of the generalized basis reduction algorithm for convex integer programming. (1997) (Yale University, New Haven, CT) . Ph.D. dissertation (in preparation)Google Scholar
• Wang X.Private Communication. (1997) Google Scholar
• Williams H. P.Model Building in Mathematical Programming (1978) (Wiley, NY) Google Scholar
• Wolsey L. A. Group-theoretic results in mixed integer programming. Oper. Res. (1971) 19:1691–1697Link, Google Scholar
• Wolsey L. A. Extensions of the group theoretic approach in integer programming. Management Sci. (1971) 18:74–83Link, Google Scholar
• Wolsey L. A.Private CommunicationGoogle Scholar