Integrality of the representation polyhedron for circular-arc models

PABLO TERLISKY; FRANCISCO J. SOULIGNAC; JAVIER MARENCO

Buenos Aires

Conferencia; XXI Latin Ibero-American Conference on Operations Research (CLAIO 2022); 2022

Asociación Latino-Ibero-Americana de investigación operativa

A proper circular-arc (PCA) model is a pair M = (C, A) such that C is a circle and A is a finite family of inclusion-free arcs of C. Each arc A of A has two endpoints: its beginning point s(A) and its ending point t(A), which are the first and last points of A reached when C is traversed clockwise, respectively. A PCA model is a (c, l)-CA model when the circumference of the circle is c and all arcs of A have length l. Two PCA models are equivalent if the endpoints of their arcs appear in the same order when C is traversed clockwise. If there is a point in C that is not contained in any arc of A, we say that M is a semiorder.For any given PCA model M, a representation problem for M is one in which the objective is to find a model M´ equivalent to M that satisfies some given numerical constraint. If the representation problem asks for a (c,l)-CA model, then the problem can be seen as a system of inequalities where the variables are values of c, l, and the beginning points of all the arcs of A except one. Thus, it describes a convex polyhedron in the R^{|A|+1} space which we call the representation polyhedron of M.In the case of semiorders, Balof, et al showed that representation polyhedrons are totally dual integral, showing therefore that any solution to a linear optimization over them is integral. In their work they allude to the work of Pirlot, who showed that in the context of semiorders the representation problem constitutes a system of difference constraints and can be studied by analyzing the cycles of a digraph he called the synthetic graph of M. Recently, Soulignac generalized the concept of the synthetic graph to apply to all PCA models.In this work we show that the properties of synthtetic graphs allow us to state that indeed the representation polyhedron for any PCA model M has integral vertices, answering one of the open questions of Soulignac´s paper. When restricted to semiorders, this result provides a much simpler proof for Balof et. al´s results.