Constraint and Integer Programming

by Milano, Michela

• ISBN13: 9781402075834
• ISBN10: 1402075839
• Format: Hardcover
• Copyright: 2003-12-01
• Publisher: Kluwer Academic Pub

Summary

Despite differing origins, constraint programming and mathematical programming are beginning to merge. Constraint programming has grown out of the logic programming community as part of an effort to embed constraints in a programming language. Mathematical programming, a much older field, is rooted in the mathematics of optimization. Because these two areas have complementary strengths, there are ongoing efforts to integrate the two.Constraint and Integer Programming presents some of the basic ideas of constraint programming and mathematical programming, explores approaches to integration, brings us up to date on heuristic methods, and attempts to discern future directions in this fast-moving field. Constraint and Integer Programming is organized as follows: Chapter 1 is a high level overview of the main concepts of Constraint Programming (CP) and Integer Programming (IP) used in the book. Chapter 2 informally introduces integration methods describing and classifying the main works in the field. Chapter 3 outlines a unifying framework which involves the main concepts of CP and IP, underlining similarities and differences, and stating the basis for possible integrations. Chapter 4 describes global constraints as a vehicle for integrating IP concepts in CP in a transparent way for the user. Chapter 5 presents various ways to integrate relaxations in Constraint Programming focussing on global constraints. Chapter 6 presents hybrid solvers and Chapter 7 outlines Column Generation and its integration in Constraint Programming. Chapter 8 examines randomization and problem structure as a basis for understanding the intrinsic difficulty of the combinatorial problems. Chapter 9 studies the use of local search and meta-heuristics in CP. Chapter 10 is devoted to open perspectives and future directions.

Table of Contents

List of Figures	xiii
List of Tables	xvii
Preface	xix
Contributing Authors	xxiii
Foreword	xxvii
John Hooker
1 Constraint and Integer Programming	1	(32)
Michela Milano and Michael Trick
1 Introduction	1	(3)
2 CP(FD) Basic Concepts	4	(11)
2.1 Modeling	5	(1)
2.2 Structure of a CP program	6	(2)
2.3 Solving	8	(5)
2.3.1 Constraint Propagation	8	(2)
2.3.2 Search	10	(2)
2.3.3 Branch and Bound in CP	12	(1)
2.4 An example: the car sequencing problem	13	(2)
3 Integer Linear Programming Basic Concepts	15	(12)
3.1 Modeling	16	(4)
3.1.1 Logical Constraints	16	(1)
3.1.2 Resource Constraints	17	(1)
3.1.3 Routing Constraints	18	(1)
3.1.4 Alternative Formulations	19	(1)
3.2 Solving	20	(6)
3.2.1 Relaxations	20	(2)
3.2.2 Branch and Bound	22	(1)
3.2.3 Improving the Effectiveness	23	(3)
3.3 An example: the car sequencing problem revisited	26	(1)
4 Incomplete search strategies	27	(1)
5 Conclusion	28	(1)
References	29	(4)
2 Two Generic Schemes for Efficient and Robust Cooperative Algorithms	33	(26)
Emilie Danna and Claude Le Pape
1 Introduction	34	(3)
2 Operations Research Algorithms and Constraint Programming	37	(2)
3 Operations Research Algorithms and Mixed Integer Programming	39	(1)
4 Constraint Programming and Mixed Integer Programming	40	(4)
5 Operations Research Algorithms and Local Search	44	(1)
6 Mixed Integer Programming and Local Search	45	(3)
7 Constraint Programming and Local Search	48	(5)
References	53	(6)
3 Branch-and-Infer: A Framework for Combining CP and IP	59	(30)
Alexander Bockmayr and Thomas Kasper
1 Introduction	59	(1)
2 Modeling in CP and IP	60	(3)
3 An illustrating example: discrete tomography	63	(4)
3.1 Integer programming models	63	(1)
3.2 Constraint programming models	64	(3)
4 Branch and Infer	67	(7)
4.1 Primitive and non-primitive constraints	67	(1)
4.2 Inferring primitive from non-primitive constraints	68	(3)
4.3 Search	71	(2)
4.4 Pruning the search tree	73	(1)
5 Symbolic constraints in IP	74	(3)
5.1 Symbolic constraint abstractions	74	(1)
5.2 Extending expressiveness	75	(1)
5.3 Improving efficiency	76	(1)
5.4 Compositionality	77	(1)
6 Example: Symbolic constraints for supply chain planning	77	(7)
6.1 Stock-resource constraint	79	(1)
6.2 Finite capacity resource	80	(1)
6.3 State resource	81	(1)
6.4 Combined example	82	(2)
7 Summary	84	(1)
References	85	(4)
4 Global Constraints and Filtering Algorithms	89	(48)
Jean-Charles Régira
1 Introduction	89	(5)
2 Global Constraints	94	(10)
2.1 Preliminaries	94	(1)
2.2 Definition and Advantages	95	(1)
2.3 Examples	96	(8)
3 Filtering Algorithms	104	(8)
3.1 Algorithms Based on Constraints Addition	105	(1)
3.2 General Arc Consistency Filtering Algorithm	106	(5)
3.2.1 Preliminaries	106	(1)
3.2.2 A First Algorithm	107	(1)
3.2.3 A better general algorithm	107	(2)
3.2.4 Discussion and Example	109	(2)
3.3 Dedicated Filtering Algorithms	111	(1)
4 Two Successful Filtering Algorithms	112	(8)
4.1 Preliminaries	113	(1)
4.2 The Alldifferent Constraint	114	(3)
4.2.1 Consistency and Arc Consistency	114	(1)
4.2.2 Complexity	115	(1)
4.2.3 Some Results	116	(1)
4.3 The Global Cardinality Constraint	117	(3)
4.3.1 Consistency and Arc Consistency	117	(1)
4.3.2 Complexity	118	(1)
4.3.3 Some results	118	(2)
5 Global Constraints and Over-constrained Problems	120	(5)
5.1 Satisfiability Sum Constraint	121	(1)
5.2 Global Soft Constraints	122	(4)
5.2.1 General Definitions of Cost	123	(1)
5.2.2 Soft Alldifferent Constraint	124	(1)
6 Quality of Filtering Algorithms	125	(1)
7 Discussion	126	(3)
7.1 Incomplete Algorithms and Fixed-Point Property	126	(1)
7.2 Closure	127	(1)
7.3 Power of a Filtering Algorithm	128	(1)
8 Conclusion	129	(2)
References	131	(6)
5 Exploiting relaxations in CP	137	(32)
Filippo Focacci, Andrea Lodi and Michela Milano
1 Introduction and Motivation	138	(1)
2 Integer Linear Programming and Relaxations	139	(5)
2.1 Continuous Linear Relaxation	141	(1)
2.2 Structured Relaxations	142	(2)
2.2.1 Surrogate Relaxation	143	(1)
2.2.2 Lagrangean Relaxation	143	(1)
3 Integrating Relaxations in CP	144	(6)
3.1 Which relaxation to use	145	(1)
3.2 Which part of the problem	145	(5)
3.2.1 Relaxation of global constraints	141	(9)
4 Relax to propagate	150	(3)
4.1 Mapping	150	(1)
4.2 The Cost-Based Propagation	151	(1)
4.3 Triggering Events	152	(1)
5 Relax to guide the search	153	(3)
5.1 Synchronous update of the oracle	153	(1)
5.1.1 Select a branching object	153	(1)
5.1.2 Select promising values	154	(1)
5.2 Asynchronous update of the oracle	154	(2)
5.2.1 Generation of static heuristics	155	(1)
5.2.2 Defining sub-problems and incomplete methods	155	(1)
6 A case study: global optimization constraints for a Path constraint	156	(9)
6.1 Global constraint architecture	156	(1)
6.2 The Path constraint case	157	(13)
6.2.1 An ILP model of the Path constraint	158	(1)
6.2.2 Continuous (linear) relaxation	159	(1)
6.2.3 The linear Assignment Problem	159	(1)
6.2.4 The Minimum Spanning r-Arborescence	160	(1)
6.2.5 Adding cutting planes	160	(2)
6.2.6 Lagrangean relaxation of cuts	162	(3)
References	165	(4)
6 Hybrid Problem Solving in ECLiPSe	169	(38)
Fanid Ajili and Mark G. Wallace
1 Introduction	170	(2)
1.1 Modelling Formalisms for Constraints and Mathematical Programming	170	(1)
1.2 Requirements on Hybrid Modelling Formalisms	170	(1)
1.3 ECLiPSe and Piecewise Linear Probing	171	(1)
2 Integration of Constraints and Operations Research	172	(2)
2.1 Constraint Programming	172	(1)
2.2 Operations Research	173	(1)
2.3 Hybridization context	173	(1)
3 Language Ingredients for Hybrid Solvers	174	(7)
3.1 Conceptual Models and Design Models	174	(1)
3.2 Context	175	(1)
3.3 Creating a Design Model - Introduction and Example	175	(2)
3.4 Information Passed between Solvers	177	(1)
3.5 Combining Solvers and Search Engine	178	(1)
3.5.1 Information Passed from Search Engine to Solvers	178	(1)
3.5.2 Information Passed from Solvers to Search Engine	178	(1)
3.6 Requirements on the Language used for Design Models	179	(1)
3.6.1 Variable Attributes	179	(1)
3.6.2 Control Requirements	179	(1)
3.7 Infeasibility Detection	180	(1)
4 ECLiPSe as a Platform for Building Hybrid Algorithms	181	(5)
4.1 Modelling in ECLiPSe	182	(1)
4.2 The Domain Solver: ic	183	(1)
4.3 The linear solver interface: eplex	184	(1)
4.4 The repair solver	185	(1)
4.5 Attributed Variables and Demons in ECLiPSe	185	(1)
5 Programming a Hybrid Search in ECLiPSe	186	(14)
5.1 An Illustrative Example	187	(2)
5.2 Problem Modelling	189	(1)
5.3 Hybrid Probe-based Algorithm	189	(4)
5.3.1 The Algorithm Design Model	191	(1)
5.3.2 Inference phase	191	(1)
5.3.3 Probing phase	192	(1)
5.3.4 Resource feasibility	192	(1)
5.4 Probing Strategies	193	(1)
5.5 Mixed Integer Programming based Probing	194	(2)
5.6 Linear Relaxation based Probing	196	(1)
5.7 Evaluation and Performance Analysis	197	(13)
5.7.1 Setting up the benchmark instances	198	(1)
5.7.2 Computational results	199	(1)
6 Conclusion	200	(3)
References	203	(4)
7 CP Based Branch-and-Price	207	(26)
Kelly Easton, George Nemhauser and Michael Trick
1 Introduction	207	(3)
2 Three Illustrative Examples	210	(9)
2.1 The Generalized Assignment Problem	210	(2)
2.2 The Traveling Tournament Problem	212	(4)
2.3 The Social Golfers Problem	216	(2)
2.4 Other Applications	218	(1)
3 Implementation Issues	219	(7)
3.1 Set Partitioning Versus Set Covering	219	(1)
3.2 Initial Solution	220	(1)
3.3 Column Management	221	(1)
3.4 LP Relaxation	222	(1)
3.5 Branching	223	(1)
3.6 CP as a Subproblem Solver	224	(1)
3.7 Column Generation Heuristics	224	(1)
3.8 Combining Column and Row Generation	225	(1)
3.9 Parallel Implementation Issues	226	(1)
4 Future Directions for CP Based Branch-and-Price	226	(3)
References	229	(4)
8 Randomized Backtrack Search	233	(60)
Carla P. Gomes
1 Introduction	234	(3)
2 Randomization of Backtrack Search Methods	237	(4)
3 Formal Models of Heavy-Tailed Behavior	241	(4)
3.1 Random Walk	241	(1)
3.2 Tree Search Model	242	(3)
4 Heavy and Fat-Tailed Distributions	245	(10)
4.1 Heavy-Tailed Distributions	248	(4)
4.1.1 Definition	249	(1)
4.1.2 Visualization of Heavy-Tailed Behavior	249	(1)
4.1.3 Estimation of Index of Stability (a)	250	(2)
4.2 Fat vs. Heavy-Tailed Distributions	252	(3)
5 Heavy and Fat-Tailed Distributions in Backtrack Search	255	(14)
5.1 CSP Formulations	255	(2)
5.2 Mixed Integer Programming Formulations	257	(3)
5.3 Boolean Satisfiability Formulations	260	(2)
5.4 Graph Coloring Formulations	262	(1)
5.5 Discussion	263	(6)
6 Restart Strategies	269	(9)
6.1 Elimination of Heavy-Tails	269	(2)
6.2 Cutoff Value for Restart Strategy	271	(2)
6.3 Formal Results on Restarts	273	(1)
6.4 Restart Results on a Range of Problem Instances	274	(2)
6.5 Learning Dynamic Restart Strategies	276	(1)
6.6 Variants of Restart Strategies	277	(1)
7 Portfolio Strategies	278	(5)
7.1 Portfolio Design	279	(1)
7.2 Portfolio Results	279	(3)
7.3 Variants of Portfolios	282	(1)
8 Conclusions	283	(2)
References	285	(8)
9 Local Search and Constraint Programming	293	(38)
LS and CP illustrated on a transportation Problem
Filippo Focacci, Francois Laburthe, Andrea Lodi
1 Introduction	294
2 A didactic transportation problem	291	(7)
3 A CP approach for dTP	298	(8)
3.1 A CP model for dTP	298	(3)
3.1.1 Basic model	300	(1)
3.2 Propagation	301	(2)
3.2.1 Disjunctive Relations	301	(1)
3.2.2 Linking trucks and bins	302	(1)
3.2.3 Propagating costs	302	(1)
3.3 A redundant routing model	303	(3)
3.3.1 Propagation	304	(2)
4 Constructive Algorithms	306	(6)
4.1 Insertion algorithms	306	(1)
4.2 Greedy insertion	307	(2)
4.3 Restricted Candidate Lists and GRASP	309	(1)
4.4 Discrepancy-based search	310	(2)
5 LS as Post-Optimization	312	(2)
5.1 LS + constraint checks	312	(2)
5.2 Constraint checks within the neighborhood iteration	314	(2)
5.3 Freezing Fragments	316	(2)
5.4 CP models for the Neighborhoods	318	(2)
6 Metaheuristics	320	(3)
6.1 Control strategies from metaheuristics	320	(2)
6.2 Managing several neighborhoods	322	(1)
7 LS during construction	323	(2)
7.1 Single Route Optimization	323	(1)
7.2 Ejection Chains	324	(1)
8 Conclusions	325	(2)
References	327	(4)
10 Open Perspectives	331	(36)
Mark Wallace, Yves Caseau and Jean-Francois Puget
1 Motivations, Challenges and Applications	331	(10)
1.1 Overview	331	(1)
1.2 Challenges	332	(1)
1.3 Focus on Hard to Solve Problems	333	(2)
1.3.1 Global Constraints	333	(1)
1.3.2 Scalability Limitations of Tree Search	334	(1)
1.3.3 Limitations of Global "Soft" Constraints	335	(1)
1.4 Problem Analysis vs. Resolution	335	(2)
1.4.1 Multi-criteria problems	335	(1)
1.4.2 Uncertain Problems	336	(1)
1.4.3 Probabilistic Data	337	(1)
1.5 Supporting the Problem Solving Process	337	(2)
1.6 Software Engineering Issues	339	(2)
1.6.1 Software Engineering in Support of Combinatorial Problem Solving	339	(1)
1.6.2 Combinatorial Problem Solving in Support of Software Engineering	340	(1)
2 Transforming Models to Algorithms	341	(10)
2.1 Conceptual and Design Models	341	(1)
2.2 Decompositions	342	(2)
2.3 Transformations	344	(3)
2.3.1 Separating Modeling for Performance Improvements	344	(1)
2.3.2 Motivations and Examples	345	(1)
2.3.3 Transforming Conceptual Models into Design Models	346	(1)
2.4 Search	347	(2)
2.4.1 Local and Constructive Search	347	(1)
2.4.2 Combining Different Search Methods	348	(1)
2.4.3 Concurrent Search	348	(1)
2.5 Inference	349	(1)
2.5.1 Global and Local Control of Inference	349	(1)
2.5.2 Controlling the Local Inference Procedure	350	(1)
2.5.3 Controlling Communication of Inferences	350	(1)
2.6 Symmetries	350	(1)
3 New Techniques	351	(8)
3.1 Stochastic Optimisation	351	(2)
3.2 Overconstrained problems and robustness	353	(1)
3.3 User Support	354	(3)
3.3.1 A Simple Environment for Solving LSICO Problems	354	(2)
3.3.2 Automating Algorithm Development and Testing	356	(1)
3.4 Packaging	357	(2)
4 New Application Areas	359	(4)
4.1 Computer-Aided decision analysis based on simulation	359	(1)
4.2 Cooperative Problem Solving	360	(1)
4.3 Interleaved Planning and Execution	360	(3)
References	363	(4)
Index	367