Title: Optimization and Separation for Structured Submodular Functions with Constraints

Jiajin Yu
School of Computer Science
College of Computing

Date: Monday, December 1, 2014
Time: 2:30 pm EST
Location: ISyE Groseclose 226A,

Advisor: Dr. Shabbir Ahmed

Committee:
Dr. Santanu S. Dey, School of Industrial and Systems Engineering
Dr. Richard J. Lipton, School of Computer Science
Dr. Sebastian Pokutta, School of Industrial and Systems Engineering
Dr. Prasad Tetali, School of Mathematics and School of Computer Science

Reader: Dr. Santanu S. Dey, School of Industrial and Systems Engineering

Abstract:

Various kinds of optimization problems involve nonlinear functions of binary variables that exhibit a property of diminishing marginal returns. Such a property is known as submodularity. Vast amount of work has been devoted to the problem of submodular optimization. In this thesis, we exploit structural information for several classes of submodular optimization problems. We strive for polynomial time algorithms with improved approximation ratio and strong mixed-integer linear formulations of mixed-integer non-linear programs where the epigraph and hypograph of submodular functions of a specific form appear as a substructure together with other side constraints.

In Chapter 2, we develop approximation algorithms for the expected utility knapsack problem. We use the sample average approximation framework to approximate the stochastic problem as a deterministic knapsack-constrained submodular maximization problem, and then use an approximation algorithm to solve the deterministic counterpart. We show that a polynomial number of samples is enough for a deterministic approximation that is close in relative error. Then, exploiting the strict monotonicity of typical utility functions, we present an algorithm that maximizes an increasing submodular function over a knapsack constraint with approximation ratio better than the classical (1-1/e) ratio.

In the next two chapters, we consider a class of submodular function f(a'x) which is a univariate concave function applied to a linear function of binary variables.

In Chapter 3, we present polyhedral results for the expected utility knapsack problem. We study a mixed-integer nonlinear set that is the hypograph of f(a'x) together together with a knapsack constraint. We propose a family of inequalities for the convex hull of the nonlinear set by exploiting both the structure of the submodular function f(a'x) and the knapsack constraint. Effectiveness of the proposed inequalities is shown by computational experiments on expected utility maximization problem with budget constraint using a branch-and-cut framework.

In Chapter 4, we study a mixed-integer nonlinear set that is the epigraph of f(a'x) together with a cardinality constraint. This mixed-integer nonlinear set arises as a substructure in various constrained submodular minimization problems. We develop a strong linear formulation of the convex hull of the nonlinear set by exploiting both the submodularity of f(a'x) and the cardinality constraint. We provide a full description of the convex hull of the nonlinear set when the vector a has identical components. We also develop a family of facet-defining inequalities when the vector a has nonidentical components. We demonstrate the effectiveness of the proposed inequalities by solving mean-risk knapsack problems using a branch-and-cut framework.