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

1.7. Conclusion

1.8. Bibliography

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. Acknowledgments

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 comments

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 inapproximabiity 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 inapproximabiity 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 problems

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 model

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

List of Authors

Index

First published in Great Britain and the United States in 2010 by ISTE Ltd and John Wiley & Sons, Inc. Adapted and updated from Optimisation combinatoire volumes 1 to 5 published 2005-2007 in France by Hermes Science/Lavoisier © LAVOISIER 2005, 2006, 2007

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 Ltd
27-37 St George’s Road
London SW19 4EU
UK
John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA

www.iste.co.uk
www.wiley.com

© ISTE Ltd 2010

The 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 Cataloging-in-Publication Data

Combinatorial optimization / edited by Vangelis Th. Paschos.

v. cm.

Includes bibliographical references and index.

Contents: v. 1. Concepts of combinatorial optimization

ISBN 978-1-84821-146-9 (set of 3 vols.)

-- ISBN 978-1-84821-148-3 (v. 2)

1. Combinatorial optimization. 2. Programming (Mathematics)

I. Paschos, Vangelis Th.

QA402.5.C545123 2010

519.6′4--dc22

2010018423

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-84821-146-9 (Set of 3 volumes)

ISBN 978-1-84821-148-3 (Volume 2)

Preface

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 Problems 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.

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.

For this volume, my thanks go firstly to the authors who have agreed to participate in the book. This work could never have come into being without the original proposal of Jean-Charles Pomerol, Vice President of the scientific committee at Hermes, and Sami Ménascé and Raphaël Ménascé, the heads of publications at ISTE. I give my warmest thanks to them for their insistence and encouragement. It is a pleasure to work with them as well as with Rupert Heywood who has ingeniously translated this book’s material from the original French.

Vangelis Th. PASCHOS

June 2010

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 to 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 have direct applications in various domains such as operations research, artificial intelligence and system architecture. For example, in operations research, the graph-coloring problem can be modeled as an instance of SAT. To decide whether a graph with n vertices can be colored with k colors, we consider k × n Boolean variables, xij, i = 1,…, n, j = 1,…, k, where xij takes the value true if and only if the vertex i is assigned the color j. Hoos [HOO 98] studied the effectiveness of various modelings of the graph-coloring problem as a satisfiability problem where we apply a specific local search algorithm to the instance of the obtained satisfiability problem. The Steiner tree problem, widely studied in operations research, contributes to network design and routing applications. In [JIA 95], the authors reduced this problem to a problem that consists of finding an assignment that maximizes the number of satisfied constraints. Certain scheduling problems have been solved by using modeling in terms of a satisfiability problem [CRA 94]. Testing various properties of graphs or hypergraphs is also a problem that reduces to a satisfiability problem. In artificial intelligence, an interesting application is the planning problem that can be represented as a set of constraints such that every satisfying assignment corresponds to a valid plan (see [KAU 92] for such a modeling). Other applications in artificial intelligence are: learning from examples, establishing the coherence of a system of rules of a knowledge base, and constructing inferences in a knowledge base. In the design of electrical circuits, we generally wish to construct a circuit with certain functionalities (described by a Boolean function) that satisfy various constraints justified by technological considerations of reliability or availability, such as minimizing the number of gates used, minimizing the depth of the circuit or only using certain types of gates.

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.

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!