- New facets and facet-generating procedures for the orientation model for vertex coloring problems Diego Delle Donne(diegoddgmail.com) Javier Marenco(jmarencoungs.edu.ar) Abstract: In this work, we study the \emph{orientation model} for vertex coloring problems with the aim of finding partial descriptions of the associated polytopes. We present new families of valid inequalities, most of them supported by paths of the input graph. We develop facet-generating procedures for the associated polytopes, which we denominate \emph{path-lifting procedures}. Given a path between two vertices and any two valid inequalities, the path-lifting procedure generates an infinite family of valid inequalities. We study conditions ensuring that the obtained inequalities define facets. Finally, we present a large family of valid inequalities, which is obtained by iteratively applying the path-lifting procedure. We conjecture that this family may be sufficient to completely describe the associated polytope when $G$ is a path. Keywords: vertex coloring, orientation model, facet-generating procedures Category 1: Combinatorial Optimization (Polyhedra ) Category 2: Integer Programming (Cutting Plane Approaches ) Citation: National University of General Sarmiento, Argentina and Université Paris 13, France. June, 2019. Download: [PDF]Entry Submitted: 07/02/2019Entry Accepted: 07/02/2019Entry Last Modified: 07/02/2019Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.