Tree-based Graph Partitioning Constraint E-Book

X. Lorca

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

Seitenzahl: 310

Veröffentlichungsjahr: 2013

Beschreibung

Combinatorial problems based on graph partitioning enable us to mathematically represent and model many practical applications. Mission planning and the routing problems occurring in logistics perfectly illustrate two such examples. Nevertheless, these problems are not based on the same partitioning pattern: generally, patterns like cycles, paths, or trees are distinguished. Moreover, the practical applications are often not limited to theoretical problems like the Hamiltonian path problem, or K-node disjoint path problems. Indeed, they usually combine the graph partitioning problem with several restrictions related to the topology of nodes and arcs. The diversity of implied constraints in real-life applications is a practical limit to the resolution of such problems by approaches considering the partitioning problem independently from each additional restriction. This book focuses on constraint satisfaction problems related to tree partitioning problems enriched by several additional constraints that restrict the possible partitions topology. On the one hand, this title focuses on the structural properties of tree partitioning constraints. On the other hand, it is dedicated to the interactions between the tree partitioning problem and classical restrictions (such as precedence relations or incomparability relations between nodes) involved in practical applications. Precisely, Tree-based Graph Partitioning Constraint shows how to globally take into account several restrictions within one single tree partitioning constraint. Another interesting aspect of this book is related to the implementation of such a constraint. In the context of graph-based global constraints, the book illustrates how a fully dynamic management of data structures makes the runtime of filtering algorithms independent of the graph density.

Leseprobe

Table of Contents

PART 1. CONSTRAINT PROGRAMMING AND FOUNDATIONS OF GRAPH THEORY

Introduction to Part 1

Chapter 1. Introduction to Constraint Programming

1.1. What is a variable?

1.2. What is a constraint?

1.3. What is a global constraint?

1.4. What is a propagation algorithm?

1.5. What is a consistency level?

1.6. What is a constraint solver?

1.7. Constraint solvers at work

1.8. Organization structure

Chapter 2. Graph Theory and Constraint Programming

2.1. Modeling graphs with constraint programming

2.2. Graph theory at work in constraint programming

2.3. Constraint programming at work in graph theory

Chapter 3. Tree Graph Partitioning

3.1. In undirected graphs

3.2. In directed graphs

PART 2. CHARACTERIZATION OF TREE-BASED GRAPH PARTITIONING CONSTRAINTS

Chapter 4. Tree Constraints in Undirected Graphs

4.1. Decomposition

4.2. Definition of constraints

4.3. A filtering algorithm for the proper-forest constraint

4.4. Filtering algorithm for the resource-forest constraint

4.5. Summary of undirected tree constraints

Chapter 5. Tree Constraints in Directed Graphs

5.1. Decomposition

5.2. Definition of constraints

5.3. Filtering algorithm for the tree constraint

5.4. Filtering algorithm for the proper-tree constraint

5.5. Summary of tree constraints in directed and undirected graphs

Chapter 6. Additional Constraints Linked to Graph Partitioning

6.1. Definition of restrictions

6.2. Complexity zoo

6.3. Interaction between the number of trees and the number of proper trees

6.4. Relation of precedence between the vertices of the graph

6.5. Relation of conditional precedence

6.6. Relation of incomparability between graph vertices

6.7. Interactions between precedence and incomparability constraints

6.8. Constraining the interior half-degree of each vertex

6.9. Summary

Chapter 7. The Case of Disjoint Paths

7.1. Minimum number of paths in acyclic directed graphs

7.2. Minimum number of paths in any directed graph

7.3. A path partitioning constraint

7.4. Summary

Chapter 8. Implementation of a Tree Constraint

8.1. Original implementation

8.2. Toward a “portable” implementation

8.3. Conclusion

PART 3. IMPLEMENTATION: TASK PLANNING

Introduction to Part 3

Chapter 9. First Model in Constraint Programming

9.1. Model for the coherence of displacements in space

9.2. Modeling resource consumption

9.3. Modeling time windows

9.4. Modeling coordination constraints between units

9.5. Limitations of the proposed model

Chapter 10. Advanced Model in ConstraintProgramming

10.1. Modeling the coherence of displacements in space

10.2. Modeling resource consumption

10.3. Integration of temporal aspects

10.4. Propagating time windows

PART 4. CONCLUSION AND FUTURE WORK

Chapter 11. Conclusion

Chapter 12. Perspectives and Criticisms

Bibliography

Index

First published 2011 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 Ltd 27–37 St George’s Road London SW19 4EU UK

www.iste.co.uk

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

www.wiley.com

© ISTE Ltd 2011

The rights of Xavier Lorca 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

Lorca, Xavier.   Tree-based graph partitioning constraint / Xavier Lorca.     p. cm.   Includes bibliographical references and index.   ISBN 978-1-84821-303-6 (hardback)   1. Constraint programming (Computer science) 2. Graph theory. I. Title.    QA76.612.L67 2011    005.1′16--dc23

2011018477

British Library Cataloguing-in-Publication Data A CIP record for this book is available from the British Library

PART 1 Constraint Programming and Foundations of Graph Theory

Introduction to Part 1

Historically situated at the crossroads of disciplines such as operational research, digital analysis, symbolic calculations, and artificial intelligence, constraint programming [HEN 89, LAU 78, MAC 77] proposes a new approach to deal with combinatory problems by attempting to combine and unify the best parts of each of these disciplines.

Early work in this domain dates back to research carried out at the frontier of artificial intelligence and computer graphics in the 1970s [MON 74]. During the previous two decades, there has been an increasing awareness of issues relating to the existence of a declarative paradigm, allowing the modeling, implementation, and resolution of combinatorial problems. As such, the unification of the different approaches proposed around the resolution of complex combinatorial problems has given rise to the emergence of a common framework that is as conceptual as it is practical: Constraint Programming. Note that manufacturers such as Bull, Cosytec, IBM, ICL, Ilog, Prologia, or Siemens have been among the first to realize the practical value of constraint programming in the resolution and/or optimization of real combinatorial problems.

Reasoning about the intrinsic properties characterizing the semantics of a problem is the aim of constraint programming. This means that this discipline seeks to separate itself as far as possible from operational reasoning to concenrate on a theoretical specification for each problem. As such, constraint programming is a declarative paradigm. This separation of concerns offers an unequaled flexibility in the world of operational research. We might easily express nonlinear constraints for a problem by, for instance, forcing two variables to take distinct values. However, this flexibility comes at a price due to the rigor and expertise necessary when we want to look at the implementation (i.e. operational character) of this type of reasoning.

This introductory part intends to allow the reader to think about problems in tree graph partitioning with a specific vision for constraint programming. To do so, Chapter 1 will familiarize the reader with the basic concepts of constraint programming. Following this, Chapter 2 will examine the representation of graphs in constraint programming and will cover some core definitions for the graphs, which will be used subsequently. Finally, we will finish this section with Chapter 3, which will be dedicated to the formalization of tree graph partitioning problems that are treated in the following section.

Chapter 1Introduction to Constraint Programming

The central idea of constraint programming is to provide a method of solving combinatorial problems based on the constraint declaration (which could also be called logical conditions that depend on variables), which should be satisfied by every valid solution of the problem considered. As such, in a simple framework, a constraint satisfaction problem (CSP) can be solved by:

– a set of variables (in the mathematical sense) that take their values in a finite set of integers;

– a set of finite domains, such as (ν) ∈ , that represents all the possible values for the variable ν ∈ ;

– a set of constraints (logical relations) reliant on subsets of variables.

A CSP solution is the assignment of variables to a value that satisfies all constraints simultaneously. The constraint solver contains the resolution mechanism that allows it to arrive at all or some of the solutions satisfying all the constraints. The declarative aspect of constraint programming stems from the fact that the end user need only declare the set of variables and the constraints linking them.

The core of constraint programming, i.e. its operational nature, depends on the propagation-research mechanism: the propagation part tries to infer new information from the current states of variables. In relation to the research element, it consists of a pathway, generally called a depth first search, of the search space of the associated CSP. A complete search algorithm has to list all the possible assignments of the variables until it finds a valid solution for the CSP or all of the solutions, or finally concludes that there is no solution that satisfies all the constraints at the same time. Such an algorithm, also described as an exhaustive search algorithm, has an exponential time complexity in relation to the problem's data (number of variables, size of domains, and number of constraints). Then, the propagation mechanism will support the search. Indeed, it allows the constraints solver to detect and suppress the inefficient (or ) parts in the search space without having to search for them explicitly. The reduction of search space is performed through the propagation of each constraint involved in the CSP, via a mechanism. The filtering process consists of examining each variable that has not yet been assigned (or instantiated), with a view to removing all inconsistent values from its domain, i.e. any value that, if assigned to this variable, would violate at least one of the active constraints in the CSP. Unfortunately, detecting and suppressing all the inconsistent values for every variable become an NP-Hard problem. It is for this reason that the “propagation-search” couplet is generally indissociable and that one of the major issues of constraint programming remains the search for a fair balance between , in terms of calculation time, and effective performance, in terms of filtering. This effective performance can be seen as the of a filtering algorithm in terms of inconsistent values detected in the domain of each variable in which it is found. In other words, when constraints are developed, it is essential to find a balance between the calculation time of the algorithm performing the constraint filtering and the effective quantity of detected inconsistent values, which allows the reduction of the amount of search space to be explored.