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

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2005

Autores

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

Ata de Conferência Internacional

Título: CSCLP 2005

Páginas: 113-127

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

Uppsala, Sweden, 20 a 22 de Junho de 2005

Classificação Científica

CORDIS: Ciências Físicas > Ciência de computadores > Informática ; Ciências Físicas > Matemática > Matemática aplicada > Investigação operacional

Outras Informações

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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 15