Computational Studies in Discrete Optimization

点击翻译按钮获取中文摘要

Discrete optimization is used to solve practical problems that involve choosing the best alternative from a field of possibilities; it has broad applications in nearly every segment of the economy. Many industries, ranging from telecommunications to VLSI, are fully dependent on discrete optimization to guide them through complex design procedures.Perhaps the most important class of discrete optimization problems are the mixed-integer-programming (MIP) models. These models have the form of minimizing or maximizing a linear function subject to linear inequality constraints, where some or all of the variables are required to take on integer values. If no variables are required to be integer, then the model is a linear-programming (LP) problem. The integral variables make MIP models much more difficult to solve than the corresponding LP models, but it is this integrality component that allows MIP models to capture decisions that are discrete in nature.The great success of discrete optimization is due in large part to the power of George Dantzig's famous simplex algorithm, designed to solve LP models; this algorithm was named one of the Top Ten Algorithms of the Century in the year 2000. In discrete optimization, the simplex algorithm is combined with a technique known as the cutting-plane method for improving the LP approximations of discrete problems. The use of cutting planes was pioneered by Dantzig, Fulkerson, and Johnson in 1954 in their work on the traveling salesman problem (TSP); many variations have been proposed over the years and cutting planes are now an essential ingredient in commercial MIP solvers and in the most successful attacks on many classes of discrete optimization problems.We propose a line of research aimed at extending the reach of discrete optimization and mixed-integer programming. The work has two main thrusts. First, we will seek to develop tools that will allow for the solution of much larger classes of LP models with the simplex method, utilizing parallel computing platforms. Secondly, we will study MIP and TSP models to develop better techniques for applying the cutting-plane method to large-scale models, again focusing on the use of parallel computing platforms. The expected outcomes are greatly improved tools and software for the solution of LP and MIP models arising in industrial applications, as well as an improved version of the widely-used Concorde code for the solution of the traveling salesman problem.An important component of the proposed project is the training of graduate students in advanced techniques in the practical solution of large-scale discrete optimization models. Students involved in the project will be well-suited for the many positions that are currently available in this area in both industry and academia.