Generalized network design problems. Modeling and optimization. (Q455036)

In this monograph, several basic network design problems (such as the minimum spanning tree problem or the traveling salesman problem) are generalized in the following way. Let \(G=(V,E)\) be an undirected graph with vertex set \(V\) and edge set \(E\), where the vertices are partitioned into pairwise disjoint clusters \(V_1, V_2, \dots ,V_k\) and each edge \(e\in E\) has associated a nonnegative cost \(c_e\). The aim is to find a subgraph \(G'=(V',E')\) of \(G\) which contains exactly one vertex from each cluster such that \(G'\) has a prescribed property depending on the actual problem (e.g. \(G'\) is required to be a tree or a cycle) and the total edge cost of \(G'\) is minimized. The generalized problems are NP-hard. In the special case when each cluster is a singleton one gets the basic problem. From the contents: 1. Introduction (combinatorial optimization and integer programming, complexity theory, heuristic and relaxation methods, generalized network design problems); 2. Generalized minimum spanning tree problem (GMSTP) (mathematical models, approximation results, solving the GMSTP); 3. Generalized traveling salesman problem (GTSP) (an efficient transformation, an exact algorithm, solving the GTSP, the drilling problem); 4. Railway traveling salesman problem (RTSP) (methods for solving the RTSP, dynamic RTSP); 5. Generalized vehicle routing problem (GVRP) (complexity, an efficient transformation to a capacitated arc routing problem, integer linear programming formulations, solving the GVRP); 6. Generalized fixed-charge network design problem (GFCNDP) (integer programming formulations, solving the GFCNDP); 7. Generalized minimum edge-biconnected network problem (GMEBCNP) (complexity, a mixed integer programming model of the GMEBCNP, solving the GMEBCNP). Methods for solving the problems are accompanied by computational results. Each chapter can be read separately because it is relatively self-contained. The book ends with the bibliography consisting of more than 200 items and an index. The author succeeds in his goal cited in the preface: ``The express purpose of this book is to describe, in a unified manner, a series of mathematical models, methods, propositions and algorithms arising from generalized design problems, developed in the last years. This book will be useful for researchers, practitioners, and graduate students in the fields of operations research, optimization, applied mathematics and computer science. Due to the substantial practical importance of some presented problems, researchers in other areas will also find this book useful.''