A major cost in semiconductor manufacturing is the generation of photo masks which are used to produce the dies. When producing smaller series of chips it can be advantageous to build a shuttle mask (or multi‐project wafer) to share the startup costs by placing different dies on the same mask. The shuttle layout problem is frequently solved in two phases: first, a floorplan of the shuttle is generated. Then, a cutting plan is found which minimizes the overall number of wafers needed to satisfy the demand of each die type. Since some die types require special production technologies, only compatible dies can be cut from a given wafer, and each cutting plan must respect various constraints on where the cuts may be placed. We present an exact algorithm for solving the minimum cutting plan problem, given a floorplan of the dies. The algorithm is based on delayed column generation, where the pricing problem becomes a maximum vertex‐weighted clique problem in which each clique consists of cutting compatible dies. The resulting branch‐and‐price algorithm is able to solve realistic cutting problems to optimality in a couple of seconds.
