EUROPT 2024
Abstract Submission

159. New techniques for finding MIP formulations for combinatorial disjunctive constraints

Invited abstract in session WD-6: Linear Programming, stream Methods for non-/monotone inclusions and their applications.

Wednesday, 11:25 - 12:40
Room: M:H

Authors (first author is the speaker)

1. Peter Dobrovoczki
Engineering and Management Intelligence Research Laboratory, HUN-REN SZTAKI
2. Tamas Kis
Institute for Computer Science and Control

Abstract

Computationally efficient MIP formulations for combinatorial disjunctive constraints (CDC-s) is still a challenging task. A combinatorial disjunctive constraint is a union of simplices with vertices pertaining to a finite set of points in the n-dimensional Euclidean space. With a combinatorial disjunctive constraint we can associate a so-called conflict (hyper) graph. If the hyper graph is an ordinary graph, then we can represent the CDC with a so-called pairwise independent branching scheme.
Findig a pairwise independent branching scheme boils down to finding a biclique cover of the conflict graph. On the one hand, the size of the biclique cover has a strong impact on the size of resulting MIP formulation. On the other hand, not all combinatorial disjunctive constraints have a pairwise independent branching scheme representation, e.g., the conflict graph is not an ordinary graph.

We propose a novel method for finding a MIP formulation for arbitrary combinatorial disjunctive constraints. Our method first works on the subgraph of the conflict graph which is an ordinary graph, and finds a biclique cover on it with a new technique. Then, we construct an auxiliary graph to resolve the remaining conflicts. The coloring of this graph yields the other half of the MIP formulation.

We demonstrate our method on a couple of problems from the literature. Our technique for finding a biclique cover of an ordinary graph is new and may be of interest on its own right.

Keywords

Status: accepted

Back to the list of papers