We consider minimization problems with bisubmodular objective functions. We propose a class of valid inequalities, which we call the poly-bimatroid inequalities and prove that these inequalities, along with trivial bound constraints, fully describe the convex hull of the epigraph of a bisubmodular function. We develop a cutting plane algorithm for general bisubmodular minimization problems using the poly-bimatroid inequalities. Computational experiments on the bi-coverage problem show that our cutting plane algorithm is more favorable than directly solving the equivalent mixed-integer formulation.
Citation
Technical Report, Northwestern University, March 2020.