An exact algorithm for general, orthogonal, two-dimensional knapsack problems

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

ELSEVIER

European Journal of Operational Research 83 (1995) 39-56

Theory and Methodology

An exact algorithm for general, orthogonal, two-dimensional knapsack problems Eleni Hadjiconstantinou *, Nicos Christofides The Management Schoo~ Imperial College of Science, Technology and Medicine, London SW7 2PG, UK

Received February 1992; revised June 1993

Abstract

We present a new exact tree-search procedure for solving two-dimensional knapsack problems in which a number of small rectangular pieces, each of a given size and value, are required to be cut from a large rectangular stock plate. The objective is to maximise the value of pieces cut or minimise the wastage. We consider the case where there is a maximum number of times that a piece may be used in a cutting pattern. The algorithm limits the size of the tree search by using a bound derived from a Lagrangean relaxation of a 0-1 integer programming formulation of the problem. Subgradient optimisation is used to optimise this bound. Reduction tests derived from both the original problem and the Lagrangean relaxation produce substantial computational gains. The computational performance of the algorithm indicates that it is an effective procedure capable of solving optimally practical two-dimensional cutting problems of medium size. Keywords: Two-dimensional; knapsack problem; Optimisation; Integer Programming

1. Introduction

T h e problem of cutting a plane rectangle into smaller rectangular pieces - each piece having a given size and value - in such a way so as to maximise the total value of pieces cut, is known as the 'knapsack problem'; in the practical literature, this is also known as the 'two-dimensional cutting-stock problem'. T h e constrained form of this problem imposes restrictions on the n u m b e r of pieces of each size required to be cut. By taking the value of a piece to be proportional to its area, the problem of minimising the amount of waste produced can be converted into the value maximisation problem. Examples of two-dimensional cutting problems can be found in many industries, including aerospace, shipbuilding, steel construction, clothing, fiat glass and furniture. Since the 1950's, the cutting stock p r o b l e m has received considerable attention as computers have b e c o m e fast and as the optimisation techniques have developed. Combinatorial optimisation is used extensively for the solution of this problem. T h e approaches proposed are summarized as survey articles by Hinxman (1980), Golden (1976), * Corresponding author. 0377-2217/95/$09.50 © 1995 Elsevier Science B.V. All fights reserved SSDI 0377-2217(93)E0278-6

40

E. Hadjiconstantinou, N. Christofides~European Journal of Operational Research 83 (1995) 39-56

Dyckhoff et al (1988), Haessler et al. (1991) and Madsen (1990). For a bibliography and a typology of problems see Dyckhoff (1990, 1992). Rectangular items can be cut in orthogonal or non-orthogonal patterns. In orthogonal patterns, the edges of small items are arranged to be parallel to the large object's edges, whereas in the non-orthogonal patterns, the angle is optional. A special case of orthogonal cutting problems allows only uninterrupted cuts to go from one end of the object to the opposite end, so that the cuts made are of 'guillotine' type. Dynamic and linear programming have been used extensively for solving this type of problem. Gilmore and Gomory (1965, 1967), Beasley (1985a) and Hertz (1972) solved the 2-D guillotine unconstrained problem where the number of times that a piece may be used in a cutting pattern is not limited. The constrained version of this problem has been solved by Christofides and Whitlock (1977) and Christofides and Hadjiconstantinou (1992) who proposed exact tree-search procedures. Wang (1983) and Oliveira and Ferreira (1990) developed heuristic algorithms for the same problem. Problems in which the optimal cutting patterns of rectangles are not restricted to those with the guillotine property, for example, cutting thick metal sheets, are much harder to solve. Non-Guillotine Cutting (NGC) problems have been considered by relatively few authors in the literature who have mainly proposed heuristic methods with worst-case and average-case performance botmds to solve various special cases of the problem, for example, the bin packing and pallet loading problems; see Baker et al. (1980, 1981), Coffman et al. (1984, 1990), Biro and Boros (1984), Smith and De Cani (1980), Bischoff and Dowsland (1982), Dowsland (1987, 1990), Hodgson (1982), Hodgson et al. (1983), Dagli and Tatoglu (1987), Farley (1990) and Daniels et al. (1990). Beasley (1985b) presented an exact tree search procedure for solving general NGC problems of small to medium size. In this paper, we present a new tree search algorithm for the solution of the two-dimensional constrained NGC problem. The algorithm limits the size of the tree search by using a tighter Upper bound derived from a Lagrangean Relaxation (LR) of a 0-1 integer programming formulation of the original problem. A subgradient optimisation method is given for minimising the resulting upper bound. Computational gains are achieved by applying reductions tests which are derived from both the original problem and the Lagrangean relaxation. The algorithm is tested on a number of randomly generated problems and computational results are presented.

2. Problem formulation

The constrained two-dimensional NGC problem is defined as follows: Let A 0 = (a0,/30) be a rectangular stock sheet having length a0 and width/30 and let R be a set of m smaller rectangular pieces R~, R 2 . . . . . R,n with dimensions (al,/31), ( a 2 , / 3 2 ) , . . . , ( a m , /3m) and a corresponding value u 1, v 2. . . . , v m. The objective is to construct a non-guillotine cutting pattern for A 0 with the highest possible total value using no more than Qi replicates of each piece R i for all i = 1.... , m. There is also a minimum requirement of Pi replicates of each piece R; to be used in the pattern. In order to distinguish between the given pieces in set R and the rectangles produced by the cuts on A 0 at any stage during the cutting process, we will refer to the former as 'pieces' and the latter as 'rectangles'. We assume the following: (i) All dimensions (ai,/3i), for i = 0 . . . . . m, are assumed integers and therefore the cuts on the rectangles are to be made in integer steps along the x- or y-axes. This limitation is not serious since in practice the actual dimensions can be scaled up. (ii) The orientation of the pieces is considered to be fixed, that is, a piece of length e and width f is not the same as a piece of length f and width e.

E. Hadjiconstantinou, N. Christofides / European Journal of Operational Research 83 (1995) 39-56

41

Rectangle A 0

[5o

Piece i

i-0

I I

p

r

o~0

Fig. 1. Locating a piece (ai, [~i) cut from A 0.

In order to formulate the problem as a z e r o - o n e integer p r o g r a m m i n g problem, let L i = {x l0 _