Exact Algorithms for the Vertex Coloring Problem Branch and Bound: Algorithm DSATUR, Brélaz (Comm. ACM, 1979); Improvement of DSATUR: Sewell (2nd DIMACS Implementation Challenge, 1993). BranchandPrice: Mehrotra, Trick (INFORMS J. on. Computing, 1996), Gualandi, Malucelli (Politecnico di Milano Technical Report, 2010), Malaguti, Monaci, T. (Discrete Optimization, 2010). Branch and Cut: MéndezDíaz, Zabala (Disc. Appl. Math. 2006, 2008). 1
Maximal Clique n n
n
n

A clique K of a graph G is a complete subgraph of G. A clique is maximal if no vertex can be added still having a clique.
The cardinality of any (maximal) clique of graph G represents a Lower Bound for the problem. A fast greedy algorithm (Johnson, J. Comp. Syst. Sci. 1974) can be used to compute a maximal clique K of G(V,E): Given an ordering of the vertices, consider the candidate vertex set W. Set W = V, K = 0 and iteratively: * Choose the vertex v of W of maximum degree and add it to the current clique K. * Remove from W vertex v and all the vertices not adjacent to the current clique K. Different orderings of the vertices generally produce different maximal cliques.
2
ILP models for VCP: Model VCPASSIGN n
Binary variables:
xih = { yh = {
n
1 if vertex i has color h 0 otherwise 1 if color h is used 0 otherwise
min ∑ yh
i =1,…,n h =1,…,n h =1,…,n
(1)
h =1
n
∑x
ih
=1
i = 1,.., n
(2)
h =1
xih + x jh ≤ yh xi ,h ∈ {0,1} yh ∈ {0,1}
∀i, j : (i, j ) ∈ E h = 1,..., n i = 1,..., n h = 1,..., n
(3)
h = 1,..., n ( 4) 3
Independent Sets n n
An Independent Set (or Stable Set) of G = (V, E) is a subset of V such that there is no edge in E connecting a pair of vertices. It is maximal if no vertex can be added still having an independent set. 1
3
2
5
4
For VCP: all the vertices of an independent set can have the same color Feasible coloring > partitioning of the graph into independent sets. 1
2
3
5
4
4
Independent Sets and Cliques n
Given a graph G = (V, E) 1
3
2
5 Independent Set
4
Its “complementary graph” G = (V, E), with 1
2
3
E = {(i, j): (i, j) ∈/ E}
5
4
clique
independent set of G → clique of G (and viceversa) clique of G → independent set of G (and viceversa)
5
Set Covering Formulation SC VCP s.t.
min ∑ xs s∈S
∑x
(1)
s
≥1
∀i ∈ V
(2)
∀s ∈ S
(3)
s:i∈s
xs ∈ {0,1}
n n
S can be defined as the family of all the maximal
Independent Sets (or Stable Sets) of graph G. The LP Relaxation of this formulation leads to tight lower bounds, and symmetry in the solution is avoided, but the number of maximal independent sets (i.e. the number of “columns”) can be exponential in the number of vertices n. 6
Set Covering Formulation SCVCP BranchandPrice Algorithms SCVCP: Master Problem n n
LP Relaxation of SCVCP: exponentially many variables (columns, independent sets) . Column Generation procedure: Solve the LP Relaxation of the SCVCP formulation by considering a subset of independent sets (columns): Restricted Master Problem (RMP); Detect possible negative reduced cost columns by solving the corresponding “Pricing Problem”, add them to the RMP and iterate. 7
Pricing Problem n
ci is the optimal dual variable associated with the ith
“covering constraint” in the SCVCP formulation (weight of vertex i). The Pricing Problem requires the solution of a Maximum Weighted Independent Set Problem (MWISP) (NPHard). n
yi = 1{ if vertex i is in the independent set}, 0 otherwise n
max ∑ ci yi i =1
yi + y j ≤ 1
∀i, j : (i, j ) ∈ E
yi ∈ {0,1}
i = 1,..., n
8
Pricing Problem (MWISP) (2)
n n
ci is the optimal dual variable associated with the ith
“covering constraint” in the SCVCP formulation. yi = 1{if vertex i is in the independent set}, 0 otherwise n
max ∑ ci yi i =1
yi + y j ≤ 1
∀i, j : (i, j ) ∈ E
yi ∈ {0,1}
i = 1,..., n
If the optimal solution value is greater than 1, then an independent set (column) with negative reduced cost has been found.
9
BranchandPrice Algorithm 1 (Gualandi, Malucelli; Tech. Rep 2010) n
Column Generation procedure: detection of possible negative reduced cost columns by alternatively solving:
1) Exact Algorithm CLIQUER (maximum weighted clique problem; Ostergard, Discr. Appl. Math. 2002). 2) Heuristic Algorithm QUALEXMS (maximum weighted clique problem; Busygin, Discr. Appl. Math. 2006). 2) Constraint Programming Algorithm (weighted version of the maxclique problem algorithm proposed by Fahle, Proc. Ann. Eur. Symp. Algorithms, Springer, 2002). 10
BranchandPrice Algorithm 2 (Malaguti, Monaci, T.; Discrete Optimization 2010) n
Column Generation procedure: detect possible negative reduced cost columns by solving MWISP, by using:
1) a Tabu Search heuristic algorithm (TS) which produces maximum weighted independent sets; 2) an ILP Solver (CPLEX 10.2), if the algorithm TS fails in finding negative reduced cost columns. 11
BranchandCut Algorithm MéndezDíaz, Zabala (Disc. Appl. Math. 2006, 2008) n
Improvement of the VCPASSIGN Formulation by adding new valid inequalities.
n
Initialization Phase:
n
Preprocessing procedure to reduce the number of vertices to be considered. Initial Upper Bound computed through the execution of algorithm DSATUR with a short time limit (5 seconds). Initial Lower Bound computed by finding a maximal clique through a greedy algorithm.
n n
n
New Branching Rules. 12
Computational Results for the Exact Approaches n
Algorithm DSATUR: Brélaz (Comm. ACM, 1979), Improved by Sewell (2nd DIMACS Implem. Challenge 1993) Implemented by Mehrotra, Trick (INFORMS J. on C., 1996)
n Branch and Cut Algorithm BCCOL (with the stronger lower bounding procedures): MéndezDíaz, Zabala (Disc. Appl. Math. 2006, 2008) n BranchandPrice Algorithm GM: Gualandi, Malucelli (Tech. Report Politecnico di Milano, 2010). n BranchandPrice Algorithm MMT: Malaguti, Monaci, T. (Discrete Optimization, 2010). n
Comparable CPU times.
13
DIMACS Benchmark Instances Johnson, Trick, 2nd DIMACS Implementation Challenge 1993 n DIMACS
benchmark graph instances compose a variety of graph classes used for evaluating the performance of VCP algorithms:  random graphs: DSJC_n.x;  geometric random graphs: DSJR_n.x; r_n.x;  quasirandom graphs: flat_n.x;  artificial graphs: le_n.x; latin_square_10; Queen_rn.rn; myciel_k  realworld applicationrelated graphs.
14
VCP: Exact Algorithms MendezDiaz, Zabala (2006, 2008) BCCOL
DSATUR
GualandiMalucelli (2010)
common instances (w.r.t. MMT)
66
66
39

proven optimal solutions only algorithm
8 1
1 0
15 2
25 (15) 13 (4)
Lower Bound LB > LB (MMT) LB = LB (MMT) LB < LB (MMT) global LB gap w.r.t. MMT
9 43 14 92
1 23 42 326
2 27 10

Upper Bound UB < UB (MMT) UB = UB (MMT) UB > UB (MMT) global UB gap w.r.t. MMT
0 24 42 333
0 18 48 304
0 27 12
*
*
MMT (2010)
