Grant: Discovery Grants Program - Individual
Simon Fraser University
$26,000.00
Exploring Polyhedra Representing Large-Scale Data Sets
FY 2019-20
Summary
Linear programming models are valuable because they can be solved quickly, even for very large-scale problems, via either pivoting-based strategies, such as the simplex method, or by interior-point methods. Both of these are effective, but also have drawbacks: the pivoting algorithms do not have good worst-case complexity guarantees, while interior point methods are vulnerable to numerical issues. An intriguing idea is to move towards a hybrid procedure that retains a pivoting structure, as thus is effectively combinatorial, but also includes moves that pass through the interior of the polyhedron. ******The most natural implementation of this is to expand the set of available directions to contain all circuit (or elementary) directions, with moves in a direction continuing until a constraint is reached. These additional circuit directions give shorter routes through polytopes, in terms of the number of pivots. One aim of this research is to use circuit and other hybrid augmentation algorithms effectively in optimization. A strong incentive to do this is the possibility of expanding to discrete and non-linear contexts. In these contexts, it will already be interesting to produce results that do not necessarily always attain the optimal solution, but provide approximation guarantees or simply work well on practical problems.******In some applications, rather than working with a fixed objective, which may not be known in advance, it is better to develop a menu of potentially (or Pareto) optimal solutions. An important special case is when the polyhedron represents a monotone Boolean function (MBF). Here the extreme points correspond to the minimal true settings of the function. Fredman and Khachiyan proposed an algorithm which generates all such extreme points in incremental quasi-polynomial time even when the MBF is only available as an oracle. A goal of this proposal is to improve our understanding of the Fredman-Khachiyan algorithm both in theory and in practice. This includes identifyng classes of MBFs that are particularly easy or difficult for the joint generation algorithm. This classification can then be used to improve implementations. A more ambitious target is determining if an output sensitive polynomial time algorithm exists for MBF generation.******MBFs are a hidden mathematical structure underlying diverse complex systems, and we believe there are many applications where understanding could improve through awareness of this structure. We are motivated in particular by applications in metabolic networks. To work with these networks, it is helpful to understand their minimal functional subsystems, known as elementary modes as well as their minimal blocking (or knockout) sets. **
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2019-07134
Name nom
Stephen, Tamon
Department département
Mathematics
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2019
Award amount
26000
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
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
Installment
inst:1 - 5
Partie
1
Nb partie
5
Application title
Exploring Polyhedra Representing Large-Scale Data Sets
Keyword
NSERC
Application summary
Linear programming models are valuable because they can be solved quickly, even for very large-scale problems, via either pivoting-based strategies, such as the simplex method, or by interior-point methods. Both of these are effective, but also have drawbacks: the pivoting algorithms do not have good worst-case complexity guarantees, while interior point methods are vulnerable to numerical issues. An intriguing idea is to move towards a hybrid procedure that retains a pivoting structure, as thus is effectively combinatorial, but also includes moves that pass through the interior of the polyhedron. ******The most natural implementation of this is to expand the set of available directions to contain all circuit (or elementary) directions, with moves in a direction continuing until a constraint is reached. These additional circuit directions give shorter routes through polytopes, in terms of the number of pivots. One aim of this research is to use circuit and other hybrid augmentation algorithms effectively in optimization. A strong incentive to do this is the possibility of expanding to discrete and non-linear contexts. In these contexts, it will already be interesting to produce results that do not necessarily always attain the optimal solution, but provide approximation guarantees or simply work well on practical problems.******In some applications, rather than working with a fixed objective, which may not be known in advance, it is better to develop a menu of potentially (or Pareto) optimal solutions. An important special case is when the polyhedron represents a monotone Boolean function (MBF). Here the extreme points correspond to the minimal true settings of the function. Fredman and Khachiyan proposed an algorithm which generates all such extreme points in incremental quasi-polynomial time even when the MBF is only available as an oracle. A goal of this proposal is to improve our understanding of the Fredman-Khachiyan algorithm both in theory and in practice. This includes identifyng classes of MBFs that are particularly easy or difficult for the joint generation algorithm. This classification can then be used to improve implementations. A more ambitious target is determining if an output sensitive polynomial time algorithm exists for MBF generation.******MBFs are a hidden mathematical structure underlying diverse complex systems, and we believe there are many applications where understanding could improve through awareness of this structure. We are motivated in particular by applications in metabolic networks. To work with these networks, it is helpful to understand their minimal functional subsystems, known as elementary modes as well as their minimal blocking (or knockout) sets. **