Optimization Online


Submodular Minimization in the Context of Modern LP and MILP Methods and Solvers

Andrew Orso(orso***at***umich.edu)
Jon Lee(jonxlee***at***umich.edu)
Siqian Shen(siqian***at***umich.edu)

Abstract: We consider the application of mixed-integer linear programming (MILP) solvers to the minimization of submodular functions. We evaluate common large-scale linear-programming (LP) techniques (e.g., column generation, row generation, dual stabilization) for solving a LP reformulation of the submodular minimization (SM) problem. We present heuristics based on the LP framework and a MILP solver. We evaluated the performance of our methods on a test bed of min-cut and matroid-intersection problems formulated as SM problems.

Keywords: submodular minimization, Lovasz extension, column generation, row generation, dual stabilization

Category 1: Combinatorial Optimization

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Integer Programming (0-1 Programming )


Download: [PDF]

Entry Submitted: 01/30/2015
Entry Accepted: 02/01/2015
Entry Last Modified: 01/30/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society