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.