دانلود کتاب Applications of Combinatorial Optimization

فهرست مطالب :

Cover Applications of Combinatorial Optimization ISBN 9781848211490 Table of Contents Preface Chapter 1 Airline Crew Pairing Optimization 1.1. Introduction 1.2. Defnition of the problem 1.2.1. Constructing subnetworks 1.2.2. Pairing costs 1.2.3. Model 1.2.4. Case without resource constraints 1.3. Solution approaches 1.3.1. Decomposition principles 1.3.2. Column generation, master problem and subproblem 1.3.3. Branching methods for fnding integer solutions 1.4. Solving the subproblem for column generation 1.4.1. Mathematical formulation 1.4.2. General principle of effective label generation 1.4.3. Case of one single resource: the bucket method 1.4.4. Case of many resources: reduction of the resource space 1.5. Conclusion 1.6. Bibliography Chapter 2 The Task Allocation Problem 2.1. Presentation 2.2. Defnitions and modeling 2.2.1. Defnitions 2.2.2. The processors 2.2.3. Communications 2.2.4. Tasks 2.2.5. Allocation types 2.2.6. Allocation/scheduling 2.2.7. Modeling 2.3. Review of the main works 2.3.1. Polynomial cases 2.3.2. Approximability 2.3.3. Approximate solution 2.3.4. Exact solution 2.3.5. Independent tasks case 2.4. A little-studied model 2.4.1. Model 2.4.2. A heuristic based on graphs 2.5. Conclusion 2.6. Bibliography Chapter 3 A Comparison of Some Valid Inequality Generation Methods for General 0-1 Problems 3.1. Introduction 3.2. Presentation of the various techniques tested 3.2.1. Exact separation with respect to a mixed relaxation 3.2.2. Approximate separation using a heuristic 3.2.3. Restriction + separation + relaxed lifting (RSRL) 3.2.4. Disjunctive programming and the lift and project procedure 3.2.5. Reformulation-linearization technique (RLT) 3.3. Computational results 3.3.1. Presentation of test problems 3.3.2. Presentation of the results 3.3.3. Discussion of the computational results 3.4. Bibliography Chapter 4 Production Planning 4.1. Introduction 4.2. Hierarchical planning 4.3. Strategic planning and productive system design 4.3.1. Group technology 4.3.2. Locating equipment 4.4. Tactical planning and inventory management 4.4.1. A linear programming model for medium-term planning 4.4.2. Inventory management 4.4.3. Wagner and Whitin model 4.4.4. The economic order quantity model (EOQ) 4.4.5. The EOQ model with joint replenishments 4.5. Operations planning and scheduling 4.5.1. Tooling 4.5.2. Robotic cells 4.6. Conclusion and perspectives 4.7. Bibliography Chapter 5 Operations Research and Goods Transportation 5.1. Introduction 5.2. Goods transport systems 5.3. Systems design 5.3.1. Location with balancing requirements 5.3.2. Multiproduct production-distribution 5.3.3. Hub location 5.4. Long-distance transport 5.4.1. Service network design 5.4.2. Static formulations 5.4.3. Dynamic formulations 5.4.4. Fleet management 5.5. Vehicle routing problems 5.5.1. Defnitions and complexity 5.5.2. Classical extensions 5.6. Exact models and methods for the VRP 5.6.1. Flow model with three indices 5.6.2. Flow model for the symmetric CVRP 5.6.3. Set partitioning model 5.6.4. Branch-and-cut methods for the CVRP 5.6.5. Column generation methods for the VRPTW 5.7. Heuristic methods for the VRP 5.7.1. Classical heuristics 5.7.2. Metaheuristics 5.7.3. The VRP in practice 5.8. Conclusion 5.9. Appendix: metaheuristics 5.9.1. Tabu search 5.9.2. Evolutionary algorithms 5.10. Bibliography Chapter 6 Optimization Models for Transportation Systems Planning 6.1. Introduction 6.2. Spatial interaction models 6.3. Traffc assignment models and methods 6.3.1. System optimization and user optimization models 6.3.2. Algorithms for traffc assignment for the user optimization model 6.3.3. The user problem as variational inequality 6.4. Transit route choice models 6.5. Strategic planning of multimodal systems 6.5.1. Demand 6.5.2. Mode choice 6.5.3. Representing transport supply and assigning demand 6.6. Conclusion 6.7. Bibliography Chapter 7 A Model for the Design of a Minimum-cost Telecommunications Network 7.1. Introduction 7.2. Minimum cost network construction 7.2.1. The diffculties of solving jointly or globally 7.2.2. Why tackle the global problem? 7.2.3. How to circumvent these diffculties 7.3. Mathematical model, general context 7.3.1. Hypotheses 7.3.2. The original problem 7.3.3. Solution principle 7.4. Proposed algorithm 7.4.1. A bit of sensitivity in an NP-hard world 7.4.2. The initial solution 7.4.3. Step-by-step exploration 7.5. Critical points 7.5.1. Parametric diffculties 7.5.2. Realities not taken into account 7.5.3. Complexity in size of the problem 7.6. Conclusion 7.7. Bibliography Chapter 8 Parallel Combinatorial Optimization 8.1. Impact of parallelism in combinatorial optimization 8.2. Parallel metaheuristics 8.2.1. Notion of walks 8.2.2. Classifcation of parallel metaheuristics 8.2.3. An illustrative example: scatter search for the quadratic assignment or QAP 8.3. Parallelizing tree exploration in exact methods 8.3.1. Return to two success stories 8.3.2. B&X model and data structures 8.3.3. Different levels of parallelism 8.3.4. Critical tree and anomalies 8.3.5. Parallel algorithms and granularity 8.3.6. The BOB++ library 8.3.7. B&X on grids of machines 8.4. Conclusion 8.5. Bibliography Chapter 9 Network Design Problems: Fundamental Methods 9.1. Introduction 9.2. The main mathematical and algorithmic tools for network design 9.2.1. Decomposition in linear programming and polyhedra 9.2.2. Flows and multiflows 9.2.3. Queuing network 9.2.4. Game theory models 9.3. Models and problems 9.3.1. Location problems 9.3.2. Steiner trees and variants 9.4. The STEINER-EXTENDED problem 9.5. Conclusion Chapter 10 Network Design Problems: Models and Applications 10.1. Introduction 10.2. Models and location problems 10.2.1. Locating the network access device 10.2.2. Locating machines and activities at the core of a production space 10.3. Routing models for telecommunications 10.3.1. Numerical tests 10.4. The design or dimensioning problem in telecommunications 10.4.1. Numerical tests 10.5. Coupled flows and multiflows for transport and production 10.5.1. Analysis of the COUPLED-FLOW-MULTIFLOW (CFM) problem 10.6. A mixed network pricing model 10.7. Conclusion 10.8. Bibliography Chapter 11 Multicriteria Task Allocation to Heterogenous Processors with Capacity and Mutual Exclusion Constraints 11.1. Introduction and formulation of the problem 11.1.1. Example a: organizing non-compulsory lesson choices by students 11.1.2. Example b: temporal activity programming 11.1.3. Example c: task scheduling on machines 11.2. Modeling the set of feasible assignments 11.3. The concept of a blocking confguration and analysis of the unblocking 11.3.1. A reminder of a few results from fow theory 11.3.2. Analysis of the minimum cut revealed by labeling a maximum fow on N 11.3.3. The concept of blocking confguration 11.3.4. Unblocking actions 11.4. The multicriteria assignment problem 11.4.1. Defnition of the criteria family 11.4.2. Satisfactory compromise selection strategy 11.5. Exploring a set of feasible non-dominated assignments in the plane 11.5.1. The bicriteria assignment problem with mutual exclusion constraints 11.5.2. Finding supported solutions of problem P 11.5.3. Matrix representation of problem P 11.5.4. Finding unsupported solutions of problem P 11.6. Numerical examples 11.6.1. Example with a blocking confguration present 11.6.2. Example without a blocking confguration 11.7. Conclusion 11.8. Bibliography List of Authors Index Summary of Volume 1 Concepts of Combinatorial Optimization Summary of Volume 2 Paradigms of Combinatorial Optimization