  


Maximizing a class of submodular utility functions with constraints
Jiajin Yu(jiajinyugatech.edu) Abstract: Motivated by stochastic 01 integer programming problems with an expected utility objective, we study the mixedinteger 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 branchandcut framework is illustrated using instances of an expected utility capital budgeting problem. Keywords: Submodularity, cutting planes, lifting, mixed integer nonlinear programming, branchandcut Category 1: Integer Programming (01 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  