Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of British Columbia

$24,000.00

Better algorithms for discrete optimization, with applications

FY 2012-13

Summary
Many important business activities can usefully be represented as optimization models where we want to find the best possible feasible values of some decision variables that maximize or minimize some objective function. A challenging but important subset of these models require that the decision variables take only integer values. Such ""discrete optimization"" problems are provably hard in general, but there are many special cases where it can be proved that a fairly simple model has guaranteed integer optimal solutions. Unfortunately, in many of these cases it is not yet known how to efficiently find such integer optimal solutions. Much of this proposed research is dedicated to extending the classes of problems where we can efficiently find such solutions. One important class comes from a discrete analog of convexity called submodularity, which is similar to complementarity in economics. I propose to investigate how to optimize submodular structures faster, use submodularity in parametric optimization, and to characterize supply chain structures containing submodularity. Another important class comes from flows in networks. I propose to use network flow methods to find algorithms for ""separation algorithms"", i.e, as a way of solving easier subproblems that arise when solving more difficult problems. This also connects to parametric and submodular problems. Another part of this research concerns situations where competing retailers have excess demand that can be satisfied by either customers or the retailers arranging that unsatisfied customers get the product from another store that does have stock available. How does this possibility affect incentives, contracts, and prices in the marketplace? Our research aims to answer such questions.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
46602-2010
Name nom
McCormick, SThomas
Department département
Sauder School of Business
Organization id
2
Institution établissement
University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2010
Award amount
24000
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
500
Area of application group en
Manufacturing processes and products
Area of application group fr
Procédés et produits industriels
Area of application en
Manufacturing processes and products
Area of application fr
Procédés et produits industriels
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
3
Nb partie
5
Application title
Better algorithms for discrete optimization, with applications
Keyword
NSERC
Application summary
Many important business activities can usefully be represented as optimization models where we want to find the best possible feasible values of some decision variables that maximize or minimize some objective function. A challenging but important subset of these models require that the decision variables take only integer values. Such ""discrete optimization"" problems are provably hard in general, but there are many special cases where it can be proved that a fairly simple model has guaranteed integer optimal solutions. Unfortunately, in many of these cases it is not yet known how to efficiently find such integer optimal solutions. Much of this proposed research is dedicated to extending the classes of problems where we can efficiently find such solutions. One important class comes from a discrete analog of convexity called submodularity, which is similar to complementarity in economics. I propose to investigate how to optimize submodular structures faster, use submodularity in parametric optimization, and to characterize supply chain structures containing submodularity. Another important class comes from flows in networks. I propose to use network flow methods to find algorithms for ""separation algorithms"", i.e, as a way of solving easier subproblems that arise when solving more difficult problems. This also connects to parametric and submodular problems. Another part of this research concerns situations where competing retailers have excess demand that can be satisfied by either customers or the retailers arranging that unsatisfied customers get the product from another store that does have stock available. How does this possibility affect incentives, contracts, and prices in the marketplace? Our research aims to answer such questions.