Polygon plate-cutting with a given order.

This note is a complement to the paper by Hoeft and Palekar [1] which describes the problem of cutting polygonal shapes from large plates of metal or glass. More specifically, we focus on polynomial time solvability for a number of subproblems of the more general plate-cutting problem. A primary

1. Introduction

Given a set of planar polygons drawn on a two-dimensional sheet (paper, metal, glass), when can we decide (in polynomial time) the optimal cutting sequence (the actual movements of a cutting instrument) for these polygons? In a recent paper by Hoeft and Palekar [1], a problem of constructing an optimal cutting sequence for a given set of simple polygons (polygons with no crossing edges) was presented. The problem is motivated by real-life applications. The movement sequence of the cutting instrument is described as a tour; i.e., an ordered sequence of direct movements between a given set of objects in a two-dimensional (Euclidian) space, starting and returning to a prespecified point. See Fig. 1 for an illustration of a typical plate-cutting problem with a cutting path (taken with permission from Hoeft and Palekar [1]).

Hoeft and Palekar have defined three cutting restriction scenarios as follows:

(1) Continuous cutting problem: here the tool path visits each object to be cut once. The tool can engage the object at any point on its perimeter, but must cut the entire object before it travels to the next object. Accordingly, the same point must be used for entry and departure from the object.

(2) Endpoint cutting problem: here the tool can enter and exit the object only at some predefined points on the boundary; however, it may cut the shape in sections.

(3) Intermittent cutting problem: this is the most general version of the problem in which the object can be cut in sections and there is no restriction on the points that can be used for entry and exit.

Hoeft and Palekar focused on the continuous cutting problem and they presented a mathematical programming formulation which casts their problem as a version of the Generalized Traveling Salesman Problem (GTSP) [2,3]. From there, it is concluded that the continuous cutting problem is NP-hard and this justifies a heuristic solution approach for the problem. The main step in the solution approach for the continuous cutting problem in the Hoeft and Palekar heuristic consists of constructing a "good" solution to the plate-cutting problem with given order; i.e., the problem in which the order of the polygons is given in advance and what has to be determined is the edge to be visited and the entry/exit point on the edge for each polygon.

It is immediately clear that this plate-cutting problem with given order no longer has the TSP (or the GTSP) structure, and therefore no claim is made as to its complexity (polynomial time solvability or NP-hardness). Still, the plate-cutting problem with given order is solved using a heuristic solution procedure based on a Lagrangian relaxation methodology.

In what follows, we prove that the plate-cutting problem with given order is solvable in polynomial time and examine a number of other plate-cutting problem settings that can also be solved in polynomial time in a similar fashion. We start with a number of simple observations.

* Any polygon P (simple or not) in two-dimensional Euclidian space can be represented by a graph G = (V, E) whose edges correspond to the edges of the polygon and its nodes correspond to the corner points of the polygon.

* Given a polygon in two-dimensional space, finding an optimal sequence (tour) of edge traversals (corresponding to polygon edge cutting in the plate cutting case) is equivalent to constructing an optimal Euler tour on the corresponding graph.

* The optimal edge cutting sequence for any polygon P in two-dimensional space can be constructed in O([\V\.sup.3]) time, where V is the set of corner points, as a solution to the corresponding Chinese Postman Problem (CPP) on the graph G.

The observations above can be easily extended to n-dimensional Euclidian space replacing the term "polygon" with "bounded polyhedron." However, in n-dimensional space for n [greater than or equal to] 3 one cannot simply traverse the edges (intersections of two faces) of the bounded polyhedron in order starting to the "left" or to the "right" of the entry/exit point on the polygon but one must construct the optimal Euler tour (CPP solution). We start with a somewhat simpler problem first.

2. Given order, corner entry/exit points for the plate-cutting problem

Problem 1 -- (P1). Suppose a finite set of K polygons in two-dimensional space with a set of K graphs [G.sub.1],...,[G.sub.K] (corresponding to the polygons) in the order in which the plate-cutting has to be performed. In addition, assume that one can enter each graph only at a node (any node). Let D = ([d.sub.ij]) be the "distance" matrix between all the node points of the different graphs. Given the matrix D, construct a closed tour of minimum length that visits each of the graphs once (i.e., enters and exits each of the graphs at the same node).

Denote by [n.sub.k] the number of nodes in the graph [G.sub.k] corresponding to the [k.sup.th] polygon.

Claim 1. An optimal solution to P1 can be constructed in O([n.sub.1](nlogn)) time, where n = [[[sigma].sup.k].sub.k=2][n.sub.k] + 2.

Proof. The proof follows the construction steps similar to those described in Dror et al. [4] for (K + 1) bipartite graphs [G.sub.i] ([V.sub.i], [E.sub.i]) for i = 1,...,[n.sub.1] An optimal solution is found by solving [n.sub.1] shortest path problems on each [G.sub.i] and comparing the solutions to obtain the optimal solution to P1.

Let [G.sub.i] (the K + 1 bipartite graph) be constructed as follows. Take a single node i [epsilon] [V.sub.1] as the first node set and the complete node sets [V.sub.2],...,[V.sub.K]. As the K + 1 node set take again the same node i [epsilon] [V.sub.1] and construct a K + 1 bipartite graph. Each node in [V.sub.k] is connected to all the nodes in [V.sub.k+1] (k = l,...,K, and [V.sub.1] = i, [V.sub.K+1] = i) with arcs of the length taken from the distance matrix D. Clearly, the shortest path solution on each such K + 1 bipartite graph corresponds to the optimal entry/exit node selection for each polygon given that the entry/exit node on the first polygon is the node i. Thus this procedure has to be repeated [n.sub.1] times to select the optimal entry/exit point in the first polygon.

Corollary 1. Given that one can enter/exit at a fixed number of points [M.sub.e] [greater than or equal to] 2 on each edge e [epsilon] G, the given order plate-cutting problem is solvable in polynomial time.

Proof. Just substitute [M.sub.e] points for each edge of the corresponding polytope in the K + 1 bipartite graph construction in Claim 1 and solve the subsequent shortest path problems.

Next, we examine the same problem but permit entry/exit of a polytope at an edge point which is not necessarily a corner point.

3. Given order, edge entry/exit points

We start with single edge polygons (think of it as a degenerate polygon) and prove that the optimal solution of the plate-cutting problem is solvable in polynomial time.

Problem 2 -- (P2). Given a finite set of K single edge polygons [e.sub.1],..., [e.sub.K], to be cut in order. Suppose that an entry/exit point on each edge can be anywhere on the edge and construct a closed tour of minimum length that visits all the edges in order at some entry/exit edge point.

Essentially, in order to solve P2 all one needs to determine is the entry/exit point on each edge for the optimal tour solution.

Claim 2. The optimal solution for P2 can be constructed in polynomial time.

Proof. To prove Claim 2 we adopt the mathematical programming formulation for a two-dimensional plate-cutting problem with a given order from the paper by Hoeft and Palekar to the single edge case of P2. The proof which follows is for the two-dimensional case but the extension to higher dimensions is straightforward.

Following Hoeft and Palekar's notation, let any edge be represented as [e.sub.i] = {([[x.sup.i].sub.1], [[y.sup.i].sub.1]), ([[x.sup.i].sub.2], [[y.sup.i].sub.2])}, and any point ([x.sup.i],[y.sup.i]) along this edge be represented by the parametric function ([x.sup.i],[y.sup.i]) = (([[x.sup.i].sub.1] + [[lambda].sub.i]([[x.sup.i].sub.2] - [[x.sup.i].sub.1]), ([[y.sup.i].sub.1] + [[lambda].sub.i]([[y.sup.i].sub.2] - [[y.sup.i].sub.1]))). Since in the plate-cutting case the distance is determined using the [l.sub.[infinity]] norm and since the point ([x.sup.i],[y.sup.i]) is uniquely determined by the [[lambda].sub.i] value, one can write the distance between two points on two edges [e.sub.i] and [e.sub.j] as distance [d.sub.ij] between [[lambda].sub.i] and [[lambda].sub.j].

[d.sub.ij] = max(\([[x.sup.i].sub.1] + [[lambda].sub.i]([[x.sup.i].sub.2] - [[x.sup.i].sub.1])) - ([[x.sup.j].sub.1] + [[lambda].sub.j]([[x.sup.j].sub.2] - [[x.sup.j].sub.1]))\,

\([[y.sup.i].sub.1] + [[lambda].sub.i]([[y.sup.i].sub.2] - [[y.sup.i].sub.1])) - ([[y.sup.j].sub.1] + [[lambda].sub.i]([[y.sup.j].sub.2] - [[y.sup.j].sub.1]))\).

To simplify the notation, Hoeft and Palekar define for any pair of edges [e.sub.i] and [e.sub.j]

[a.sub.ij] = ([[x.sup.i].sub.1] - [[x.sup.j].sub.1], [c.sub.ij] = ([[y.sup.i].sub.1] - [[y.sup.j].sub.1]).

For any edge [e.sub.i] define

[b.sub.i] = ([[x.sup.i].sub.2] - [[x.sup.i].sub.1], [f.sub.i] = ([[y.sup.i].sub.2] - [[y.sup.i].sub.1]).

Now the distance between [[lambda].sub.i] and [[lambda].sub.j] is written as

[d.sub.ij] = max[\[a.sub.ij] + [[lambda].sub.i][b.sub.i] - [[lambda].sub.j][b.sub.j]\, \[c.sub.ij] + [[lambda].sub.i][f.sub.i] - [[lambda].sub.j][f.sub.j]\].

The P2 problem can now be formulated as follows (assume that edge K + 1 is the same as the edge 1):

v(P2) = min [[[sigma].sup.K].sub.i=1][d.sub.i,i+1], (1)

subject to

[d.sub.i,i+1] [greater than or equal to] \[a.sub.i,i+1] + [[lambda].sub.i][b.sub.i] - [[lambda].sub.i+1][b.sub.i+1]\, i = 1,...,K, (2)

[d.sub.i,i+1] [greater than or equal to] \[c.sub.i,i+1] + [[lambda].sub.i][f.sub.i] - [[lambda].sub.i+1][f.sub.i+1]\, i = 1,...,K, (3)

0 [less than or equal to] [[lambda].sub.i] [less than or equal to] 1, i = 1,...,K, (4)

[d.sub.i,i+1] [greater than or equal to] 0, i = 1,...,K, (5)

The above problem can be solved as a linear program, thus the polynomial time solvabilty of P2 is obtained as a consequence of polynomial time solvability for linear programming.

4. Given order, convex polytope plate-cutting

Given the result of Claim 2, to obtain the optimal plate-cutting convex polygon solution, one approach could be to try, one at a time for each polygon, all the adjacent edges. However this does not lead to a polynomial time algorithm even in the two-dimensional case. In the two-dimensional case, examining each optimal corner adjacent edge would imply solving [2.sup.K] linear programs of the type presented in the previous section. Still, we claim that in the two-dimensional case there exists a polynomial time algorithm for this problem. In fact, the polynomial solvability of this problem (selecting optimal entry/exit points for each polygon) can be easily extended to n-dimensional space and bounded polyhedra. It is simply a solution to the linear programming representation of this problem based on the linear inequality description of each of the convex polygons.

Let [P.sub.i] = {[A.sup.i][x.sup.i] [less than or equal to] [b.sup.i], [x.sup.i] [greater than or equal to] 0} represent the ith polygon. Thus, the system [A.sup.i][x.sup.i] [less than or equal to] [b.sup.i], [x.sup.i] [greater than or equal to] 0, i = 1,...,N, represents all N polygons (or polyhedra). Since the order for the plate-cutting is given, all that is required is that a solution vector ([x.sup.1], [x.sup.2],...,[x.sup.N]) be feasible (i.e., [A.sup.i][x.sup.i] [less than or equal to] [b.sup.i], [x.sup.i] [greater than or equal to] 0, i = 1,...,N) and the total distance (in [l.sub.[infinity]] norm) representation given by [[[sigma].sup.N].sub.i] [d.sub.i,i+1] be minimized (note that N + 1 becomes 1 in order to return to the first polytope). One only has to add for each pair (i, i + 1) of polygons the following four inequalities to the system above.

[[x.sup.i].sub.1] - [[x.sup.i+1].sub.1] [less than or equal to] [d.sub.i,i+1], i = 1,...,N,

[[x.sup.i+1].sub.1] - [[x.sup.i].sub.1] [less than or equal to] [d.sub.i,i+1], i = 1,...,N,

[[y.sup.i].sub.1] - [[y.sup.i+1].sub.1] [less than or equal to] [d.sub.i,i+1], i = 1,...,N,

[[y.sup.i+1].sub.1] - [[y.sup.i].sub.1] [less than or equal to] [d.sub.i,i+1], i = 1,...,N.

Now, all that is left is to solve the corresponding linear program.

Claim 3. The given order, convex polytope plate-cutting problem is solvable in polynomial time.

Proof. We distinguish two possible outcomes of the linear program solution to the above formulation.

Case 1: the minimizing solution to the above linear program generates an entry/exit sequence of points on the edges of the corresponding polygons. As a result, the polynomial time solvability of the convex cutting-plate problem is based on the polynomial time solvability for linear programs.

Case 2: the minimizing solution to the above linear program generates some entry/exit points inside the polygons. This is possible because the [l.sub.[infinity]] norm is used for distances. With the [l.sub.[infinity]] norm, the length of any single edge in a nondegenerate triangle might be equal to the sum of the lengths of the two other edges. This might result in multiple optimal linear programming solutions, some of which might contain points inside to the polygons. For the cutting-plate problem, solutions with inside points are infeasible. However, given any such infeasible optimal solution, a modification to the solution requires at most N on-line adjustments in the cutting pattern described by the infeasible optimal linear program solution. One only has to follow each cutting line between the polygons until it meets the polygon boundary. From that point (after cutting out the polygon), one continues to the entry point of the next polygon. The first entry point, the (infeasible) inside point, and the ent ry point of the next polygon, define a triangle. The optimality of the infeasible solution implies that the length of the edge between the first boundary entry point and the entry point of the next polygon must equal the length of the other two edges. Figure 2 provides an illustration with four polygons and entry points denoted by u, w, and z (polygon number 1 is a single point).

In Fig. 2 assume that point 1 has coordinates (0, 0), point v has coordinates (b, a + c), point w has coordinates (0, 2b), and point u has coordinates (b - d, a). In addition, b [greater than] a + c. Observe that the sum distance norm max {x, y} over the path 1, c, w, z, 1 equals to 4b, and the sum distance over the path 1, u, w, z, 1 also equals to 4b.

This on-line modification to an infeasible fixed order cutting pattern can be done one polygon at a time along the cutting sequence. Thus, polynomiality of this optimal procedure is still based on the polynomial time solvability for linear programs. An off-line procedure would require the determination of the polygon boundary entry points which requires the solution of pairs of linear equations, one for each line segment of the corresponding polygon. Still, this does not affect the polynomiality of the overall solution process.

Note that for the nonconvex polygon in the two-dimensional case the above solution approach will not work. It is clear that one can extend these polynomial solvability results to bounded polyhedra of higher dimension than 2.

5. Other extensions and conclusions

Another problem which can be approached in similar fashion is the problem referred to by Hoeft and Palekar as the end point cutting problem where the tool can enter and exit the object only at some predefined points on the boundary but can cut the shapes in sections. If the order of the cuts for each shape is given, we can also model this problem as a shortest path problem on some bipartite graph constructed in a similar fashion to the one in P1. Each pair of possible entry and exit points will correspond to a single node in such a bipartite graph. The distance between the nodes is the distance between the exit node of one pair (entry, exit) and the entry node of the next set of bipartite graph nodes. Thus following the previous discussion, such a cutting path problem version is polynomially solvable. In the case where the order of the cuts for each shape is not given but the candidate entry and exit points for each shape are known in advance, an algorithmic approach (no longer polynomial) of the type describ ed in Dror and Langevin [5], where entry and exit nodes are explicitly modeled can be easily implemented.

In conclusion, in this note, the interesting problem of plate-cutting as described by Hoeft and Palekar [1] has been examined is some detail. For the problem of plate-cutting with a given order and convex polygons we have proven the existence of a polynomial time solution. In the course of this analysis, the existence of a polynomial time solution has been proven for a number of related sub-problems.

Biography

Moshe Dror is a Professor in the MIS Department at the College of Business and Public Administration, University of Arizona. His current research ranges from combinatorial problems such as routing and machine scheduling to problems of cost allocation in logistics. He has written extensively on those topics and his publications have appeared in numerous journals and as book chapters. He received a Ph.D. degree from the University of Maryland at College Park, an I.E. degree and an M.Sc. (in Mathematial Methods) degree, both from Columbia University. He serves as a Departmental Editor (Applied Optimization) for IIE Transactions on Operations Engineering and on a number of other journals' editorial boards.

References

(1.) Hoeft, J. and Palekar, U.S. (1997) Heuristics for the plate-cutting traveling salesman problem. IIE Transactions, 29, 719-731.

(2.) Laporte, G., Mercure, H. and Nobert, Y. (1987) Generalized traveling salesman problem through n clusters. Discrete Applied Mathematics, 18, 185-197.

(3.) Noon, G.E. and Bean, J.C. (1993) An efficient transformation of the generalized traveling salesman problem. INFOR, 31, 39-44.

(4.) Dror, M., Stern, H. and Trudeau, P. (1987) Postman tour on graph with precedence relation on arcs. Networks, 17, 283-294.

(5.) Dror, M. and Langevin, A. (1997) A generalized traveling salesman problem approach to the directed clustered rural postman problem. Transportation Science, 31, 187-192.