ON DIFFERENT APPROACHES OF A MIXED INTEGER LINEAR PROGRAMMING PROGRAM: AN APPLICATION TO THE MINIMUM CHROMATIC VIOLATION PROBLEM

ESCALANTE MARIANA SILVINA

Quito

Congreso; XVI ENCUENTRO DE MATEMÁTICA Y SUS APLICACIONES; 2018

Escuela Politecnica Nacional

The main purpose of this talk is to present two different approachesfor tackling combinatorial problems, both using polyhedral and graphtheoretical tools. For doing so, I organize divide the presentation intotwo quite different parts, each of them associated with a particularproblem.The first one is the Maximum Stable Set Problem in a Graph. Astable set is a set of mutually nonadjacent nodes in a graph. Thestable set polytope is the convex hull of the characteristic vectors ofstable sets. There are very well-known polyhedral relaxations of thispolytope, however they are tight on very particular families of graphs.In this talk we focus on a non polyhedral relaxation obtained afterapplying the PSD-operato defined by Lvasz and Schrijver (known asN+-operator). We consider those graphs for which one iteration of thisPSD operator achieves the stable set polytope. In particular, we workon the validity of a conjecture characterizing this family of graphs.The second problem is connected to coloring in graphs. We con-sider a case arising from classroom assignment in an institution wherecourses can share some specific rooms, like labs. This gives raise towhat we call the Minimum Chromatic Violation Problem since thereare some restrictions coming from the coloring problem, that can beviolated. We formulate this problem as an integer program and studythe polyhedral structure of its feasible region. Due to its formulationwe relate this polytope with the two extreme situations: the coloringpolytope and the k-partition polyope.