(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

Graph Coloring via Constraint Programming-based Column Generation

Stefano Gualandi
Dipartimento di Elettronica e Informazione
Politecnico di Milano, Italy

Wednesday, 01 April, 2009 at 14:15
Auditorium U49E

ABSTRACT

We consider the classical optimization problem of finding the chromatic number of large general graphs (Min-GCP). Constraint Programming (CP) is a successful method for checking if a k-coloring exists, since constraint propagation can be exploited effectively. However, standard CP approaches lack an efficient mechanism to guide the search towards the optimal region, and to derive effective bounds of the optimal solution. Hybrid methods that integrate CP with mathematical programming techniques have been recently investigated. A promising hybrid approach is the so–called Constraint Programming-based Column Generation that formulates and solves the pricing subproblem as a Constraint Programming problem.

In a previous formulation by Mehrotra and Trick (1996) based on Column Generation, the master is a set partitioning problem and the pricing is a maximum weighted independent set problem. In our CP-based Column Generation approach, the pricing subproblem has two versions: the first one, computationally expensive, corresponds to finding the most negative reduced cost column; the second one corresponds to the decision problem of finding a maximal independent set with negative reduced cost smaller than a dynamic threshold. During our column generation algorithm, we alternatively use the two versions and exploit the features of Constraint Programming for efficiently solving the second.

We report computational results on the graphs of the well known DIMACS repository.

Joint work with Federico Malucelli

Host: Marco Chiarandini


SDU HOME | IMADA HOME | Previous Page
Daniel Merkle