In a previous work we presented six facet-inducing families of valid inequalities for the polytope associated to an integer programming formulation of the acyclic coloring problem. In this work we study their disjunctive rank, as defined by [E. Balas, S. Ceria and G. Cornuéjols, Math. Program. 58 (1993) 295–324]. We also propose to study a dual concept, which we call the disjunctive anti-rank of a valid inequality.
Accepté le :
DOI : 10.1051/ro/2015053
Keywords: Acyclic coloring, disjunctive rank
Braga, Mónica 1 ; Marenco, Javier 1
@article{RO_2016__50_3_627_0,
author = {Braga, M\'onica and Marenco, Javier},
title = {Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {627--644},
year = {2016},
publisher = {EDP Sciences},
volume = {50},
number = {3},
doi = {10.1051/ro/2015053},
zbl = {1378.90058},
mrnumber = {3538844},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2015053/}
}
TY - JOUR AU - Braga, Mónica AU - Marenco, Javier TI - Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2016 SP - 627 EP - 644 VL - 50 IS - 3 PB - EDP Sciences UR - https://www.numdam.org/articles/10.1051/ro/2015053/ DO - 10.1051/ro/2015053 LA - en ID - RO_2016__50_3_627_0 ER -
%0 Journal Article %A Braga, Mónica %A Marenco, Javier %T Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope %J RAIRO - Operations Research - Recherche Opérationnelle %D 2016 %P 627-644 %V 50 %N 3 %I EDP Sciences %U https://www.numdam.org/articles/10.1051/ro/2015053/ %R 10.1051/ro/2015053 %G en %F RO_2016__50_3_627_0
Braga, Mónica; Marenco, Javier. Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 3, pp. 627-644. doi: 10.1051/ro/2015053
N. Aguilera, S. Bianchi and G. Nasini, Relaciones entre los rangos de las facetas de problemas asociados a matching. Proc. of the XVIII JAIIO (1999) 10–21.
, and , Acyclic colouring of graphs. Random Struct. and Algorithms 2 (1991) 277–288. | Zbl | MR | DOI
and , On the polyhedral lift-and-project methods and the fractional stable set polytope. Discrete Optim. 6 (2009) 206–213. | Zbl | MR | DOI
Y. Au and L. Tunçel, A comprehensive analysis of polyhedral lift-and-project methods. Manuscript (2013).
, and , Lift-and-Project Cutting Plane Algorithm for Mixed 0 - 1 Programs. Math. Program. 58 (1993) 295–324. | Zbl | MR | DOI
, On acyclic colorings of planar graphs. Discrete Math. 25 (1979) 211–236. | Zbl | MR | DOI
, and , Acyclic colourings of planar graphs with large girth. J. London Math. Soc. 2 (1999) 344-352. | Zbl | MR | DOI
, , and , Acyclic colouring of 1-planar graphs. Discrete Appl. Math. 114 (2001) 29–41. | Zbl | MR | DOI
and , Disjunctive ranks and anti-ranks of some facet-inducing inequalities of the acyclic coloring polytope. Electron. Notes Discrete Math. 37 (2011) 213–218. | Zbl | MR | DOI
, and , A polyhedral study of the acyclic coloring problem. Discrete Appl. Math. 160 (2012) 2606–2617. | Zbl | MR | DOI
, Every 4-valent graph has an acyclic 5-coloring. Soobsc Akad. Nauk Gruzin SSR 93 (1979) 21–24. | Zbl | MR
and , The cyclic coloring problem and estimation of sparse Hessian matrices. SIAM J. Alg. Disc. Meth. 7 (1986) 221–235. | Zbl | MR | DOI
and , Estimation of sparse Jacobian matrices and graph coloring problems. SIAM J. Numer. Anal. 20 (1983) 187–209. | Zbl | MR | DOI
and , Acyclic Coloring of Graphs of Maximum Degree Five: Nine Colors are Enough. Inf. Process. Lett. 105 (2008) 65–72. | Zbl | MR | DOI
, and . What color is your Jacobian? Graph coloring for computing derivatives. SIAM Rev. 47 (2005) 629–705. | Zbl | MR | DOI
, , and , New Acyclic and Star Coloring Algorithms with Application to Computing Hessians. SIAM J. Sci. Comput. 29 (2007) 1042–1072. | Zbl | MR | DOI
, , and , Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation. INFORMS J. Comput. 21 (2009) 209–223. | Zbl | MR | DOI
, Acylic colorings of planar graphs. Israel J. Math. 14 (1973) 390-408. | Zbl | MR | DOI
J. Lasserre, An explicit exact SDP relaxation for nonlinear 0-1 programs. Vol. 2081 of Lect. Notes Comput. Sci. (2001) 293–303. | Zbl | MR
, A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res. 28 (2003) 470–496. | Zbl | MR | DOI
and , On the relationship between disjunctive relaxations and minors in packing and covering problems. Revista de la Unión Matemática Argentina 46 (2005) 11–22. | Zbl | MR
I. Loiseau, I. Méndez Díaz and G. Nasini, Determinación del rango disyuntivo de facetas del problema de ordenación lineal. Proc. of the XXII JAIIO (1993) 124–130.
and , Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1 (1991) 166–190. | Zbl | MR | DOI
C. Mathieu and A. Sinclair, Sherali-Adams relaxations of the matching polytope. Proc. of STOC’09 (2009) 293–302. | Zbl | MR
I. Méndez Díaz and G. Nasini, El problema del ordenamiento lineal y el operador BCC. Proc. of the XVIII JAIIO (1999) 22–32.
T. Rothvoß, The Lasserre hierarchy in approximation algorithms. MAPSP 2013 tutorial (2013).
and , A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3 (1990) 411–430. | Zbl | MR | DOI
Cité par Sources :
