Principles and Practice of Constraint Programming - CP 2004: 10th International Conference, CP 2004, Toronto, Canada, September 27 - October 2004, Proceedings, Volume 10 (Google eBook)

Front Cover
Mark Wallace
Springer Science & Business Media, Sep 13, 2004 - Computers - 822 pages
0 Reviews
The 10th International Conference on the Principles and Practice of Constraint Programming (CP 2003) was held in Toronto, Canada, during September 27 – October 1, 2004. Information about the conference can be found on the Web at http://ai.uwaterloo.ca/~cp2004/ Constraint programming (CP) is about problem modelling, problem solving, programming, optimization, software engineering, databases, visualization, user interfaces, and anything to do with satisfying complex constraints. It reaches into mathematics, operations research, arti?cial intelligence, algorithms, c- plexity, modelling and programming languages, and many aspects of computer science. Moreover, CP is never far from applications, and its successful use in industry and government goes hand in hand with the success of the CP research community. Constraintprogrammingcontinuesto beanexciting,?ourishingandgrowing research?eld,astheannualCPconferenceproceedingsamplywitness.Thisyear, from 158 submissions, we chose 46 to be published in full in the proceedings. Instead of selecting one overall best paper, we picked out four “distinguished” papers – though we were tempted to select at least 12 such papers. In addition we included 16 short papersin the proceedings– these were presentedas posters at CP 2004. This volume includes summaries of the four invited talks of CP 2004. Two speakers from industry were invited. However these were no ordinary industrial representatives,buttwoofthe leadingresearchersinthe CPcommunity:Helmut Simonis of Parc Technologies, until its recent takeover by Cisco Systems; and Jean Francoi ̧ s Puget, Director of Optimization Technology at ILOG. The other two invited speakers are also big movers and shakers in the researchcommunity.
  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Preprocessing Techniques for Distributed Constraint Optimization
706
Variable Ordering Heuristics Show Promise
711
The Tractability of Global Constraints
716
Support Inference for Generic Filtering
721
Strong CostBased Filtering for Lagrange Decomposition Applied to Network Design
726
The Impact of ANDOR Search Spaces on Constraint Satisfaction and Counting
731
A General Extension of Constraint Propagation for Constraint Optimization
737
How Much Backtracking Does It Take to Color Random Graphs? Rigorous Results on Heavy Tails
742

Constraint Propagation as a Proof System
77
BacktrackFree Search for RealTime Constraint Satisfaction
92
Deriving Filtering Algorithms from Constraint Checkers
107
Leveraging the Learning Power of Examples in Automated Constraint Acquisition
123
Disjoint Partition and Intersection Constraints for Set and Multiset Variables
138
Decomposition and Learning for a Hard Real Time Task Allocation Problem
153
Quantified Constraint Satisfaction and 2Semilattice Polymorphisms
168
Smart LookAhead Arc Consistency and the Pursuit of CSP Tractability
182
Modeling Solution Quality by Extreme Value Theory
197
A Complete Characterization of Complexity for Boolean Constraint Optimization Problems
212
Financial Portfolio Optimisation
227
Bounding the Resource Availability of Partially Ordered Events with Constant Resource Impact
242
Monotone Literals and Learning in QBF Reasoning
260
Streamlined Constraint Reasoning
274
A Domain Consistency Algorithm for the Stretch Constraint
290
A Hybrid Method for Planning and Scheduling
305
CountingBased LookAhead Schemes for Constraint Satisfaction
317
Completable Partial Solutions in Constraint Programming and ConstraintBased Scheduling
332
Set Domain Propagation Using ROBDDs
347
Global Constraints for Integer and Set Value Precedence
362
Quality of LPBased Approximations for Highly Combinatorial Problems
377
Constraint Satisfaction in Semistructured Data Graphs
393
Strategies for Global Optimization of Temporal Preferences
408
A Candidate List Strategy with a Simple Diversification Device
423
Beyond the ClausestoVariables Ratio
438
Symbolic Decision Procedures for QBF
453
Propagation Guided Large Neighborhood Search
468
A Regular Language Membership Constraint for Finite Sequences of Variables
482
Generating Robust Partial Order Schedules
496
Full Dynamic Substitutability by SAT Encoding
512
Improved Bound Computation in Presence of Several Clique Constraints
527
Improved Algorithms for the Global Cardinality Constraint
542
ImpactBased Search Strategies for Constraint Programming
557
The Cardinality Matrix Constraint
572
Controllability of Soft Temporal Constraint Problems
588
Hybrid Set Domains to Strengthen Constraint Propagation and Reduce Symmetries
604
Speeding Up Constraint Propagation
619
Theoretical Foundations of CPBased Lagrangian Relaxation
634
A Constraint for Bin Packing
648
Solving Nonclausal Formulas with DPLL Search
663
A Hyperarc Consistency Algorithm for the Soft Alldifferent Constraint
679
Efficient Strategies for Weighted Maximum Satisfiability
690
Solving the Crane Scheduling Problem Using Intelligent Search Schemes
747
Algorithms for Quantified Constraint Satisfaction Problems
752
Preliminary Results
757
OnDemand Bound Computation for BestFirst Constraint Optimization
762
A New Algorithm for Maintaining Arc Consistency After Constraint Retraction
767
Computing the Frequency of Partial Orders
772
On Tightness of Constraints
777
Concurrent Dynamic Backtracking for Distributed CSPs
782
Set Variables and Local Search
788
NKings for Dynamic Systems
789
Relation Variables in Qualitative Spatial Reasoning
790
Synchronous Asynchronous and Hybrid Algorithms for DisCSP
791
LongTerm Learning for Algorithm Control
792
Solution Extraction with the Critical Path in GraphplanBased Optimal Temporal Planning
793
Machine Learning for Portfolio Selection Using Structure at the Instance Level
794
Local Search with Maximal Independent Sets
795
A Dynamic Restart Strategy for Randomized BT Search
796
A BDDBased Approach to Interactive Configuration
797
Extending Supersolutions
798
Choosing Efficient Representations of Abstract Variables
799
A Hypergraph Separator Based Variable Ordering Heuristic for Solving Real World SAT
800
Exploiting Symmetries via Permutations for PC Board Manufacturing
801
Combining Local Search with Maintaining Arc Consistency and a ConflictBased Statistics
802
Programming Robotic Devices with a Timed Concurrent Constraint Language
803
Heuristics for the Distributed Breakout Algorithm
804
Explanations and Numeric CSPs
805
Softly Constrained CP Nets
806
Online Constraint Solving and Rectangle Packing
807
Modelling Chemical Reactions Using Constraint Programming and Molecular Graphs
808
Constraining SpecialPurpose Domain Types
809
A Constraint Based Planning Architecture
810
Applying Constraint Satisfaction Techniques to 3D Camera Control
811
AEO Server and AEO Studio
812
A CP Application for Reconfiguring a Power Distribution Network for Power Losses Reduction
813
A ConstraintBased Planner Applied to Data Processing Domains
815
A C++ Library for Fast BacktrackFree Interactive Product Configuration
816
A ConstraintBased System for Hiring and Managing Graduate Teaching Assistants
817
A WebBased Meeting Scheduling Solver With Privacy Guarantees Without Trusted Servers
818
A ConstraintBased Graphics Library for BProlog
819
Author Index
820
Copyright

Common terms and phrases

About the author (2004)

Mark Wallace's most recent book is Felonies of Illusion, just out from Edge Books. His most recent book of fiction is Walking Dreams: Selected Early Tales. Wallace has authored more than ten books and chapbooks of poetry, including Nothing Happened and Besides I Wasn't There and Sonnets of a Penny-A-Liner. Temporary Worker Rides A Subway won the 2002 Gertrude Stein Poetry Award and was published by Green Integer Books. His multi-genre work Haze (Edge Books) was published in 2004, and his first collection of fiction, The Big Lie, was published by Avec Books in Fall 2000. His critical articles and reviews have appeared in numerous publications. Along with Steven Marks, he edited Telling It Slant: Avant Garde Poetics of the 1990s (University of Alabama Press) a collection of 26 essays by different writers on the subject of contemporary avant garde poetry and poetics. Wallace teaches literature and creative writing at Cal State San Marcos.

Bibliographic information