CO Seminar – Koen Ligthart
November 15 @ 12:30 - 13:30
Location: MF 13
Speaker: Koen Ligthart (TU/e)
Title: Computing the Relaxation Complexity for Finite Point Sets Using Column Elimination
Abstract:
We investigate the following problem: given two finite point sets X and Y, what is the least number of facets of a polyhedron that contains all points of X and no points of Y? This quantity is called the relaxation complexity of X with respect to Y, denoted rc(X,Y), and computing it is known to be NP-hard. It can be related to the least number of constraints needed to model variable relations in an integer program without adding additional variables. We cast the problem of finding rc(X,Y) as a coloring problem on a hypergraph with vertex set Y and edges being formed by the subsets of Y that cannot simultaneously be separated from X with a single hyperplane. To color this hypergraph, we build on and generalize an existing column elimination algorithm for coloring ordinary graphs by Van Hoeve [Mathematical Programming, 192, 631 (2022)].
The column elimination algorithm uses a decision diagram to provide a compact representation of a superset of all the independent sets in the hypergraph. Iteratively, a candidate solution is created that covers every point of Y with a set from the diagram. Such coloring is improper when a color class contains a hyperedge. The difficulty in our application is that the hypergraphs may have exponentially many edges, which is why they are dynamically generated. The edges are used to iteratively refine the decision diagram until a feasible optimal solution is found. We compare an implementation of the column elimination algorithm with an existing column generation algorithm on a set of concrete problem instances.
The talk is based on joint work with Christopher Hojny.