Skip to content Skip to main navigation Report an accessibility issue

Exploiting Decomposable Structure to Design Better Algorithms for Solving Integer Programs

Dr. Natashia Boland

Stewart School of Industrial & Systems Engineering

Georgia Institute of Technology

Friday, October 12, 2018

2:30-3:30pm   JDT 410



Optimization problems in which some or all of the variables are constrained to take integer values are of broad applicability in a wide range of fields, ranging from medicine and healthcare to banking and finance to environmental management and conservation. Over recent decades, exact algorithms for their solution have become faster and more efficient, culminating in a variety of commercial software platforms and public domain codes that provide exceptional capability for solving practical problems to optimality. However, this seems to have only increased the appetite of practitioners to solve ever-larger problems, which challenge the state-of-the-art. In this talk, we bring together two apparently disparate observations: (i) many practical problems have decomposable structure and (ii) despite the enormous strides in solution algorithms, one key element common to all of them, namely, the branching rule, has remained largely untouched since it was first presented in the 1960’s. Yet the branching rule defines how the search space is divided in the “divide-and-conquer’’ paradigm that forms the basis of all exact algorithms; it is central to the algorithm. Here, we will describe a new idea for exploiting decomposable structure in problems to derive alternative, powerful, new branching rules. These rules are demonstrated to speed up commercial solvers by orders of magnitude, on two classes of problems having different characteristics. The potential to generalize these ideas will also be discussed.



Natashia Boland is a professor in the Stewart School of Industrial & Systems Engineering at the Georgia Institute of Technology. She received her BSc(Hons) and PhD from the University of Western Australia in 1988 and 1992, respectively. After completing two years of postdoctoral research in 1994 and 1995, at the University of Waterloo, Canada, and Georgia Tech, respectively, she took up her first faculty position in her home country of Australia, in the Department of Mathematics and Statistics at the University of Melbourne. In 2008 she moved the University of Newcastle, Australia, to take up a position as Professor of Applied Mathematics, where she remained until moving, in 2015, to take up her current position.

Dr. Boland is an expert in the field of integer linear programming and discrete optimization, and an exponent of its application to address complex problems in government and industry. Her contributions to the field have spanned theory, algorithms, modeling and applications, in mining, defense, renewable energy, airline planning, freight transport, port logistics and environmental water management.

Recently, her methodological work has focused on two main directions. Seeking better solution of planning problems in time-space networks, she has developed techniques that generate only the parts of the network really needed to determine near-optimal solutions, with high accuracy and in far faster computing times than previously available. The second is on addressing problems with multiple objectives. She is developing technology that can efficiently, in practice, offer the decision-maker a comprehensive view of the trade-offs available to them, given the constraints of their system. Such technology is especially helpful in settings in which issues such as fairness, risk, environmental impact, and human factors, as well as costs or profits, play an important role in the decision-making.

Dr Boland has published more than 70 refereed journal articles and has graduated 20 PhD students. Her research is currently supported by NSF, UPS and Optym.