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 | 9th International Conference, CPAIOR 2012, Nantes, France, May 28 - June 1, 2012, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

9th International Conference, CPAIOR 2012, Nantes, France, May 28 - June 1, 2012, Proceedings

Nicolas Beldiceanu Narendra Jussien Eric Pinson(Herausgeber*in)

Springer (Verlag)

Erschienen am 15. Mai 2012

XI, 409 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-29828-8 (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

Title
Preface
Organization
Table of Contents
A Contractor Based on Convex Interval Taylor
Motivation
Background
Extremal Interval Taylor Form
Corner Selection for a Tight Convexification
Preliminary Interval Linearization
eXtremal Interval Newton
X-Newton Iteration
X-Newton
Experiments
Experiments in Constrained Global Optimization
Experiments in Constraint Satisfaction
Conclusion
References
FDCC: A Combined Approach for SolvingConstraints over Finite Domains and Arrays
Introduction
Motivating Examples
Background
Combining cc and fd
Overview
The cc Decision Procedure
The fd Decision Procedure
Cooperation between cc and fd
Running Examples
Implementation and Experimental Results
Implementation of fdcc
Experimental Evaluation on Random Instances
Related Work
Conclusions and Perspectives
References
Variable Ordering for the Application of BDDs to the Maximum Independent Set Problem
Introduction
Preliminaries and Notation
Exact BDD Compilation
Variable Ordering for Exact BDD Compilation
Variable Ordering for Relaxation BDDs
Experimental Results
Exact BDDs for Trees
Exact BDD Width versus Relaxation BDD Bound
Relaxation Bounds
Conclusion
References
Graph Coloring Facets from All-Different Systems
Introduction
The Problem
Previous Work
Cycles
Valid Inequalities
Facet-Defining Inequalities
Bounds on the Objective Function
Mapping to 0-1 Cuts
Computational Results
Separation Algorithm
Conclusions and Future Research
References
Complete Characterization of Near-Optimal Sequences for the Two-Machine Flow Shop Scheduling Problem
Introduction
The Lattice of Permutations: Definitions and Properties
Characteristic Solutions
Finding the Minimum Sequence
Integer Linear Programming Approaches
Constraint Programming Approach
Finding All Minimal Sequences
Computational Experiments
PB1: Finding a Sequence of Minimum Level
PB2: Finding All Minimal Sequences
Conclusions and Further Research Directions
References
Global Cyclic Cumulative Constraint
Introduction
The Problem
Modular Representation for Cyclic Schedules
Model
Global Cyclic Cumulative Constraint GCCC
Start Time Filtering Algorithm
Modulus Filtering Algorithm
Experimental Results
Related Works
Conclusions
References
A Computational Geometry-Based Local Search Algorithm for Planar Location Problems
Introduction
The Tabu Search
Incremental Neighborhood
Closing a Facility
Opening a Facility
A New Incremental Algorithm
The Closest Points to a New Facility
Updating the Two Closest Points When Opening a Facility
Updating the Two Closest Points When Closing a Facility
Updating Algorithms 2 and 3
Time and Space Complexities
Empirical Study
Conclusion
References
The Conjunction of Interval Among Constraints
Introduction
A Scheduling Example
Problem Statement
Complexity
Preliminary Assumptions
The Cardinality Decomposition (P)
Equivalence between (P) and (PL)
Tractability of (PL)
Bound Consistency
Consistency Strength
Filtering Algorithms
Computational Evaluation
The Multi-dimensional Interval-Amongs
A Target Localization Example
Complexity
Related Works
Conclusion
References
Flow-Based Combinatorial Chance Constraints
Introduction
Stochastic Constraint Programming and Related Work
The Chance-Alldifferent Constraint
Hardness of Determining Consistency
Filtering the Chance-Alldifferent Constraint
Policy Tree Representation
Filtering Based on Minimum-Cost Network Flows
Filtering Based on Most Likely Solutions
Extension to Other Flow-Based Constraints
Computational Results
Conclusion and Future Work
References
Explaining Flow-Based Propagation
Introduction
Lazy Clause Generation
Flow Networks
Ford and Fulkerson's Algorithm
Network Flow Propagator
Explaining Failure
Explaining Pruning
Minimum Cost Flow Networks
Dual Network Simplex
Minimum Cost Network Flow Propagator
Explaining Failure
Explaining Fathoming
New sequence and gsc Encodings
Experiments
Conclusions
References
Constraint Optimization Problems and Bounded Tree-Width Revisited
Introduction
Preliminaries
Constraint Optimization Problems
Relational Structures and Homomorphisms
Hypergraphs and Tree Decompositions
Parameterized Complexity and Parameterized Constraint Optimization Problems
Polynomial-Time Algorithms for Constraint OptimizationProblems with Bounded Fractional Hypertree Width
Parameterization, Tractability, Domination, and Hardness
Tractability Results
The Domination Lattice and Hardness Results
Conclusions
References
A High Level Language for Solver Independent Model Manipulation and Generation of Hybrid Solvers
Introduction
Related Work
Introduction to CML
Sequential Composition of LS and CP
Column Generation
LNS
Results
Conclusion
References
Explaining Propagators for s-DNNF Circuits
Introduction
Propagating DNNF
Smooth Decomposable Negation Normal Form
DNNF Decomposition
DNNF Propagation
Propagation from the Root
Incremental Propagation
Explaining DNNF Propagation
Minimal Explanation
Greedy Explanation
Explanation Weakening
Experimental Results
Shift Scheduling
Forklift Scheduling
Conclusion
References
Reconsidering Mixed Integer Programming and MIP-Based Hybrids for Scheduling
Introduction
Problem Definition
Reconsidering MIP
Experimental Results
Discussion
Constraint Integer Programming
Two CIP Models
Solving CIP Models
Experiments with CIP
Discussion
Conclusion
References
Activity-Based Search for Black-Box Constraint Programming Solvers
Introduction
Impact-Based Search
The WDEG Heuristic
Activity-Based Search
Experimental Results
The Experimental Setting
The Core Results
Sensitivity Analysis
Some Behavioral Observations
Conclusion
References
Instance-Specific Algorithm Configuration as a Method for Non-Model-Based Portfolio Generation
Introduction
ISAC
Algorithm Configuration for Algorithm Selection
Model-Based Solver Selection
Non-model Based Solver Selection
Using ISAC as Portfolio Generator
Algorithm Configuration vs. Algorithm Selection of SAT Solvers
Pure Solver Portfolio vs. SATzilla
Meta-solver Configuration vs. SATzilla
Improved Algorithm Selection
Latent-Class Model-Based Algorithm Selection
Comparison with Other Algorithm Configurators
ISAC vs. ArgoSmart
ISAC vs. Hydra
Conclusion
References
Pheromone-Based Heuristic Column Generation for Vehicle Routing Problems with Black Box Feasibility
Introduction
Vehicle Routing Problem with Black Box Feasibility
Approach
Addressing the VRPBB as a Set Partitioning Problem
Heuristic Column Generation
Applications of the VRPBB
The Three-Dimensional Loading Capacitated Vehicle Routing Problem
The Multi-Pile Vehicle Routing Problem
Experimental Results
Results on the 3L-CVRP
Results on the MP-VRP
Conclusion
References
Simple Temporal Problems in Route Scheduling for the Dial-a-Ride Problem with Transfers
Introduction
DARPT
The DARPT Feasibility Problem
Routes without Transfer
Routes with Transfers
Simple Temporal Problem Formulation for the DARPT
STP Consistency
Necessary and Sufficient Conditions for the DARPT Route Feasibility
NC1: Time Windows Satisfaction
NC2: Single Route Constraint Satisfaction
SC1: Heuristic Constant Time Rescheduling
SC2: Heuristic Cordeau and Laporte Rescheduling
Applying Necessary and Sufficient Conditions
Computational Experiments
ALNS Metaheuristic
Instances
Results
Conclusion
References
Solving the Longest Simple Path Problem with Constraint-Based Techniques
Introduction
The Exact Algorithm
CP Model for Solving Longest Path between Two Specified Vertices
The Exact Algorithm
The Tabu Search Algorithm
The Modeling
Experiments
Conclusion
References
On Beam Search for Multicriteria Combinatorial Optimization Problems
Introduction
Multicriteria Combinatorial Optimization
Beam Search for Multicriteria Optimization
Bounds for the Bicriteria {0,1} Knapsack Problem
Upper Bounds
Acceptance Test
The -Indicator -Subset Selection
Problem Formulation
Algorithm for Bicriteria Case
Implementation and Time Complexity
Restart and Variable Ordering Strategy
Experimental Analysis
Beam Search Implementation
Benchmark Instances
Experimental Results
Concluding Remarks
References
Combining Static and Dynamic Models for Boosting Forward Planning
Introduction
Illustrative Example
Constraint-Based Timed Automaton (CTA)
Constraint-Based Observers
Example 1: A CP-Observer for the Illustrative Space Example
Example 2: an ILP-Observer for the Trucks Planning Problem
Forward Search Pruned by Observers
Experiments
Conclusion
References
Hybrid Heuristics for Multimodal Homecare Scheduling
Introduction
The Multimodal Homecare Scheduling Problem
Objective Function
Related Work
Initial Solutions with Constraint Programming
The CP Model and CP Search Setup
Iterative Clustering
Random Solution Generation
Solution Improvement by Metaheuristics
Variable Neighborhood Descent
General Variable Neighborhood Search
A Hybrid Evolutionary Algorithm
Simulated Annealing Hyper-Heuristic (SAHH)
Scatter Search
Computational Results
Initial Solution Generation Using CP
Evaluating Metaheuristics
Conclusions
References
Guiding Combinatorial Optimization with UCT
Introduction
MIP Search, Node Selection, and UCT
Guiding MIP Optimization with UCT
Experimental Evaluation
References
Maximising the Net Present Value for Resource-Constrained Project Scheduling
Introduction
Resource-Constrained Project Scheduling Problem with Discounted Cash Flows
The Net-Present-Value Constraint Propagator
Propagator without Precedence Relations
Propagator with Precedence Relations
Using a Generic LP Propagator for PspDc
Experiments
Conclusion and Future Work
References
Randomized Adaptive Vehicle Decomposition for Large-Scale Power Restoration
Introduction
Prior Work
Problem Formalization
Overview of Constraint Injection
Pickup and Delivery Routing with Precedence Constraints
Large Neighborhood Search
Randomized Adaptive Decompositions
Experimental Results
Benchmarks
Quality of the Results
LNS versus RAVD
Convergence of the Results
The Impact of the Precedence Constraints
Conclusion
References
A Multilevel Algorithm for Large Unconstrained Binary Quadratic Optimization
Introduction
The Backbone Multilevel Memetic Algorithm
The General Multilevel Scheme
The Backbone-Based Coarsening Phase
Initial Population of Solutions
The Population-Based Memetic Algorithm HMA
The Asymmetric Uncoarsening Phase
Experimental Results
Comparison between the BMMA and HMA Algorithms
Comparison between BMMA and Other State-of-the-Art Algorithms
Discussion
Conclusion
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken