Название:Applied Integer Programming: Modeling and Solution
Автор Der-San Chen, Robert G. Batson, Yu Dang
Издательство: WILEY
Год: 2015
Страниц:488
Язык: English
Формат: pdf
Размер: 12 Mb
An accessible treatment of the modeling and solution of integer programming problems, featuring modern applications and software
In order to fully comprehend the algorithms associated with integer programming, it is important to understand not only how algorithms work, but also why they work. Applied Integer Programming features a unique emphasis on this point, focusing on problem modeling and solution using commercial software. Taking an application-oriented approach, this book addresses the art and science of mathematical modeling related to the mixed integer programming (MIP) framework and discusses the algorithms and associated practices that enable those models to be solved most efficiently.
The book begins with coverage of successful applications, systematic modeling procedures, typical model types, transformation of non-MIP models, combinatorial optimization problem models, and automatic preprocessing to obtain a better formulation. Subsequent chapters present algebraic and geometric basic concepts of linear programming theory and network flows needed for understanding integer programming. Finally, the book concludes with classical and modern solution approaches as well as the key components for building an integrated software system capable of solving large-scale integer programming and combinatorial optimization problems.
Throughout the book, the authors demonstrate essential concepts through numerous examples and figures. Each new concept or algorithm is accompanied by a numerical example, and, where applicable, graphics are used to draw together diverse problems or approaches into a unified whole. In addition, features of solution approaches found in today's commercial software are identified throughout the book.
Thoroughly classroom-tested, Applied Integer Programming is an excellent book for integer programming courses at the upper-undergraduate and graduate levels. It also serves as a well-organized reference for professionals, software developers, and analysts who work in the fields of applied mathematics, computer science, operations research, management science, and engineering and use integer-programming techniques to model and solve real-world optimization problems.
Table of ContentsPREFACE.
PART I MODELING.
1 Introduction.
1.1 Integer Programming.
1.2 Standard Versus Nonstandard Forms.
1.3 Combinatorial Optimization Problems.
1.4 Successful Integer Programming Applications.
1.5 Text Organization and Chapter Preview.
1.6 Notes.
1.7 Exercises.
2 Modeling and Models.
2.1 Assumptions on Mixed Integer Programs.
2.2 Modeling Process.
2.3 Project Selection Problems.
2.4 Production Planning Problems.
2.5 Workforce/Staff Scheduling Problems.
2.6 Fixed-Charge Transportation and Distribution Problems.
2.7 Multicommodity Network Flow Problem.
2.8 Network Optimization Problems with Side Constraints.
2.9 Supply Chain Planning Problems.
2.10 Notes.
2.11 Exercises.
3 Transformation Using 0–1 Variables.
3.1 Transform Logical (Boolean) Expressions.
3.2 Transform Nonbinary to 0–1 Variable.
3.3 Transform Piecewise Linear Functions.
3.4 Transform 0–1 Polynomial Functions.
3.5 Transform Functions with Products of Binary and Continuous Variables: Bundle Pricing Problem.
3.6 Transform Nonsimultaneous Constraints.
3.7 Notes.
3.8 Exercises.
4 Better Formulation by Preprocessing.
4.1 Better Formulation.
4.2 Automatic Problem Preprocessing.
4.3 Tightening Bounds on Variables.
4.4 Preprocessing Pure 0–1 Integer Programs.
4.5 Decomposing a Problem into Independent Subproblems.
4.6 Scaling the Coefficient Matrix.
4.7 Notes.
4.8 Exercises.
5 Modeling Combinatorial Optimization Problems I.
5.1 Introduction.
5.2 Set Covering and Set Partitioning.
5.3 Matching Problem.
5.4 Cutting Stock Problem.
5.5 Comparisons for Above Problems.
5.6 Computational Complexity of COP.
5.7 Notes.
5.8 Exercises.
6 Modeling Combinatorial Optimization Problems II.
6.1 Importance of Traveling Salesman Problem.
6.2 Transformations to Traveling Salesman Problem.
6.3 Applications of TSP.
6.4 Formulating Asymmetric TSP.
6.5 Formulating Symmetric TSP.
6.6 Notes.
6.7 Exercises.
PART II REVIEW OF LINEAR PROGRAMMING AND NETWORK FLOWS.
7 Linear Programming—Fundamentals.
7.1 Review of Basic Linear Algebra.
7.2 Uses of Elementary Row Operations.
7.3 The Dual Linear Program.
7.4 Relationships Between Primal and Dual Solutions.
7.5 Notes.
7.6 Exercises.
8 Linear Programming: Geometric Concepts.
8.1 Geometric Solution.
8.2 Convex Sets.
8.3 Describing a Bounded Polyhedron.
8.4 Describing Unbounded Polyhedron.
8.5 Faces, Facets, and Dimension of a Polyhedron.
8.6 Describing a Polyhedron by Facets.
8.7 Correspondence Between Algebraic and Geometric Terms.
8.8 Notes.
8.9 Exercises.
9 Linear Programming: Solution Methods.
9.1 Linear Programs in Canonical Form.
9.2 Basic Feasible Solutions and Reduced Costs.
9.3 The Simplex Method.
9.4 Interpreting the Simplex Tableau.
9.5 Geometric Interpretation of the Simplex Method.
9.6 The Simplex Method for Upper Bounded Variables.
9.7 The Dual Simplex Method.
9.8 The Revised Simplex Method.
9.9 Notes.
9.10 Exercises.
10 Network Optimization Problems and Solutions.
10.1 Network Fundamentals.
10.2 A Class of Easy Network Problems.
10.3 Totally Unimodular Matrices.
10.4 The Network Simplex Method.
10.5 Solution via LINGO.
10.6 Notes.
10.7 Exercises.
PART III SOLUTIONS.
11 Classical Solution Approaches.
11.1 Branch-and-Bound Approach.
11.2 Cutting Plane Approach.
11.3 Group Theoretic Approach.
11.4 Geometric Concepts.
11.5 Notes.
11.6 Exercises.
12 Branch-and-Cut Approach.
12.1 Introduction.
12.2 Valid Inequalities.
12.3 Cut Generating Techniques.
12.4 Cuts Generated from Sets Involving Pure Integer Variables.
12.5 Cuts Generated from Sets Involving Mixed Integer Variables.
12.6 Cuts Generated from 0–1 Knapsack Sets.
12.7 Cuts Generated from Sets Containing 0–1 Coefficients and 0–1 Variables.
12.8 Cuts Generated from Sets with Special Structures.
12.9 Notes.
12.10 Exercises.
13 Branch-and-Price Approach.
13.1 Concepts of Branch-and-Price.
13.2 Dantzig–Wolfe Decomposition.
13.3 Generalized Assignment Problem.
13.4 GAP Example.
13.5 Other Application Areas.
13.6 Notes.
13.7 Exercises.
14 Solution via Heuristics, Relaxations, and Partitioning.
14.1 Introduction.
14.2 Overall Solution Strategy.
14.3 Primal Solution via Heuristics.
14.4 Dual Solution via Relaxation.
14.5 Lagrangian Dual.
14.6 Primal–Dual Solution via Benders’ Partitioning.
14.7 Notes.
14.8 Exercises.
15 Solutions with Commercial Software.
15.1 Introduction.
15.2 Typical IP Software Components.
15.3 The AMPL Modeling Language.
15.4 LINGO Modeling Language.
15.5 MPL Modeling Language.
REFERENCES.
APPENDIX: ANSWERS TO SELECTED EXERCISES.
INDEX.
depositfiles.com
turbobit.net
Рейтинг: | 4.8 баллов / 2537 оценок |
Формат: | Книга |
Уже скачали: | 12746 раз |
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
«Сборник формул по математике», Цикунов А.Е. Сборник содержит формулы элементарной и высшей математики — арифметики и алгебры, геометрии и тригонометрии, векторной и линейной алгебры, дифференциальног . . .
Спутник партизанаГод выпуска: 1942Жанр: РуководствоИздательство: ДальгизФормат: DjVuКачество: Отсканированные страницыКоличество страниц: 358Описание:Партизаны заставляют немецких оккупантов быть все . . .
Оружие РоссииГод выпуска: 1997Жанр: каталог, том IV, вооружение и военная техника ракетных войск стратегического назначенияИздательство: Военный парадФормат: PDFКачество: Отсканированные страницыКолич . . .
« The Cuckoo's Calling »Автор: Robert GalbraithОписание:«A brilliant debut mystery in a classic vein: Detective Cormoran Strike investigates a supermodel's suicide. After losing his leg to a land mine . . .
БаффетологияГод выпуска: 2006Автор: Баффет М., Кларк Д.Издательство: ПопурриISBN: 985-483-684-3Формат: PDFКачество: Отсканированные страницыКоличество страниц: 415Описание: Эта книга не является очере . . .
В первой части книги Айнса «Обыкновенные дифференциальные уравнения» рассматриваются дифференциальные уравнения в вещественной области, во второй - в комплексной области. Изложены основные работы Штур . . .
Использование макросов в ExcelГод выпуска: 2004Автор: Стивен РоманИздательство: ПитерISBN: 5-94723-584-6Формат: djvuКачество: Отсканированные страницыКоличество страниц: 512--------------------------С . . .
«Дискретная математика. Алгоритмы и программы», Б.Н. Иванов. Книга посвящена современному курсу дискретной математики. Теоретические основы курса сопровождаются практически значимыми алгоритмами, реал . . .
Пушкин называл Анну Петровну Керн (1800-1879) «гением чистой красоты» и «вавилонской блудницей». Её обаяние, ум и душевные качества нашли многочисленных почитателей, от великого поэта до императора Ал . . .
«Развитие памяти для чайников», Арден Джон. Улучшить память может практически каждый человек, независимо от того, где он работает и чем занимается. О способах, используемых для облегчения механическог . . .
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Applied Integer Programming: Modeling and Solution 1st Edition. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.