Informs Annual Meeting 2017

TA76

INFORMS Houston – 2017

TA77

3 - On the use of L-BFGS in Derivative-Free Optimization Albert S.Berahas, Northwestern University, Evanston, IL, 60208, United States, albertberahas@u.northwestern.edu, Jorge Nocedal, Richard Byrd The efficiency and efficacy of using finite-differencing to estimate derivatives in the Derivative-Free Optimization (DFO) setting still remains an unexplored domain. In this talk, we present a finite-difference quasi-Newton method for minimizing smooth deterministic, and noisy, black-box functions, and illustrate the performance of the method on several test-problems. We argue that popular model-based trust-region methods may not, for certain classes of problems, be more efficient in their use of function information than the finite-difference BFGS method, and that these problems have special identifying characteristics. 372E Large Scale Optimization Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Samir Elhedhli, University of Waterloo, University of Waterloo, Waterloo, ON, N2L 3G1, Canada, elhedhli@uwaterloo.ca 1 - Benders Decomposition for Uncapacitated Multicommodity Network Design Carlos Zetina, Concordia University, 1455 De Maisonneuve, Montreal, QC, H2L.4H1, Canada, c_zetina@encs.concordia.ca, Ivan Contreras, Jean-Francois Cordeau In this study, we present a Benders based exact algorithm to solve the uncapacitated multicommodity network design problem. Our algorithm combines the use of a modified Benders reformulation, lower bound strengthening and upper bound heuristics. We analyze the performance of the algorithm on benchmark instances and compare them with current solution methods 2 - A layer-Based Branch-and-price Approach for 3D Bin Packing Samir Elhedhli, University of Waterloo, Department of Management Sciences, 2000 University Street West, Waterloo, ON, N2L.3G1, Canada, elhedhli@uwaterloo.ca, Burak Can Yildiz, Fatma Gzara We propose a new formulation and a branch-and-price solution approach where the subproblems are two dimensional layers, a feature that is highly desirable in practice. The approach allows the inclusion of important practical constraints such as support, family groupings, isle friendliness, and load bearing. We conduct extensive computational experiments and compare against existing approaches. We also use industrial data to train and propose a realistic data set. The proposed approach outperforms the best performing algorithm in the literature and succeeds in solving practical size instances in very reasonable computational times. 3 - Network Planning of Green Telecommunication Networks Joe Naoum-Sawaya, Ivey Business School, 1255 Western Road, London, ON, N6G 0N1, Canada, jnaoum-sawaya@ivey.ca We present the network planning problem of an LTE cellular network with switchable base stations, ie. where the configuration of the antennae is dynamic, depending on demand. This is formulated as a two-stage stochastic program under demand uncertainty with integers in both stages. We develop its Dantzig- Wolfe reformulation and solve it using column generation. Preliminary results confirm the efficiency of the approach. 4 - Data Driven Robust Order Batching for Warehouse Management: A Branch and Price Approach Vedat Bayram, Assistant Professor, TED University, Endustri Muhendisligi Bolumu, Ziya Gokalp Caddesi No:48, Kolej Cankaya, Ankara, 06420, Turkey, vedat.bayram@tedu.edu.tr, Gohram Baloch, Fatma Gzara, Samir Elhedhli In this presentation, we report on data analytics solutions for a warehouse management and control systems company. We present data driven robust order batching solutions by developing an optimization model and a state of the art branch and price algorithm that employs simultaneous column and row generation procedures. TA76

372F Conic Reformulation for Integer and Quadratic Programming Sponsored: Optimization, Linear and Conic Optimization Sponsored Session Chair: Ziteng Wang, Northern Illinois Universtiy, DeKalb, IL, 60115, United States, zwang3@niu.edu 1 - Quadratic Programs with Hollows Boshi Yang, PhD, Clemson University, Clemson, SC, United States, boshiy@clemson.edu, Kurt M.Anstreicher, Samuel Burer Let F be a quadratically constrained bounded set, and let E1, ... , El denote ellipsoids contained in F with non-intersecting interiors. We prove that minimizing an arbitrary quadratic q() over G := F \ (\cup_{k=1}^l int(Ek)) is no more difficult than minimizing q() over F in the following sense: if a given SDP relaxation for min{ q(x) : x in F } is tight, then the addition of l linear constraints derived from E1, ... , El yields a tight SDP relaxation for min { q(x) : x in G }. Inspired by these results, we resolve a related question in a seemingly unrelated area, mixed integer nonconvex quadratic programming. 2 - A Completely Positive Programming Approach to the Cardinality Constrained Quadratic Programming Ziting Wang, Northern Illinois University, DeKalb, IL, United States, zwang3@niu.edu, Ye Tian In this paper, we propose a completely positive programming reformulation of the cardinality constrained portfolio selection problem. By constructing a sequence of computable cones of nonnegative quadratic forms over a union of second-order cones, an -optimal solution of the original problem can be found in nite iterations using semidenite programming techniques. In order to obtain a good lower bound eciently, an adaptive scheme is adopted in our approximation algorithm. The numerical results show that the proposed algorithm can nd better approximate and feasible solutions than other known methods in the literature. 3 - A New Linear Reformulation for Binary Quadratic Programming Problems Shan Jiang, North Carolina State University, sjiang8@ncsu.edu, Tiantian Nie, Shu-Cherng Fang, Qi An This paper presents a new 0-1 mixed-integer linear reformulation of a binary quadratic programming (BQP) problem. The proposed $O(n)$-sized linear reformulation is distinguished from other known $O(n)$-sized linear reformulations by a new linearization strategy that simultaneously treats symmetric quadratic terms. Besides the new structure embedded, the proposed reformulation also reduces the number of required continuous variables and linear constraints. Numerical experiments on various BQP instances demonstrate the superior computational efficiency of the proposed reformulation over other state-of-the-art linear reformulations. 381A Generation and Transmission Capacity-Expansion Planning Sponsored: Energy, Natural Res & the Environment Electricity Sponsored Session Chair: Ramteen Sioshansi, The Ohio State University, 240 Baker Systems Engineering Building, 1971 Neil Avenue, Columbus, OH, 43210-1271, United States, sioshansi.1@osu.edu Co-Chair: Antonio J. Conejo, The Ohio State University, 286 Baker Systems Engineering Building, 1971 Neil Avenue, Columbus, OH, 43210-1271, United States, conejonavarro.1@osu.edu 1 - Combining the L-shaped Method and Lagrangian Relaxation for Expansion Planning with Energy Storage Devices and Renewable Portfolio Standard Constraints Roderick Go, Johns Hopkins University, Baltimore, MD, 21218, United States, rgo1@jhu.edu, Francisco David Munoz, Jean-Paul Watson We propose a convergent solution algorithm to solve capacity expansion planning problems that co-optimize transmission, generation, and energy storage investment decisions on a transmission network subject to linking policy constraints like Renewable Portfolio Standards. In the proposed algorithm, we introduce a novel hybridization of Lagrangian relaxation and the L-shaped method that allows us to efficiently compute upper and lower bounds on optimal system cost. Additionally, we introduce a heuristic method to accelerate the solution while maintaining bounds. We illustrate the performance of these algorithms using the IEEE 24-bus test case with 52 weeks of hourly data. TA78

298