The shortest path problem arises in various applied settings where some material (e.g., computer data packet, telephone calls, vehicles) is sent between two specified points in a network as quickly, cheaply or reliably as possible. In practice we want to optimize a combination of those criteria (i.e., we have a bi- or multicriteria shortest path problem). This book proposes a 2-step method for the constrained shortest path problem. A relaxation is solved to get upper and lower bounds and then the gap is closed with clever path ranking to obtain the exact solution. Different old and new methods are compared both theoretically and experimentally. The proposed 2-step method also works for a more general class of constrained network optimization problems. In addition the generic approach is illustrated with several examples and a newly developed Constrained Network Optimization Software Package (CNOP) is introduced that provides this generic 2-step approach as well as all state of the art algorithms for constrained shortest paths. This book is a valuable resource for researchers, students as well as practitioners working on the constrained shortest path problem and related problems.

Column Generation is an insightful overview of the state of the art in integer programming column generation and its many applications. The volume begins with "A Primer in Column Generation" which outlines the theory and ideas necessary to solve large-scale practical problems, illustrated with a variety of examples. Other chapters follow this introduction on "Shortest Path Problems with Resource Constraints," "Vehicle Routing Problem with Time Window," "Branch-and-Price Heuristics," "Cutting Stock Problems," each dealing with methodological aspects of the field. Three chapters deal with transportation applications: "Large-scale Models in the Airline Industry," "Robust Inventory Ship Routing by Column Generation," and "Ship Scheduling with Recurring Visits and Visit Separation Requirements." Production is the focus of another three chapters: "Combining Column Generation and Lagrangian Relaxation," "Dantzig-Wolfe Decomposition for Job Shop Scheduling," and "Applying Column Generation to Machine Scheduling." The final chapter by François Vanderbeck, "Implementing Mixed Integer Column Generation," reviews how to set-up the Dantzig-Wolfe reformulation, adapt standard MIP techniques to the column generation context (branching, preprocessing, primal heuristics), and deal with specific column generation issues (initialization, stabilization, column management strategies).

This book constitutes the refereed proceedings of the 8th Annual European Symposium on Algorithms, ESA 2000, held in Saarbrcken, Germany in September 2000. The 39 revised full papers presented together with two invited papers were carefully reviewed and selected for inclusion in the book. Among the topics addressed are parallelism, distributed systems, approximation, combinatorial optimization, computational biology, computational geometry, external-memory algorithms, graph algorithms, network algorithms, online algorithms, data compression, symbolic computation, pattern matching, and randomized algorithms.

In this thesis, we use integer programming techniques to solve the resource constrained shortest path problem (RCSPP) which seeks a minimum cost path between two nodes in a directed graph subject to a finite set of resource constraints. Although NP-hard, the RCSPP is extremely useful in practice and often appears as a subproblem in many decomposition schemes for difficult optimization problems.

Finding a shortest path is one of the most well-studied optimization problems. In this thesis we focus on shortest paths in geometric and graph theoretic settings subject to different feasibility constraints that arise in practical applications of such paths. One of the most fundamental problems in computational geometry is finding shortest paths in terrains, which has many applications in robotics, computer graphics and Geographic Information Systems (GISs). There are many variants of the problem in which the feasibility of a path is determined by some geometric property of the terrain. One such variant is the shortest descending path (SDP) problem, where the feasible paths are those that always go downhill. We need to compute an SDP, for example, for laying a canal of minimum length from the source of water at the top of a mountain to fields for irrigation purpose, and for skiing down a mountain along a shortest route. The complexity of finding SDPs is open. We give a full characterization of the bend angles of an SDP, showing that they follow a generalized form of Snell's law of refraction of light. We also reduce the SDP problem to the problem of finding an SDP through a given sequence of faces, by adapting the sequence tree approach of Chen and Han for our problem. Our results have two implications. First, we isolate the difficult aspect of SDPs. The difficulty is not in deciding which face sequence to use, but in finding the SDP through a given face sequence. Secondly, our results help us identify some classes of terrains for which the SDP problem is solvable in polynomial time. We give algorithms for two such classes. The difficulty of finding an exact SDP motivates the study of approximation algorithms for the problem. We devise two approximation algorithms for SDPs in general terrains---these are the first two algorithms to handle the SDP problem in such terrains. The algorithms are robust and easy-to-implement. We also give two approximation algorithms for the case when a face sequence is given. The first one solves the problem by formulating it as a convex optimization problem. The second one uses binary search together with our characterization of the bend angles of an SDP to locate an approximate path. We introduce a generalization of the SDP problem, called the shortest gently descending path (SGDP) problem, where a path descends but not too steeply. The additional constraint to disallow a very steep descent makes the paths more realistic in practice. For example, a vehicle cannot follow a too steep descent---this is why a mountain road has hairpin bends. We give two easy-to-implement approximation algorithms for SGDPs, both using the Steiner point approach. Between a pair of points there can be many SGDPs with different number of bends. In practice an SGDP with fewer bends or smaller total turn-angle is preferred. We show using a reduction from 3-SAT that finding an SGDP with a limited number of bends or a limited total turn-angle is hard. The hardness result applies to a generalization of the SGDP problem called the shortest anisotropic path problem, which is a well-studied computational geometry problem with many practical applications (e.g., robot motion planning), yet of unknown complexity.

This book offers advanced parallel and distributed algorithms and experimental laboratory prototypes of unconventional shortest path solvers. In addition, it presents novel and unique algorithms of solving shortest problems in massively parallel cellular automaton machines. The shortest path problem is a fundamental and classical problem in graph theory and computer science and is frequently applied in the contexts of transport and logistics, telecommunication networks, virtual reality and gaming, geometry, and social networks analysis. Software implementations include distance-vector algorithms for distributed path computation in dynamics networks, parallel solutions of the constrained shortest path problem, and application of the shortest path solutions in gathering robotic swarms. Massively parallel algorithms utilise cellular automata, where a shortest path is computed either via matrix multiplication in automaton arrays, or via the representation of data graphs in automaton lattices and using the propagation of wave-like patterns. Unconventional shortest path solvers are presented in computer models of foraging behaviour and protoplasmic network optimisation by the slime mould Physarum polycephalum and fluidic devices, while experimental laboratory prototypes of path solvers using chemical media, flows and droplets, and electrical current are also highlighted. The book will be a pleasure to explore for readers from all walks of life, from undergraduate students to university professors, from mathematicians, computers scientists and engineers to chemists and biologists.