Informs Annual Meeting 2017

WC77

INFORMS Houston – 2017

2 - Optimal Channel Structure for Refurbished Products Narendra Singh, Indian School of Business, Knowledge City,

4 - Learning to Run Heuristics in Tree Search Elias Khalil, Georgia Institute of Technology, 1062 Hemphill Avenue NW, Atlanta, GA, 30318, United States, lyes@gatech.edu, Bistra Dilkina, George Nemhauser, Shabbir Ahmed, Yufen Shao Primal Heuristics are a key contributor to the improved performance of branch- and-bound solvers for integer programming. We study the problem of deciding at which node a heuristic should be run, such that the overall primal performance of the solver is optimized. We present a theoretical framework for analyzing this decision-making process in a simplified setting, and use Machine Learning to predict whether a heuristic will succeed at a given node. Experimentally, our approach improves the primal performance of SCIP on MIPLIB2010 Benchmark and a family of hard Independent set instances. 372F Optimization, Integer Programming Contributed Session Chair: Takeshi Tsuyuguchi, University of Colorado, Denver, CO, United States, takeshi.tsuyuguchi@ucdenver.edu 1 - A Branch and Cut Algorithm for the Set Covering Problem with Conflict Constraints Saeed Saffari, North Carolina State University, Raleigh, NC, 27606, United States, ssaffar@ncsu.edu, Yahya Fathi We consider the well-known set covering problem in which we have incompatibilities between certain pairs of columns, i.e., from each conflicting pair at most one column can occur in the optimal subset. We propose a branch-and- cut algorithm for solving this problem in which we employ appropriate valid inequalities derived from the corresponding conflict graph. We also introduce appropriate pre-processing techniques and a constructive heuristic algorithm in this context. We present the results of a limited computational experiment to demonstrate the effectiveness of the proposed methods. 2 - Solving Set Covering Problems via Benders Decomposition Marcus V. Poggi, PUC-Rio, Rua M. S. Vicente 225, Rio de Janiero, 22591-900, Brazil, poggi@inf.puc-rio.br We enhance Zou, Ahmed and Sun’s 2016 work on Benders decomposition for stochastic programs with binary state variables with valid inequalities to reduce the integrality gap of the relaxation of the children problems. We apply the resulting algorithm to set covering problems with no special structure. We propose automatic decomposition strategies and focus the analysis on when certain strategies dominate others. Experiments are conducted over a series of well known literature set covering instances. 3 - Solving Clique Partitioning Problem: A Comparison of Models and Solvers Takeshi Tsuyuguchi, University of Colorado, 4295 E Mexico Ave., Apt 206, Denver, CO, 80222, United States, takeshi.tsuyuguchi@ucdenver.edu, Gary Kochenberger, Haibo Wang Finding optimal solutions to clique partitioning problems remains a computational challenge and is not practically possible. However, commercial solvers have improved tremendously in recent years, enabling acceptable, sometimes optimal, solutions for modest sized problems to be found in a reasonable amount of computer time. In this paper we explore and compare the use of four commercial solvers on a set of modest sized test problems. For each problem instance, a conventional linear model is compared with an alternative, equivalent quadratic model. Standard clique partitioning problems as well as those with minimum clique sized restrictions are considered. WC77

Sector 81, SAS.Nagar, Mohali, 140 306, India, narendra_singh@isb.edu, Ahmed Timoumi

We study a supply chain where a manufacturer produces new products and refurbishes used products. The manufacturer sells new products through a retailer and decides whether to sell refurbished products directly or through the same retailer or through a different retailer. We examine whether and when should the manufacturer choose a particular channel for the refurbished products. 3 - Secondary Market Operational Strategy of OEM: the Impact of Inertia and Forward-looking Consumer Ling-Fei Cai, Beijing Institute of Technology, Zhongguancun South Street No.5, Beijing, 100081, China, 461714207@qq.com, Xuan Shi The thriving of secondary market has leaded to huge impact to durable good OEMs. In this paper, we consider a monopolist market with single manufacturer, discuss operational strategy which include pricing and secondary market control strategy, with the impact of inertia and forward-looking consumer. We show that, forward-looking consumer will not lead to cannibalization effect when the cost and durability of the product is high enough. The consumer constitution make great impact to the pricing and secondary market control strategy when the cost and the durability are modest, OEM should adopt high price and open up secondary market only when the proportion of forward-looking consumer is high enough. 372E Three Facets of Integer Programming Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Aleksandr M. Kazachkov, Carnegie Mellon University, Pittsburgh, PA, 15213-3890, United States, akazachk@cmu.edu 1 - Parametric Inequalities and the Solution of Multi-stage Optimization Problems Ted K. Ralphs, Lehigh University, Industrial and Systems Engineering, 200 W. Packer Avenue, Bethlehem, PA, 18015, United States, ted@lehigh.edu In this talk, we’ll discuss the theoretical framework underlying solution algorithms based on the generation of so-called parametric valid inequalities for a general class of optimization problems that includes multi-stage and multi-level problems. We describe the theory of such inequalities, present methods for generating them, and describe a generalized branch-and-cut framework that incorporates them. 2 - Optimizing Truck Dispatching Decisions in Open-pit Mining using Integer Programming Amanda Smith, University of Wisconsin-Madison, 1513 University Avenue, Madison, WI, 53706, United States, asmith28@wisc.edu, Jeff T. Linderoth, Jim R. Luedtke We present a novel approach to the open-pit mining truck-dispatching problem that employs mixed-integer programming (MIP). The dispatching problem is challenging because it requires real-time decisions of a large-scale system with competing objectives. We propose an optimization-driven approach to solving the dispatching problem in the form of a MIP model. The model is difficult to solve directly within time constraints due to its large size. Therefore, we propose heuristic algorithms to quickly produce high quality feasible solutions to the model and present computational results demonstrating the effectiveness of the heuristics. 3 - Vehicle Routing Problems with Time Windows and Convex Node Costs We study a problem of routing several vehicles to serve a set of customers within desired time windows and minimize the total customer inconvenience cost. We model the inconvenience cost of each customer as a convex function of her service starting time. We propose a set partitioning formulation for this problem, and apply a branch-and-price framework to solve this formulation. The computational study shows the effectiveness of our algorithm compared to state- of-the-art mixed integer convex programming solvers on an extensive set of instances with quadratic inconvenience costs. WC76 Qie He, University of Minnesota, 111 Church Street SE, Minneapolis, MN, 55455, United States, qhe@umn.edu, Yongjia Song

529