Javier Marenco 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 … Read more
Despite the fact that many vertex coloring problems are polynomially solvable on certain graph classes, most of these problems are not “under control” from a polyhedral point of view. The equivalence between optimization and separation suggests the existence of integer programming formulations for these problems whose associated polytopes admit elegant characterizations. In this work we … Read more
In this work we consider the uniform capacitated single-item single-machine lot-sizing problem with continuous start-up costs. A continuous start-up cost is generated in a period whenever there is a nonzero production in the period and the production capacity in the previous period is not saturated. This concept of start-up does not correspond to the standard … Read more
In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation … Read more