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

• Type: Article in International Conference Proceedings Book
• Date: 2005

Authors

Maria Antónia Carravilla (Author) FEUP; Cristina Ribeiro (Author) FEUP

Conference proceedings International

Title: CSCLP 2005

Pages: 113-127

Joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming

Uppsala, Sweden, 20 a 22 de Junho de 2005

Scientific classification

CORDIS: Physical sciences > Computer science > Informatics ; Physical sciences > Mathematics > Applied mathematics > Operations research

Other information

Abstract (EN): 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 where polygon-shaped pieces are placed over a plate; the goal is to minimize 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 nesting problems, 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 15