A Polynomial Time OPT + 1 Algorithm for the Cutting Stock Problem with a Constant Number of Object Lengths

References

• Coffman E. G., Garey M. R., Johnson D. S., Hochbaum D. S. Approximation algorithms for bin packing: A survey. Approximation Algorithms for NP-Hard Problems (1997) (PWS Publishing Company, Boston) 46–86Google Scholar
• Dantzig G. B., Thapa M. N.Linear Programming: Theory and Extensions (2003) (Springer, New York) Google Scholar
• Eisemann K. The trim problem. Management Sci. (1957) 3(3):279–284Link, Google Scholar
• Eisenbrand F., Shmonin G. Carathéorody bounds for integer cones. Oper. Res. Lett. (2006) 34:564–568Crossref, Google Scholar
• Filippi C. On the bin packing problem with a fixed number of object weights. Eur. J. Oper. Res. (2007) 181:117–126Crossref, Google Scholar
• Filippi C., Agnetis A. An asymptotically exact algorithm for the high-multiplicity bin packing problem. Math. Programming (2005) 104(1):21–57Crossref, Google Scholar
• Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem. Oper. Res. (1961) 9(6):849–859Link, Google Scholar
• Grötschel M., Lovász L., Schrijver A. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica (1981) 1(2):169–197Crossref, Google Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization (1988) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Hochbaum D. S., Shamir R. Strongly polynomial algorithms for the high multiplicity scheduling problem. Oper. Res. (1991) 39:648–653Link, Google Scholar
• Kaltofen E., Villard G. On the complexity of computing determinants. Computational Complexity (2004) 13(3-4):91–130Crossref, Google Scholar
• Kannan R. Minkowski's convex body theorem and integer programming. Math. Oper. Res. (1987) 12(3):415–440Link, Google Scholar
• Kannan R., Bachem A. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput. (1979) 8(4):499–507Crossref, Google Scholar
• Karmakar N., Karp R. M. An efficient approximation scheme for the one-dimensional bin packing problem. Proc. 23rd Annual Sympos. Foundations Comput. Sci. (1982) Chicago(IEEE Computer Society, Washington, DC) 312–320Google Scholar
• Khachiyan L. G. A polynomial algorithm in linear programming. Dokladi Akadademii Nauk SSSR (1979) 244:1093–1096[English translation: 1979. Soviet Math. Doklady 20 191–194.]Google Scholar
• Lenstra A. K., Lenstra H. W., Lovász L. Factoring polynomials with rational coefficients. Mathematische Annalen (1982) 261:515–534Crossref, Google Scholar
• Lenstra H. W. Integer programming with a fixed number of variables. Math. Oper. Res. (1983) 8(4):538–548Link, Google Scholar
• Marcotte O. The cutting stock problem and integer rounding. Math. Programming (1985) 33(1):82–92Crossref, Google Scholar
• McCormick S. T., Smallwood S. R., Spieksma F. C. R. A polynomial algorithm for multiprocessor scheduling with two job lengths. Math. Oper. Res. (2001) 26(1):31–49Link, Google Scholar
• Orlin J. B. A polynomial algorithm for integer programming covering problems satisfying the integer round-up property. Math. Programming (1982) 22:231–235Crossref, Google Scholar
• Papadimitriou C. H., Steiglitz K.Combinatorial Optimization: Algorithms and Complexity (1982) (Prentice-Hall, Inc., Englewood Cliffs, NJ) Google Scholar
• Schrijver A.Theory of Linear and Integer Programming (1986) (John Wiley, Chichester, UK) Google Scholar