Optimization Online


Maximizing a class of submodular utility functions with constraints

Jiajin Yu(jiajinyu***at***gatech.edu)
Shabbir Ahmed(sahmed***at***isye.gatech.edu)

Abstract: Motivated by stochastic 0-1 integer programming problems with an expected utility objective, we study the mixed-integer nonlinear set: $P = \cset{(w,x)\in \reals \times \set{0,1}^N}{w \leq f(a'x + d), b'x \leq B}$ where $N$ is a positive integer, $f:\reals \mapsto \reals$ is a concave function, $a, b \in \reals^N$ are nonnegative vectors, $d$ is a real number and $B$ is a positive real number. We propose a family of inequalities for the convex hull of $P$ by exploiting submodularity of the function $f(a'x + d)$ over $\{0,1\}^N$ and the knapsack constraint $b'x \leq B$. Computational effectiveness of the proposed inequalities within a branch-and-cut framework is illustrated using instances of an expected utility capital budgeting problem.

Keywords: Submodularity, cutting planes, lifting, mixed integer nonlinear programming, branch-and-cut

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Stochastic Programming

Citation: Submitted for publication, December 2014.

Download: [PDF]

Entry Submitted: 12/30/2014
Entry Accepted: 12/30/2014
Entry Last Modified: 12/30/2014

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