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