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
Published on 15. May 2012
XI, 409 pages
978-3-642-29828-8 (ISBN)
Description
This book constitutes the refereed proceedings of the 9th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2012, held in Nantes, France, in May/June 2012.
The 26 revised full papers presented were carefully reviewed and
selected from 64 submissions. The papers are focused on both theoretical and practical, application-oriented issues in combinatorial optimization and feature current research with a special focus on inference and relaxation methods, integration methods, modeling methods, innovative applications of CP/AI/OR techniques, and implementation of CP/AI/OR techniques and optimization systems.
More details
Other editions
Additional editions
Nicolas Beldiceanu | Narendra Jussien | Eric Pinson
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
Book
05/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- 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
