{"601952":{"#nid":"601952","#data":{"type":"event","title":"ISyE Seminar - Vineet Goyal","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETITLE:\u003C\/strong\u003E On the Power of Affine Policies in Two-stage Adjustable Robust Optimization\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EABSTRACT:\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAffine policies are widely used as a solution approach in dynamic optimization where computing an optimal adjustable solution is usually intractable. While the worst case\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eperformance of affine policies can be significantly bad, the empirical performance is observed to be near-optimal for a large class of problem instances. For instance, in the two-stage dynamic robust optimization problem with linear covering constraints and uncertain right hand side, the worst-case approximation bound for affine policies is O(\u0026radic;m) that is also tight (see Bertsimas and Goyal [8]), whereas observed empirical performance is near-optimal. This work aims to address this stark-contrast between the worst-case and the empirical performance of affine policies.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe show that affine policies are provably a good approximation for the two-stage adjustable robust optimization problem with high probability on random instances\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ewhere the constraint coefficients are generated i.i.d. from a large class of distributions; thereby, providing a theoretical justification of the observed empirical performance. We also consider the performance of affine policies for an important class of uncertainty sets, namely the budget of uncertainty and intersection of budget of uncertainty sets. We show that surprisingly affine policies provide nearly the best possible approximation for this class of uncertainty sets that matches the hardness of approximation; further confirming the power of affine policies.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis talk is based is joint work with my student Omar El Housni.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBIO:\u003C\/strong\u003E\u0026nbsp;Vineet Goyal is Associate Professor in the Industrial Engineering and Operations Research Department at Columbia University where he joined\u0026nbsp;in\u0026nbsp;2010. He received his Bachelor\u0026#39;s degree\u0026nbsp;in\u0026nbsp;Computer Science from Indian Institute of Technology, Delhi\u0026nbsp;in\u0026nbsp;2003 and his Ph.D.\u0026nbsp;in\u0026nbsp;Algorithms, Combinatorics and Optimization (ACO) from Carnegie Mellon University\u0026nbsp;in\u0026nbsp;2008. Before coming to Columbia, he spent two years as a Postdoctoral Associate at the Operations Research Center at MIT. He is interested\u0026nbsp;in\u0026nbsp;the design of efficient and robust data-driven algorithms for large scale dynamic optimization problems with applications\u0026nbsp;in\u0026nbsp;\u0026nbsp;revenue management and smart grid problems. His research has been continually supported by grants from NSF and industry including NSF CAREER Award\u0026nbsp;in\u0026nbsp;2014 and faculty research awards from Google, IBM and Adobe.\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"ISyE Seminar - Vineet Goyal"}],"uid":"34547","created_gmt":"2018-02-06 15:08:09","changed_gmt":"2018-03-01 14:42:46","author":"nhendricks6","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-04-04T16:00:00-04:00","event_time_end":"2018-04-04T17:00:00-04:00","event_time_end_last":"2018-04-04T17:00:00-04:00","gmt_time_start":"2018-04-04 20:00:00","gmt_time_end":"2018-04-04 21:00:00","gmt_time_end_last":"2018-04-04 21:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"1242","name":"School of Industrial and Systems Engineering (ISYE)"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}