{"346051":{"#nid":"346051","#data":{"type":"event","title":"Ph.D. Defense by Jiajin Yu","body":[{"value":"\u003Cp\u003ETitle: \u003Cstrong\u003EOptimization and Separation for Structured Submodular Functions with Constraints\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EJiajin Yu\u003C\/strong\u003E\u003Cbr \/\u003ESchool of Computer Science\u003Cbr \/\u003ECollege of Computing\u003C\/p\u003E\u003Cp\u003EDate: Monday, December 1, 2014\u003Cbr \/\u003ETime: 2:30 pm EST\u003Cbr \/\u003ELocation: ISyE Groseclose 226A,\u003C\/p\u003E\u003Cp\u003EAdvisor: Dr. Shabbir Ahmed\u003C\/p\u003E\u003Cp\u003ECommittee:\u003Cbr \/\u003EDr. Santanu S. Dey, School of Industrial and Systems Engineering\u003Cbr \/\u003EDr. Richard J. Lipton, School of Computer Science\u003Cbr \/\u003EDr. Sebastian Pokutta, School of Industrial and Systems Engineering\u003Cbr \/\u003EDr. Prasad Tetali, School of Mathematics and School of Computer Science\u003C\/p\u003E\u003Cp\u003EReader: Dr. Santanu S. Dey, School of Industrial and Systems Engineering\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EVarious 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.\u003C\/p\u003E\u003Cp\u003EIn 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.\u003C\/p\u003E\u003Cp\u003EIn the next two chapters, we consider a class of submodular function f(a\u0027x) which is a univariate concave function applied to a linear function of binary variables.\u003C\/p\u003E\u003Cp\u003EIn 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\u0027x) 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\u0027x) 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.\u003C\/p\u003E\u003Cp\u003EIn Chapter 4, we study a mixed-integer nonlinear set that is the epigraph of f(a\u0027x) 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\u0027x) 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.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Optimization and Separation for Structured Submodular Functions with Constraints"}],"uid":"28077","created_gmt":"2014-11-14 14:45:36","changed_gmt":"2016-10-08 02:10:22","author":"Danielle Ramirez","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-12-01T13:30:00-05:00","event_time_end":"2014-12-01T16:30:00-05:00","event_time_end_last":"2014-12-01T16:30:00-05:00","gmt_time_start":"2014-12-01 18:30:00","gmt_time_end":"2014-12-01 21:30:00","gmt_time_end_last":"2014-12-01 21:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[{"id":"1808","name":"graduate students"},{"id":"100811","name":"Phd Defense"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78771","name":"Public"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}