Paradigms of Combinatorial Optimization E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 1612

Veröffentlichungsjahr: 2014

Beschreibung

Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains: mathematics, theoretical computer science and management. The three volumes of the Combinatorial Optimization series aim to cover a wide range of topics in this area. These topics also deal with fundamental notions and approaches as with several classical applications of combinatorial optimization. Concepts of Combinatorial Optimization, is divided into three parts: - On the complexity of combinatorial optimization problems, presenting basics about worst-case and randomized complexity; - Classical solution methods, presenting the two most-known methods for solving hard combinatorial optimization problems, that are Branch-and-Bound and Dynamic Programming; - Elements from mathematical programming, presenting fundamentals from mathematical programming based methods that are in the heart of Operations Research since the origins of this field.

Leseprobe

Table of Contents

Preface

PART I Paradigmatic Problems

Chapter 1 Optimal Satisfiability

1.1. Introduction

1.2. Preliminaries

1.3. Complexity of decision problems

1.4. Complexity and approximation of optimization problems

1.5. Particular instances of constraint satisfaction problems

1.6. Satisfiability problems under global constraints

Chapter 2 Scheduling Problems

2.1. Introduction

2.2. New techniques for approximation

2.3. Constraints and scheduling

2.4. Non-regular criteria

2.5. Bibliography

Chapter 3 Location Problems

3.1. Introduction

3.2. Continuous problems

3.3. Discrete problems

3.4. On-line problems

3.5. The quadratic assignment problem

3.6. Conclusion

3.7. Bibliography

Chapter 4 MiniMax Algorithms and Games

4.1. Introduction

4.2. Games of no chance: the simple cases

4.3. The case of complex no chance games

4.4. Quiescence search

4.5. Case of games using chance

4.6. Conclusion

4.7. Bibliography

Chapter 5 Two-dimensional Bin Packing Problems

5.1. Introduction

5.2. Models

5.3. Upper bounds

5.4. Lower bounds

5.5. Exact algorithms

5.6. Acknowledgements

5.7. Bibliography

Chapter 6 The Maximum Cut Problem

6.1. Introduction

6.2. Complexity and polynomial cases

6.3. Applications

6.4. The cut polytope

6.5. Semi-definite programming (SDP) and the maximum cut problem

6.6. The cut cone and applications

6.7. Approximation methods

6.8. Related problems

6.9. Conclusion

6.10. Bibliography

Chapter 7 The Traveling Salesman Problem and its Variations

7.1. Introduction

7.2. Elementary properties and various subproblems

7.3. Exact solving algorithms

7.4. Approximation algorithm for max TSP

7.5. Approximation algorithm for min TSP

7.6. Constructive algorithms

7.7. Conclusion

7.8. Bibliography

Chapter 8 0–1 Knapsack Problems

8.1. General solution principle

8.2. Relaxation

8.3. Heuristic

8.4. Variable fixing

8.5. Dynamic programming

8.6. Solution search by hybridization of branch-and-bound and dynamic programming

8.7. Conclusion

8.8. Bibliography

Chapter 9 Integer Quadratic Knapsack Problems

9.1. Introduction

9.2. Solution methods

9.3. Numerical experiments

9.4. Conclusion

9.5. Bibliography

Chapter 10 Graph Coloring Problems

10.1. Basic notions of colorings

10.2. Complexity of coloring

10.3. Sequential methods of coloring

10.4. An exact coloring algorithm

10.5. Tabu search

10.6. Perfect graphs

10.7. Chromatic scheduling

10.8. Interval coloring

10.9. T-colorings

10.10. List colorings

10.11. Coloring with cardinality constraints

10.12. Other extensions

10.13. Edge coloring

10.14. Conclusion

10.15. Bibliography

PART II New Approaches

Chapter 11 Polynomial Approximation

11.1. What is polynomial approximation?

11.2. Some first examples of analysis: constant approximation ratios

11.3. Approximation schemes

11.4. Analyses depending on the instance

11.5. Conclusion: methods and issues of approximation

11.6. Bibliography

Chapter 12 Approximation Preserving Reductions

12.1. Introduction

12.2. Strict and continuous reductions

12.3. AP-reduction and completeness in the classes NPO and APX

12.4. L-reduction and completeness in the classes Max-SNP and APX …

12.5. Affine reduction

12.6. A few words on GAP-reduction

12.7. History and comment

12.8. Bibliography

Chapter 13 Inapproximability of Combinatorial Optimization Problems

13.1. Introduction

13.2. Some technical preliminaries

13.3. Probabilistically checkable proofs

13.4. Basic reductions

13.5. Optimized reductions and PCP constructions

13.6. An overview of known inapproximability results

13.7. Integrality gap results

13.8. Other topics

13.9. Conclusions

13.10. Prove optimal results for 2-query PCPs

13.11. Settle the Unique Games Conjecture

13.12. Prove a strong inapproximability result for Metric TSP

13.13. Acknowledgements

13.14. Bibliography

Chapter 14 Local Search: Complexity and Approximation

14.1. Introduction

14.2. Formal framework

14.3. A few familiar optimization problems and their neighborhoods

14.4. The PLS class

14.5. Complexity of the standard local search algorithm

14.6. The quality of local optima

14.7. Approximation results

14.8. Conclusion and open problems

14.9. Bibliography

Chapter 15 On-line Algorithms

15.1. Introduction

15.2. Some classical on-line problem

15.3. Competitive analysis of deterministic algorithms

15.4. Randomization

15.5. Extensions of competitive analysis

15.6. Bibliography

Chapter 16 Polynomial Approximation for Multicriteria Combinatorial Optimization Problems

16.1. Introduction

16.2. Presentation of multicriteria combinatorial problems

16.3. Polynomial approximation and performance guarantee

16.4. Bibliographical notes

16.5. Conclusion

16.6. Bibliography

Chapter 17 An Introduction to Inverse Combinatorial Problems

17.1. Introduction

17.2. Definitions and notation

17.3. Polynomial inverse problems and solution techniques

17.4. Hard inverse problems

17.5. Conclusion

17.6. Bibliography

Chapter 18 Probabilistic Combinatorial Optimization

18.1. Motivations and applications

18.2. The issues: formalism and methodology

18.3. Problem complexity

18.4. Solving problems

18.5. Approximation

18.6. Bibliography

Chapter 19 Robust Shortest Path Problems

19.1. Introduction

19.2. Taking uncertainty into account: the various models

19.3. Measures of robustness

19.4. Complexity and solution of robust shortest path problems in the interval mode

19.5. Complexity and solution of robust shortest path problems in a discrete set of scenarios model

19.6. Conclusion

19.7. Bibliography

Chapter 20 Algorithmic Games

20.1. Preliminaries

20.2. Nash equilibria

20.3. Mixed extension of a game and Nash equilibria

20.4. Algorithmic problems

20.5. Potential games

20.6. Congestion games

20.7. Final notes

20.8. Bibliography

Chapter 21 Combinatorial Optimization with Competing Agents

21.1. Introduction

21.2. Social welfare optimization in Social Networks

21.3. A simple connection game

21.4. Efficiency of truthful algorithms without payment

21.5. Bibliography

General Bibliography

List of Authors

Index

Summary of Volume 1 Concepts of Combinatorial Optimization

First edition published 2010 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.© ISTE Ltd 2010

First published 2014 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK

www.iste.co.uk

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.wiley.com

©ISTE Ltd 2014The rights of Vangelis Th. Paschos to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2014942904

British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-84821-657-0

Preface

This revised and updated second edition of Paradigms of Combinatorial Optimization is the second volume of the Combinatorial Optimization series. It deals with advanced concepts as well as a series of problems, studies and research which have made, and continue to make, their mark on the evolution of this discipline. This work is divided into two parts:

– Part I: Paradigmatic Problems;

– Part II: New Approaches.

Part I contains the following chapters:

– Optimal Satisfiability by Cristina Bazgan;

– Scheduling Problems by Philippe Chrétienne and Christophe Picouleau;

– Location Problems by Aristotelis Giannakos;

– MinMax Algorithms and Games by Michel Koskas;

– Two-dimensional Bin Packing Problems by Andrea Lodi, Silvano Martello, Michele Monaci and Daniele Vigo;

– The Maximum Cut Problem by Walid Ben-Ameur, Ali Ridha Mahjoub and José Neto;

– The Traveling Salesman Problem and its Variations by Jérôme Monnot and Sophie Toulouse;

– 0–1 Knapsack Problems by Gérard Plateau and Anass Nagih;

– Integer Quadratic Knapsack Problems by Dominique Quadri, Eric Soutif and Pierre Tolla;

– Graph Coloring Problems by Dominique De Werra and Daniel Kobler.

All these chapters not only deal with the problems in question, but also highlight various tools and methods from combinatorial optimization and operations research. Obviously, this list is very limited and does not pretend to cover all the flagship problems in combinatorial optimization.

It is best to view the problems in this book as a sample that testifies to the richness of the themes and problems that can be tackled by combinatorial optimization, and of the tools developed by this discipline. Part II includes the following chapters:

– Polynomial Approximation by Marc Demange and Vangelis Th. Paschos;

– Approximation Preserving Reductions by Giorgio Ausiello and Vangelis Th. Paschos;

– Inapproximability of Combinatorial Optimization Problems by Luca Trevisan;

– Local Search: Complexity and Approximation by Eric Angel, Petros Christopoulos and Vassilis Zissimopoulos;

– On-line Algorithms by Giorgio Ausiello and Luca Becchetti;

– Polynomial Approximation for Multicriteria Combinatorial Optimization Problems by Eric Angel, Evripidis Bampis and Laurent Gourvès;

– An Introduction to Inverse Combinatorial Optimization by Marc Demange and Jérôme Monnot;

– Probabilistic Combinatorial Optimization by Cécile Murat and Vangelis Th. Paschos;

– Robust Shortest Path Problems by Virginie Gabrel and Cécile Murat;

– Algorithmic Games by Aristotelis Giannakos and Vangelis Th. Paschos.

– Combinatorial Optimization with Competing Agents by Diodato Ferraioli, Laurent Gourvès, Stefano Moretti, Fanny Pascual and Olivier Spanjaard.

The themes of this part are at the border between research operations and combinatorial optimization, theoretical computer science and discrete mathematics. Nevertheless, all these subjects have their rightful place in the vast scientific field that we call combinatorial optimization. They are developed, at least in part, at the heart of this discipline, fertilize it, widen its renown, and enrich its models.

In the second edition of this volume, I would like to thank again the authors who agreed to participate in the book. This work could never have come into being without the original proposal of Jean-Charles Pomerol, President of the scientific board at ISTE, and Sami Ménascé and Raphaël Ménascé, the President and Vice-President of ISTE, respectively. I once again give my warmest thanks to them for their insistence and encouragement.

Vangelis Th. PASCHOSJune 2014

PART I

Paradigmatic Problems

Chapter 1

Optimal Satisfiability

1.1. Introduction

Given a set of constraints defined on Boolean variables, a satisfiability problem, also called a Boolean constraint satisfaction problem, consists of deciding whether there exists an assignment of values to the variables that satisfies all the constraints (and possibly establishing such an assignment). Often, such an assignment does not exist and, in this case, it is natural to seek an assignment that satisfies a maximum number of constraints or minimizes the number of non-satisfied constraints.

An example of a Boolean constraint satisfaction problem is the problem known as Sat, which consists of deciding whether a propositional formula (expressed as a conjunction of disjunctions) is satisfiable or not. Sat was the first problem shown t o be NP-complete by Cook [COO 71] and Levin [LEV 73] and it has remained a central problem in the study of NP-hardness of optimization problems [GAR 79]. The NP-completeness of Sat asserts that no algorithm for this problem can be efficient in the worst case, under the hypothesis P ≠ NP. Nevertheless, in practice many efficient algorithms exist for solving the Sat problem.

Satisfiability problems also have other applications in automatic reasoning, computer vision, databases, robotics, and computer-assisted design. Gu, Purdom, Franco and Wah wrote an overview article [GU 97] that cites many applications of satisfiability problems (about 250 references).

Faced with a satisfiability problem, we can either study it from the theoretical point of view (establish its exact or approximate complexity, construct algorithms that guarantee an exact or approximate solution), or solve it from the practical point of view. Among the most effective methods for the practical solution of satisfiability problems are local search, Tabu search, and simulated annealing. For further details, refer to [GU 97] and [GEN 99], which offer a summary of the majority of practical algorithms for satisfiability problems.

In this chapter, we present the principal results of exact and approximation complexity for satisfiability problems according to the type of Boolean functions that participate in the constraints. Our goal is not to present exhaustively all the results that exist in the literature but rather to identify the most studied problems and to introduce the basic concepts and algorithms. The majority of satisfiability problems are hard. It is therefore advantageous, both from the theoretical and practical points of view, to identify some specific cases that are easier. We have chosen to present the most studied specific cases: planar instances, instances with a bounded number of occurrences of each variable, and dense instances. Several optimization problems can be modeled as a satisfiability problem with an additional global constraint on the set of feasible solutions. In particular, the MIN BISECTION problem, whose approximation complexity has not yet been established, can be modeled as a satisfiability problem where the set of feasible solutions is the set of the balanced assignments (with as many variables set to 0 as to 1). We also present a few results obtained on satisfiability problems under this global constraint.

Readers who wish to acquire a deeper knowledge of the complexity of satisfiability problems should consult the monograph by Creignou, Khanna and Sudan [CRE 01], where the proofs of the majority of important results in this domain can be found and that cover, besides the results presented here, other aspects such as counting complexity and function representation complexity, as well as other satisfiability problems. Note also that there is an electronic compendium by Crescenzi and Kann [CRE 95b], which regroups known results of approximation complexity for optimization problems, in particular for satisfiability problems.