A Polyhedral Approach to Bisubmodular Function Minimization

03/12/2020
by   Qimeng Yu, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset