Librería Portfolio

Features

Reflects more modern approaches and new applications
Extends prototype examples to more realistic settings
Introduces the elementary theory of linear and integer optimization
Uses real-world case studies to illustrate application of the theory
Summary

Presenting a strong and clear relationship between theory and practice, Linear and Integer Optimization: Theory and Practice is divided into two main parts. The first covers the theory of linear and integer optimization, including both basic and advanced topics. Dantzig's simplex algorithm, duality, sensitivity analysis, integer optimization models, and network models are introduced.

More advanced topics also are presented including interior point algorithms, the branch-and-bound algorithm, cutting planes, complexity, standard combinatorial optimization models, the assignment problem, minimum cost flow, and the maximum flow/minimum cut theorem.

The second part applies theory through real-world case studies. The authors discuss advanced techniques such as column generation, multiobjective optimization, dynamic optimization, machine learning (support vector machines), combinatorial optimization, approximation algorithms, and game theory.

Besides the fresh new layout and completely redesigned figures, this new edition incorporates modern examples and applications of linear optimization. The book now includes computer code in the form of models in the GNU Mathematical Programming Language (GMPL). The models and corresponding data files are available for download and can be readily solved using the provided online solver.

This new edition also contains appendices covering mathematical proofs, linear algebra, graph theory, convexity, and nonlinear optimization. All chapters contain extensive examples and exercises. This textbook is ideal for courses for advanced undergraduate and graduate students in various fields including mathematics, computer science, industrial engineering, operations research, and management science.



Table of Contents

Basic Concepts of Linear Optimization
The Company Dovetail
Definition of an LO-Model
Alternatives of the Standard LO-Model
Solving LO-Models Using a Computer Package
Linearizing Nonlinear Functions
Examples of Linear Optimization Models
Building and Implementing Mathematical Models
Exercises

LINEAR OPTIMIZATION THEORY: BASIC TECHNIQUES

Geometry and Algebra of Feasible Regions
The Geometry of Feasible Regions
Algebra of Feasible Regions; Feasible Basic Solutions
Exercises

Dantzig's Simplex Algorithm
From Vertex to Vertex to an Optimal Solution
LO-Model Reformulation
The Simplex Algorithm
Simplex Tableaus
Discussion of the Simplex Algorithm
Initialization
Uniqueness and Multiple Optimal Solutions
Models with Equality Constraints
The Revised Simplex Algorithm
Exercises

Duality, Feasibility, and Optimality
The Companies Dovetail and Salmonnose
Duality and Optimality
Complementary Slackness Relations
Infeasibility and Unboundedness; Farkas' Lemma
Primal and Dual Feasible Basic Solutions
Duality and the Simplex Algorithm
The Dual Simplex Algorithm
Exercises

Sensitivity Analysis
Sensitivity of Model Parameters
Perturbing Objective Coefficients
Perturbing Right Hand Side Values (Nondegenerate Case)
Piecewise Linearity of Perturbation Functions
Perturbation of the Technology Matrix
Sensitivity Analysis for the Degenerate Case
Shadow Prices and Redundancy of Equality Constraints
Exercises

Large-Scale Linear Optimization
The Interior Path
Formulation of the Interior Path Algorithm
Convergence to the Interior Path; Maintaining Feasibility
Termination and Initialization
Exercises

Integer Linear Optimization
Introduction
The Branch-and-Bound Algorithm
Linearizing Logical Forms with Binary Variables
Gomory's Cutting-Plane Algorithm
Exercises

Linear Network Models
LO-Models with Integer Solutions; Total Unimodularity
ILO-Models with Totally Unimodular Matrices
The Network Simplex Algorithm
Exercises

Computational Complexity
Introduction to Computational Complexity
Computational Aspects of Dantzig's Simplex Algorithm
The Interior Path Algorithm Has Polynomial Running Time
Computational Aspects of the Branch-and-Bound Algorithm
Exercises

LINEAR OPTIMIZATION PRACTICE: ADVANCED TECHNIQUES

Designing a Reservoir for Irrigation
The Parameters and the Input Data
Maximizing the Irrigation Area
Changing the Input Parameters of the Model
GMPL Model Code
Exercises

Classifying Documents by Language
Machine Learning
Classifying Documents Using Separating Hyperplanes
LO-Model for Finding Separating Hyperplane
Validation of a Classifier
Robustness of Separating Hyperplanes; Separation Width
Models that Maximize the Separation Width
GMPL Model Code
Exercises

Production Planning; A Single Product Case
Model Description
Regular Working Hours
Overtime
Allowing Overtime and Idle Time
Sensitivity Analysis
GMPL Model Code
Exercises

Production of Coffee Machines
Problem Setting
An LO-Model that Minimizes Backlogs
Old and Recent Backlogs
Full Week Productions
Sensitivity Analysis
GMPL Model Code
Exercises

Conflicting Objectives: Producing Versus Importing
Problem Description and Input Data
Modeling Two Conflicting Objectives; Pareto Optimal Point
Goal Optimization for Conflicting Objective
Soft and Hard Constraints
Sensitivity Analysis
Alternative Solution Techniques
A Comparison of the Solutions
GMPL Model Code
Exercises

Coalition Formation and Profit Distribution
The Farmers Cooperation Problem
Game Theory; Linear Production Games
How to Distribute the Total Profit Among the Farmers?
Profit Distribution for Arbitrary Numbers of Farmers
Sensitivity Analysis
Exercises

Minimizing Trimloss When Cutting Cardboard
Formulating the Problem
Gilmore-Gomory's Solution Algorithm
Calculating an Optimal Solution
Exercises

Off-Shore Helicopter Routing
Problem Description
Vehicle Routing Problems
Problem Formulation
ILO Formulation
Column Generation
Dual Values as Price Indicators for Crew Exchanges
A Round-Off Procedure for Determining an Integer Solution
Computational Experiments
Sensitivity Analysis
Exercises

The Catering Service Problem
Formulation of the Problem
The Transshipment Problem Formulation
Applying the Network Simplex Algorithm
Sensitivity Analysis
GMPL Model Code
Exercises

Appendix A Mathematical Proofs
Appendix B Linear Algebra
Appendix C Graph Theory
Appendix D Convexity
Appendix E Nonlinear Optimization
Appendix F Writing LO-Models in GNU MathProg (GMPL)