Network Synthesis Problems
As the telecommunication industry introduces new sophisticated technologies, the nature of services and the volume of demands have changed. Indeed, a broad range of new services for users appear, combining voice, data, graphics, video, etc. This implies n
- PDF / 16,520,420 Bytes
- 218 Pages / 439.37 x 666.142 pts Page_size
- 86 Downloads / 272 Views
COMBINATORIAL OPTIMIZATION VOLUME 8
Through monographs and contributed works the objective of the series is to publish state of the art expository research covering all topics in the field of combinatorial optimization. In addition,
the series will include books which are suitable for graduate level courses in computer science, engineering, business, applied mathematics, and operations research. Combinatorial (or discrete) optimization problems arise in various applications, including communications network design, VLSI design, machine vision, airline crew scheduling, corporate planning, computer-aided design and manufacturing, database query design, cellular telephone frequency assignment, constraint directed reasoning, and computational biology. The topics of the books will cover complexity analysis and algorithm design (parallel and serial), computational experiments and applications in science and engineering. Series Editors:
Ding-Zhu Du, University of Minnesota Panos M. Pardalos, University of Florida Advisory Editorial Board:
Afonso Ferreira, CNRS-UP ENS Lyon Jun Gu, University of Calgary David S. Johnson, AT&T Research James B. Orlin, MI. T. Christos H. Papadimitriou, University of California at Berkeley Fred S. Roberts, Rutgers University Paul Spirakis, Computer Tech Institute (CTI)
The titles published in this series are listed at the end of this volume.
Network Synthesis
Problems
by Christelle Wynants Service de Mathematiques de la Gestion, Institut de Statistique et de Recherche Operationnelle, Universite Libre de Bruxelles, Brussels, Belgium
SPRINGER-SCIENCE+BUSINESS MEDIA, B.V.
A C.I.P. Catalogue record for this book is available from the Library of Congress.
ISBN 978-1-4419-4843-4 ISBN 978-1-4757-3349-5 (eBook) DOI 10.1007/978-1-4757-3349-5
Printed on acid-free paper
AlI Rights Reserved
© 2001 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 2001 Softcover reprint ofthe hardcover Ist edition 2001 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanica1, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner.
Contents
List of Figures
IX
List of Tables
xii xiii
Abstract
xv
Acknowledgments
xvii
Introduction
1. TELECOMMUNICATION CONTEXT AND TERMINOLOGY 2. NETWORK SYNTHESIS PROBLEM
1 11
2.1
Definition
12
2.2
Applications
14
2.3
Formulations
17
2.3.1
Notation
17
2.3.2
Node-arc formulation
18
2.3.3
Edge-path formulation
21
2.3.4
NSSC cutset formulation
23
v
V1
2.4
Previous contributions
3. SINGLE COMMODITY FLOW REQUIREMENTS 3.1
Problem description
25 31 32
3.1.1
Line restoration problem
32
3.1.2
Multi-hour problem with single commodity
34
3.2
Problem complexity
35
3.3
Solutions of a special case
43
3.3.1
Fractional capacities
44
3.3.2
Integral capacities
65
4. MULTICOMMODITY FLOW REQUIREMENTS
83
4.1
Introduction
84
Data Loading...
