Applied Integer Programming

Name: Applied Integer Programming | Modeling and Solution
Brand: Wiley
Price: 133.99 EUR
Availability: OnlineOnly

Modeling and Solution

Der-San Chen Robert G. Batson Yu Dang(Autor*in)

Wiley (Verlag)

Erschienen am 9. September 2011

468 Seiten

E-Book

PDF mit Adobe-DRM

Systemvoraussetzungen

978-1-118-16599-7 (ISBN)

133,99 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Adobe-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

An accessible treatment of the modeling and solution of integerprogramming problems, featuring modern applications andsoftware In order to fully comprehend the algorithms associated withinteger programming, it is important to understand not onlyhow algorithms work, but also why they work.Applied Integer Programming features a unique emphasis onthis point, focusing on problem modeling and solution usingcommercial software. Taking an application-oriented approach, thisbook addresses the art and science of mathematical modeling relatedto the mixed integer programming (MIP) framework and discusses thealgorithms and associated practices that enable those models to besolved most efficiently. The book begins with coverage of successful applications,systematic modeling procedures, typical model types, transformationof non-MIP models, combinatorial optimization problem models, andautomatic preprocessing to obtain a better formulation. Subsequentchapters present algebraic and geometric basic concepts of linearprogramming theory and network flows needed for understandinginteger programming. Finally, the book concludes with classical andmodern solution approaches as well as the key components forbuilding an integrated software system capable of solvinglarge-scale integer programming and combinatorial optimizationproblems. Throughout the book, the authors demonstrate essential conceptsthrough numerous examples and figures. Each new concept oralgorithm is accompanied by a numerical example, and, whereapplicable, graphics are used to draw together diverse problems orapproaches into a unified whole. In addition, features of solutionapproaches found in today's commercial software are identifiedthroughout the book. Thoroughly classroom-tested, Applied Integer Programmingis an excellent book for integer programming courses at theupper-undergraduate and graduate levels. It also serves as awell-organized reference for professionals, software developers,and analysts who work in the fields of applied mathematics,computer science, operations research, management science, andengineering and use integer-programming techniques to model andsolve real-world optimization problems.

Rezensionen / Stimmen

"Thoroughly classroom-tested, Applied integer programming is an excellent book for integer programming courses at the upper-undergraduate and graduate levels." (Mathematical Reviews, 2011) "The book is intended as a textbook for an application oriented course for senior undergraduate or postgraduate students, mainly with an engineering, business school, or applied mathematics background. Each chapter comes with several exercises, solutions of which are provided in an appendix. Many figures illustrate the flow of algorithms and other concepts." (Zentralblatt MATH, 2010)

Weitere Details

Weitere Ausgaben

Personen

Inhalt

Intro
Applied Integer Programming: Modeling and Solution
CONTENTS
PREFACE
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.3.1 Knapsack Problem
2.3.2 Capital Budgeting Problem
2.4 Production Planning Problems
2.4.1 Uncapacitated Lot Sizing
2.4.2 Capacitated Lot Sizing
2.4.3 Just-in-Time Production Planning
2.5 Workforce/Staff Scheduling Problems
2.5.1 Scheduling Full-Time Workers
2.5.2 Scheduling Full-Time and Part-Time Workers
2.6 Fixed-Charge Transportation and Distribution Problems
2.6.1 Fixed-Charge Transportation
2.6.2 Uncapacitated Facility Location
2.6.3 Capacitated Facility Location
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.1.1 Truth Table of Boolean Operations
3.1.2 Basic Logical (Boolean) Operations on Variables
3.1.3 Multiple Boolean Operations on Variables
3.2 Transform Nonbinary to 0-1 Variable
3.2.1 Transform Integer Variable
3.2.2 Transform Discrete Variable
3.3 Transform Piecewise Linear Functions
3.3.1 Arbitrary Piecewise Linear Functions
3.3.2 Concave Piecewise Linear Cost Functions: Economy of Scale
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.6.1 Either/Or Constraints
3.6.2 p Out of m Constraints Must Hold
3.6.3 Disjunctive Constraint Sets
3.6.4 Negation of a Constraint
3.6.5 If/Then 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.3.1 Bounds on Continuous Variables
4.3.2 Bounds on General Integer Variables
4.3.3 Bounds on 0-1 Variables
4.3.4 Variable Fixing Redundant Constraints, and Infeasibility
4.4 Preprocessing Pure 0-1 Integer Programs
4.4.1 Fixing 0-1 Variables
4.4.2 Detecting Redundant Constraints And Infeasibility
4.4.3 Tightening Constraints (or Coefficients Reduction)
4.4.4 Generating Cutting Planes from Minimum Cover
4.4.5 Rounding by Division with GCD
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.2.1 Set Covering Problem
5.2.2 Set Partitioning and Set Packing
5.2.3 Set Covering in Networks
5.2.4 Applications of Set Covering Problem
5.3 Matching Problem
5.3.1 Matching Problems in Network
5.3.2 Integer Programming Formulation
5.4 Cutting Stock Problem
5.4.1 One-Dimensional Case
5.4.2 Two-Dimensional Case
5.5 Comparisons for Above Problems
5.6 Computational Complexity of COP
5.6.1 Problem Versus Problem Instance
5.6.2 Computational Complexity of an Algorithm
5.6.3 Polynomial Versus Nonpolynomial Function
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.2.1 Shortest Hamiltonian Paths
6.2.2 TSP with Repeated City Visits
6.2.3 Multiple Traveling Salesmen Problem
6.2.4 Clustered TSP
6.2.5 Generalized TSP
6.2.6 Maximum TSP
6.3 Applications of TSP
6.3.1 Machine Sequencing Problems in Various Manufacturing Systems
6.3.2 Sequencing Problems in Electronic Industry
6.3.3 Vehicle Routing for Delivery/Dispatching
6.3.4 Genome Sequencing for Genetic Study
6.4 Formulating Asymmetric TSP
6.4.1 Subtour Elimination by Dantzig-Fulkerson-Johnson Constraints
6.4.2 Subtour Elimination by Miller-Tucker-Zemlin (MTZ) Constraints
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.1.1 Euclidean Space
7.1.2 Linear and Convex Combinations
7.1.3 Linear Independence
7.1.4 Rank of a Matrix
7.1.5 Basis
7.1.6 Matrix Inversion
7.1.7 Determinant of a Matrix
7.1.8 Upper and Lower Triangular Matrices
7.2 Uses of Elementary Row Operations
7.2.1 Finding the Rank of a Matrix
7.2.2 Calculating the Inverse of a Matrix
7.2.3 Converting to a Triangular Matrix
7.2.4 Calculating the Determinant of a Matrix
7.2.5 Solving a System of Linear Equations
7.3 The Dual Linear Program
7.3.1 The Linear Program in Standard Form
7.3.2 Formulating the Dual Problem
7.3.3 Economic Interpretation of the Dual
7.3.4 Importance of the Dual
7.4 Relationships Between Primal and Dual Solutions
7.4.1 Relationships Between All Primal and All Dual Feasible Solutions
7.4.2 Relationship Between Primal and Dual Optimum Solutions
7.4.3 Relationships Between Each Complementary Pair of Variables at Optimum
7.5 Notes
7.6 Exercises
8 Linear Programming: Geometric Concepts
8.1 Geometric Solution
8.1.1 Objective Function
8.1.2 Solution Space
8.1.3 Requirement Space
8.2 Convex Sets
8.2.1 Convex Sets and Polyhedra
8.2.2 Directions of Unbounded Convex Sets
8.2.3 Convex and Polyhedral Cones
8.2.4 Convex and Concave Functions
8.3 Describing a Bounded Polyhedron
8.3.1 Representation by Extreme Points
8.3.2 Example Application of Representation Theorem
8.4 Describing Unbounded Polyhedron
8.4.1 Finding Extreme Direction Algebraically
8.4.2 Representing by Extreme Points and Extreme Directions
8.4.3 Example of Representation Theorem
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.2.1 Basic Feasible Solution
9.2.2 Adjacent Basic Feasible Solution
9.2.3 Reduced Costs
9.3 The Simplex Method
9.3.1 Better and Feasible Solution
9.3.2 Updating Simplex Tableau by Pivoting
9.3.3 Optimality Test
9.3.4 Initial Basic Feasible Solution
9.4 Interpreting the Simplex Tableau
9.4.1 Entire Simplex Tableau
9.4.2 Rows of Simplex Tableau
9.4.3 Columns of Simplex Tableau
9.4.4 Pivot Column and Pivot Row
9.4.5 Predicting the New Objective Value Before Updating
9.5 Geometric Interpretation of the Simplex Method
9.5.1 Basic Feasible Solution Versus Extreme Point
9.5.2 Explanation of "Simplex Method" Nomenclature
9.5.3 Identifying an Extreme Ray in a Simplex Tableau
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.2.1 The Minimum Cost Network Flow Problem
10.2.2 Formulating the Transportation-Assignment Problem as an MCNF Problem
10.2.3 Formulating the Transshipment Problem as an MCNF Problem
10.2.4 Formulating the Maximum Flow Problem as an MCNF Problem
10.2.5 Formulating the Shortest Path Problem as an MCNF Problem
10.3 Totally Unimodular Matrices
10.3.1 Definition
10.3.2 Sufficient Condition for a Totally Unimodular Matrix
10.3.3 Some Properties of Totally Unimodular Matrices
10.3.4 Matrix Structure of the MCNF Problem
10.3.5 Lower Triangular Matrix and Forward Substitution
10.3.6 Naturally Integer Solution for the MCNF Problem
10.4 The Network Simplex Method
10.4.1 Feasible Spanning Trees Versus Basic Feasible Solutions
10.4.2 The Network Algorithm
10.4.3 Numerical Example
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.1.1 Basic Concepts
11.1.2 Branch-and-Bound Algorithm
11.2 Cutting Plane Approach
11.2.1 Dual Cutting Plane Approach
11.2.2 Fractional Cutting Plane Method
11.2.3 Mixed Integer Cutting Plane Method
11.3 Group Theoretic Approach
11.3.1 Group Theory Terminology
11.3.2 Deriving the Group (Minimization) Problem
11.3.3 Formulating a Group Problem
11.3.4 Solving Group Problem as a Shortest Route Problem
11.3.5 Solving the Original Integer Program
11.4 Geometric Concepts
11.4.1 Various Polyhedrons in Original Space
11.4.2 Corner Polyhedron in Solution Space of Nonbasic Variables
11.5 Notes
11.6 Exercises
12 Branch-and-Cut Approach
12.1 Introduction
12.1.1 Basic Concept
12.1.2 Branch-and-Cut Algorithm
12.1.3 Generating Valid Cuts and Preprocessing
12.2 Valid Inequalities
12.2.1 Valid Inequalities for Linear Programs
12.2.2 Valid Inequalities for Integer Programs
12.2.3 Types of Valid Inequalities
12.3 Cut Generating Techniques
12.3.1 Rounding Technique
12.3.2 Disjunction Technique
12.3.3 Lifting Technique
12.4 Cuts Generated from Sets Involving Pure Integer Variables
12.4.1 Gomory Fractional Cut
12.4.2 Chvátal-Gomory Cut
12.4.3 Pure Integer Rounding Cut
12.4.4 Objective Integrality Cut
12.5 Cuts Generated from Sets Involving Mixed Integer Variables
12.5.1 Gomory Mixed Integer Cut
12.5.2 Mixed Integer Rounding Cut
12.6 Cuts Generated from 0-1 Knapsack Sets
12.6.1 Knapsack Cover
12.6.2 Lifted Knapsack Cover
12.6.3 GUB Cover
12.7 Cuts Generated from Sets Containing 0-1 Coefficients and 0-1 Variables
12.8 Cuts Generated from Sets with Special Structures
12.8.1 Flow Cover from Fixed-Charge Flow Network
12.8.2 Plant/Facility Location (Fixed-Charge Transportation)
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.3.1 Conventional Formulation
13.3.2 Column Generation Formulation
13.3.3 Initial Solution
13.4 GAP Example
13.4.1 GAP Branching Scheme
13.4.2 Tailing-Off Effect of Column Generation
13.4.3 Treatment of Identical Machines
13.4.4 Branch-and-Price Algorithm
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.2.1 Better Formulation by Preprocessing
14.2.2 LP-Based Branch-and-Bound Framework
14.2.3 Heuristics for Tightening Lower Bounds
14.2.4 Relaxations for Tightening Upper Bounds
14.2.5 Strong Cuts for Tightening Solution Polyhedron
14.3 Primal Solution via Heuristics
14.3.1 Local Search Approaches
14.3.2 Artificial Intelligence Approaches
14.4 Dual Solution via Relaxation
14.4.1 Linear Programming Relaxation
14.4.2 Combinatorial Relaxation
14.4.3 Lagrangian Relaxation
14.5 Lagrangian Dual
14.5.1 Lagrangian Dual in LP
14.5.2 Lagrangian Dual in IP
14.5.3 Properties of the 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.2.1 Solvers
15.2.2 Presolvers
15.2.3 Modeling Languages
15.2.4 User's Options/Intervention
15.2.5 Data and Application Interfaces
15.3 The AMPL Modeling Language
15.3.1 Components of the AMPL Modeling Language
15.3.2 An AMPL Example: the Diet Problem
15.3.3 Enhanced AMPL Modeling Techniques
15.3.4 AMPL Compatible MIP Solvers
15.4 LINGO Modeling Language
15.4.1 Prescription of Tolerances
15.4.2 Presolver-Automatic Problem Reduction
15.4.3 Solvers for Linear/Integer Programming
15.4.4 Interfacing with the User
15.4.5 LINGO Modeling Conventions
15.4.6 LINGO Model for the Diet Problem
15.5 MPL Modeling Language
15.5.1 MPL Modeling Conventions
15.5.2 MPL Model for the Diet Problem
15.5.3 MPL Compatible MIP Solvers
REFERENCES
APPENDIX: ANSWERS TO SELECTED EXERCISES
INDEX

Inhalt (PDF)

Systemvoraussetzungen

Als PDF speichern Als Link merken