Grant: Discovery Grants Program - Individual
University of Waterloo
$22,000.00
Improved methods and applications of Mixed-Integer Programming
FY 2014-15
Summary
Mixed-Integer Programming (MIP) is an extremely important tool in quantitative decision making within modern corporations. Its applications include air transportation, telecommunications, logistics and manufacturing. This research program will investigate key issues to improve the performance of MIP tools and increase the spectrum of their applications. The proposed program will train 3 PhD students, 2 MMath students and 1 Postdoctoral fellow. These HQPs will gain skills and knowledge in optimization theory and in the implementation of optimization algorithms. These valuable skills are in high demand in academia and in industry, thus giving the HQP a great range of possibilities for successful careers. The first part of my project will focus on improving the methodology and theory of cutting planes for MIPs. Cutting planes are one of the most important tools in any software for MIPs, having received significant attention by the research community. Nonetheless, only recently has there been a shift in focus from cutting planes derived from single-constraint relaxations to multiple-constraint relaxations. The aim of this program will be to investigate new classes of cuts that fall into this category, by exploiting some of my recent results that developed a promising new framework for such cuts. My objective is to gain a deeper understanding of the theory of this new framework and its connections to other existing frameworks and then investigate its potential and limitations. The second part of the project will focus on developing state-of-the-art MIP-based software for solving routing-type problems. These kinds of problems are an important class of combinatorial optimization problems which have immediate applications in Logistics. Besides developing new cutting-planes for these problems, we also will address other issues that arise in this particular application including how to design a code that is accurate in spite of the inaccuracies intrinsic to floating point arithmetic. Furthermore, I will investigate convergency issues and how to design better formulations. Finally, I will consider the impact on these algorithms when uncertain data is considered. The theory and algorithms developed in this proposal have the potential to impact commercial MIP solvers, which by consequence can have a significant impact in all of its abovementioned application areas. In addition, the specific techniques developed for routing type problems can have a great impact in the Logistics sector which is a very important sector in any industry that relies on delivering goods/equipment/materials to its consumers. Therefore, the potential benefits to Canada are widespread.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2014-05623
Name nom
Fukasawa, Ricardo
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
2014
Competition year année de concours
2014
Award amount
22000
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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
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
1
Nb partie
5
Application title
Improved methods and applications of Mixed-Integer Programming
Keyword
NSERC
Application summary
Mixed-Integer Programming (MIP) is an extremely important tool in quantitative decision making within modern corporations. Its applications include air transportation, telecommunications, logistics and manufacturing. This research program will investigate key issues to improve the performance of MIP tools and increase the spectrum of their applications. The proposed program will train 3 PhD students, 2 MMath students and 1 Postdoctoral fellow. These HQPs will gain skills and knowledge in optimization theory and in the implementation of optimization algorithms. These valuable skills are in high demand in academia and in industry, thus giving the HQP a great range of possibilities for successful careers. The first part of my project will focus on improving the methodology and theory of cutting planes for MIPs. Cutting planes are one of the most important tools in any software for MIPs, having received significant attention by the research community. Nonetheless, only recently has there been a shift in focus from cutting planes derived from single-constraint relaxations to multiple-constraint relaxations. The aim of this program will be to investigate new classes of cuts that fall into this category, by exploiting some of my recent results that developed a promising new framework for such cuts. My objective is to gain a deeper understanding of the theory of this new framework and its connections to other existing frameworks and then investigate its potential and limitations. The second part of the project will focus on developing state-of-the-art MIP-based software for solving routing-type problems. These kinds of problems are an important class of combinatorial optimization problems which have immediate applications in Logistics. Besides developing new cutting-planes for these problems, we also will address other issues that arise in this particular application including how to design a code that is accurate in spite of the inaccuracies intrinsic to floating point arithmetic. Furthermore, I will investigate convergency issues and how to design better formulations. Finally, I will consider the impact on these algorithms when uncertain data is considered. The theory and algorithms developed in this proposal have the potential to impact commercial MIP solvers, which by consequence can have a significant impact in all of its abovementioned application areas. In addition, the specific techniques developed for routing type problems can have a great impact in the Logistics sector which is a very important sector in any industry that relies on delivering goods/equipment/materials to its consumers. Therefore, the potential benefits to Canada are widespread.