Conic Optimization Approaches for Hard Discrete Problems in Engineering

离散优化问题在现实生活中的应用非常广泛。例如，设计工厂的人必须决定如何放置不同大小的机器，以便工厂尽可能平稳地运行。这个问题被称为设施布局问题，因为机器的可能布置数量非常多，所以出了名的难。更广泛地说，布局问题出现在工程中的各种应用中。例如，复杂的电子电路，如移动电话中使用的电路，也可以建模为设施布局问题。*此外，电路的复杂性使得有必要将各种部件分组到高度连接的子电路中，这些子电路可以被视为初始布局设计的单个元素。这种组件分组可以使用一种称为图分区的技术来建模。图划分也可以应用于为移动电话分配频率以最小化干扰的问题。由于这些问题的内在复杂性，开发新的和更有效的算法至关重要。*本研究的目的是设计基本模型和算法来高效地计算工程应用中产生的一类困难离散问题的高质量解。该方案支持的工作将集中在挖掘二次曲线优化的优势上。圆锥优化是一种涉及矩阵优化的数学方法。过去20年的大量研究表明，对于涉及大量可能性的问题，它产生了显着改进的算法。这项研究将为新软件帮助解决大规模设施布局和图形划分问题奠定基础。**

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