A Polyhedral Approach to Bisubmodular Function Minimization

DOI10.1016/J.ORL.2020.10.007MaRDI QIDQ6336663arXivFDO

Authors Qimeng Yu, Simge Küçükyavuz

Publication date 12 March 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.ORL.2020.10.007

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

arXiv classification

cs.DM math.OC

Abstract: We consider minimization problems with bisubmodular objective functions. We propose valid inequalities, namely the poly-bimatroid inequalities, and provide a complete linear description of the convex hull of the epigraph of a bisubmodular function. Furthermore, we develop a cutting plane algorithm for constrained bisubmodular minimization based on the poly-bimatroid inequalities. Our computational experiments on the minimization subproblem in robust coupled sensor placement show that our algorithm can solve highly non-linear problems that do not admit compact mixed-integer linear formulations.

This page was built for publication: A Polyhedral Approach to Bisubmodular Function Minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6336663)