Box Facets and Cut Facets of Lifted Multicut Polytopes

Lucas Fabian Naumann, Jannik Irmai, Shengxian Zhao +1

The lifted multicut problem is a combinatorial optimization problem whose feasible solutions relate one-to-one to the decompositions of a graph $G=(V,E)$. Given an augmentation…