Grant: Discovery Grants Program - Individual
McMaster University
$86,000.00
Linear Optimization: Theory and Applications
FY 2024-25
Summary
Data-driven analytics methodologies are presently at the forefront of efficient decision making and decision support in many industries. One prominent set of examples of this state-of-the-art optimization tools that made headway is optimizing energy generation, storage, transmission and delivery, and trading. These applications spread from operational to strategic time horizons. To name a few, optimization combined with other methods such as machine-learning is successfully used to improve the steam assisted gravity drainage (SAGD) process in oil recovery; optimization models and methods play a key role in determining efficient energy storage and dispatch strategies for smart grids, as well as help determine effective layouts for wind and solar farms; quantitative modelling and optimization occupy a central role when trading (energy) financial derivatives. Many data-driven problems can be formulated or approximated as linear optimization problems. There has been substantial progress in recent years in both the theoretical formulations and computational performances, including novel analysis of linear optimization algorithms and models for integer optimization. For instance, insights into the simplex method were obtained, Hirsch conjecture and its continuous analogue were disproved, and central-path following methods were shown to be non-strongly polynomial.
Still there remains a dearth of work to further advance linear optimization theory and algorithms. This research proposal aims at searching for new ideas and extensions via the investigation of the strengths and limitations of currently used advanced algorithms. The methodology is based on a combination of novel constructions and worst-case examples, and advanced computational approaches to close the gap between the currently established lower and upper bounds. Worst-case instances appear in many contexts due to their extremal properties. For instance, the structures conjectured to maximize the diameter of lattice polytopes arise in the determination of the complexity of convex matroid optimization, and in the computation of the number of generalized retarded functions in quantum field theory. Combinatorial and high dimensional geometric properties are often unexpected. Computational experiments are therefore a key factor for identifying and proving theoretical properties.
Another key focus of this research proposal is to develop new models to handle questions with applications in management sciences, supply-chain and transportation. Specifically, the proposal aims at further exploring optimization formulations to tackle question dealing with assemble-to-order (ATO) system and with shared electric vehicles. The objectives includes to further analyze the impact of component commonality for periodic review ATO systems, and to optimize the locations for charging stations for one-way electric car sharing programs by strategically locating charging stations given estimates of traffic flow.
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-06846
Name nom
Deza, Antoine
Department département
Computing and Software - Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2020
Award amount
86000
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
800
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information and communication services
Area of application fr
Services d'information et de télécommunications
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
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Linear Optimization: Theory and Applications
Keywords
optimization algorithms; linear optimization; combinatorial optimization; continuous optimization; enumeration algorithms; computational geometry; discrete geometry
Application summary
Data-driven analytics methodologies are presently at the forefront of efficient decision making and decision support in many industries. One prominent set of examples of this state-of-the-art optimization tools that made headway is optimizing energy generation, storage, transmission and delivery, and trading. These applications spread from operational to strategic time horizons. To name a few, optimization combined with other methods such as machine-learning is successfully used to improve the steam assisted gravity drainage (SAGD) process in oil recovery; optimization models and methods play a key role in determining efficient energy storage and dispatch strategies for smart grids, as well as help determine effective layouts for wind and solar farms; quantitative modelling and optimization occupy a central role when trading (energy) financial derivatives. Many data-driven problems can be formulated or approximated as linear optimization problems. There has been substantial progress in recent years in both the theoretical formulations and computational performances, including novel analysis of linear optimization algorithms and models for integer optimization. For instance, insights into the simplex method were obtained, Hirsch conjecture and its continuous analogue were disproved, and central-path following methods were shown to be non-strongly polynomial.
Still there remains a dearth of work to further advance linear optimization theory and algorithms. This research proposal aims at searching for new ideas and extensions via the investigation of the strengths and limitations of currently used advanced algorithms. The methodology is based on a combination of novel constructions and worst-case examples, and advanced computational approaches to close the gap between the currently established lower and upper bounds. Worst-case instances appear in many contexts due to their extremal properties. For instance, the structures conjectured to maximize the diameter of lattice polytopes arise in the determination of the complexity of convex matroid optimization, and in the computation of the number of generalized retarded functions in quantum field theory. Combinatorial and high dimensional geometric properties are often unexpected. Computational experiments are therefore a key factor for identifying and proving theoretical properties.
Another key focus of this research proposal is to develop new models to handle questions with applications in management sciences, supply-chain and transportation. Specifically, the proposal aims at further exploring optimization formulations to tackle question dealing with assemble-to-order (ATO) system and with shared electric vehicles. The objectives includes to further analyze the impact of component commonality for periodic review ATO systems, and to optimize the locations for charging stations for one-way electric car sharing programs by strategically locating charging stations given estimates of traffic flow.