LINEAR PROGRAMMING by James P. Ignizio and Tom M. Cavalier Prentice Hall International Series in Industrial and Systems Engineering Prentice Hall, Englewood Cliffs, NJ, 666pp (1994). ISBN 0-13-183757-5

TABLE OF CONTENTS

• CHAPTER 1: INTRODUCTION AND OVERVIEW
  

PART 1: CONVENTIONAL LINEAR PROGRAMMING

• CHAPTER 2: THE (CONVENTIONAL) LINEAR PROGRAMMING MODEL
  
• CHAPTER 3: FOUNDATIONS OF THE SIMPLEX METHOD
  
• CHAPTER 4: THE SIMPLEX METHOD: TABLEAU AND COMPUTATION
  
• CHAPTER 5: SPECIAL SIMPLEX IMPLEMENTATIONS
  
• CHAPTER 6: DUALITY AND SENSITIVITY ANALYSIS
  
• CHAPTER 7: ALTERNATIVES TO THE SIMPLEX ALGORITHM
  
• CHAPTER 8: APPLICATIONS OF LP IN INFORMATION TECHNOLOGY
  

PART 2: NETWORK AND INTEGER MODELS

• CHAPTER 9: THE NETWORK SIMPLEX METHOD
  
• CHAPTER 10: THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
  
• CHAPTER 11: INTEGER PROGRAMMING
  
• CHAPTER 12: HEURISTIC PROGRAMMING - AND AI
  

PART 3: MULTIOBJECTIVE OPTIMIZATION

• CHAPTER 13: MULTIOBJECTIVE OPTIMIZATION
  
• CHAPTER 14: MULTIOBJECTIVE MODELS
  
• CHAPTER 15: MULTIPLEX ALGORITHM
  
• CHAPTER 16: DUALITY AND SENSITIVITY ANALYSIS IN LINEAR MULTIPLEX
  
• CHAPTER 17: EXTENSIONS OF MULTIPLEX
  

• APPENDIX: LINEAR ALGEBRA REVIEW
  

1. INTRODUCTION AND OVERVIEW

• The Linear Decision Model
• What is Linear Programming? A Preview
• Purpose
• Applications of Linear Programming: A Preview
• Traditional Applications
• Applications in Artificial Intelligence and Information
• Technology
• Dealing with Problems of Sizes and Complexity
• Beyond the Capabilities of Linear Programming
• Intended Audience and Prerequisites
• What is Different About This Text?
• Overview of Material to Follow
• Course Structure Recommendations
  




PART 1: CONVENTIONAL LINEAR PROGRAMMING


2. THE (CONVENTIONAL) LINEAR PROGRAMMING MODEL
• Chapter Overview
• Models and Model Types
• General Guidelines in Model Building
• Definitions
• Basic Steps in Linear Programming Model Formulation
• Determination of the Decision Variables
• Formulation of the Objective
• Formulation of the Constraints
• The General Form of the Linear Programming Model
• Assumptions of the Linear Programming Model
• Examples of Linear Programming Model Formulation
• Model Validity
• An Evaluation of Model Structure
• An Evaluation of Model Logic
• An Evaluation of the Design and/or Input Data
• An Evaluation of Model Response
• Summary
• Exercises




3. FOUNDATIONS OF THE SIMPLEX METHOD
• Chapter Overview
• Converting a Linear Program into Standard Form
• Constraint Conversion
• The Objective Function
• Notation and Definitions
• Graphical Solution of 2-dimensional Linear Programs
• Convex Sets and Polyhedral Sets
• Extreme Points, Extreme Directions, and Optimality
• Basic Feasible Solutions and Extreme Points
• Summary
• Exercises




4. THE SIMPLEX METHOD: TABLEAU AND COMPUTATION
• Chapter Overview
• Algebra of the Simplex Method
• Checking for Optimality
• Determining the Entering Variable
• Determining the Departing Variable
• Optimality Conditions and Directions
• Checking for an Unbounded Objective
• The Simplex Method in Tableau Form
• Identifying B^-1 from the Simplex Tableau
• Finding and Initial Basic Feasible Solution
• The Two-Phase Method
• The Big-M Method
• Unrestricted Variables and Variables with Negative Lower Bounds
• Degeneracy and Cycling
• The Lexicographic Minimum Ratio Test and Finite Convergence
• Summary
• Exercises




5. SPECIAL SIMPLEX IMPLEMENTATIONS
• Chapter Overview
• The Revised Simplex Method
• Suboptimization
• The Product Form of the Inverse
• Operations with Elementary Matrices
• The Bounded Variables Simplex Method
• Checking for Optimality
• Determining the Entering Variable
• Increasing a Nonbasic Variable x_k from Its Lower Bound l_k
• Decreasing a Nonbasic Variable x_k from Its Upper Bound l_k
• Decomposition
• Summary
• Exercises




6. DUALITY AND SENSITIVITY ANALYSIS
• Chapter Overview
• Formulation of the Linear Programming Dual
• The Canonical Form of the Dual
• General Duality
• The Standard Form
• Relationships in Duality
• Primal-Dual Tableau Relationships
• Complementary Slackness
• Geometric Interpretation of Optimality Conditions
• Economic Interpretation of the Dual
• The Dual Variables as Rates of Change
• The Dual Simplex Algorithm
• An Extended Dual Simplex Algorithm
• Sensitivity Analysis in Linear Programming
• Changes in the Objective Coefficients
• Changes in the Right-Hand Side
• Changes in the Technological Coefficients, a_i,j
• Addition of a New Variable
• Addition of a New Constraint
• Parametric Programming
• Systemic Variation of the Cost Vector c
• Systemic Variation of the Right-Hand Side Vector b
• Resource Values and Ranges
• Objective Coefficients and Ranges
• Summary
• Exercises




7. ALTERNATIVES TO THE SIMPLEX ALGORITHM
• Chapter Overview
• Computational Complexity
• Khachian's Ellipsoid Algorithm
• Affine Scaling Algorithms
• A Primal Affine Scaling Algorithm
• Finding an Initial Strictly Positive Solution
• Karmarkar's Projective Algorithm
• Summary
• Exercises




8. APPLICATIONS OF LP IN INFORMATION TECHNOLOGY
• Chapter Overview
• Problem Types
• Methods in Information Technology
• Prediction via Linear Programming
• Pattern Classification via LP
• Enhanced Approached to Pattern Classification
• Baek & Ignizio Algorithm for Pattern Classification
• Other Modifications
• Cluster Analysis via Mathematical Programming
• Input-Output Analysis and LP
• Simulation of Continuous Processing Systems
• Summary and Conclusions
• Exercises




PART 2: NETWORK AND INTEGER MODELS


9. THE NETWORK SIMPLEX METHOD
• Chapter Overview
• Network Terminology
• Minimum Cost Network Flow Problems
• Bases and Rooted Spanning Trees
• Unimodularity
• The Network Simplex Method
• Brief Review of the Standard Primal Simplex Method
• Computing the Flows
• Checking for Optimality and Choosing the Entering Arc
• Determining the Departing Arc
• Finding an Initial Basic Feasible Solution
• Degeneracy and Cycling
• Strongly Feasible Trees
• Network Flow Problems with Bounds on the Flows
• Determining the Entering Variable
• Increasing the Flow on a Nonbasic Arc from Its Lower Bound
• Decreasing the Flow on a Nonbasic Arc from Its Upper Bound
• Applications
• Summary
• Exercises




10. THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
• Chapter Overview
• The Transportation Problem
• Properties of the Coefficient Matrix
• Feasibility of the Model
• Finiteness of the Objective Value
• Finding and Initial Basic Feasible Solution
• Optimality Conditions
• Determining the Dual Solution
• Checking for Optimality
• Determining the Departing Variable
• The Assignment Problem
• The Dual Problem and Complementary Slackness
• A Basic Primal-Dual Strategy
• Choosing an Initial Dual Feasible Solution
• Identifying an Assignment Corresponding to a Reduced Matrix
• Modifying the Dual Solution and the Reduced Matrix
• Summary
• Exercises




11. INTEGER PROGRAMMING
• Chapter Overview
• Introduction
• Graphical Solution of 2-Dimensional Integer Programs
• Computational Complexity
• Formulating Integer Programing Problems
• The Knapsack Problem
• The Set Covering Problem
• The Fixed-Charge Problem
• The Traveling Salesman Problem
• Either-Or Constraints
• P out of M Constraints
• Representing General Integer Variables Using Zero-One Variables
• Transforming a Piecewise Linear Function
• Branch-and-Bound Enumeration
• Branching
• Computing Bounds
• Fathoming
• Search Strategies
• Implicit Enumeration
• The Zero Completion at a Node
• The Infeasibility Test
• Refinements
• Cutting Plane Methods
• Dual Fractional Cuts for Pure Integer Programs
• Summary
• Exercises




12. HEURISTIC PROGRAMMING - AND AI
• Chapter Overview
• Terminology and Definitions
• Attitudes, Opinions, and AI
• Fundamental Heuristics Types
• The Add-Drop Heuristic Programming Method for Cluster Analysis/Site Location
• Observations and Extensions
• The Exchange Heuristic Programming Method for Cluster Analysis/Site Location
• Observations and Extensions
• A Heuristic Program for Scheduling and Deployment Problems
• Extensions to Problems of Deployment
• A Heuristic Program for Minimal Conflict Scheduling
• Genetic "Algorithms"
• Some Observations
• Tabu Search, Simulated Annealing, Expert Systems, and Neural Networks
• Tabu Search
• Simulated Annealing
• Expert Systems
• Neural Networks
• Assessment of Heuristic Programming Methods
• Summary and Conclusions
• Exercises




PART 3: MULTIOBJECTIVE OPTIMIZATION


13. MULTIOBJECTIVE OPTIMIZATION
• Chapter Overview
• The Familiar Versus the the Nonconventional
• An Illustrative Example
• Conversion of a Linear Program via Objective Function Transformation (or Deletion)
• Conversion to a Linear Program via Utility Theory: A Method of Aggregation
• Conversion to a Goal Program
• Conversion to a Chebyshev Goal Program
• The Generating Method: The (Nearly) Perfect Approach
• The Lexicographic Vectormax (Vectormin) Approach
• Interactive Methods
• Myths and Misconceptions
• The Multiplex Approach: A Preview
• Overview of Material to Follow
• Summary
• Exercises




14. MULTIOBJECTIVE MODELS
• Chapter Overview
• Terminology
• Modeling Basics
• The Weighting of Objectives
• The Establishment of Aspiration Levels
• The Processing of Goals
• The Weighting of Unwanted Goal Deviations
• The Ranking of Goals and/or Objectives
• Scaling and Normalization of Goals
• The Development of an Achievement Vector
• Multiplex Formulations
• Multiplex Model: Linear Programs
• Multiplex Model: Archimedean Linear Goal Programs
• Multiplex Model: Non-Archimedean Linear Goal Programs
• Multiplex Model: Chebyshev and Fuzzy Linear Goal Programs
• Multiplex Model: Linear Lexicographic Vectormin Problems
• Good and Poor Modeling Practices
• Summary
• Exercises




15. MULTIPLEX ALGORITHM
• Chapter Overview
• Reduced form of the Multiplex Model
• Basic Solutions and Basic Feasible Solutions
• Associated Conditions
• Revised Multiplex Algorithm
• Algorithm Steps
• Explicit Form of the Inverse: Tableau Representation
• Sequential Multiplex
• The Sequential Algorithm: For Linear Multiplex
• Observations
• Computational Considerations
• Summary
• Exercises




16. DUALITY AND SENSITIVITY ANALYSIS IN LINEAR MULTIPLEX
• Chapter Overview
• The Formulation of the Multidimensional Dual
• Economic Interpretation
• MDD Algorithms
• The General MDD Algorithm
• The Restricted MDD Algorithm
• Sensitivity Analysis in Linear Multiplex
• Discrete Sensitivity Analysis
• Range Analysis
• Sensitivity Analysis in Sequential Linear Multiplex
• Summary
• Exercises




17. EXTENSIONS OF MULTIPLEX
• Chapter Overview
• Integer Models
• Nonlinear Models
• Intelligent Interfaces
• Summary and Conclusions
  




APPENDIX: LINEAR ALGEBRA REVIEW

• Vectors
• Vector Addition
• Multiplication of a Vector by a Scalar
• Vector Multiplication
• Norm of a Vector
• Special Vector Types
• Linear Dependence and Independence
• Spanning Sets and Bases
• Matrices
• Matrix Addition
• Multiplication by a Scalar
• Matrix Multiplication
• Special Matrices
• Determinants
• The Inverse of a Matrix
• The Rank of a Matrix
• The Solution of Simultaneous Linear Equations
• A Unique Solution of Ax = b
• An Infinite Number of Solutions to Ax = b