CNOP
A Package for Constrained Network Optimization

Constrained Shortest Paths

and Related Problems. Constrained Network Optimization  

Mark Ziegelmann

This volume is available at

www.amazon.com

and

 www.amazon.de

and at selected bookstores

59.00 € / 76.00 $

ISBN-10: 3836446332

Constrained Shortest Paths

and Related Problems. Constrained Network Optimization  

Mark Ziegelmann

This volume is available at

www.amazon.com

and

 www.amazon.de

and at selected bookstores

59.00 € / 76.00 $

ISBN-10: 3836446332

We present a generic package for resource constrained network optimization problems. We illustrate the flexibility and the use of our package by solving four applications: route planning, curve approximation, minimum cost reliability constrained spanning trees and the table layout problem.
There are a large number of graph and network algorithms that can be efficiently solved in polynomial time, like the shortest path problem, minimum spanning tree problem or flow problems. However, adding a single side constraint involving another cost function to these problems usually makes the problem NP-hard (see Garey and Johnson). Since many practical applications can be modeled using resource constraints, it is of great interest to nevertheless solve the problem efficiently. We studied the constrained shortest path problem which is to find a path of minimal cost satisfiying additional resource constraint(s). We extended previous methods of Handler and Zang and Beasley and Christofides that solve the problem by first solving a Lagrangean relaxation and then closing the gap by path ranking. In our experiments we found that the method is efficient and clearly superior to ILP solving, naive path ranking and dynamic programming. It was also highly competitive to labeling methods. The same approach as in constrained shortest paths also applies to other network optimization problems with resource constraints: first solving a Lagrangean relaxation and then ranking solutions. Since the problem is of great practical interest in operations research we decided to develop a general package that provides efficient algorithms for specific problems and is easily adapted to other problems.

Here are some snapshots of our demos.

• Route Planning

• Curve Approximation

• Constrained geodesic shortest paths

• Minimum Cost Reliability Constrained Spanning Trees

• Table Layout Problem

• M. Ziegelmann
      Constrained Shortest Paths and Related Problems: Constrained Network Optimization
      VDM-Verlag, 2007. (to see the introduction of this book click here)

• Download data and the CNOP package for the constrained shortest path problem

• K. Mehlhorn, M. Ziegelmann
      CNOP - A package for constrained network optimization
      3rd Workshop on Algorithm Engineering and Experiments (ALENEX01)
      LNCS 2153 Springer, Berlin 2001, pp. 17-31.

• K. Mehlhorn, M. Ziegelmann
      Resource Constrained Shortest Paths
      Proc. 8th European Symposium on Algorithms (ESA2000)
      LNCS 1879 Springer, Berlin 2000, pp. 326-337.

The code is tested for gcc, LEDA 5.2, DD-Geokernel 2.5 and CPLEX 6.5 (for slightly limited functionality only LEDA is required) under Solaris and Linux. The KAI C compiler and the SUN Pro C compiler is also supported under Solaris.

The download is free for non-commercial use. For commercial use contact Algorithmic Solutions.

Questions, comments and bugs report to mark.ziegelmanngmx.de