TY - JOUR
T1 - A polyhedral approach to bisubmodular function minimization
AU - Yu, Qimeng
AU - Küçükyavuz, Simge
N1 - Funding Information:
We thank the reviewer for comments that improved the paper. This research was supported in part through the computational resources and staff contributions provided for the Quest high performance computing facility at Northwestern University which is jointly supported by the Office of the Provost, USA, the Office for Research, USA, and Northwestern University Information Technology, USA.
Funding Information:
We thank the reviewer for comments that improved the paper. This research was supported in part through the computational resources and staff contributions provided for the Quest high performance computing facility at Northwestern University which is jointly supported by the Office of the Provost, USA , the Office for Research, USA , and Northwestern University Information Technology, USA .
Publisher Copyright:
© 2020 Elsevier B.V.
PY - 2021/1
Y1 - 2021/1
N2 - 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.
AB - 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.
KW - Bisubmodular minimization
KW - Bisubmodular polyhedra
KW - Convex hull
KW - Coupled sensor placement
KW - Cutting planes
UR - http://www.scopus.com/inward/record.url?scp=85095964513&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85095964513&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2020.10.007
DO - 10.1016/j.orl.2020.10.007
M3 - Article
AN - SCOPUS:85095964513
VL - 49
SP - 5
EP - 10
JO - Operations Research Letters
JF - Operations Research Letters
SN - 0167-6377
IS - 1
ER -