A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths (Q2884299)

The goal of the cutting stock problem (CSP) is to pack a set \(\Omega\) of \(n\) objects into the minimum possible number of bins, each of integer capacity \(\beta\). Objects are of \(d\) different types \(T=\{T_1, T_2, \dots,T_d\}\), where \(d\) is constant and objects of type \(T_i\) have positive integer length \(p_i\).NEWLINENEWLINEIt is known that CSP is strongly NP-hard, and no approximation algorithm for it can have approximation ratio smaller than 3/2 unless \(\mathrm{P}=\mathrm{NP}\).NEWLINENEWLINEIn this paper the authors present a polynomial \(d^{O(d2^d)}\times 2^{O(8^d)}\times O((\log^2n+\log\beta)^3\log^5n)\) time algorithm that computes a solution using at most one more bin than an optimum solution. The crucial ideas behind the algorithm are the integer programming formulation (IP) for CSP of \textit{P. C. Gilmore} and \textit{R. E. Gomory} [Oper. Res. 9, 849--859 (1961; Zbl 0096.35501)]; partitioning the set of objects into large and small ones and rewriting the IP so that only constant number of constraints is needed to restrict the placement of big objects into the bins; and obtaining a mixed-integer program (MIP) with a constant number of integer variables by relaxing integrality constraints on the variables controlling the packing for the small objects.NEWLINENEWLINEFinally, the authors prove that \textit{H. W. Lenstra jun.}'s algorithm [Math. Oper. Res. 8, 538--548 (1983; Zbl 0524.90067)] can be used to solve MIP in polynomial time.