A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem

The two-dimensional orthogonal non-guillotine cutting problem (NGCP) appears in many industries (like wood and steel industries) and consists in cutting a rectangular master surface into a number of rectangular pieces, each with a given size and value. The pieces must be cut with their edges always parallel or orthogonal to the edges of the master surface (orthogonal cuts). The objective is to maximize the total value of the pieces cut.In this paper, we propose a two-level approach for solving the NGCP, where, at the first level, we select the subset of pieces to be packed into the master surface without specifying the layout, while at a second level we check only if a feasible packing layout exists. This approach has been already proposed by Fekete and Schepers [S.P. Fekete, J. Schepers, A new exact algorithm for general orthogonal d-dimensional knapsack problems, ESA 97, Springer Lecture Notes in Computer Science 1284 (1997) 144–156; S.P. Fekete, J. Schepers, On more-dimensional packing III: Exact algorithms, Tech. Rep. 97.290, Universität zu Köln, Germany, 2000; S.P. Fekete, J. Schepers, J.C. van der Veen, An exact algorithm for higher-dimensional orthogonal packing, Tech. Rep. Under revision on Operations Research, Braunschweig University of Technology, Germany, 2004] and Caprara and Monaci [A. Caprara, M. Monaci, On the two-dimensional knapsack problem, Operations Research Letters 32 (2004) 2–14]. We propose improved reduction tests for the NGCP and a cutting-plane approach to be used in the first level of the tree search to compute effective upper bounds.Computational tests on problems derived from the literature show the effectiveness of the proposed approach, that is able to reduce the number of nodes generated at the first level of the tree search and the number of times the existence of a feasible packing layout is tested.     

New lower bounds for the three-dimensional finite bin packing problem

The three-dimensional finite bin packing problem (3BP) consists of determining the minimum number of large identical three-dimensional rectangular boxes, bins, that are required for allocating without overlapping a given set of three-dimensional rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. We propose new lower bounds for the problem where the items have a fixed orientation and then we extend these bounds to the more general problem where for each item the subset of rotations by 90° allowed is specified. The proposed lower bounds have been evaluated on different test problems derived from the literature. Computational results show the effectiveness of the new lower bounds.     

Bounds for Two-Dimensional Cutting

This note considers the problem of cutting rectangular pieces from a single large rectangle so as to maximize the value of the pieces cut. A number of bounds that can be used in any tree search procedure for the problem are derived from a zero-one formulation of the problem. Computational results are presented.     

The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case

The Two-Dimensional Finite Bin Packing Problem (2BP) consists of determining the minimum number of large identical rectangles, bins, that are required for allocating without overlapping a given set of rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. In this paper we describe new lower bounds for the 2BP where the items have a fixed orientation and we show that the new lower bounds dominate two lower bounds proposed in the literature. These lower bounds are extended in Part II (see Boschetti and Mingozzi 2002) for a more general version of the 2BP where some items can be rotated by . Moreover, in Part II a new heuristic algorithm for solving both versions of the 2BP is presented and computational results on test problems from the literature are given in order to evaluate the effectiveness of the proposed lower bounds.     

Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints

The paper examines a new problem in the irregular packing literature that has many applications in industry: two-dimensional irregular (convex) bin packing with guillotine constraints. Due to the cutting process of certain materials, cuts are restricted to extend from one edge of the stock-sheet to another, called guillotine cutting. This constraint is common place in glass cutting and is an important constraint in two-dimensional cutting and packing problems. In the literature, various exact and approximate algorithms exist for finding the two dimensional cutting patterns that satisfy the guillotine cutting constraint. However, to the best of our knowledge, all of the algorithms are designed for solving rectangular cutting where cuts are orthogonal with the edges of the stock-sheet. In order to satisfy the guillotine cutting constraint using these approaches, when the pieces are non-rectangular, practitioners implement a two stage approach. First, pieces are enclosed within rectangle shapes and then the rectangles are packed. Clearly, imposing this condition is likely to lead to additional waste. This paper aims to generate guillotine-cutting layouts of irregular shapes using a number of strategies. The investigation compares three two-stage approaches: one approximates pieces by rectangles, the other two approximate pairs of pieces by rectangles using a cluster heuristic or phi-functions for optimal clustering. All three approaches use a competitive algorithm for rectangle bin packing with guillotine constraints. Further, we design and implement a one-stage approach using an adaptive forest search algorithm. Experimental results show the one-stage strategy produces good solutions in less time over the two-stage approach.     

A hybrid genetic algorithm for the two-dimensional single large object placement problem

In the two-dimensional single large object placement problem, we are given a rectangular master surface which has to be cut into a set of smaller rectangular items, with the aim of maximizing the total value of the pieces cut. We consider the special case in which the items cannot be rotated and must be cut with their edges always parallel to the edges of the surface. We present new greedy algorithms and a hybrid genetic approach with elitist theory, immigration rate, heuristics on-line and tailored crossover operators. Extensive computational results for a large number of small and large benchmark test problems are presented. The results show that our approach outperforms existing heuristic algorithms.     

Fast heuristic for constrained homogenous T-shape cutting patterns

Homogenous T-shape (HTS) cutting patterns are welcomed when the two-phase process is used to produce rectangular pieces from the stock plate, where the plate is cut into homogenous strips at the first phase, and the strips are divided into pieces at the second phase. A heuristic is presented for generating constrained HTS patterns, where the objective is to maximize the pattern value that is equal to the total value of the included pieces, observing the upper bound constraint on the frequency of each piece type. The heuristic is based on dynamic programming and branch-and-bound techniques. It can yield solutions close to optimal with short computation time. By providing good initial solutions, the heuristic can greatly improve the time efficiency of an existing exact branch-and-bound algorithm.     

A tabu search algorithm for a two-dimensional non-guillotine cutting problem

In this paper we study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems.     

The minimum size instance of a Pallet Loading Problem equivalence class

The Pallet Loading Problem (PLP) maximizes the number of identical rectangular boxes placed within a rectangular pallet. Boxes may be rotated 90° so long as they are packed with edges parallel to the pallet’s edges, i.e., in an orthogonal packing. This paper defines the Minimum Size Instance (MSI) of an equivalence class of PLP, and shows that every class has one and only one MSI. We develop bounds on the dimensions of box and pallet for the MSI of any class. Applying our new bounds on MSI dimensions, we present an algorithm for MSI generation and use it to enumerate all 3,080,730 equivalence classes with an area ratio (pallet area divided by box area) smaller than 101 boxes. Previous work only provides bounds on the ratio of box dimensions and only considers a subset of all classes presented here.     

A MIP-CP based approach for two- and three-dimensional cutting problems with staged guillotine cuts

This work presents guillotine constraints for two- and three-dimensional cutting problems. These problems look for a subset of rectangular items of maximum value that can be cut from a single rectangular container. Guillotine constraints seek to ensure that items are arranged in such a way that cuts from one edge of the container to the opposite edge completely separate them. In particular, we consider the possibility of 2, 3, and 4 cutting stages in a predefined sequence. These constraints are considered within a two-level iterative approach that combines the resolution of integer linear programming and constraint programming models. Experiments with instances of the literature are carried out, and the results show that the proposed approach can solve in less than 500 s approximately 60% and 50% of the instances for the two- and three-dimensional cases, respectively. For the two-dimensional case, in comparison with the recent literature, it was possible to improve the upper bound for 16% of the instances.

     

Algorithms for Unconstrained Two-Dimensional Guillotine Cutting

In this paper we consider the unconstrained, two-dimensional, guillotine cutting problem. This is the problem that occurs in the cutting of a number of rectangular pieces from a single large rectangle, so as to maximize the value of the pieces cut, where any cuts that are made are restricted to be guillotine cuts.We consider both the staged version of the problem (where the cutting is performed in a number of distinct stages) and the general (non-staged) version of the problem.A number of algorithms, both heuristic and optimal, based upon dynamic programming are presented. Computational results are given for large problems.     

Improved state space relaxation for constrained two-dimensional guillotine cutting problems

Christofides and Hadjiconstantinou (1995) introduced a dynamic programming state space relaxation for obtaining upper bounds for the Constrained Two-dimensional Guillotine Cutting Problem. The quality of those bounds depend on the chosen item weights, they are adjusted using a subgradient-like algorithm. This paper proposes Algorithm X, a new weight adjusting algorithm based on integer programming that provably obtains the optimal weights. In order to obtain even better upper bounds, that algorithm is generalized into Algorithm X2 for obtaining optimal two-dimensional item weights. We also present a full hybrid method, called Algorithm X2D, that computes those strong upper bounds but also provides feasible solutions obtained by: (1) exploring the suboptimal solutions hidden in the dynamic programming matrices; (2) performing a number of iterations of a GRASP based primal heuristic; and (3) executing X2H, an adaptation of Algorithm X2 to transform it into a primal heuristic. Extensive experiments with instances from the literature and on newly proposed instances, for both variants with and without item rotation, show that X2D can consistently deliver high-quality solutions and sharp upper bounds. In many cases the provided solutions are certified to be optimal.     

A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems

This paper presents a greedy randomized adaptive search procedure (GRASP) for the constrained two-dimensional non-guillotine cutting problem, the problem of cutting the rectangular pieces from a large rectangle so as to maximize the value of the pieces cut. We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well-known instances previously reported, first to select the best alternatives and then to compare the efficiency of our algorithm with other procedures.     

MIP models for two-dimensional non-guillotine cutting problems with usable leftovers

In this study we deal with the two-dimensional non-guillotine cutting problem of how to cut a set of larger rectangular objects to a set of smaller rectangular items in exactly a demanded number of pieces. We are concerned with the special case of the problem in which the non-used material of the cutting patterns (objects leftovers) may be used in the future, for example if it is large enough to fulfill future item demands. Therefore, the problem is seen as a two-dimensional non-guillotine cutting/packing problem with usable leftovers, also known in the literature as a two-dimensional residual bin-packing problem. We use multilevel mathematical programming models to represent the problem appropriately, which basically consists of cutting the ordered items using a set of objects of minimum cost, among all possible solutions of minimum cost, choosing one that maximizes the value of the usable leftovers, and, among them, selecting one that minimizes the number of usable leftovers. Because of special characteristics of these multilevel models, they can be reformulated as one-level mixed integer programming (MIP) models. Illustrative numerical examples are presented and analysed.     

T-shape homogenous block patterns for the two-dimensional cutting problem

This paper presents an algorithm for unconstrained T-shape homogenous block cutting patterns of rectangular pieces. A vertical cut divides the stock sheet into two segments. Each segment consists of sections that have the same length and direction. A section contains a row of homogenous blocks. A homogenous block consists of homogenous strips of the same piece type. Each cut on the block produces just one strip. The directions of two strips cut successively from a block are either parallel or orthogonal. The algorithm uses a dynamic programming recursion to generate optimal blocks, solves knapsack problems to obtain the block layouts on the sections and the section layout on segments of various lengths, and optimally selects two segments to compose the cutting pattern. The computational results indicate that the algorithm is efficient in improving material usage, and the computation time is reasonable.     

Strip generation algorithms for constrained two-dimensional two-staged cutting problems

The constrained two-dimensional cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate of length L and width W, as to maximize the sum of the profits of the pieces to be cut. Each piece type i, i = 1, …, n, is characterized by a length l_i, a width w_i, a profit (or weight) c_i and an upper demand value b_i. The upper demand value is the maximum number of pieces of type i which can be cut on rectangle (L, W). In this paper, we study the two-staged fixed orientation C_TDC, noted FC_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two guillotine cuts, and each piece has a fixed orientation. We solve the FC_2TDC problem using several approximate algorithms, that are mainly based upon a strip generation procedure. We evaluate the performance of these algorithms on instances extracted from the literature.     

Bidirectional best-fit heuristic for orthogonal rectangular strip packing

In a non-guillotinable rectangular strip packing problem (RF-SPP), the best orthogonal placement of given rectangular pieces on a strip of stock sheet having fixed width and infinite height are searched. The aim is to minimize the height of the strip while including all the pieces in appropriate orientations. In this study, a novel bidirectional best-fit heuristic (BBF) is introduced for solving RF-SPPs. The proposed heuristic as a new feature considers the gaps in both horizontal and vertical directions during the placement process. The performance of BBF is compared to some previous approaches, including one of the best heuristics from the literature. BBF achieves better results than the existing heuristics and delivers a better or matching performance as compared to the most of the previously proposed meta-heuristics for solving RF-SPPs.     

New formulations of the Hop-Constrained Minimum Spanning Tree problem via Miller-Tucker-Zemlin constraints

Given an undirected network with positive edge costs and a natural number p, the Hop-Constrained Minimum Spanning Tree problem (HMST) is the problem of finding a spanning tree with minimum total cost such that each path starting from a specified root node has no more than p hops (edges). In this paper, we develop new formulations for HMST. The formulations are based on Miller-Tucker-Zemlin (MTZ) subtour elimination constraints, MTZ-based liftings in the literature offered for HMST, and a new set of topology-enforcing constraints. We also compare the proposed models with the MTZ-based models in the literature with respect to linear programming relaxation bounds and solution times. The results indicate that the new models give considerably better bounds and solution times than their counterparts in the literature and that the new set of constraints is competitive with liftings to MTZ constraints, some of which are based on well-known, strong liftings of Desrochers and Laporte (1991).     

A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems

This paper is concerned with the problem of unconstrained two-dimensional cutting of small rectangular pieces, each of which has its own profit and size, from a large rectangular plate so as to maximize the profit-sum of the pieces produced. Hifi and Zissimopoulos's recursive algorithm using G and Kang's upper bound is presently the most efficient exact algorithm for the problem. We propose a best-first branch and bound algorithm based upon the bottom-up approach that is more efficient than their recursive algorithm. The proposed algorithm uses efficient upper bound and branching strategies that can reduce the number of nodes that must be searched significantly. We demonstrate the efficiency of the proposed algorithm through computational experiments.     

Simple block patterns for the two-dimensional cutting problem

This paper presents an algorithm for the unconstrained two-dimensional cutting problem of rectangular pieces. It proposes the simple block (SB) pattern consisting of simple blocks. The SB pattern is defined recursively. Each cut on the stock plate produces just one simple block. A horizontal cut produces a horizontal block with width equal to that of the leftmost piece in the block. A vertical cut produces a vertical block with length equal to that of the bottommost piece in the block. The algorithm generates the optimal SB pattern recursively, and selects optimally the first piece in each block. It uses upper bound to prune some unpromising branches during the searching process. The computational results indicate that the algorithm is highly efficient in improving material utilization, and the computation time is reasonable.