Informs Annual Meeting 2017

TA75

INFORMS Houston – 2017

TA73

Recently, researchers have developed algorithms that solve maximum clique rather quickly for real-life graphs despite the computational intractability of the problem. An explanation for the success of these approaches on these graphs is their sparsity, allowing one to delete low-degree vertices in a preprocessing step. We provide an alternative explanation based on the empirically observed proximity of the clique number to the graph’s degeneracy d. We develop an algorithm that runs in time polynomial in the graph’s size, but exponential in d - . When this difference is a constant, the running time is O(dm) = O(m1.5). Since 70% of common instances have d - ≤ 3, our algorithm is highly competitive. 2 - The Optimal Design of Low Latency Virtual Backbones Hamidreza Validi, Oklahoma State University, Stillwater, OK, 74078, United States, hamidreza.validi@okstate.edu, Austin Buchanan In wireless networks, two nodes may not be close enough to communicate directly, necessitating the use of intermediate nodes for relaying information. Often, one seeks a (smallest possible) subset of nodes to serve as designated relay nodes. In this talk, we discuss a hop-constrained variant of this optimization problem and propose an integer programming approach to solve it. 3 - On the 2-club Polytope of Graphs Foad Mahdavi Pajouh, University of Massachusetts Boston, 100 Morrissey Boulevard, Boston, MA, 02125-3393, United States, foad.mahdavi@umb.edu, Balabhaskar Balasundaram, Illya V. Hicks A k-club in a graph is a subset of its vertices such that the subgraph induced by this set has diameter at most k. Polyhedral study of the k-club model is a challenging task as this property is not hereditary. This talk presents a new class of facets for the 2-club polytope that contains all known nontrivial facets as special cases. Computational results addressing the effectiveness of these new inequalities will also be presented. 4 - Parsimonious Formulations for Low-diameter Clusters Hosseinali Salemi, Oklahoma State University, 15 North University Place, Apartment Number 2, Stillwater, OK, 74075, United States, hosseinali.salemi@okstate.edu, Austin Buchanan In the analysis of social and biological networks, one often searches for tightly knit clusters. One property of a “good” cluster is that it have a small diameter, which leads to the concept of a k-club. We propose a new IP formulation for detecting k-clubs and show that a relatively simple implementation of it often outperforms previous approaches. 372D Nonlinear and Stochastic Optimization Sponsored: Optimization, Nonlinear Programming Sponsored Session Chair: Albert S Berahas, Northwestern University, Evanston, IL, 60208, United States, albertberahas@u.northwestern.edu Co-Chair: Jorge Nocedal, Northwestern University, Evanston, IL, 60208-3118, United States, j-nocedal@northwestern.edu 1 - Linear Convergence of Gradient and Proximal-gradient Methods under the Polyak-lojasiewicz Condition Mark Schmidt, 201 2366 Main Mall, Vancouver, BC, V6T1Z4, Canada, schmidtm@cs.ubc.ca In 1963, Polyak proposed condition that is sufficient to show gradient descent has a global linear convergence rate, without strong-convexity. We show that this condition is weaker than the main conditions used to relax strong-convexity over the last 25 years. We also it to give new analyses of coordinate descent and stochastic gradient methods. We give a natural generalization of the inequality that applies to proximal-gradient methods for non-smooth optimization, and show this gives a simple linear convergence proof for LASSO and SVMs. Along the way, we give new convergence results for a wide variety of problems in machine learning. 2 - An Optimal Randomized Incremental Gradient Method Independent of Exact Gradient Evaluations Yi Zhou, Georgia Institute of Technology, 3209 Druid Hills Reserve Dr, Atlanta, GA, 30329, United States, yizhou@gatech.edu, Guanghui Lan In this talk, we consider a class of finite-sum convex optimization problems whose objective function is given by the average of m smooth components together with a strongly convex term. We first present a deterministic predictive accelerated gradient descent (PAGED) method that achieves the optimal black- box iteration complexity for solving these problems. We then develop a randomized variant, Rand-PAGED method, which needs no exact gradient evaluations and computes the gradient of one randomly selected smooth component iteratively but can possibly achieve better complexity bounds than optimal deterministic first-order methods in terms of the number of gradient evaluations. TA75

372B Open Pit Mine Planning Sponsored: Energy, Natural Res & the Environment, Natural Resources Mining Sponsored Session Chair: Alexandra M. Newman, Colorado School of Mines, Golden, CO, 80401, United States, anewman@mines.edu 1 - Scheduling Optimization for a Continuous Steel Caster Alexandra Newman, Colorado School of Mines, Golden, CO, United States, anewman@mines.edu, Joshua Betz In continuous steel casting operations, molten steel is batched into heats inside a ladle that is cast into slabs, which are then rolled into coils. We present a mixed integer program to produce a daily casting schedule that is solved using state-of- the art software. This model minimizes penalties incurred by violating plant best practices while strictly adhering to safety and logical constraints. A heuristic produces an initial feasible solution to expedite solutions, which we compare to current plant practice. 2 - A Study of Problem Specific Cutting Planes for the Open Pit Strategic Mine Scheduling Problem Orlando Rivera Letelier, Universidad Adolfo Ibanez, Santiago, Chile, orlando.rivera@uai.cl We study four types of problem specific cutting planes for the Open Pit Strategic Mine Scheduling Problem: Cliques, Early Starts, VRHS and Hourglass cuts. Two of them, the Cliques and the Early Start cuts are well-known cuts in the literature for the Precedence Constrained Knapsack Problem, while the other two types, the VRHS and the Hourglass cuts are new cuts developed for this work that make use of the production capacity constraints of the problem. We make computational tests in a set of real mines instances of the production scheduling problem, showing that the root node gap can be improved in average from 9.21% to 0.74%, which allows to solve to near optimallity instances of this problem. 3 - Revisiting Lane’s Model: An Optimization Approach Patricio Lamas, Universidad Adolfo Ibanez, Santiago, Chile, In 1964 Kenneth, Lane proposed an algorithm for optimizing the cutoff grade in an open pit mining project. Lane’s algorithm has made their way into multiple commercial software systems. However, the algorithm is regarded as a heuristic since no convergence proof is available in the literature. We present a formal description of Lane’s algorithm, and present theoretical results regarding the behavior of the optimal cut-off grade. Moreover, we propose a new mathematical optimization formulation for the problem, and use it as a benchmark to test the performance of Lane’s algorithm. Our computational results for real-world mines show that Lane’s algorithm finds the optimal solution for all instances. 4 - An Efficient Frontier Analysis to Determine Final Pit under Geological Uncertainty Enrique Jelvez, PhD, Advanced Mining Technology Center, Santiago, Chile, ejelvez@delphoslab.cl Enrique Jelvez, PhD, Delphos Mine Planning Lab & Department of plamas@alumnos.uai.cl, Marcos Goycoolea, Bernardo Kulnig Pagnoncelli, Adriana Piazza The final pit problem consists of finding the set of blocks that maximizes the undiscounted value of exploitation subject to precedence constraints. Although there exist efficient algorithms to compute it in a deterministic setting, the information on which this decision is made is subject to uncertainty. In this work, we present a comparison of several options to calculate final pit, including geological uncertainty given by a number of conditional simulations. In particular, we develop a model that allows us to generate the efficient frontier of final pit alternatives in the expected return-risk context, when the risk is measured in terms of Conditional Value at Risk. 372C Network Problems with Hop Constraints Sponsored: Computing Sponsored Session Chair: Austin Buchanan, Oklahoma State University, Stillwater, OK, 74078, United States, buchanan@okstate.edu 1 - Why is Maximum Clique Easy on Real-life Graphs? Jose Luis Walteros, University at Buffalo, SUNY, 413 Bell Hall, Buffalo, NY, 14260, United States, josewalt@buffalo.edu, Austin Buchanan TA74 Mining Engineering, University of Chile, Santiago, Chile, ejelvez@delphoslab.cl, Nelson Morales, Nelson Morales, Julian Ortiz

297