Natashia Lesley Boland
Frontiers of Integer Programming
Optimization problems in which some or all of the variables are constrained to take integer values are applicable in a many 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 packages and public domain codes that provide exceptional capability for solving practical problems to optimality. This has opened up new frontiers.
Many decision makers, in practice, consider multiple, competing objectives. In medicine, radiation oncologists seek to minimize the damage to a critical organ while maximizing the damage to a cancerous tumor. In environmental management, the health of populations of competing, threatened species must be maximized. Leveraging the power of exact integer programming solvers, algorithms that compute the optimal trade-off curve, also known as the Pareto frontier, for integer programming problems with multiple objectives, have been developed in recent years. These greatly enhance what optimization can offer the decision-maker, giving them a complete picture of the options available to them, and allowing them to exercise their experience and expertise in selecting the solution to implement.
The astonishing capabilities of exact solvers has only increased the appetite of practitioners to solve ever-larger problems, which challenges the state-of-the-art. These solver capabilities have been achieved by decades of research enhancing the “divide-and-conquer” branch-and-bound method that lies at the heart of all exact solvers. Yet one key element of this method has remained largely untouched since it was first presented in the 1960’s: the branching rule, by which the solution space is divided. Recent work has shown that for problems with decomposable structure, new branching rules, developed to exploit that structure, can have dramatic effects on the performance of the branch-and-bound method.
In this talk, we will discuss both these developments, at the frontiers of integer programming research, and, in the process, identify further research opportunities for the field.
Natashia Boland is a professor in the H. Milton Stewart School of Industrial & Systems Engineering at the Georgia Institute of Technology. She received her PhD in 1992 from the University of Western Australia. After two years of postdoctoral research at the University of Waterloo and Georgia Tech, respectively, she took up a faculty position at the University of Melbourne. In 2008 she moved to the University of Newcastle, Australia, remaining until 2015, when she took up her current position.
Dr. Boland is an expert in the field of integer linear programming, and an exponent of its application to complex problems in government and industry. Her contributions have spanned theory, algorithms, modeling and applications, in mining, defense, renewable energy, airline planning, freight transport, logistics and environmental water management.
Recently, her methodological work has focused on: (1) better solution of planning problems in time-space networks; (2) solving problems with multiple objectives so as to offer the decision-maker a comprehensive view of the trade-offs available to them; and (3) improving fundamental methods for solution of integer programs.
Dr. Boland has published more than 75 refereed journal articles and graduated 20 PhD students. Her research is currently supported by NSF, UPS and Optym.
J. Cole Smith
The Applications, Mathematics, and Algorithms of Two-Player Optimization Problems
The optimization fields of bilevel programming, interdiction, and robust optimization have become vital areas of study over the past few decades. Problems in these fields typically involve two players making decisions in turn, where each player’s actions affect each other’s objectives and/or resources. These models increasingly important relevance in protecting critical infrastructure, determining vulnerabilities in complex systems, and analyzing how systems can be designed to achieve desired outcomes for the players. This lecture will discuss some of the applications that inspired developments in these areas, and will contrast the models used to represent the different games. Despite the variations in algorithms designed to solve these models, there are many commonalities as well. This talk will discuss, in a lightly technical manner, the commonalities of these approaches and how advances in one research area benefits the development of algorithms in the other areas. Finally, I will discuss some emerging research areas and opportunities for future research in this field.
Dr. J. Cole Smith is Associate Provost of Academic Initiatives and Professor of Industrial Engineering at Clemson University. His research has been supported by the NSF, DARPA, AFOSR, DTRA, and the ONR, and he has spent one summer as a Distinguished Visiting Professor in the National Security Agency’s summer program in operations research technology. His research regards mathematical optimization models and algorithms, especially those arising in combinatorial optimization, and he has had the pleasure of collaborating with colleagues across many different disciplines. Dr. Smith’s awards include the Young Investigator Award from the ONR, the Hamid K. Elden Outstanding Young Industrial Engineer in Education award, the Operations Research Division Teaching Award, the 2014 Glover-Klingman prize for best paper in Networks, and the best paper award from IIE Transactions in 2007. He became a Fellow of IISE in 2018. Currently, he also serves on the IISE Board of Trustees as Senior Vice President – Continuing Education, and on the INFORMS Board of Directors as Vice President/Publications.
Alice E. Smith
Dr. Elena Fernández obtained a degree in Mathematics in 1979 at the University of Zaragoza and in 1988 her PhD in Computer Science at the Technical University of Catalonia- BcnTech (UPC) in Barcelona. Since 2007 she is Professor of Operations Research in the Department of Statistics and Operations Research at UPC. Her research interest focuses on mathematical programming models for discrete optimization, mainly on applications for transportation and logistics involving discrete location, network design and vehicle routing. She has published over 80 scientific papers in the flagship journals of her discipline, with about 70 co-authors from a dozen of different countries. Elena has served in editorial roles in TOP, the Operations Research Journal of the Spanish Society SEIO, Computers & Operations Research and the EURO Journal on Computation Optimization. In 2015-16 she served as the President of the Association of European Operational Research Societies (EURO).
Advances in Exact Algorithms for Vehicle Routing
The Vehicle Routing Problem (VRP) is among the most widely studied problems in the fields of operations research and combinatorial optimization. Its relevance stems from its direct application in the real world systems that distribute goods and provide services, vital to the modern economies. Reflecting the large variety of conditions present in those systems, the VRP literature is spread into dozens of variants. For example, there are variants that consider time windows, multiple depots, mixed vehicle fleet, split deliveries, pickups and deliveries, precedences, etc. The currently best exact VRP algorithms are based on the combination of column generation and cut separation, in the so called Branch-Cut-and-Price (BCP) algorithms. This talk surveys significant recent contributions by several authors. In particular, it presents the concept of cuts with limited-memory (Pecin et al. 2014), a technique that represented a breakthrough on some of the most classical VRP variants, allowing the optimal solution of instances with up to a few hundreds points. The talk also presents the ongoing efforts for creating the first effective generic exact VRP algorithms. They should be suited to many distinct variants and still have a good performance.
Eduardo Uchoa is Professor of Production Engineering at Universidade Federal Fluminense, Niterói, Brazil. He is currently ranked as Researcher Level 1 by the Brazilian funding agency CNPq and has a Scientist of the State of Rio de Janeiro grant. His research areas include the theory and application of integer programming approaches solving for large NP-hard combinatorial optimization problems. In particular, he had made significant contributions for the joint use of column and cut generation techniques, in the so called branch-cut-and-price algorithms. Professor Uchoa is author and co-author of several papers that have appeared in leading journals such as Mathematical Programming, Mathematical Programming Computation, European Journal of Operational Research, Transportation Science, Computers and Operations Research, Annals of Operations Research, Networks and Interfaces and in conferences like IPCO.