Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$45,000.00

Computational Studies in Discrete Optimization

FY 2017-18

Summary
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.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2014-04349
Name nom
Cook, William
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2014
Award amount
45000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
1206
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Engineering
Area of application fr
Génie
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Partie
4
Nb partie
5
Application title
Computational Studies in Discrete Optimization
Keyword
NSERC
Application summary
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.
University of Waterloo - $45,000 Grant (2017-18) | Canada Spends