Semidefinite programming-based approaches for hard combinatorial optimization problems in engineering: modelling, algorithms and applications

组合优化问题出现在各种各样的现实生活中的应用。例如，设计工厂的人必须决定如何放置不同尺寸的各种机器，以便工厂尽可能平稳地运行。这个问题被称为设施布局问题，并且由于机器的可能布置的数量非常大而非常困难。更一般地，布局问题产生于工程中的各种应用。例如，使用宏单元设计技术来设计诸如在移动的电话中使用的复杂电子电路，并且宏单元设计的一些芯片设计问题可以被建模为设施布局问题。由于这些电路固有的复杂性，设计过程非常耗时，因此开发新的算法来提高计算机自动化设计过程的效率是至关重要的。此外，这些问题的更好的算法可能会导致电路元件的改进布局。

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.