Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

McGill University

$35,000.00

Polyhedral computation and quantum information

EF 2013-14

Résumé
I am proposing to work on polyhedral computation, and in particular, its applications in quantum information and discrete optimization.Quantum Information.In collaboration with researchers at ERATO and the University of Tokyo, we have made extensive advances in recent years in understanding Bell inequalities and, to a much lesser extent, quantum correlations. Our future goals are to provide efficient procedures (where possible) to compute maximum violations of Bell inequalities and to provide feasible quantum setups that give such violations. These setups are natural candidates for exploiting optimally the additional power given by quantum information processing. Discrete Optimization.We are currently studying discrete optimization problems related to mining optimization, in particular the solution to the so-called ""optimum pit"" problem with additional knapsack like constraints. We are adopting a polyhedral approach, which eventually should yield strong cutting planes that can be used in a branch and cut solution (these problems are NP-hard). We will also study LP and semidefinite approximations. The related polyhedra are directed analogues of the well studied cut and semimetric polytopes.Polyhedral Computation.I will continue the development of the lrs library. This freely distributed and widely used code employs the reverse search technique and exact arithmetic to compute the vertices or facets of high dimensional polyhedra and related problems in polyhedral computation. New theoretical advances will be needed to improve the performance of the code on highly symmetric and highly degenerate combinatorial polytopes. Recent additions to the package includes a program to compute Nash Equilibria by means of two nested reverse searches on related polyhedra.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
3013-2009
Name nom
Avis, David
Department département
Computer Science, School of
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2013
Competition year année de concours
2009
Award amount
35000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
802
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 systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
5
Nb partie
5
Application title
Polyhedral computation and quantum information
Keyword
NSERC
Application summary
I am proposing to work on polyhedral computation, and in particular, its applications in quantum information and discrete optimization.Quantum Information.In collaboration with researchers at ERATO and the University of Tokyo, we have made extensive advances in recent years in understanding Bell inequalities and, to a much lesser extent, quantum correlations. Our future goals are to provide efficient procedures (where possible) to compute maximum violations of Bell inequalities and to provide feasible quantum setups that give such violations. These setups are natural candidates for exploiting optimally the additional power given by quantum information processing. Discrete Optimization.We are currently studying discrete optimization problems related to mining optimization, in particular the solution to the so-called ""optimum pit"" problem with additional knapsack like constraints. We are adopting a polyhedral approach, which eventually should yield strong cutting planes that can be used in a branch and cut solution (these problems are NP-hard). We will also study LP and semidefinite approximations. The related polyhedra are directed analogues of the well studied cut and semimetric polytopes.Polyhedral Computation.I will continue the development of the lrs library. This freely distributed and widely used code employs the reverse search technique and exact arithmetic to compute the vertices or facets of high dimensional polyhedra and related problems in polyhedral computation. New theoretical advances will be needed to improve the performance of the code on highly symmetric and highly degenerate combinatorial polytopes. Recent additions to the package includes a program to compute Nash Equilibria by means of two nested reverse searches on related polyhedra.