  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.
