Abstract
We consider the well-known cutting stock problem (CSP). An instance of CSP possesses IRUP (the integer round up property) if difference (the gap) between its optimal function value and optimal value of its continuous relaxation is less than 1. If the gap is 1 or greater, then an instance is non-IRUP. Constructing non-IRUP instances is very hard and a question about how large the gap can be is an open theoretical problem. Aim of our research is to find non-IRUP instances with minimal capacity. We have found a non-IRUP instance with integer sizes of items having capacity \(L=16\), while a previously known instance of such kind had capacity \(L = 18\). We prove that all instances with capacity \(L \le 10\) have IRUP.
Supported by RFBR, project 19-07-00895.
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
In classic formulation, the cutting stock problem (CSP) is stated as follows: there are \(m \in \mathbb {N}\) groups of items of different lengths \(l_1, \cdots , l_m\) and availabilities \(b_1, \cdots , b_m\). The goal is to pack all items into the minimal number of containers of the same capacity L (the total length of all items inside any container should not exceed L).
The cutting stock problem is one of the earliest problems that have been studied through methods of operational research [10]. This problem has many real-world applications, especially in industries where high-value material is being cut [6] (steel industry, paper industry). No exact algorithm is known that solves practical problem instances optimality, so there are lots of heuristic approaches. Each year the number of publications about this problem increases, so we refer the reader to bibliography [20] and the most resent survey [4].
Throughout this paper we abbreviate an instance of CSP as \(E := (L,l,b)\). The total number of items is \(n = \sum _{i=1}^m b_i\). Without loss of generality, we assume that all numbers in the input data are positive integers and \(0< l_1< \cdots < l_m \le L\).
The classical approach for solving CSP is based on the formulation of Gilmore and Gomory [9]. Any subset of items (called a pattern) is formalized as a vector \(a = (a_1, \cdots , a_m)^\top \in \mathbb {Z}^m_+\) where \(a_i \in \mathbb {Z}_+\) denotes the number of items i in the pattern a. A pattern a of E is feasible if \(a^\top l \le L\). So, we can define the set of all feasible patterns \(P^f(E) = \{ a \in \mathbb {Z}^m_+ \; | \; a^\top l \le L \}\). For a given set of patterns \(P = \{ a^1, \cdots , a^r \}\), let A(P) be the \((n \times r)\)-matrix whose columns are given by the patterns \(a^i\). Then the CSP can be formulated as follows:
The common approximate solution approach involves considering the continuous relaxation of CSP
Here x and \(x^C\) are called the optimal solutions for the integer and continuous problems respectively, and z(E) and \(z_C(E)\) are called the optimal function values.
The difference \(\varDelta (E) = z(E) - z_C(E)\) is called the gap of instance E. Practical experience and numerous computations have shown that for most instances the gap is very small. An instance E has the integer round up property (IRUP) if \(\varDelta (E) < 1\). Otherwise, E is called a non-IRUP instance. This notation was introduced by Baum and Trotter [1]. Subsequently, the largest known gap was increased [7, 8, 14, 15, 17, 19]. Currently, the largest gap known is \(\frac{6}{5}\), and there is no example of a gap of at least 2.
The first known constructions of non-IRUP instances were rather huge. The example of Marcotte [14] having \(L = 3\,397\,386\,355\) was decreased to \(L = 1\,111\,139\) by Chan [3]. The authors of [2, 5] gave an example with \(L = 100\). In [13] an example with \(L = 18\) has been found using so-called equivalence of instances (see also [11, 12]). In this paper we focus on improving bounds for minimal possible L.
The paper has the following structure. In Sect. 2 we describe some theory related to our model which is presented in Sect. 3. In Sect. 4 we present computational results and, finally, we draw a conclusion in Sect. 5.
2 Preliminaries
In this section we describe some theory we use throughout the paper. We believe that results presented in this section are well-known, but we present their proofs for the sake of completeness. Anyway, the reader may be referred to [16, 18] where some results are mentioned.
Given an instance \(E = (L,l,b)\), let \(x^C\) be an optimal continuous solution of E. Then \(\overline{x}\) is the integer part of \(x^C\) and \(x^*\) is the fractional part of \(x^C\), so \(x^C = \overline{x} + x^*\) and \(0 \le x^*_i < 1\) for all \(1 \le i \le r\). Also \(z_C(E) = e^\top \overline{x} + e^\top x^*\) where \(e = (1,\cdots ,1) \in \mathbb {R}^m_+\). Replacing b by \(\overline{b} = b-A(P^f(E)) \overline{x}\) yields the residual instance \(\overline{E} = (L,l,\overline{b})\). An instance E is called reducible if there exists an optimal continuous solution of E with non-zero integer part.
Lemma 1
\(x^*\) is an optimal continuous solution of \(\overline{E}\).
Proof
On one hand, \(z_C(\overline{E}) \le e^\top x^*\) because \(x^*\) is a feasible solution for \(A(P^f(E))x=\overline{b}\). On the other hand \(z_C(E) \le e^\top \overline{x} + z_C(\overline{E})\) which is equivalent to \(z_C(\overline{E}) \ge e^\top x^*\). So, \(z_C(\overline{E}) = e^\top x^*\).
Lemma 2
\(\varDelta (E) \le \varDelta (\overline{E})\).
Proof
\(z(E) - z_C(E) \le (e^\top \overline{x} + z(\overline{E})) - (e^\top \overline{x} + e^\top x^*) = z(\overline{E}) - z_C(\overline{E})\).
Consider a set of instances \(\mathbb {E}(L,l) = \{ E(L,l,b) \; | \; b \in \mathbb {Z}^m_+ \}\) where L and l are fixed. Now we are interested in maximal possible the gap \(\varDelta (E)\) over all instances \(E \in \mathbb {E}(L,l)\).
Lemma 3
The maximal gap \(\varDelta (E)\) occurs over instances \(E \in \mathbb {E}(L,l)\) with \(z_C(E) < m\).
Proof
Consider an instance \(E \in \mathbb {E}(L,l)\) with \(z_C(E) \ge m\). There exists an optimal continuous solution \(x^C\) of E which has at most m non-zero components because all feasible patterns form a m-dimensional vector space. Then by the pigeonhole principle, \(x^C_i \ge 1\) for some \(1 \le i \le r\). Therefore E is reducible.
Using Lemma 3 we already can find the maximal possible gap over \(\mathbb {E}(L,l)\) in finite time iterating over all instances \(E \in \mathbb {E}(L,l)\) with \(z_C(E) < m\). However, we are going to improve this result.
Lemma 4
The maximal gap \(\varDelta (E)\) occurs over instances \(E \in \mathbb {E}(L,l)\) with \(z(E) \le m\).
Proof
Consider the m-dimensional vector space S induced by all feasible patterns. Let us build a convex hull H over all the feasible patterns and let \(F = \{ (f_1,\cdots ,f_m)^\top \}\) be a set of facets of H, where \(f_i \in P^f(E)\).
Consider some facet \(f = (f_1,\cdots ,f_m)^\top \in F\). The linear combination \(x^\top f\) where \(x \in \mathbb {R}^m_+\) covers some subspace \(S'\) of S. Every integer point \(b \in S'\) corresponds to an instance \(E = (L,l,b)\), and a vector x such that \(b = x^\top f\) can always be transformed into an optimal continuous solution \(x^C\) of E by inserting zero elements. Now consider a m-dimensional parallelepiped \(S'_1 \subset S' \subseteq S\) formed by linear combination \({x^1}^\top f\) where \(x^1 \in \mathbb {R}^m_+\) and \(0 \le x^1_i \le 1\) for all \(1 \le i \le m\). All integer points b inside \(S'_1\) correspond to instances E with \(z(E) \le m\). And all integer points b from \(S'\) outside \(S'_1\) correspond to reducible instances E.
We remark that Lemma 3 does not imply Lemma 4 directly because there exist instances E with \(z(E) \ge m+1\) and \(z_C(E) < m\) (and with \(\varDelta (E) > 1\)).
3 Model
Consider an instance \(E = (L, l, b)\) which possesses all possible item lengths: \(l = (1, \cdots , L)\). When L is fixed, l is fixed too. The matrix of patterns \(A(P^f(E))\) depends on L and l only, so it is also fixed. Availabilities of the item types b we consider as variables.
Now we build the following ILP model:
where k is the fixed value of z(E) for an optimal integer solution, x is the optimal continuous solution, and y is the optimal integer solution.
Now we have to ensure that k is indeed the optimal integer function value of E, i.e. a solution of the system where \(\sum y_i < k\) is impossible. To this end we add special constraints to bound the vector b:
Here, \(b_i \le u\) implies \(w^u_i = 1\). Now consider all integer solutions of size \(k-1\) \(C_{k-1}(E) := \{ A(P^f(E))y \; | \; y \in \mathbb {Z}^r_+ \; \wedge \; \sum y_i = k-1 \}\). To ensure that all integer solutions of the system are not less than k, we add the following constraints:
The latter constraint works as follows: for fixed \(c \in C_{k-1}(E)\), if \(b_i \le c_i\) for all \(1 \le i \le m\), then \(\sum w^{c_i}_i = m\) and we have an integer function value less than k.
For small values of L and k the model is small enough to be solved in reasonable time. However, the model can be reduced by the following observation: l can be \((1, \cdots , L-1)\) because any number of items of size L does not change the value of \(\varDelta (E)\). Also, the model can be further reduced by replacing the set of feasible patterns \(P^f(E)\) with a set of inextensible patterns \(P^f_*(E) = \{ a \in \mathbb {Z}^m_+ \; | \; a^\top l \le L \; \wedge \; a^\top l + l_1 > L \}\). To this end we also have to transform equations (1) and (2) into inequalities with the “\(\ge \)” sign. The final model is the following:
Now, using this model we can find instances with the maximal gap for fixed L and k, and using Lemma 4 we can build the lower bound for minimal possible L of non-IRUP instance by solving the model for all \(k < L\) for some fixed L.
4 Results
We implemented our model as C++ program using CPLEX 12.7. The program was run on machine Intel Core i7-5820K 4.2 GHz with 6 cores 32 Gb RAM. Results are presented in Table 1.
For \(L=10\) and \(k=9\) the ILP program had \(\approx 600\,000\) constraints and the running time was about 52 h. The following non-IRUP instances were found: \((16,(2,3,7,8,10)^\top ,(2,1,1,1,1)^\top )\) and \((16,(2,3,7,8,10)^\top ,(2,1,1,3,1)^\top )\).
It is possible to prove a more general result; namely, that a series of instances \(E_t = (16,(2,3,7,8,10)^\top ,(2,1,1,2t+1,1)^\top )\) is non-IRUP for every t. \(z(E_t) = t+3\), because it is easy to pack all the items into \(t+3\) containers, but it is impossible to pack them into \(t+2\) ones. Indeed, suppose it is possible, then all containers should be fully filled. By a parity argument, items of sizes 3 and 7 should be in a single container, but then there is no way to fill this container completely. \(z_C(E_t) \le t+2\) because there is a feasible solution \(\frac{1}{2}(0,2,0,0,1)^\top + \frac{1}{2}(3,0,0,0,1)^\top + \frac{2t+1}{2}(0,0,0,2,0)^\top + \frac{1}{2}(1,0,2,0,0)^\top \). So, \(\varDelta (E_t) \ge 1\).
5 Conclusion
We have suggested a model to calculate the maximal possible gap for the fixed capacity L and the optimal integer function value k and have run it for small values of L and k. We have improved the best known bound for minimal capacity of non-IRUP instance from \(L=18\) to \(L=16\). Also we have computationally proved that all instances with \(L \le 10\) have IRUP.
We conjecture that \(L=16\) is the sharp bound for the minimal possible L and we plan to improve our model to prove this conjecture.
References
Baum, S., Trotter Jr., L.: Integer rounding for polymatroid and branching optimization problems. SIAM J. Algebraic Discrete Methods 2(4), 416–425 (1981)
Caprara, A., Dell’Amico, M., Díaz Díaz, J., Iori, M., Rizzi, R.: Friendly bin packing instances without integer round-up property. Math. Program. Series A and B (2014). https://doi.org/10.1007/s10107-014-0791-z
Chan, L., Simchi-Levi, D., Bramel, J.: Worst-case analyses, linear programming and the bin-packing problem. Math. Program. 83(1–3), 213–227 (1998)
Delorme, M., Iori, M., Martello, S.: Bin packing and cutting stock problems: mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1), 1–20 (2016)
Díaz Díaz, J.: Exact and heuristic solutions for combinatorial optimization problems. Ph.D. thesis, Università Degli Studi di Modena e Reggio Emilia (2012)
Dyckhoff, H., Kruse, H.J., Abel, D., Gal, T.: Trim loss and related problems. Omega 13(1), 59–72 (1985)
Fieldhouse, M.: The duality gap in trim problems. SICUP Bull. 5(4) (1990)
Gau, T.: Counter-examples to the IRU property. SICUP Bull. 12(3) (1994)
Gilmore, P., Gomory, R.: A linear programming approach to the cutting-stock problem. Oper. Res. 9(6), 849–859 (1961)
Kantorovich, L.V.: Mathematical methods of organizing and planning production. Manage. Sci. 6(4), 366–422 (1960)
Kartak, V.M., Ripatti, A.V.: Large proper gaps in bin packing and dual bin packing problems. J. Global Optim. (2018). https://doi.org/10.1007/s10898-018-0696-0
Kartak, V.M., Ripatti, A.V.: The minimum raster set problem and its application to the d-dimensional orthogonal packing problem. Eur. J. Oper. Res. 271(1), 33–39 (2018). https://doi.org/10.1016/j.ejor.2018.04.046
Kartak, V.M., Ripatti, A.V., Scheithauer, G., Kurz, S.: Minimal proper non-IRUP instances of the one-dimensional cutting stock problem. Discrete Appl. Math. 187(Complete), 120–129 (2015)
Marcotte, O.: An instance of the cutting stock problem for which the rounding property does not hold. Oper. Res. Lett. 4(5), 239–243 (1986)
Rietz, J., Dempe, S.: Large gaps in one-dimensional cutting stock problems. Discrete Appl. Math. 156(10), 1929–1935 (2008)
Rietz, J., Scheithauer, G., Terno, J.: Tighter bounds for the gap and non-IRUP constructions in the one-dimensional cutting stock problem. Optimization 51(6), 927–963 (2002)
Scheithauer, G., Terno, J.: About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem. In: Gaul, W., Bachem, A., Habenicht, W., Runge, W., Stahl, W.W. (eds.) Operations Research Proceedings, vol. 1991, pp. 439–444. Springer, Heidelberg (1992). https://doi.org/10.1007/978-3-642-46773-8_111
Scheithauer, G., Terno, J.: The modified integer round-up property of the one-dimensional cutting stock problem. Eur. J. Oper. Res. 84(3), 562–571 (1995)
Scheithauer, G., Terno, J.: Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem. Oper. Res. Lett. 20(2), 93–100 (1997)
Sweeney, P.E., Paternoster, E.R.: Cutting and packing problems: a categorized, application-orientated research bibliography. J. Oper. Res. Soc. 43(7), 691–706 (1992)
Acknowledgements
The authors would like to thank the anonymous referees for valuable remarks.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Ripatti, A.V., Kartak, V.M. (2019). Bounds for Non-IRUP Instances of Cutting Stock Problem with Minimal Capacity. In: Bykadorov, I., Strusevich, V., Tchemisova, T. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Communications in Computer and Information Science, vol 1090. Springer, Cham. https://doi.org/10.1007/978-3-030-33394-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-33394-2_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-33393-5
Online ISBN: 978-3-030-33394-2
eBook Packages: Computer ScienceComputer Science (R0)