Conic Optimization Approaches for Hard Discrete Problems in Engineering

点击翻译按钮获取中文摘要

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.**