Grant: Discovery Grants Program - Individual
Simon Fraser University
$38,000.00
Navigating the Contours of Combinatorial Feasible Sets
FY 2024-25
Summary
One of the great insights of operations research is that combinatorial data, such as lists of priorities for scheduling or potential routes through networks, can be encoded as high-dimensional vectors along with the relevant objectives and constraints. This allows the formulation of optimization models for these problems, whose solution requires a detailed understanding of a high-dimension feasible set. The aim of this proposal is to develop effective procedures to describe and optimize over combinatorial feasible sets presented as polyhedra or monotone Boolean Functions (MBF).
For general polyhedra, this involves developing the machinery of circuit and other hybrid augmentation algorithms. These procedures use the pivoting structure of linear programming, but also include moves that pass through the interior of the polyhedron (via circuits). In joint work with A. Wiebe, we will bring slack realization space techniques to this analysis. We will start by resolving the question of Stephen and Yusun on whether the Klee-Walkup polytope is circuit-Hirsch tight. This is a first step towards resolving the circuit analogue of the Hirsch conjecture. The wider theoretical here is the polynomial Hirsch conjecture and the existence of strongly polynomial-time algorithms for linear programming. On the practical importance is the possibility of expanding to discrete and nonlinear contexts, where we aim for approximation guarantees or simply good performance on practical problems.
A fundamental class of polyhedra for applications are those that represent MBFs. Here we are interested in joint generation algorithms that enumerate the extreme points of such a polyhedron along with those of its dual function. On the theoretical side, we will identify classes of MBFs that are particularly easy or difficult for the joint generation algorithm. We note that the known examples that are challenging for these algorithms are extremely symmetric, so in work with student S. Islam, we are characterizing the role of symmetry in the algorithms. At the same time, in work with undergraduate P. Salimi, we are employing deep reinforcement learning to find less symmetric challenging examples. A major goal is to determine if an output sensitive polynomial time algorithm exists for MBF generation.
Progress on the theoretical front feeds into further development on the implementation side. We are on the forefront of implementations, including the recent codes developed by N. Sedaghat, which provide optimized versions of the Fredman-Khachiyan algorithm B. We will continue to develop public open-source code for these problems, which have many applications. A particular motivation is the use of MBFs in modelling metabolic networks.
This work helps with the modelling and solution of large-scale problems, and puts trainees in a strong position to contribute. I plan to continue to engage with external partners on their related applications.
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-2024-06800
Name nom
Stephen, Tamon
Department département
Mathematics - 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
2024
Competition year année de concours
2024
Award amount
38000
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
405
Area of application group en
Environment
Area of application group fr
Environnement
Area of application en
Modelling and mathematical simulation of natural processes
Area of application fr
Modélisation et simulation mathématique des processus naturels
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
Navigating the Contours of Combinatorial Feasible Sets
Keywords
operations research; optimization; algorithms; discrete mathematics; linear programming; integer programming; computational geometry; boolean functions; polyhedra; computational complexity
Application summary
One of the great insights of operations research is that combinatorial data, such as lists of priorities for scheduling or potential routes through networks, can be encoded as high-dimensional vectors along with the relevant objectives and constraints. This allows the formulation of optimization models for these problems, whose solution requires a detailed understanding of a high-dimension feasible set. The aim of this proposal is to develop effective procedures to describe and optimize over combinatorial feasible sets presented as polyhedra or monotone Boolean Functions (MBF).
For general polyhedra, this involves developing the machinery of circuit and other hybrid augmentation algorithms. These procedures use the pivoting structure of linear programming, but also include moves that pass through the interior of the polyhedron (via circuits). In joint work with A. Wiebe, we will bring slack realization space techniques to this analysis. We will start by resolving the question of Stephen and Yusun on whether the Klee-Walkup polytope is circuit-Hirsch tight. This is a first step towards resolving the circuit analogue of the Hirsch conjecture. The wider theoretical here is the polynomial Hirsch conjecture and the existence of strongly polynomial-time algorithms for linear programming. On the practical importance is the possibility of expanding to discrete and nonlinear contexts, where we aim for approximation guarantees or simply good performance on practical problems.
A fundamental class of polyhedra for applications are those that represent MBFs. Here we are interested in joint generation algorithms that enumerate the extreme points of such a polyhedron along with those of its dual function. On the theoretical side, we will identify classes of MBFs that are particularly easy or difficult for the joint generation algorithm. We note that the known examples that are challenging for these algorithms are extremely symmetric, so in work with student S. Islam, we are characterizing the role of symmetry in the algorithms. At the same time, in work with undergraduate P. Salimi, we are employing deep reinforcement learning to find less symmetric challenging examples. A major goal is to determine if an output sensitive polynomial time algorithm exists for MBF generation.
Progress on the theoretical front feeds into further development on the implementation side. We are on the forefront of implementations, including the recent codes developed by N. Sedaghat, which provide optimized versions of the Fredman-Khachiyan algorithm B. We will continue to develop public open-source code for these problems, which have many applications. A particular motivation is the use of MBFs in modelling metabolic networks.
This work helps with the modelling and solution of large-scale problems, and puts trainees in a strong position to contribute. I plan to continue to engage with external partners on their related applications.