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.
Citation
Submitted for publication, December 2014.
Article
View Maximizing a class of submodular utility functions with constraints