Groupe d’études et de recherche en analyse des décisions

G-2007-11

A Column Generation Approach for Design of Networks using Path-Protecting p -Cycles

, , et

We investigate a first column generation (CG) formulation for the design of failure independent path-protecting (FIPP) p -cycle survivable transport network. Previous work has proposed different formulations and heuristics for FIPP p -cycles which extend span-protecting p -cycles by adding the property of providing end-to-end failure independent path switching against either span or node failures. We develop a CG model that additionally allows the exploration of FIPP p -cycles without imposing mutual disjointness among working routes protected by the same cycle. The proposed CG model decomposes the FIPP p -cycle design problem into the master problem which takes care of the demand constraints, and the pricing problem which includes the constraints associated with the properties and the characteristics of a FIPP p -cycle. The key feature of a CG model lies in a generation of cycles motivated by the value of the reduced cost of the pricing problem, the key global indicator that is the driving element of the simplex algorithm. Results show a clear advantage of the CG model over the previous models, in particular in exploiting cycles that are not restricted to those satisfying a mutual disjointness condition on the working paths. Although it is not always possible to guarantee that the solutions obtained with the CG model are optimal, it can be shown that they are very close to the optimal ones.

, 24 pages