Lecture Notes in Computer Science 6701 - Springer

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Alfred Kobsa University of California, Irvine, CA, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen TU Dortmund University, Germany Madhu Sudan Microsoft Research, Cambridge, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max Planck Institute for Informatics, Saarbruecken, Germany

6701

Julia Pahl Torsten Reiners Stefan Voß (Eds.)

Network Optimization 5th International Conference, INOC 2011 Hamburg, Germany, June 13-16, 2011 Proceedings

13

Volume Editors Julia Pahl Stefan Voß Torsten Reiners University of Hamburg Institute of Information Systems Von-Melle-Park 5, 20146 Hamburg, Germany E-mail: {pahl, reiners}@econ.uni-hamburg.de, [email protected] Torsten Reiners Curtin University School of Information Systems Perth, WA 6845, Australia E-mail: [email protected]

ISSN 0302-9743 e-ISSN 1611-3349 ISBN 978-3-642-21526-1 e-ISBN 978-3-642-21527-8 DOI 10.1007/978-3-642-21527-8 Springer Heidelberg Dordrecht London New York Library of Congress Control Number: 2011928709 CR Subject Classification (1998): C.2, D.4.4, E.1, F.2.2, G.2.2, H.3.5, H.4.3 LNCS Sublibrary: SL 5 – Computer Communication Networks and Telecommunications

© Springer-Verlag Berlin Heidelberg 2011 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)

Preface

The International Network Optimization Conference (INOC) is the conference of the European Network Optimization Group (ENOG) which aims at regularly bringing together experts from different disciplines especially from operations research, graph theory, queuing theory and stochastic search with the main focus on network optimization. The conference is intended to be a forum for researchers and practitioners working in the area of network optimization. Certainly networks may be seen in the widest possible sense. Telecommunication networks on the physical as well as the logical layer have been the focus of INOC-related research from the very beginning. This relates to network design problems, (multi-commodity) flow problems, location and routing. However, INOC does not only deal with telecommunication networks, but with networks in the widest sense. These could be networks for vehicle routing, electricity provision or maritime shipping, just to mention a few. One might argue whether globalization and (ferocious) competition are at the very heart of what is needed for mankind. However, one might still follow the idea of an ever increasing need for decision support and solutions of network-related problems using latest information technology. This is especially important regarding the value chain and networks of firms. This may draw special attention to the latest developments in technologies and the challenges that come along regarding theoretical as well as practical implications of network optimization. This volume of the Lecture Notes in Computer Science consists of selected papers presented at the INOC 2011, held at the University of Hamburg, Germany, during June 13–16. The INOC 2011 is the successor of a series of scientific conferences on network optimization. The first was held in 2003 aiming at providing a fruitful environment for discussion and exchange of ideas on current and future challenges regarding information science and communication technologies. Previous conferences were held in Pisa (Italy, 2009), Spa (Belgium, 2007), Lisbon (Portugal, 2005) and Evry (France, 2003). These are well documented as follows: INOC 2003 W. Ben-Ameur and A. Petrowskin, Proceedings of the International Network Optimization Conference INOC 2003, ISSN: 1762-5734, Evry (2003). Special issue of Annals of Operations Research, Vol. 146, Issues 1, pp. 1-202 (2006), editors W. Ben-Ameur, D. Bienstock and I. Saniee INOC 2005 L. Gouveia and C. Mourao, Proceedings of the International Network Optimization Conference INOC 2005, Lisbon (2005), ISSN: 1762-5734. Special issue “Multicommodity Flows and Network Design” of Networks, Vol. 49, Issue 1, pp. 1–133 (2007), guest editors L. Gouveia and S. Voß.

VI

Preface

INOC 2007 Contributions are available online at http://www.euro-online.org /enog/inoc2007/INOC%202007%20-%20program.htm. Special issue “Network Optimization” of Networks, Vol. 55, Issue 3, pp. 169– 297 (2007), editors B. Fortz and L. Gouveia, INOC 2009 M.G. Scutell` a, CD-Rom with proceedings. Special Issue of Networks, in preparation, guest editors L. Gouveia and M.G. Scutell` a. The INOC 2011 was located in the most beautiful city in Germany, Hamburg. Hamburg is part of important logistics and telecommunication networks. Among others, we feature two airports within the city, one of the three biggest container ports in Europe belonging to the largest container ports worldwide. As a metropolitan region, numerous trade activities involving multitudes of companies take place every day providing great challenges for optimization up- and downstream along the value chain. That makes Hamburg the perfect place to inspire new ideas in the field of network optimization as well as information and communication sciences. The contributions presented at the conference as well as the selected papers in these proceedings highlight recent developments in network optimization. We grouped contributions as follows: – – – –

Network design Network flows Routing and transportation Further optimization problems and applications • Energy-oriented network design • Telecom applications • Location • Maritime shipping • Telecom • Graph theory • Miscellaneous

Organizing a conference and publishing the proceedings is of course an endeavor involving many people in numerous activities. We first want to thank all authors and presenters for their contributions. Moreover, we greatly appreciate the valuable help and cooperation from the members of the international Program Committee as well as the referees. June 2011

Julia Pahl Torsten Reiners Stefan Voß

Organization

Organization Chair Julia Pahl Torsten Reiners Stefan Voß

University of Hamburg, Germany Curtin University, Australia and University of Hamburg, Germany University of Hamburg, Germany

Organizing Committee Marco Caserta Silvia Schwarze

IE Business School, Madrid, Spain University of Hamburg, Germany

Program Committee and Referees Edoardo Amaldi, Milan, Italy Anita Amberg, Darmstadt, Germany Panagiotis Angeloudis, London, UK Anant Balakrishnan, Austin, USA Tolga Bektas, Southampton, UK Michael G.H. Bell, London, UK Walid Ben-Ameur, Evry, France Christian Bierwirth, Halle-Wittenberg, Germany Branko Bubalo, Berlin, Germany Kai Br¨ ussau, Hamburg, Germany Christelle Caillouet, Aachen, Germany Marco Caserta, Madrid, Spain Grit Claßen, Aachen, Germany Angel Corberan, Burjassot, Spain Amaro de Sousa, Aveio, Portugal Karl F. D¨ orner, Linz, Austria Bernard Fortz, Brussels, Belgium Mathias Fricke, Darmstadt, Germany Martin Josef Geiger, Hamburg, Germany Bernard Gendron, Montreal, Canada Bruce Golden, College Park, USA Monica Gentili, Salerno, Italy Stefan Gollowitzer, Vienna, Austria Luis Gouveia, Lisbon, Portugal

Peter Greistorfer, Graz, Austria Richard Hartl, Vienna, Austria Holger H¨oller, Hamburg, Germany Dmitry Ivanov, Hamburg, Germany Arie M.C.A. de Koster, Aachen, Germany Manuel Kutschka, Aachen, Germany Martin Labbe, Brussels, Belgium Gilbert Laporte, Montreal, Canada Markus Leitner, Vienna, Austria Stephan Lemkens, Aachen, Germany Stefan Lessmann, Hamburg, Germany Janny M.Y. Leung, Hong Kong, China Ivana Ljubic, Vienna, Austria Abilio Lucena, Rio de Janeiro, Brazil Tom Magnanti, Massachusetts, USA Ridha Mahjoub, Paris, France Vittorio Maniezzo, Cesena, Italy Alexander Martin, Erlangen, Germany Dirk Mattfeld, Braunschweig, Germany Bel´en Meli´ an, La Laguna, Spain Michel Minoux, Paris, France Eli Olinick, Dallas, USA Adam Ourou, Issy-les-Moulineaux, France

VIII

Organization

Sophie Parragh, Vienna, Austria Pierre Pesneau, Talence, France Subramanian Raghavan, College Park, USA G¨ unther Raidl, Vienna, Austria Mauricio G.C. Resende, New Jersey, USA Juan Jos´e Salazar Gonz´ alez, La Laguna, Spain Alexandre Salles da Cunha, Belo Horizonte, Brazil Gabriele Schneidereit, Hamburg, Germany Silvia Schwarze, Hamburg, Germany Maria Grazia Scutell`a, Pisa, Italy

Marc Sevaux, Lorient, France Xiaoning Shi, Shanghai, China Doug Shier, Clemson, USA Luidi Simonetti, Rio de Janeiro, Brazil Maria Grazia Speranza, Brescia, Italy Hartmut Stadtler, Hamburg, Germany Robert Stahlbock, Hamburg, Germany Thomas St¨ utzle, Brussels, Belgium Fabien Tricoire, Vienna, Austria Eduardo Uchoa, Niteroi, Brazil Jens Wollenweber, N¨ urnberg, Germany David L. Woodruff, Davis, USA

Table of Contents

Part I: Theoretical Problems / Uncertainty / Graph Theory / Network Design On the Design of Optical OFDM-Based Networks . . . . . . . . . . . . . . . . . . . . Amal Benhamiche, Ridha Mahjoub, and Nancy Perrot

1

An Exact Algorithm for Robust Network Design . . . . . . . . . . . . . . . . . . . . . Christoph Buchheim, Frauke Liers, and Laura Sanit` a

7

SRG-Disjoint Design with Dedicated and Shared Protection . . . . . . . . . . . Bernardetta Addis, Giuliana Carello, and Federico Malucelli

18

Improved Formulations for the Ring Spur Assignment Problem . . . . . . . . Paula Carroll, Bernard Fortz, Martine Labb´e, and Se´ an McGarraghy

24

A Chance-Constrained Model and Cutting Planes for Fixed Broadband Wireless Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Grit Claßen, David Coudert, Arie M.C.A. Koster, and Napole˜ ao Nepomuceno Formulations and Branch-and-Cut Algorithm for the K -rooted Mini-Max Spanning Forest Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Alexandre Salles da Cunha, Luidi Simonetti, and Abilio Lucena Negative Cycle Separation in Wireless Network Design . . . . . . . . . . . . . . . . Fabio D’Andreagiovanni, Carlo Mannino, and Antonio Sassano

37

43

51

A Node Splitting Technique for Two Level Network Design Problems with Transition Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Stefan Gollowitzer, Lu´ıs Gouveia, and Ivana Ljubi´c

57

The Two Level Network Design Problem with Secondary Hop Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Stefan Gollowitzer, Lu´ıs Gouveia, and Ivana Ljubi´c

71

Spanning Trees with Generalized Degree Constraints Arising in the Design of Wireless Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lu´ıs Gouveia, Pedro Moura, and Amaro de Sousa

77

Reformulation by Intersection Method on the MST Problem With Lower Bound on the Number of Leaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lu´ıs Gouveia and Jo˜ ao Telhada

83

X

Table of Contents

A Polyhedral Approach for Solving Two Facility Network Design Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Faiz Hamid and Yogesh K. Agarwal FTTH Network Design under OA&M Constraints . . . . . . . . . . . . . . . . . . . . Matthieu Chardy and Cedric Hervet Introducing the Virtual Network Mapping Problem with Delay, Routing and Location Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Johannes Inf¨ uhr and G¨ unther R. Raidl Cutset Inequalities for Robust Network Design . . . . . . . . . . . . . . . . . . . . . . Arie M.C.A. Koster, Manuel Kutschka, and Christian Raack

92 98

105 118

Stabilized Branch-and-Price for the Rooted Delay-Constrained Steiner Tree Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Markus Leitner, Mario Ruthmair, and G¨ unther R. Raidl

124

A Heuristic Algorithm for a Prize-Collecting Local Access Network Design Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ivana Ljubi´c, Peter Putz, and Juan-Jos´e Salazar-Gonz´ alez

139

The Two Layer Network Design Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . Sara Mattia Affine Recourse for the Robust Network Design Problem: Between Static and Dynamic Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Michael Poss and Christian Raack On the Weight-Constrained Minimum Spanning Tree Problem . . . . . . . . . Agostinho Agra, Adelaide Cerveira, Cristina Requejo, and Eul´ alia Santos The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm . . . . . . . . . . . . . . . . . . . . . . . . Luidi Simonetti, Alexandre Salles da Cunha, and Abilio Lucena Multilayer Survivable Optical Network Design . . . . . . . . . . . . . . . . . . . . . . . Sylvie Borne, Virginie Gabrel, Ridha Mahjoub, and Raouia Taktak Hop-Level Flow Formulation for the Hop constrained Survivable Network Design Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ridha Mahjoub, Luidi Simonetti, and Eduardo Uchoa

145

150 156

162 170

176

Part II: Network Flow Maximum Delay Computation under Traffic Matrix Uncertainty and Its Application to Interdomain Path Selection . . . . . . . . . . . . . . . . . . . . . . . Isabel Amigo, Sandrine Vaton, Thierry Chonavel, and Federico Larroca

182

Table of Contents

The Spatially Equitable Multicommodity Capacitated Network Flow Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Paolo Dell’Olmo and Antonino Sgalambro Approximating Minimum Cut with Bounded Size . . . . . . . . . . . . . . . . . . . . Giulia Galbiati

XI

196 210

Lexicographical Minimization of Routing Hops in Telecommunication Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lu´ıs Gouveia, Pedro Patr´ıcio, and Amaro de Sousa

216

A Method for Obtaining the Maximum (δ, η)-Balanced Flow in a Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Wataru Kishimoto

230

Quickest Cluster Flow Problems on Tree Networks . . . . . . . . . . . . . . . . . . . Kathrin Leiner and Stefan Ruzika

243

Strong Duality for the Maximum Borel Flow Problem . . . . . . . . . . . . . . . . Ronald Koch and Ebrahim Nasrabadi

256

Modeling the Gateway Location Problem for Multicommodity Flow Rerouting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Maurizio Bruglieri, Paola Cappanera, Alberto Colorni, and Maddalena Nonato

262

Affine Decision Rules for Tractable Approximations to Robust Capacity Planning in Telecommunications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Adam Ouorou

277

Optimal Download Time in a Cloud-Assisted Peer-to-Peer Video on Demand Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pablo Rodr´ıguez-Bocca and Claudia Rostagnol

283

The Maximum Flow Problem with Conflict and Forcing Conditions . . . . Ulrich Pferschy and Joachim Schauer Algebraic Methods for Stochastic Minimum Cut and Maximum Flow Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Katherine C. Hastings and Douglas R. Shier Reliable and Restricted Quickest Path Problems . . . . . . . . . . . . . . . . . . . . . Stefan Ruzika and Markus Thiemann Modeling and Optimization of Production and Distribution of Drinking Water at VMW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Derek Verleye and El-Houssaine Aghezzaf

289

295 309

315

XII

Table of Contents

Part III: Routing and Transportation On the Hazmat Transport Network Design Problem . . . . . . . . . . . . . . . . . . Edoardo Amaldi, Maurizio Bruglieri, and Bernard Fortz

327

Complexity of Inverse Shortest Path Routing . . . . . . . . . . . . . . . . . . . . . . . . Mikael Call and Kaj Holmberg

339

The Skill Vehicle Routing Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Paola Cappanera, Lu´ıs Gouveia, and Maria Grazia Scutell` a

354

The Biobjective Inventory Routing Problem – Problem Solution and Decision Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Martin Josef Geiger and Marc Sevaux

365

Problem Transformations for Vehicle Routing and Scheduling in the European Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Asvin Goel

379

New Models for and Numerical Tests of the Hamiltonian p-Median Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Stefan Gollowitzer, Dilson Lucas Pereira, and Adam Wojciechowski

385

Solving Variants of the Vehicle Routing Problem with a Simple Parallel Iterated Tabu Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mirko Maischberger and Jean-Fran¸cois Cordeau

395

The Multi-Commodity One-to-One Pickup-and-Delivery Traveling Salesman Problem: A Matheuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I. Rodr´ıguez-Mart´ın and Juan Jos´e Salazar-Gonz´ alez

401

An Adaptive Large Neighborhood Search Heuristic for a Snow Plowing Problem with Synchronized Routes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . M. Ang´elica Salazar-Aguilar, Andr´e Langevin, and Gilbert Laporte

406

A Novel Column Generation Algorithm for the Vehicle Routing Problem with Cross-Docking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fernando Afonso Santos, Geraldo Robson Mateus, and Alexandre Salles da Cunha

412

Impacts of Imprecise Demand Forecasts in Network Capacity Control: An Online Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . J¨ orn Sch¨ onberger and Herbert Kopfer

426

A Branch-and-Price Algorithm for the Risk-Equity Constrained Routing Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nora Touati-Moungla, Pietro Belotti, Vincent Jost, and Leo Liberti

439

A Matheuristic for the Dial-a-Ride Problem . . . . . . . . . . . . . . . . . . . . . . . . . Roberto Wolfler Calvo and Nora Touati-Moungla

450

Table of Contents

XIII

Part IV: Further Optimization Problems and Applications A MILP-Based Heuristic for Energy-Aware Traffic Engineering with Shortest Path Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Edoardo Amaldi, Antonio Capone, Luca G. Gianoli, and Luca Mascetti

464

Designing AC Power Grids Using Integer Linear Programming . . . . . . . . . Arie M.C.A. Koster and Stephan Lemkens

478

Energy Saving in Fixed Wireless Broadband Networks . . . . . . . . . . . . . . . . David Coudert, Napole˜ ao Nepomuceno, and Issam Tahiri

484

MIP Modeling of Incremental Connected Facility Location . . . . . . . . . . . . Ashwin Arulselvan, Andreas Bley, Stefan Gollowitzer, Ivana Ljubi´c, and Olaf Maurer

490

A Computational Study of the Pseudo-Boolean Approach to the p-Median Problem Applied to Cell Formation . . . . . . . . . . . . . . . . . . . . . . . Boris Goldengorin and Dmitry Krushinsky

503

Cache Location in Tree Networks: Preliminary Results . . . . . . . . . . . . . . . . Bauguion Pierre, Ben Ameur Walid, and Gourdin Eric

517

The Multi Terminal q-FlowLoc Problem: A Heuristic . . . . . . . . . . . . . . . . . Stephanie Heller and Horst W. Hamacher

523

Optimal Bandwidth Allocation in Mesh-Based Peer-to-Peer Streaming Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mar´ıa Elisa Bertinat, Dar´ıo Padula, Franco Robledo Amoza, Pablo Rodr´ıguez-Bocca, and Pablo Romero

529

Hub Location Problems with Choice of Different Hub Capacities and Vehicle Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Julia Sender and Uwe Clausen

535

A Stochastic Optimization Model for Positioning Disaster Response Facilities for Large Scale Emergencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Anurag Verma and Gary M. Gaukler

547

Efficient Robust Linear Optimization for Large Repositioning Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Haris Gavranovi´c and Mirsad Buljubaˇsi´c

553

Robust Supply Vessel Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Elin E. Halvorsen-Weare and Kjetil Fagerholt

559

XIV

Table of Contents

A Liner Shipping Network Design – Routing and Scheduling Impacted by Environmental Influences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Volker Windeck and Hartmut Stadtler

574

A VND-ILS Heuristic to Solve the RWA Problem . . . . . . . . . . . . . . . . . . . . Alexandre Xavier Martins, Christophe Duhamel, Mauricio Cardoso de Souza, Rodney Rezende Saldanha, and Philippe Mahey

577

Recoverable Robust Knapsacks: Γ -Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . Christina B¨ using, Arie M.C.A. Koster, and Manuel Kutschka

583

A Tabu Search Heuristic Based on k -Diamonds for the Weighted Feedback Vertex Set Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Francesco Carrabs, Raffaele Cerulli, Monica Gentili, and Gennaro Parlato Cuts, c-Cuts, and c-Complexes over the n-Cube . . . . . . . . . . . . . . . . . . . . . M. Reza Emamy-Khansary

589

603

Exact and Metaheuristic Approaches to Extend Lifetime and Maintain Connectivity in Wireless Sensors Networks . . . . . . . . . . . . . . . . . . . . . . . . . . Andrea Raiconi and Monica Gentili

607

Computing Upper Bounds for a LBPP With and Without Probabilistic Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hugo Rodr´ıguez, Pablo Adasme, Abdel Lisser, and Ismael Soto

620

Mixed Integer Programming Model for Pricing in Telecommunication . . . Mustapha Bouhtou, Jean-Robin Medori, and Michel Minoux

626

UL RSSI as a Design Consideration for Distributed Antenna Systems, Using a Radial Basis Function Model for UL RSSI . . . . . . . . . . . . . . . . . . . Sarel Roets, Praven Reddy, and Poovendren Govender

631

Handling Rest Requirements and Preassigned Activities in Airline Crew Pairing Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Michael R¨ omer and Ta¨ıeb Mellouli

643

On the Cover Scheduling Problem in Wireless Sensor Networks . . . . . . . . Andr´e Rossi, Marc Sevaux, Alok Singh, and Martin Josef Geiger

657

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

669