Intersection cuts meet submodularity: the good and the bad
Date:
Intersection cuts can tighten a polyhedral outer approximation of a non-convex set. We study intersection cuts for submodular and submodular-supermodular maximization problems. We construct corresponding S-free sets and propose a cut computation algorithm. We report our good and bad experiences with intersection cuts in max cut, maximization of Boolean multilinear functions, maximization of utility functions, and D-optimal design problems. We found experimentally and thus conjecture that intersection cuts hardly improve the polyhedral outer approximations of non-monotone submodular maximization problems and problems with convex MINLP problems. So, a new measure of cut efficiency in terms of the corner polyhedral relaxation is in need. This talk is based on a joint work with Leo Liberti. slides
This talk is presented at session Aussois C ombinatorial Optimization Workshop 2023 (Aussois2023).