Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$26,000.00

Improving integer programming solvers

EF 2018-19

Résumé
Integer Programming (IP) solvers are possibly the most important tool at the disposal of Operations Research practitioners for solving quantitative problems. With this research program, we propose to bring direct improvements to the performance of IP solvers, to help practitioners solve larger problems faster, and obtain better solution within their finite computing resources.*The last 30 years have seen the development of three major commercial solver codes, all supported by successful companies. The source code of these solvers is considered an industry secret, which creates a disconnect between the academic research and the reality faced by Operations Research practitioners. We propose to help the existing open source IP solvers become competitive with the state-of-the-art. This will provide a better framework for the computational validation of theoretical ideas, and will also benefit commercial codes, as new results are published. As a first step, we will contribute a new implementation of the simplex method, a crucial building block in the development an IP solver. Our new simplex code already outperforms all open source implementations, and as a part of this program, we will keep working on performance improvements.*We will also study the generation of sparse cutting planes. IP problems are described by a set of linear constraints, plus integrality constraints on some or all of the variables. Cutting planes (or cuts) are additional inequalities that can be added to a formulation of an IP instance. They cut off part of the search space that solvers need to explore, without removing any integer feasible solution. One undesirable side-effect of cuts is that they make the formulation larger, and the performance of IP solvers is negatively affected by formulations with a high number of nonzero coefficients. We thus propose to focus on sparse cuts, i.e., valid inequalities with few nonzero coefficients. To the best of our knowledge, current solvers simply discard dense cuts instead of actively looking for sparse ones.*Finally, we will tackle the implementation issues that arise when using lattice-based reformulation methods. Reformulation methods are very promising for problems where standard approaches are ineffective, and they have yielded impressive results on specially-structured instances. However, they are currently limited to low-dimensional problems, because the lattice operations become prohibitively slow on large problems. We will study ways to modify lattice algorithms and their implementation so that they can work on large problems by exploiting sparsity.*The impact of Operations Research methods on productivity and efficiency is well-known, and better solvers will benefit a broad range of industries in Canada and abroad. We expect all industries that leverage Operations Research to gain from more efficient processes and faster, more accurate decision making.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2018-04335
Name nom
Poirrier, Laurent
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2018
Competition year année de concours
2018
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 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
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
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
1
Nb partie
5
Application title
Improving integer programming solvers
Keyword
NSERC
Application summary
Integer Programming (IP) solvers are possibly the most important tool at the disposal of Operations Research practitioners for solving quantitative problems. With this research program, we propose to bring direct improvements to the performance of IP solvers, to help practitioners solve larger problems faster, and obtain better solution within their finite computing resources.*The last 30 years have seen the development of three major commercial solver codes, all supported by successful companies. The source code of these solvers is considered an industry secret, which creates a disconnect between the academic research and the reality faced by Operations Research practitioners. We propose to help the existing open source IP solvers become competitive with the state-of-the-art. This will provide a better framework for the computational validation of theoretical ideas, and will also benefit commercial codes, as new results are published. As a first step, we will contribute a new implementation of the simplex method, a crucial building block in the development an IP solver. Our new simplex code already outperforms all open source implementations, and as a part of this program, we will keep working on performance improvements.*We will also study the generation of sparse cutting planes. IP problems are described by a set of linear constraints, plus integrality constraints on some or all of the variables. Cutting planes (or cuts) are additional inequalities that can be added to a formulation of an IP instance. They cut off part of the search space that solvers need to explore, without removing any integer feasible solution. One undesirable side-effect of cuts is that they make the formulation larger, and the performance of IP solvers is negatively affected by formulations with a high number of nonzero coefficients. We thus propose to focus on sparse cuts, i.e., valid inequalities with few nonzero coefficients. To the best of our knowledge, current solvers simply discard dense cuts instead of actively looking for sparse ones.*Finally, we will tackle the implementation issues that arise when using lattice-based reformulation methods. Reformulation methods are very promising for problems where standard approaches are ineffective, and they have yielded impressive results on specially-structured instances. However, they are currently limited to low-dimensional problems, because the lattice operations become prohibitively slow on large problems. We will study ways to modify lattice algorithms and their implementation so that they can work on large problems by exploiting sparsity.*The impact of Operations Research methods on productivity and efficiency is well-known, and better solvers will benefit a broad range of industries in Canada and abroad. We expect all industries that leverage Operations Research to gain from more efficient processes and faster, more accurate decision making.