2016 INFORMS Annual Meeting Program

WD19

INFORMS Nashville – 2016

WD19 106B-MCC Advances in Mixed-Integer Programming Theory and Algorithms Sponsored: Computing Sponsored Session Chair: Adolfo Raphael Escobedo, Arizona State University, Brickyard Engineering (BYENG) 553, 699 S Mill Ave, Tempe, AZ, 85281, United States, adolfo.escobedo@asu.edu 1 - Extensions Of Subadditive Duality For Conic Mixed-integer Programs Diego Moran, Universidad Adolfo Ibañez, dmoran@gatech.edu, Burak Kocuk In a recent paper it was proven that the subadditive dual for mixed-integer conic program is a strong dual under a strict feasibility requirement. In this paper, we generalize this result by exploring alternative sufficient conditions when strict feasibility is not present. In particular, we prove that in the case of essential strict feasibility and in the case of bounded feasible region, the subadditive dual has zero duality gap. Moreover, we show that the dual is solvable when essential strict feasibility holds while the solvability of the dual problem cannot be guaranteed for bounded feasible regions. Finally, we discuss a relationship between strong duality and cut generating functions. 2 - The Hamiltonian P-median Problem: Complexity And Algorithms Erick Moreno-Centeno, Department of Industrial and Systems Engineering, Texas A&M University, emc@tamu.edu, Ahmed Mohamed Marzouk, Halit Uster Given an undirected graph, G, the Hamiltonian p-median problem is to find p cycles partitioning G with minimum cost. This problem is NP-hard for any given value of p; however, the problem’s actual difficulty depends on the value of p. Similarly, the state-of-the-art algorithms outperform each other (or fail altogether) depending on the value of p. We give some insights on these observations. This work is in collaboration with Halit Uster and Ahmed Marzouk, both from Southern Methodist University. 3 - A Quadratic Relaxation For A Dynamic Knapsack Problem With Stochastic Item Sizes Daniel Blado, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, deblado@gatech.edu We examine the stochastic knapsack problem with random item sizes that are realized upon each attempted insertion. The process aims to maximize expected profit and ends after a failed insertion. We investigate dynamic programming- based LP bounds and their gap with the optimal adaptive policy. Our relaxation involves a quadratic value function approximation that encodes interactions between remaining items. We compare the bound to the best known pseudopolynomial bound and contrast their corresponding policies with two greedy policies. We conclude that the quadratic bound is theoretically more efficient than the pseudopolyomial bound yet empirically competitive in value and runtime. 4 - Routing Optimization With Time Windows Under Uncertainty We study an a priori Traveling Salesman Problem with Time Windows under uncertain travel times. We propose a decision criterion for articulating service levels that takes into account both the probability of lateness and its magnitude, and can be applied in contexts where either the distributional information of the uncertain travel times is fully or partially known. The criterion has the computationally attractive feature of convexity that enables us to formulate and solve the problem more effectively. Particularly, we obtain in some cases closed- form solutions to the Benders subproblems. Yu Zhang, Northeastern University, Shenyang, China, waltyuzhang@gmail.com, Roberto Baldacci, Melvyn Sim, Jiafu Tang

2 - A Reduced-space Algorithm For Minimizing L1-regularized Convex Functions Tianyi Chen, Johs Hopkins University, tchen59@jhu.edu We present a new method for minimizing the sum of a convex function and an l1-norm regularizer. The main features of the new method include: (i) an evolving set of indices corresponding to variables that are predicted to be nonzero at a solution; (ii) a reduced-space subproblem defined in terms of the predicted support; (iii) conditions that determine how accurately each subproblem must be solved; (iv) a computationally practical condition that determines when the predicted support should be updated; and (v) a reduced proximal gradient step that ensures sufficient decrease. We prove a convergence guarantee for our method and demonstrate its efficiency on a large set of model prediction problems. 3 - R-linear Convergence Rate Of A Limited Memory Steepest Descent Method Wei Guo, Lehigh University, weg411@lehigh.edu We provide some theoretical convergence results for a limited memory steepest descent (LMSD) method, proposed by Fletcher, when minimizing strictly convex quadratics. First, we show a finite termination property for the algorithm when there are duplicate eigenvalues. However, our main result shows an R-linear convergence rate for the algorithm when minimizing a strictly convex quadratic of any dimension with any limited memory history length. This extends the R- linear convergence rate of the Barzilai Borwein “two-point step size” method which uses information from only the previous iteration. Chair: Kiel Michael Martin, USAF, 8940 Rochester Dr, Colorado Springs, CO, 80920, United States, c05kielmartin@gmail.com 1 - An Operational Model To Support Cotton Trade In India Sundaravalli Narayanaswami, I I M, Ahmedabad, 380015, India, sundaravallin@iima.ac.in, Narasimhan Ravichandran Cotton Corporation of India (CCI) is a government agency created to regulate the market dynamics of cotton trade in India, (a cotton surplus country) to promote and protect the economic interest of cotton growing farmers in India. When there is a demand supply imbalance, CCI operates by appropriate price intervention and procurement of the quantity available to stabilize price. The procured quantity is sold by CCI at an appropriate time to maximize the economic value. The operational expenses are reimbursed by the Union Government. We develop and present simulation based models to facilitate negotiation between the government and CCI on this activity. 2 - Internet Of Things And Smart City Michael Chuang, SUNY New Paltz, 1 Hawk Drive, New Paltz, NY, 12561, United States, chuangm@newpaltz.edu Internet of Things have emerged as an enabler in various domains for facilitating business or operations such as its application in smart cities. In this preliminary study, we will review various scenarios where internet of things show potentials in smart city applications, and also opportunities and challenges for Internet of Things to be developed in this area. 3 - Connected Vehicle Analytics For In Vehicle Air Quality Management Yimin Liu, Mobility Analytics Manager, Ford Motor Company, One American Road, Dearborn, MI, 48121, United States, yliu59@ford.com, Yu Chen, Jinjing Yang, Oleg Gusikhin, Omar Makke, Jeff Yeung This talk presents a concept of cloud-based system for in-cabin air quality management. It leverages SmartDeviceLink technology to seamlessly integrate smartphone apps with Ford SYNC infotainment system and allow programmatically manage vehicle HVAC (Heating, Ventilation and Air Conditioning) settings. This approach allows integrating advanced connected car technologies, portable after-market sensors and cloud-based analytics into climate control loop. 4 - Sustaining The Drone Enterprise Kiel Michael Martin, Assistant Professor, USAF, 8940 Rochester Dr, Colorado Springs, CO, 80920, United States, c05kielmartin@gmail.com, Dan Richmond, John Swisher The Remotely Piloted Aircraft (RPA), colloquially labeled the “drone,” has become iconic of American military campaigns this century. The most salient question concerning these aircraft at the Pentagon today is operational, not ethical: given increasing global demand, how can the United States Air Force (USAF) produce and retain sufficient numbers of pilots to fly these aircraft? As part of a recent effort by the Secretary of Defense to stabilize the RPA enterprise, we developed a dynamic manpower projection model, quantifying the potential impact of myriad initiatives and directly informing new, Air Force-wide RPA policy. WD18 106A-MCC Business Apps Contributed Session

461