Conflict hypergraphs to define new families of facets for the independence system polytope

LaROMaD, Fac. Maths, USTHB, Pb 32, 16111 Bab Ezzouar, Algeria

^* Corresponding author: chaboughani@gmail.com

Received: 19 November 2018
Accepted: 10 February 2023

Abstract

In this paper, we develop a technique for exact simultaneous upliftings of circuit inequalities of an independence system polytope. The resulting inequalities define new families of valid inequalities for this polytope. They are obtained by simultaneously adding the most appropriate set of variables with the highest possible values of the lifting coefficient that maintain the validity. More specifically, in this technique, we introduce a procedure to generate two conflict hypergraph structures types: hypertrees and clutter. In this setting, we use the hyperedges cardinalities of these structures to compute the suitable lifting coefficient values. We then give necessary and sufficient conditions for both the circuit inequalities and the new families of valid inequalities to be facet-defining. We also give a condition of the positivity of the lifted circuit inequality coefficient values.