A polyhedral approach to bisubmodular function minimization

Qimeng Yu; Simge Küçükyavuz

doi:10.1016/j.orl.2020.10.007

A polyhedral approach to bisubmodular function minimization

Qimeng Yu, Simge Küçükyavuz^*

^*Corresponding author for this work

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

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.

Original language	English (US)
Pages (from-to)	5-10
Number of pages	6
Journal	Operations Research Letters
Volume	49
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2020.10.007
State	Published - Jan 2021

Funding

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. 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 .

Keywords

Bisubmodular minimization
Bisubmodular polyhedra
Convex hull
Coupled sensor placement
Cutting planes

ASJC Scopus subject areas

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

Access to Document

10.1016/j.orl.2020.10.007

Cite this

@article{0b455a0db7de4f028d2746dce18be1a8,

title = "A polyhedral approach to bisubmodular function minimization",

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.",

keywords = "Bisubmodular minimization, Bisubmodular polyhedra, Convex hull, Coupled sensor placement, Cutting planes",

author = "Qimeng Yu and Simge K{\"u}{\c c}{\"u}kyavuz",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2021",

month = jan,

doi = "10.1016/j.orl.2020.10.007",

language = "English (US)",

volume = "49",

pages = "5--10",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A polyhedral approach to bisubmodular function minimization

AU - Yu, Qimeng

AU - Küçükyavuz, Simge

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

SN - 0167-6377

VL - 49

SP - 5

EP - 10

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

A polyhedral approach to bisubmodular function minimization

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this