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 $
ISBN10: 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 $
ISBN10: 3836446332

Abstract.
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 NPhard (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.
The code is tested for gcc,
LEDA 5.2,
DDGeokernel
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 noncommercial use. For commercial use contact Algorithmic Solutions.
Questions, comments and bugs report to
mark.ziegelmanngmx.de
