Алгоритм, основанный на методе ветвей и границ

 Во многих случаях исходные данные задачи размещения задаются в виде расширенной матрицы цепей схемы РЭА, расположения вертикальных и горизонтальных каналов в монтажном пространстве с числами магистралей в них (магистраль представляет собой часть канала). В качестве критерия берется минимум числа внутрисхемных пересечений.

 Расширенная матрица цепей

C =

имеет n строк (по числу элементов) и в общем случае 2d х 2r столбцов, где d — число контактов верхней (нижней) части элемента; r — число магистралей вертикального канала для соединения от верхних и нижних контактов.

По матрице С_ц рассчитывается вспомогательная матрица пересечений

P = _kxk

где k — число цепей; р_ij — число пересечений между фрагментами цепей с_iи c_j расположенными в одном канале, причем фрагмент цепи с_і расположен под фрагментом c_j. Если фрагмент цепи с_i не может быть расположен ниже с_j,

то p_ij= .