Handbook on Modelling for Discrete Optimization

by Williams, H. paul; Pitsoulis, Leonidas S.

• ISBN13: 9780387329413
• ISBN10: 0387329412
• Format: Hardcover
• Copyright: 2006-04-01
• Publisher: Springer-Verlag New York Inc

Summary

The primary objective underlying the Handbook on Modelling for Discrete Optimization is to demonstrate and detail the pervasive nature of Discrete Optimization. While its applications cut across an incredibly wide range of activities, many of the applications are only known to specialists. It is the aim of this handbook to correct this. It has long been recognized that "modelling" is a critically important mathematical activity in designing algorithms for solving these discrete optimization problems. Nevertheless solving the resultant models is also often far from straightforward. In recent years it has become possible to solve many large-scale discrete optimization problems. However, some problems remain a challenge, even though advances in mathematical methods, hardware, and software technology have pushed the frontiers forward. This handbook couples the difficult, critical-thinking aspects of mathematical modelling with the hot area of discrete optimization. It will be done in an academic handbook treatment outlining the state-of-the-art for researchers across the domains of the Computer Science, Math Programming, Applied Mathematics, Engineering, and Operations Research. Included in the handbook's treatment are results from Graph Theory, Logic, Computer Science, and Combinatorics. The chapters of this book are divided into two parts: (1) one dealing with general methods in the modelling of discrete optimization problems and (2) the other with specific applications. The first chapter of this volume, written by H. Paul Williams, can be regarded as a basic introduction of how to model discrete optimization problems as mixed integer problems, and outlines the main methods of solving them. In the second part of the book various real life applications are presented, most of them formulated as mixed integer linear or nonlinear programming problems. These applications include network problems, constant logic problems, many engineering problems, computer design, finance problems, medical diagnosis and medical treatment problems, applications of the Genome project, an array of transportation scheduling problems, and other applications. Further information including a detailed Table of Contents and Preface can be found and examined on the Handbook's web page at http://www.springer.com/0-387-32941-2.

Table of Contents

List of Figures	ix
List of Tables	xiii
Contributing Authors	xv
Preface	xix
Acknowledgments	xxii
Part 1 Methods
1 The Formulation and Solution of Discrete Optimisation Models	3	(36)
H. Paul Williams
1. The Applicability of Discrete Optimisation	3	(1)
2. Integer Programming	4	(1)
3. The Uses of Integer Variables	5	(4)
4. The Modelling of Common Conditions	9	(2)
5. Reformulation Techniques	11	(11)
6. Solution Methods	22	(14)
References	36	(3)
2 Cuntinuous Approaches for Solving Discrete Optimization Problems	39	(22)
Panos M. Pardalos, Oleg A. Prokopyev and Stanislav Busygin
1. Introduction	39	(1)
2. Equivalence of Mixed Integer and Complementarity Problems	40	(2)
3. Continuous Formulations for 0-1 Programming Problems	42	(1)
4. The Maximum Clique and Related Problems	43	(5)
5. The Satisfiability Problem	48	(3)
6. The Steiner Problem in Graphs	51	(1)
7. Semidefinite Programming Approaches	52	(2)
8. Minimax Approaches	54	(1)
References	55	(6)
3 Logic-Based Modeling	61	(42)
John N. Hooker
1. Solvers for Logic-Based Constraints	63	(1)
2. Good Formulations	64	(5)
3. Propositional Logic	69	(8)
4. Cardinality Formulas	77	(6)
5. 0-1 Linear Inequalities	83	(2)
6. Cardinality Rules	85	(2)
7. Mixing Logical and Continuous Variables	87	(5)
8. Additional Global Constraints	92	(5)
9. Conclusion	97	(2)
References	99	(4)
4 Modelling for Feasibility - the case of Mutually Orthogonal Latin Squares Problem	103	(26)
Gautam Appa, Dimitris Magos, Ioannis Mourtos and Leonidas Pitsoulis
1. Introduction	104	(2)
2. Definitions and notation	106	(2)
3. Formulations of the kMOLS problem	108	(14)
4. Discussion	122	(3)
References	125	(4)
5 Network Modelling	129	(22)
Douglas R. Shier
1. Introduction	129	(1)
2. Transit Networks	130	(3)
3. Amplifier Location	133	(1)
4. Site Selection	134	(3)
5. Team Elimination in Sports	137	(2)
6. Reasoning in Artificial Intelligence	139	(2)
7. Ratio Comparisons in Decision Analysis	141	(3)
8. DNA Sequencing	144	(2)
9. Computer Memory Management	146	(2)
References	148	(3)
6 Modeling and Optimization of Vehicle Routing Problems	151	(44)
Jean-Francois Cordeau and Gilbert Laporte
1. Introduction	151	(1)
2. The Vehicle Routing Problem	152	(11)
3. The Chinese Postman Problem	163	(5)
4. Constrained Arc Routing Problems	168	(13)
5. Conclusions	181	(1)
References	181	(14)
Part II Applications
7 Radio Resource Management	195	(32)
Katerina Papadaki and Vasilis Friderikos
1. Introduction	196	(3)
2. Problem Definition	199	(4)
3. Myopic Problem Formulations	203	(5)
4. The dynamic downlink problem	208	(14)
5. Concluding Remarks	222	(2)
References	224	(3)
8 Strategic and tactical planning models for supply chain: an application of stochastic mixed integer programming	227	(38)
Gautam Mitra, Chandra Poojari and Suvrajeet Sen
1. Introduction and Background	228	(6)
2. Algorithms for stochastic mixed integer programs	234	(3)
3. Supply chain planning and management	237	(7)
4. Strategic supply chain planning: a case study	244	(15)
5. Discussion and conclusions	259	(1)
References	260	(5)
9 Logic Inference and a Decomposition Algorithm for the Resource-Constrained Scheduling of Testing Tasks in the Development of New Pharmaceutical and Agrochemical Products	265	(26)
Christos T. Maravelias and Ignacio E. Grossmann
1. Introduction	266	(1)
2. Motivating Example	266	(2)
3. Model	268	(3)
4. Logic Cuts	271	(6)
5. Decomposition Heuristic	277	(4)
6. Computational Results	281	(1)
7. Example	281	(1)
8. Conclusions	282	(1)
9. Nomenclature	283	(1)
10. Acknowledgment	284	(1)
References	284	(1)
Appendix: Example Data	285	(6)
10 A Mixed-integer Nonlinear Programming Approach to the Optimal Planning of Offshore Oilfield Infrastructures	291	(1)
Susara A. van den Heever and Ignacio E. Grossmann
1. Introduction	291	(3)
2. Problem Statement	294	(1)
3. Model	295	(6)
4. Solution Strategy	301	(5)
5. Example	306	(3)
6. Conclusions and Future Work	309	(2)
7. Acknowledgment	311	(1)
8. Nomenclature	312	(2)
References	314	(3)
11 Radiation Treatment Planning: Mixed Integer Programming Formulations and Approaches	317	(1)
Michael C. Ferris, Robert R. Meyer and Warren D'Souza
1. Introduction	318	(3)
2. Gamma Knife Radiosurgery	321	(6)
3. Brachytherapy Treatment Planning	327	(4)
4. IMRT	331	(5)
5. Conclusions and Directions for Future Research	336	(1)
References	336	(5)
12 Multiple Hypothesis Correlation in Track-to-Track Fusion Management	341	(3)
Aubrey B. Poore, Sabino M. Gadaleta and Benjamin J. Slocumb
1. Track Fusion Architectures	344	(3)
2. The Frame-to-Frame Matching Problem	347	(3)
3. Assignment Problems for Frame-to-Frame Matching	350	(10)
4. Computation of Cost Coefficients using a Batch Methodology.	360	(8)
5. Summary	368	(1)
References	369	(4)
13 Computational Molecular Biology	373	(1)
Giuseppe Lancia
1. Introduction	373	(4)
2. Elementary Molecular Biology Concepts	377	(4)
3. Alignment Problems	381	(20)
4. Single Nucleotide Polymorphisms	401	(5)
5. Genome Rearrangements	406	(6)
6. Genomic Mapping and the TSP	412	(3)
7. Applications of Set Covering	415	(2)
8. Conclusions	417	(1)
References	418	(9)
Index	427