Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems

Name: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems | 8th International Conference, CPAIOR 2011, Berlin, Germany, May 23-27, 2011. Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

8th International Conference, CPAIOR 2011, Berlin, Germany, May 23-27, 2011. Proceedings

Tobias Achterberg J. Christopher Beck(Herausgeber*in)

Springer (Verlag)

Erschienen am 5. Mai 2011

X, 254 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-21311-3 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Title
Preface
Organization
Table of Contents
Preference Elicitation and Preference Learning in Social Choice
Propagation in Constraints: How One Thing Leads to Another
On Bilevel Programming and Its Impact in Branching, Cutting and Complexity
Optimization Methods for the Partner Units Problem
Introduction
The Partner Units Problem
Formal Definition
The Partner Units Problem Is Intractable
Forbidden Subgraphs of the Pup
K-Regular Graphs
Bounds on the Number of Units Required
Symmetry Breaking
Encodings for the General Case
Answer Set Programming
Propositional Satisfiability Testing
Integer Programming
Constraint Satisfaction Problem
A Special Case: InterUnitCap = 2
A Specialized Algorithm for InterUnitCap = 2
Adapting the Encodings to InterUnitCap = 2
Evaluation
Experimental Results
Analysis
Future Work
References
Manipulating MDD Relaxations for Combinatorial Optimization
Introduction
Preliminaries
Top-Down MDD Compilation
Exact Top-Down Compilation
Approximate Top-Down Compilation
Value Enumeration
Application to Set Covering
Equivalence Test
Relaxation Operation
Filtering
Experimental Results
Bandwidth and the Minimum Bandwidth Problem
Problem Generation
Evaluating the MDD Parameters
Evaluating the Impact of the Bandwidth
Scaling Up
Conclusion
References
The AllDifferent Constraint with Precedences
Introduction
Formal Background
Some Examples
Exam Time-Tabling
Scheduling
Breaking Value Symmetry
AllDiffPrec
Bounds Consistency
Faster Bounds Consistency Algorithm
Bounds Consistency Decomposition
Domain Consistency
Other Related Work
Conclusions
References
Retail Store Workforce Scheduling by Expected Operating Income Maximization
Introduction
Forecasting in Retail Workforce Management
Statistical Forecasting Models
Case Study
Constraint Programming for Schedule Construction
Conclusion
References
Spatial and Objective Decompositions for Very Large SCAPs
Background and Motivation
Previous Work
The Single Commodity Allocation Problem (SCAP)
The Basic Approach
Spatial Decomposition
Objective Decomposition
Benchmarks and Results
Conclusion
References
Upgrading Shortest Paths in Networks
Introduction
The Upgrading Shortest Paths Problem
Problem Definition
Computational Complexity
Solution Methods
Mixed Integer Programming
A Naive Greedy Algorithm
An Iterative Greedy Algorithm
Experimental Results
Greedy Algorithm Performance
Results on Grizzly Bear Data
Conclusions and Future Work
References
Parallel Machine Scheduling with Additional Resources: A Lagrangian-Based Constraint Programming Approach
Introduction
Integer Program and its Lagrangian Relaxation Problem
Lagrangian-Based Constraint Programming Approach
Computational Results and Conclusion
References
Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry
Introduction
Related Work
Basic Notation and Definitions
Graph Symmetry Handling
Lexicographic Graph Symmetry Handling
Combinations of Graph and Color Symmetry
A Branch-Cut-and-Propagate Algorithm
Preprocessing
Node Labeling Heuristics
Branching Rules
Valid Inequalities
Dominated Nodes
Computational Results
Conclusion and Future Work
References
Climbing Depth-Bounded Adjacent Discrepancy Search for Solving Hybrid Flow Shop Scheduling Problems with Multiprocessor Tasks
Introduction
Problem Definition
Discrepancy Search
General Statement
Depth-Bounded Discrepancy Search
Climbing Discrepancy Search
Proposal: Climbing Depth-Bounded Adjacent Discrepancy Search
CDADS: Main Features
Heuristics
Schedule Generation Scheme
Lower Bound
Computational Study
Test Beds
Restart Policy
Results
Comparison of CDADS Solutions with State-Of-the-Art Results
Conclusions
References
On Counting Lattice Points and Chv\'{a}tal-Gomory Cutting Planes
Introduction
Counting for Cutting
Empirical Results
Conclusions
References
Precedence Constraint Posting for Cyclic Scheduling Problems
Introduction
Problem Description
Cyclic and Periodic Scheduling
Related Work
Cyclic Precedence Constraint Posting
Concurrency and Requirement Functions
Minimal Critical Sets
MCS Resolvers
Implementing the Cyclic PCP
Cyclic Iterative Flattening
Temporal Consistency Check
Detecting Contention Peaks and MCS
Sampling and Adding a Resolver
Experimental Results
Conclusion and Future Work
References
A Probing Algorithm for MINLP with Failure Prediction by SVM
Introduction
Background
The Probing Algorithm
Support Vector Machine for Failure Prediction
Measuring the Effect of FBBT
Support Vector Machines
Aggressive Probing Failure Prediction with SVM
Computational Experiments
Test Instances
Training the SVM Classifier
Testing the Probing Algorithm
Branch-and-Bound After Probing
Conclusions
References
Recovering Indirect Solution Densities for Counting-Based Branching Heuristics
Introduction
Framework
Channelling Solution Densities through element Constraints
Generalizing the Counting Algorithm for knapsack Constraints
Stronger Back-Propagation from the Cost Variable
Experiments: Capacitated Facility Location
Conclusion
References
Using Hard Constraints for Representing Soft Constraints
Introduction
Background
Constraint Network
Satisfiability Sum Constraint
Ssc: Partition Based Filtering
Ssc: Conflict Set Based Filtering
The S2H Schema
Hardening of Soft Constraints
Catch of the Failure and Deletion
Instantiation of the S2H Schema
Partition Based Filtering
Conflict Set Based Filtering
Implementation of the S2H Schema
Creation of a New Choice Point
Use of an Independent Solver in Parallel
Internal Addition and Catch of Failure
Summary
Conclusion
References
The Objective Sum Constraint
Introduction
Objective Sum Constraint
Lower Bounds
Multiple Constraints Involving a Sub-objective Variable
Multiple Sub-objective Constraints Involving a Variable
A New Lower Bound of the Objective Variable
Filtering Algorithm
Application
Related Work
Conclusion
References
Almost Square Packing
Introduction
Constraint Programming Model
Generating Candidate Enclosing Rectangles
Symmetry Removal
Search
Redundant Constraints
Impact of Interval Size
Decomposition
Comparison
Conclusion
References
Efficient Planning of Substation Automation System Cables
Introduction
SAS Cable Planning
Integer Linear Program Formulation
Results
Conclusion
References
A New Algorithm for Linear and Integer Feasibility in Horn Constraints
Introduction
Statement of Problem
Motivation and Related Work
The Implied DCS of a HCS
Least Elements of Horn Constraint Systems
The New Algorithm
Correctness
Analysis
Analysis of H2D
Analysis of NCCD
Analysis of MV
Analysis of Algorithm 6.1
Extended Horn Constraints
Conclusion
References
Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources
Introduction
Related Works
TimeTable Edge Finding
Timetable
Overload Checking
Time Bound Adjustment Rule
Time Bound Adjustment Algorithm
Time Complexity
Symmetry
Improvements
Improved Time Bound Adjustments
Improved Computation of Energy Consumption
Comparison with Standard and Extended Edge Finding
Experimental Results
References
Identifying Patterns in Sequences of Variables
Introduction
Background
Pattern Constraint
Conclusions
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken