TITLE: Maximizing a Class of Submodular Utility Functions: An IP approach
SPEAKER: Dr. Shabbir Ahmed
ABSTRACT:
We report polyhedral results for a class of combinatorial optimization problems involving submodular utility maximization. Strong valid inequalities are derived by lifting lower dimensional inequalities. We provide a complete characterization of the lifting function and its subadditive approximation. Computational experiments with capital budgeting problems show the effectiveness of the derived inequalities within a branch-and-cut approach.
Joint work with Alper Atamturk, UC Berkeley
Paper available at http://www.optimization-online.org/DB_HTML/2008/04/1948.html
Contact: ISyE DOS Optimization Seminars (http://www2.isye.gatech.edu/dos/)