2016 INFORMS Annual Meeting Program

TC12

INFORMS Nashville – 2016

TC12 104B-MCC New Results on Nonconvex Optimization Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Daniel Bienstock, Columbia University, 500 W 120th St, New York, NY, 10027, United States, dano@columbia.edu Co-Chair: Daniel Bienstock, Columbia University, Departments of IEOR and APAM, Columbia University, New York, NJ, 10027, United States, dano@columbia.edu 1 - Centerpoints: A Link Between Optimization And Convex Geometry Amitabh Basu, Johns Hopkins University, basu.amitabh@jhu.edu, Timm Oertel We introduce a concept that generalizes several different notions of a “centerpoint” in the literature. We develop an oracle-based algorithm for convex mixed-integer optimization based on centerpoints. Further, we show that algorithms based on centerpoints are “best possible” in a certain sense. Motivated by this, we establish several structural results about this concept and provide We consider the Multilinear set defined as the set of binary points satisfying a collection of multilinear equations. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. In this talk, we study the decomposability properties of Multilinear sets. Utilizing an equivalent hypergraph representation, we derive necessary and sufficient conditions under which a Multilinear set is decomposable based on the structure of pair-wise intersection hypergraphs. Finally, we propose a polynomial- time algorithm to optimally decompose a Multilinear set into simpler subsets. 3 - An FPTAS For Minimizing Some Indefinite Quadratics Over The Integer Points In A Polyhedron In Fixed Dimension Robert Hildebrand, IBM Research, robdhildebrand@gmail.com Although integer linear programming is an NP-Hard problem, Lenstra showed that in fixed dimension the problem can be solved in polynomial time. On the other hand, the problem of minimizing a quartic polynomial objective function over the the integer points in polyhedra is NP-Hard even in dimension 2. The complexity of minimizing quadratic and cubic polynomials in fixed dimension remains an open question. As a step in this direction, we will present an FPTAS for minimizing some quadratic polynomials in fixed dimension.This is joint work with Robert Weismantel and Kevin Zemmer. Recent Advances in Computational Optimization Sponsored: Optimization, Computational Optimization and Software Sponsored Session Chair: Gonzalo Munoz, Columbia University, 500 W. 120th Street, IEOR Department, New York, NY, 10027, United States, gonzalo@ieor.columbia.edu 1 - Low-rank/sparse-inverse Decomposition Victor Fuentes, University of Michigan, Ann Arbor, MI, United States, vicfuen@umich.edu, Jon Lee A well-known matrix decomposition problem is to split an input matrix into sparse and low-rank components. We look at decomposing an input matrix as the sum of a matrix having a sparse inverse and a low-rank matrix. One approach that we have developed is a convex SDP approximation. Also, employing the Woodbury matrix identity, we establish another framework for attacking the problem. Our numerical results demonstrate that: (1) our proposed methodology is useful and practical, (2) our method leads to a means for generating good test instances for algorithms that we are developing for the problem, and (3) a direct generalization of the recovery theorem for the ordinary version of the problem is unlikely. 2 - Improving The Randomization Step In Feasibility Pump Andres Iroume, Georgia Institute of Technology, efficient algorithms for computing these points. 2 - On Decomposability Of Multilinear Sets Alberto Del Pia, University of Wisconsin-Madison, delpia@wisc.edu, Aida Khajavirad TC13 104C-MCC

theoretical upper bounds on the running time (to the best of our knowledge for the first time for feasibility pump) and provide computational results that show a considerable reduction both in terms of numbers of iterations and computing time when applied to MIPLIB instances. 3 - A Branch-and-bound Algorithm For The Facility Location Problem With Random Utilities Eduardo Moreno, Universidad Adolfo Ibáñez, Santiago, Chile, eduardo.moreno@uai.cl, Alexandre S Freire, Wilfredo Yushimito The maximum capture problem with random utilities seeks to locate new facilities in a competitive market such that the captured demand of users is maximized, assuming that each individual chooses among all available facilities according to a random utility model. We also introduce a new branch-and-bound algorithm based on a column generation scheme for solving the original problem. Extensive computational experiments are presented, benchmarking the proposed approach with other linear and non-linear relaxations of the problem. Computational experiments show that our algorithm is competitive with all other methods as there is no method which outperforms the others in all instances. 4 - Submodular Path Inequalities For Capacitated Lot-sizing With Inventory And Backlogging Bounds Birce Tezel, University of California-Berkeley, Berkeley, CA, 94720, United States, btezel@berkeley.edu, Alper Atamturk We consider single item capacitated lot-sizing problems with backlogging (CLSB) where the maximum production, inventory and backlogging values are bounded. Using the underlying fixed-charge network structure of CLSB, we derive strong submodular path inequalities. These inequalities generalize flow cover inequalities for single node relaxations of CLSB. The computational results suggest that submodular path inequalities are quite effective in solving CLSB instances when used in a branch-and-cut algorithm. TC14 104D-MCC Sustainable and Responsible Supply Chain Management I Sponsored: Energy, Natural Res & the Environment I Environment & Sustainability Sponsored Session Chair: Sandra D Eksioglu, Clemson University, Clemson, SC, United States, seksiog@clemson.edu 1 - Valuing A Cellulosic Biofuel Project Considering Supply Uncertainty Guiping Hu, Iowa State University, gphu@iastate.edu, Yihua Li, Chung-Li Tseng, Wei-Chung Miao Iowa intends to invest in cellulosic biofuel production to expand its renewable fuels consumption. The yield of main feedstock, corn stover, fluctuates due to climate change, especially the rainfall amount. Dual sourcing is a possible strategy to mitigate the supply uncertainty, which in our case is the option of investing in growing dedicated energy crops as an additional supply source. A real options approach is used to analyze the optimal investment timing and benefits of the dual sourcing. 2 - Lot Sizing With Emission Dependent Demand Gokce Palak, Shenandoah University, gpalak@su.edu We extend economic lot sizing models to maximize profit and minimize emissions. This model captures the tradeoffs between supplier and mode selection decisions, as well as profits and emissions. We analyze impacts of price and emissions sensitive demand on the replenishment decisions. 3 - A Competitive Supply Chain Framework With Sustainable Environmental Policies Min Yu, University of Portland, Portland, OR, United States, yu@up.edu, Jose Cruz We develop a competitive supply chain network model with multiple firms, each of which produces a differentiated product. Multiple production, storage, and transport mode options are allowed. In order to control firms’ environmental emissions, the policy-maker seeks to decide the optimal policy instrument. Numerical illustrations provide managerial insights and policy implications.

airoume@gatech.edu, Santanu Subhas Dey, Marco Serpa Molinaro, Marco Serpa Molinaro

In this work, we modify the randomization step in feasibility pump. This step is used when staling is detected in order to avoid cycling. In our version, we use a WALKSAT-type method that automatically detects sparse structures. We prove

306