Informs Annual Meeting 2017

SA76

INFORMS Houston – 2017

SA75

3 - Inventory Routing in Continuous Time using Time-Expanded Models

372D Algorithms for Structured Optimization Problems I Sponsored: Optimization, Nonlinear Programming Sponsored Session Chair: Shiqian Ma, The Chinese University of Hong Kong, Shatin, Hong Kong, sqma@se.cuhk.edu.hk 1 - Value-function Based Non-cooperative Games Inspired by the family of network interdiction games which are proposed by Andrew Liu and his collaborators, we studied a two-stage non-cooperative game. The objective function of each player’s optimization problem contains a value function of a second-stage linear program, which is dependent on the first-stage variables in a way that a point-wise linear function upper bounds the second- stage decision variable. We first establish results regarding the existence of solution. Then we show that under Slater’s conditions and some other conditions, Lemke’s method can compute a solution to such games. 2 - Difference of Convex Approaches to Statistical Learning Miju Ahn, University of Southern California, Los Angeles, CA, United States, mijuahn@usc.edu We discuss a difference-of-convex (dc) programming approach to the sparsity representation problem in statistical learning. We present a unified formulation of many existing surrogate sparsity functions that are employed as approximations of the L-0 function, summarize optimality and sparsity results of the resulting dc optimization problem using such sparsity functions, discuss a LASSO based algorithm for solving the latter problem, and present numerical results on two sets of sparse statistical estimation problems: least square regression and logistic classification. 3 - Linear Convergence of Randomized Feasible Descent Methods under the Weak Strong Convexity Assumption Chenxin Ma, Lehigh University, Bethlehem, PA, United States, chm514@lehigh.edu, Martin Takac, Rachael Tappenden In this paper we generalize the framework of the Feasible Descent Method (FDM) to a Randomized (R-FDM) and a Randomized Coordinate-wise Feasible Descent Method (RC-FDM) framework. We show that many machine learning algorithms, including the famous SDCA algorithm for optimizing the SVM dual problem, or the stochastic coordinate descent method for the LASSO problem, fits into the framework of RC-FDM.We prove linear convergence for both R-FDM and RC- FDM under the weak strong convexity assumption. Moreover, we show that the duality gap converges linearly for RC-FDM, which implies that the duality gap also converges linearly for SDCA applied to the SVM dual problem. Tianyu Hao, PhD Student, University of Southern California, 3715 McClintock Avenue, GER240, Los Angeles, CA, 90089-0193, United States, tianyuha@usc.edu, Jong-Shi Pang 372E Advances in General Purpose Cutting Planes Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Matthias Koeppe, University of California-Davis, Davis, CA, 95616, United States, mkoeppe@math.ucdavis.edu 1 - Interactive Software for Cut-generating Functions and Beyond Yuan Zhou, University of California-Davis, 1 Shields Avenue, Department of Mathematics, Davis, CA, 95616, United States, yzh@math.ucdavis.edu, Matthias Koeppe We present software for investigations with cut-generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath. 2 - V-polyhedral Cuts Aleksandr M. Kazachkov, Carnegie Mellon University, Pittsburgh, PA, United States, akazachk@cmu.edu, Egon Balas Generating cutting planes for mixed-integer programs from valid general disjunctions, containing multiple inequalities per term, has been an active topic of inquiry in recent years. We investigate this idea from the V-polyhedral perspective, using a properly selected set of points and rays to generate cuts. Our framework, called V-polyhedral cuts, can be viewed as a strict extension of the generalized intersection cut paradigm, which only applies to generating cuts from convex sets. We discuss theoretical properties of V-polyhedral cuts and the results from an implementation of one variant of the method. SA76

Natashia Boland, Georgia Institute of Technology, Ferst Drive, Atlanta, GA, 30332, United States, natashia.boland@gmail.com, Felipe Lagos, Martin W. P.Savelsbergh Inventory routing is the problem of routing vehicles in space and time to deliver product to customers whose demand is a function of time, so that customers are never short of product and so that the sum of delivery and/or inventory costs are minimized. To date, research on inventory routing problems has focused on discrete time settings. Here we treat continuous time: customers demand is a continuous function of time. We show how integer programming models based on time discretization can be constructed so as to yield both primal and dual bounds on the value of the continuous-time problem, leading to a solution procedure, for which we present computational results. 372C Bilevel Optimization Sponsored: Computing Sponsored Session Chair: Juan Borrero, University of Pittsburgh, Pittsburgh, PA, 15260, United States, jsb81@pitt.edu Co-Chair: Hosein Zare, University of Pittsburgh, Pittsburgh, PA, 15260, United States, moz3@pitt.edu 1 - Solving Facility Location Problem through Robust Bilevel Optimization We study facility location problem through robust bilevel optimization, a novel model as well as solution procedure is proposed. Computational demonstrations based on practical system will also be discussed in the talk. 2 - Asymmetric Bilevel Linear Programming with Incomplete Information and Learning Juan Borrero, Oklahoma State University, 322 Engineering N, Stillwater, OK, 74078, United States, jsb81@pitt.edu, Oleg A. Prokopyev, Denis R. Saure We consider an asymmetric bilevel linear problem where the leader and follower interact repeatedly. At each period the leader implements an upper-level solution after which the follower reacts by solving the lower-level problem. The leader has incomplete information about the cost function of the follower’s problem, and learns about it from observing his reaction to her actions. Given that the leader’s objective is to find an optimal solution of the full-information bilevel problem, we study a set of greedy and ‘best’-case decision policies that are able to find an optimal solution in finite time periods, and can provide a real-time certificate of optimality to the leader. 3 - A New Bilevel Market Based Capacity Expansion Bo Zeng, University of Pittsburgh, 3700 O’Hara Street, Benedum Hall, Pittsburgh, PA, 15260, United States, bzeng@pitt.edu Bilevel optimization has been used to build capacity expansion models for power grid. Considering multiple market clearing responses, we build a new model for market based capacity expansion. Numerical results will be reported. 4 - Optimal Strategies in Pediatric Vaccine Pricing Problem Hosein Zare, University of Pittsburgh, 4200 Fifth Avenue, Pittsburgh, PA, 15260, United States, moz3@pitt.edu, Oleg A. Prokopyev, Osman Yalin Ozaltin We consider pediatric vaccine pricing problem in an oligopolistic market and explore the optimal pricing approach in a bilevel setting. Given that the customer in the lower-level problem selects a subsets of available vaccines to minimize the cost of vaccination, the vaccine manufacturer in the upper-level problem sets the price of vaccines to compete with other manufacturers and maximize her profit. We study the problem under different assumptions and provide the optimal pricing strategy in each situation. SA74 Liang Xu, University of Pittsburgh, 3700 O’Hara Street, 1048 Benedum Hall, Pittsburgh, PA, 15261, United States, lix21@pitt.edu, Bo Zeng

29

Made with FlippingBook flipbook maker