Combining Memetic Algorithms and Branch & Cut & Price for Some Network Design Problems

01.06.2003 - 30.01.2006
Research funding project
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.

People

Project leader

Project personnel

Institute

Grant funds

  • FWF - Österr. Wissenschaftsfonds (National) Austrian Science Fund (FWF)

Keywords

GermanEnglish
Kombinatorische Optimierungcombinatorial optimization
Netzwerk-Designnetwork design
Metaheuristikenmeta heuristics
Ganzzahlige lineare Programmierunginteger linear programming

Publications