In this chapter, we present the integration of various forms of problem relaxation in Constraint Programming (CP). The main motivation for the integration proposed concerns the introduction in CP languages of some form of {em optimality reasoning}. Indeed, CP languages provide effective and powerful tools for reducing the search space of the problem by removing infeasible values. However, they barely consider the problem objective function and implement a naive form of branch-and-bound which poorly reduces the search space to be explored. % Relaxations can be integrated in CP in different ways. Some approaches propose to automatically translate the whole CP program in linear form, while some other focus only on global constraints. In this perspective, a further differentiation can be noted. Some approaches translate all global constraints in a unique linear store, while others embed an optimization component within each global constraint. In other approaches, the part of the problem to be relaxed is decided by the user that explicitly states it in the program. First, we provide an introduction on different kinds of relaxation and we discuss many integration approaches, how they exploit results coming from the relaxation, providing references to related bibliography. In the second part of the chapter, we consider global constraints as suitable software components to integrate relaxations in CP. We discuss, as a case study, a particular global constraint, the path constraint, and show different relaxations and their tightness.

F. FOCACCI, A. LODI, M. MILANO (2004). Exploiting Relaxations in CP. BOSTON : Kluwer academic publisher.

Exploiting Relaxations in CP

LODI, ANDREA;MILANO, MICHELA
2004

Abstract

In this chapter, we present the integration of various forms of problem relaxation in Constraint Programming (CP). The main motivation for the integration proposed concerns the introduction in CP languages of some form of {em optimality reasoning}. Indeed, CP languages provide effective and powerful tools for reducing the search space of the problem by removing infeasible values. However, they barely consider the problem objective function and implement a naive form of branch-and-bound which poorly reduces the search space to be explored. % Relaxations can be integrated in CP in different ways. Some approaches propose to automatically translate the whole CP program in linear form, while some other focus only on global constraints. In this perspective, a further differentiation can be noted. Some approaches translate all global constraints in a unique linear store, while others embed an optimization component within each global constraint. In other approaches, the part of the problem to be relaxed is decided by the user that explicitly states it in the program. First, we provide an introduction on different kinds of relaxation and we discuss many integration approaches, how they exploit results coming from the relaxation, providing references to related bibliography. In the second part of the chapter, we consider global constraints as suitable software components to integrate relaxations in CP. We discuss, as a case study, a particular global constraint, the path constraint, and show different relaxations and their tightness.
2004
Constraint and Integer Programming - Toward a Unified Methodology
137
167
F. FOCACCI, A. LODI, M. MILANO (2004). Exploiting Relaxations in CP. BOSTON : Kluwer academic publisher.
F. FOCACCI; A. LODI; M. MILANO
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/30144
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact