Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Simon Fraser University

$11,000.00

Pivoting Algorithms and Geometric Optimization Problems

EF 2014-15

Résumé
The main theme for this proposal is pivoting algorithms for discrete optimization. The fundamental objects studied are the diameter of polyhedra and colourful linear programming. The most important geometric optimization problem is linear programming. A linear program (LP) requires to minimize (or maximize) a linear function c^t x over a d-dimensional polyhedron P={Ax <= b}, i.e. the intersection of n half-spaces in R^d. A polyhedron contains finitely many 0- and 1-dimensional faces called vertices and edges. These form a simple graph, called the graph of P, and denoted G_P. The simplex method solves LPs by pivoting along edges through the vertices of G_P. It is very widely used and extremely effective in practice, but its theoretical performance is poorly understood. Pivoting algorithms require at least as many pivots as the diameter of G_P, however it is not even known if this diameter must be polynomial in the input (effectively, in n and d). There is substantial recent progress on this question, highlighted by Santos' counter-example to Hirsch's 1957 conjecture that the diameter is bounded by n-d. However, the key open question, the ""polynomial Hirsch conjecture"", of whether there is a polynomial upper bound in n and d, remains open. We are interested in various approaches to this problem. An appealing starting point is the recent work of Bonifas et al., who track the volume of normal cones seen at the vertices in a depth-first exploration of G_P. This gives an improved polynomial upper bound for polytopes when the incidence matrix A is totally unimodular. The volume estimates depend critically on the integrality of A. We propose to begin by examining whether their approach can be modified to work if, for instance, we bound the condition numbers of submatrices of A rather than the determinants. More ambitiously, we can try to produce an amortized version of their volume expansion lemma, which could then reduce the dependence on A, at least under suitable conditions. An interesting combinatorial generalization of LP is known as Colourful Linear Programming (CLP). As is well known, LP feasibility can be reduced to a problem of finding a feasible basis, i.e. a set of (d+1) points in R^d whose convex hull contains a point p. In the CLP, points in R^d are given as input data, and are also partitioned into (d+1) colours. The objective is to find a set of (d+1) points, one of each colour, which contains p in its convex hull. Such a set exists, but finding it efficiently is a challenging problem whose tractability is not yet understood. Like LP, this question is naturally approached by geometric pivoting algorithms. Barany and Onn studied two beautiful algorithms for solving the problem, each polynomial in the input and 1/r, where r is the radius of a ball centred at p and contained in the convex hull of each colour. The first of these algorithms relies on repeatedly computing the point of minimum norm on the current simplex, while the second is combinatorial. In previous work, we showed exponential behaviour of the combinatorial algorithm by constructing a family of examples with rapidly decreasing values of r. However the norm-minimization version of the algorithm seems quite robust. A preliminary goal is to get a tight analysis of this algorithm - either show that it is genuinely polynomial, or, more likely, to get a family of examples that clearly shows exponential behaviour. We will further consider whether norm minimization on a simplex can be done in polynomial time using a combinatorial algorithm. This would allow us to implement the robust algorithm using exact arithmetic, and speed up the computation in practice. Finally, we consider questions related to monotone Boolean functions.
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2014-06371
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
2014
Competition year année de concours
2014
Award amount
11000
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
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
1
Nb partie
5
Application title
Pivoting Algorithms and Geometric Optimization Problems
Keyword
NSERC
Application summary
The main theme for this proposal is pivoting algorithms for discrete optimization. The fundamental objects studied are the diameter of polyhedra and colourful linear programming. The most important geometric optimization problem is linear programming. A linear program (LP) requires to minimize (or maximize) a linear function c^t x over a d-dimensional polyhedron P={Ax <= b}, i.e. the intersection of n half-spaces in R^d. A polyhedron contains finitely many 0- and 1-dimensional faces called vertices and edges. These form a simple graph, called the graph of P, and denoted G_P. The simplex method solves LPs by pivoting along edges through the vertices of G_P. It is very widely used and extremely effective in practice, but its theoretical performance is poorly understood. Pivoting algorithms require at least as many pivots as the diameter of G_P, however it is not even known if this diameter must be polynomial in the input (effectively, in n and d). There is substantial recent progress on this question, highlighted by Santos' counter-example to Hirsch's 1957 conjecture that the diameter is bounded by n-d. However, the key open question, the ""polynomial Hirsch conjecture"", of whether there is a polynomial upper bound in n and d, remains open. We are interested in various approaches to this problem. An appealing starting point is the recent work of Bonifas et al., who track the volume of normal cones seen at the vertices in a depth-first exploration of G_P. This gives an improved polynomial upper bound for polytopes when the incidence matrix A is totally unimodular. The volume estimates depend critically on the integrality of A. We propose to begin by examining whether their approach can be modified to work if, for instance, we bound the condition numbers of submatrices of A rather than the determinants. More ambitiously, we can try to produce an amortized version of their volume expansion lemma, which could then reduce the dependence on A, at least under suitable conditions. An interesting combinatorial generalization of LP is known as Colourful Linear Programming (CLP). As is well known, LP feasibility can be reduced to a problem of finding a feasible basis, i.e. a set of (d+1) points in R^d whose convex hull contains a point p. In the CLP, points in R^d are given as input data, and are also partitioned into (d+1) colours. The objective is to find a set of (d+1) points, one of each colour, which contains p in its convex hull. Such a set exists, but finding it efficiently is a challenging problem whose tractability is not yet understood. Like LP, this question is naturally approached by geometric pivoting algorithms. Barany and Onn studied two beautiful algorithms for solving the problem, each polynomial in the input and 1/r, where r is the radius of a ball centred at p and contained in the convex hull of each colour. The first of these algorithms relies on repeatedly computing the point of minimum norm on the current simplex, while the second is combinatorial. In previous work, we showed exponential behaviour of the combinatorial algorithm by constructing a family of examples with rapidly decreasing values of r. However the norm-minimization version of the algorithm seems quite robust. A preliminary goal is to get a tight analysis of this algorithm - either show that it is genuinely polynomial, or, more likely, to get a family of examples that clearly shows exponential behaviour. We will further consider whether norm minimization on a simplex can be done in polynomial time using a combinatorial algorithm. This would allow us to implement the robust algorithm using exact arithmetic, and speed up the computation in practice. Finally, we consider questions related to monotone Boolean functions.