Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$28,000.00
Conic Optimization Approaches for Hard Discrete Problems in Engineering
FY 2017-18
Summary
Discrete optimization problems occur in a wide variety of real-life applications. For example, the person designing a factory must decide how to place the various machines of different sizes so that the factory will operate as smoothly as possible. This problem is known as the facility layout problem and is notoriously difficult because of the very large number of possible arrangements for the machines. More generally, layout problems arise from a variety of applications in engineering. For instance, complex electronic circuits, such as those used in mobile telephones, can also be modelled as facility layout problems. Moreover, the complexity of the circuits makes it necessary to group the various components into highly connected subcircuits that can be treated as a single element for the initial layout design. This grouping of components can be modelled using a technique called graph partitioning. Graph partitioning can also be applied to the problem of assigning frequencies to mobile telephones to minimize interference. Because of the inherent complexity of these problems, the development of new and more efficient algorithms is of paramount importance. The purpose of this research is to devise fundamental models and algorithms to efficiently compute high-quality solutions for classes of hard discrete problems arising from engineering applications. The work supported by this proposal will focus on exploiting the strength of conic optimization. Conic optimization is a mathematical technique involving optimization over matrices. A large body of research in the last 20 years has shown that it yields significantly improved algorithms for problems involving very large numbers of possibilities. This research will establish the foundations for new software to help solve large-scale facility layout and graph partitioning problems.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2015-05183
Name nom
Anjos, Miguel
Department département
Mathématiques et génie industriel - Mathématiques et génie industriel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2015
Award amount
28000
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
500
Area of application group en
Manufacturing processes and products
Area of application group fr
Procédés et produits industriels
Area of application en
Manufacturing processes and products
Area of application fr
Procédés et produits industriels
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
3
Nb partie
5
Application title
Conic Optimization Approaches for Hard Discrete Problems in Engineering
Keyword
NSERC
Application summary
Discrete optimization problems occur in a wide variety of real-life applications. For example, the person designing a factory must decide how to place the various machines of different sizes so that the factory will operate as smoothly as possible. This problem is known as the facility layout problem and is notoriously difficult because of the very large number of possible arrangements for the machines. More generally, layout problems arise from a variety of applications in engineering. For instance, complex electronic circuits, such as those used in mobile telephones, can also be modelled as facility layout problems. Moreover, the complexity of the circuits makes it necessary to group the various components into highly connected subcircuits that can be treated as a single element for the initial layout design. This grouping of components can be modelled using a technique called graph partitioning. Graph partitioning can also be applied to the problem of assigning frequencies to mobile telephones to minimize interference. Because of the inherent complexity of these problems, the development of new and more efficient algorithms is of paramount importance. The purpose of this research is to devise fundamental models and algorithms to efficiently compute high-quality solutions for classes of hard discrete problems arising from engineering applications. The work supported by this proposal will focus on exploiting the strength of conic optimization. Conic optimization is a mathematical technique involving optimization over matrices. A large body of research in the last 20 years has shown that it yields significantly improved algorithms for problems involving very large numbers of possibilities. This research will establish the foundations for new software to help solve large-scale facility layout and graph partitioning problems.