Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$33,000.00
Semidefinite programming-based approaches for hard combinatorial optimization problems in engineering: modelling, algorithms and applications
FY 2012-13
Summary
Combinatorial 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, are designed using macro-cell design techniques, and some chip design problems of macro-cell design can be modelled as facility layout problems. Because of the inherent complexity of these circuits, the design process is extremely time-consuming, hence the development of new algorithms to improve the efficiency of computer-automated design processes is of paramount importance. Furthermore, better algorithms for these problems are likely to lead to improved placements for the circuit components.
Semidefinite programming is a new mathematical technique involving optimization over matrices. A large body of research in the last 15 years has shown that it yields significantly improved theoretical and practical algorithms for some classes of hard problems involving very large numbers of possibilities. The main objective of the proposed research is to explore the application of semidefinite programming to hard engineering optimization problems of a combinatorial nature in order to find not only good solutions,but also tight bounds on the objective value of the unknown global optimal solution, which are essential to estimate the quality of the solutions found. These ingredients are the key to developing more efficient algorithms for solving these hard problems. The ultimate goal of this research is an efficient semidefinite programming-based set of algorithms integrated as a self-contained software package that provides excellent solutions for a large class of hard combinatorial problems as well as a guarantee of global optimality, or near optimality, for those solutions.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
312125-2010
Name nom
Anjos, Miguel
Department département
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
2012
Competition year année de concours
2010
Award amount
33000
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
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
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
Semidefinite programming-based approaches for hard combinatorial optimization problems in engineering: modelling, algorithms and applications
Keyword
NSERC
Application summary
Combinatorial 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, are designed using macro-cell design techniques, and some chip design problems of macro-cell design can be modelled as facility layout problems. Because of the inherent complexity of these circuits, the design process is extremely time-consuming, hence the development of new algorithms to improve the efficiency of computer-automated design processes is of paramount importance. Furthermore, better algorithms for these problems are likely to lead to improved placements for the circuit components.
Semidefinite programming is a new mathematical technique involving optimization over matrices. A large body of research in the last 15 years has shown that it yields significantly improved theoretical and practical algorithms for some classes of hard problems involving very large numbers of possibilities. The main objective of the proposed research is to explore the application of semidefinite programming to hard engineering optimization problems of a combinatorial nature in order to find not only good solutions,but also tight bounds on the objective value of the unknown global optimal solution, which are essential to estimate the quality of the solutions found. These ingredients are the key to developing more efficient algorithms for solving these hard problems. The ultimate goal of this research is an efficient semidefinite programming-based set of algorithms integrated as a self-contained software package that provides excellent solutions for a large class of hard combinatorial problems as well as a guarantee of global optimality, or near optimality, for those solutions.