Informatica

The quadratic assignment problem (QAP) is one of the well‐known combinatorial optimization problems and is known for its various applications. In this paper, we propose a modified simulated annealing algorithm for the QAP – M‐SA‐QAP. The novelty of the proposed algorithm is an advanced formula of calculation of the initial and final temperatures, as well as an original cooling schedule with oscillation, i.e., periodical decreasing and increasing of the temperature. In addition, in order to improve the results obtained, the simulated annealing algorithm is combined with a tabu search approach based algorithm. We tested our algorithm on a number of instances from the library of the QAP instances – QAPLIB. The results obtained from the experiments show that the proposed algorithm appears to be superior to earlier versions of the simulated annealing for the QAP. The power of M‐SA‐QAP is also corroborated by the fact that the new best known solution was found for the one of the largest QAP instances – THO150.

A multiextremal problem on the synthesis of external circuit of a tunable subnanosecond pulse TRAPATT-generator was investigated using algorithms of local optimization and cluster analysis.

It is well known that, in general, exact algorithms for the Quadratic Assignment Problem (QAP) cannot solve problems of size N>15. Therefore, it is necessary to use heuristic approaches for solving large-scale QAPs. In this paper, we consider a class of heuristic approaches based on local search criteria. In particular, we selected four algorithms; CRAFT, Simulated Annealing, TABU search and the Graph Partitioning (GP) approach and studied their relative performance in terms of the quality of solutions and CPU times. All of these algorithms performed roughly the same, based on the results of two sets of test problems executed on an IBM ES/3090-600S computer.