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