Grant: Discovery Grants Program - Individual
University of Waterloo
$52,000.00
Theory, computations and applications of structured Mixed-Integer Programs
FY 2023-24
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. The long-term goal of my research is to improve solution methods for MIPs, by providing better theoretical understanding of its properties, improving algorithmic ideas and ultimately allowing one to solve real-world optimization problems at a larger scale. This proposal advances this goal by studying particular structures that appear in some applications. Two research streams will be addressed. The first stream deals with considering sparsity in MIPs, particularly in cutting planes. Sparsity is a measure of the number of nonzero components, and it is an important factor that allows several algorithms to become faster. It is a prominent feature in several benchmark MIPs that came from practical applications - in a large set of such benchmark MIPs, the average sparsity is close to 1%. Cutting planes are one of the most important components in the practical solution of MIPs and, among all cutting planes, split cuts are the ones with greater impact. In a recent work, we have investigated split cuts obtained from sparse splits and show, through computational experiments, that this subclass of split cuts is very important. Therefore, this first stream will address theoretical and computational questions that arise based on such a sparsity parameter, with the ultimate goal to improve the performance of MIP algorithms. The second stream is dedicated to studying the structure obtained in the context of MIP formulations for vehicle routing (VRP), particularly under uncertainty. The VRP is an important optimization problem that seeks to find the minimum cost way to route a fleet of vehicles to satisfy a set of customer demands in such a way that the capacity of each vehicle is respected. It finds applications in logistics and transportation. One limiting assumption in the VRP is that all customer demands are known in advance, which is not always the case. Thus, recently, renewed research interest has been devoted to studying variants of the problem where demands are uncertain (i.e. stochastic VRP). Thus, this second stream aims to significantly advance the state-of-the-art in solving the stochastic VRP. Of particular interest are data-driven approaches, i.e. approaches that optimize using only historical data as input. The proposal will investigate new algorithms for existing versions of the problem and new paradigms for modeling more realistic versions of it. Ultimately, the development of such approaches will significantly increase the applicability of VRP models in real-world applications. HQP trained as a result of this proposal will gain valuable skills in quantitative decision making, acquiring both theoretical and implementation knowledge, which is important in both academia and industry.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2020-04030
Name nom
Fukasawa, Ricardo
Department département
Combinatorics and Optimization - 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
2023
Competition year année de concours
2020
Award amount
52000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
2956
Research subject group en
Applied mathematics
Research subject group fr
Optimisation and optimal control theory
Research subject en
Mathématiques appliquées
Research subject fr
Optimisation et théories de commande optimale
Application title
Theory, computations and applications of structured Mixed-Integer Programs
Keyword
computational optimization; cutting planes; mixed integer programming; stochastic programming; vehicle routing
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. The long-term goal of my research is to improve solution methods for MIPs, by providing better theoretical understanding of its properties, improving algorithmic ideas and ultimately allowing one to solve real-world optimization problems at a larger scale. This proposal advances this goal by studying particular structures that appear in some applications. Two research streams will be addressed. The first stream deals with considering sparsity in MIPs, particularly in cutting planes. Sparsity is a measure of the number of nonzero components, and it is an important factor that allows several algorithms to become faster. It is a prominent feature in several benchmark MIPs that came from practical applications - in a large set of such benchmark MIPs, the average sparsity is close to 1%. Cutting planes are one of the most important components in the practical solution of MIPs and, among all cutting planes, split cuts are the ones with greater impact. In a recent work, we have investigated split cuts obtained from sparse splits and show, through computational experiments, that this subclass of split cuts is very important. Therefore, this first stream will address theoretical and computational questions that arise based on such a sparsity parameter, with the ultimate goal to improve the performance of MIP algorithms. The second stream is dedicated to studying the structure obtained in the context of MIP formulations for vehicle routing (VRP), particularly under uncertainty. The VRP is an important optimization problem that seeks to find the minimum cost way to route a fleet of vehicles to satisfy a set of customer demands in such a way that the capacity of each vehicle is respected. It finds applications in logistics and transportation. One limiting assumption in the VRP is that all customer demands are known in advance, which is not always the case. Thus, recently, renewed research interest has been devoted to studying variants of the problem where demands are uncertain (i.e. stochastic VRP). Thus, this second stream aims to significantly advance the state-of-the-art in solving the stochastic VRP. Of particular interest are data-driven approaches, i.e. approaches that optimize using only historical data as input. The proposal will investigate new algorithms for existing versions of the problem and new paradigms for modeling more realistic versions of it. Ultimately, the development of such approaches will significantly increase the applicability of VRP models in real-world applications. HQP trained as a result of this proposal will gain valuable skills in quantitative decision making, acquiring both theoretical and implementation knowledge, which is important in both academia and industry.