CP and MIP in the resolution of hard combinatorial problems : a case study with nesting problems

Abstract

Mixed Integer Programming (MIP) is a well-established approach to the optimization of combinatorial problems. The complexity of MIP models restricts their application to small-sized instances. For larger instances heuristic methods provide satisfactory solutions in many application domains.Constraint Programming (CP) has also addressed the resolution of combinatorial optimization problems. The CP paradigm is appropriate for representing the constraints that characterize problem solutions as well as for programming resolution strategies. A CP program can be regarded as a flexible problem model that can be used both for optimization and for applying heuristic methods.The integration of CP and MIP has been explored to take advantage of the feasibility-oriented features of CP together with the optimization-oriented behavior of MIP. The integration strategy depends on the problem nature and typically requires some insight on the communication between the two models.Nesting problems are NP-hard combinatorial problems wherepolygon-shaped pieces are placed over a plate; the goal is tominimize the length of the resulting layout. The problem has been addressed via MIP and heuristic methods in the OR community. The solution via CP models has also been studied. Nesting problems are particularly demanding in what concerns modelling: the natural problem variables are points in a two-dimensional space that make constraint propagation hard; it is also hard to predict for a partial solution its potential for being part of a compact layout.As a first step in exploring hybrid CP/MIP models for nestingproblems, we present a case study where MIP and CP models are compared in a nesting problem instance with convex pieces. We then propose a hybrid approach to nesting problems combining a modified CP approach and LP optimization.