6533b837fe1ef96bd12a25c7

RESEARCH PRODUCT

Adaptive memory programming for the dynamic bipartite drawing problem

subject

description

Abstract The bipartite drawing problem is a well-known NP-hard combinatorial optimization problem with numerous applications. The aim is to minimize the number of edge crossings in a two-layer graph, in which the edges are drawn as straight lines. We consider the dynamic variant of this problem, called the dynamic bipartite drawing problem (DBDP), which consists of adding (resp. or removing) vertices and edges to (resp. or from) a given bipartite drawing, thereby obtaining a new drawing with a layout similar to that of the original drawing. To solve this problem, we propose a tabu search method that incorporates adaptive memory to search the solution space efficiently. In this study, we compare the explicit memory in the proposed method, which is called iterated solution-based tabu search (ISB-TS), with that in the previous best method on the basis of attributive memory, thereby comparing these two memory implementations. Extensive computational experiments on two sets of more than 1000 problem instances indicate that the proposed ISB-TS is highly competitive in comparison with existing methods. Key components of the approach are analyzed to evaluate their effect on the proposed algorithm and determine which search mechanisms are better suited for this type of problems.