Combining Memetic Algorithms with Branch & Cut & Price

We consider several combinatorial network design problems which represent important challenges in industrial fields like telecommunication, energy provision, or district heating. The common goal in these problems is to find a cheapest possible set of links between nodes for establishing a network that fulfills certain constraints. For example in the degree-constrained minimum spanning tree problem, the number of links that may be attached to each node is limited and the network must have tree structure and span all nodes. In another problem, communication demands between nodes are given and links have maximum capacities that may not be exceeded. We also consider problems in which an existing network must be augmented by additional links in order to become robust against failures of single nodes or edges. All these problems are NP-hard, which means in practice that large instances usually cannot be solved to provable optimality. To attack such problems by means of computers, two particularly effective streams of approaches have emerged in the past. On the one side, exact techniques based on branch-and-bound and linear programming exist. For easier or not too large problem instances, such techniques are often able to yield provably optimal solutions. Branch-and- cut-and-price (BCP) is one of the most effective algorithms of this category with respect to our network design problems. On the other side, evolutionary algorithms combined with problem-specific heuristics, local search, and specialized operators -- so-called memetic algorithms (MAs) -- have shown to be often well suited for relatively quickly finding high-quality solutions to large and difficult instances as well. In this project, we continue the development of effective MAs and BCP algorithms for the considered network design problems. In addition, we investigate several approaches of combining "the best of the two worlds". By exchanging good solutions and other valuable information, both approaches can benefit much. Synergetic effects make the combined MA/BCP-approach more effective than each single method.

The project considered several combinatorial network design problems which represent important challenges in industrial fields like telecommunication, energy provision, and district heating. The common basic goal in these problems is to find a cheapest possible set of links between nodes for establishing a network that fulfills specific requirements. Furthermore, difficult problems from the area of two-dimensional cutting and packing and a scheduling problem coming from automobile manufacturing have also been considered. All these problems are known to be NP-hard, i.e., it is usually very difficult to practically solve large instances in reasonable computation time. To attack such problems by means of computers, two particularly effective streams of approaches have emerged in the past. On the one side, exact techniques based on branch-and-bound and linear programming exist. For easier or not too large problem instances, such techniques are often able to yield provably optimal solutions. Branch-and-cut, branch-and-price, and branch-and-cut-and-price (BCP) are among the most effective algorithms of this category with respect to the combinatorial optimization problems we considered. On the other side, metaheuristics, in particular evolutionary algorithms combined with problem-specific heuristics, local search, and specialized operators so-called memetic algorithms (MAs) have shown to be often well suited for relatively quickly finding high-quality solutions to large and difficult instances of such problems as well. In this project, we successfully continued the development of effective MAs and BCP algorithms for the considered optimization problems. In addition, we investigated several approaches of combining "the best of the two worlds". Our results document that synergetic effects make such combined MA/BCP-approaches often much more effective than each single method alone. These combinations can roughly be categorized into collaborative and integrative methods. Collaborative approaches can be of sequential or parallel nature, while in integrative methods BCP may be a subordinate of the MA or vice versa. The developed algorithms have on one side been specialized for the considered problems in order to get the best possible results, but on the other side, the basic principles are more generic and can also be applied to many other hard combinatorial optimization problems.