Maximum Weight Matching

Next: Iterated Matching Up: Cutting Stock by Iterated Previous: Slicing Trees

# Maximum Weight Matching

To find out in every iteration step, which of the available rectangles have to be paired, a maximum weight matching in a complete undirected weighted graph is used. The nodes of the graph represent the available (meta) rectangles, the edges represent the possible pairs and the weights give information about the benefit of a pair. The higher the weight, the better the pair. The weights are found by a so called benefit function, which evaluates the possible pairing of two rectangles by considering the corresponding shape functions. For example, a possible benefit function for the pairing of two rectangles is to calculate the average waste of all possible layouts of the resulting meta rectangle and to subtract this value from 100. This encourages the formation of meta rectangles having many densely packed layouts. If all weights of the edges are calculated, the maximum weight matching finds the set of edges, which maximizes the sum of all weights under the constraint that no two edges are adjacent.

This problem can be formulated as a LP-problem as follows:

Maximize

subject to

Here, is the number of available meta rectangles and is the cost matrix. The value of is if the rectangles and are matched and if not.

Edmonds showed, that the maximum weight matching problem can be solved in time . The algorithm used in this application was suggested by Gabow [Gab 1973]. Figure 6 shows the matching algorithm for seven rectangles in three iteration steps. The edges with zero benefit are not shown.

Figure 6:   Maximum weight matching in three iterations

Andreas Fritsch
Mon Dec 19 14:08:31 MET 1994