Contents
|
‹ Previous
|
Next ›
|
Download EPUB
|
PDF
Contents
Sources and Attribution
Use of Generative AI
Notation
1 Mathematical Programming
1.1 Warm-Up Scenario
1.2 Why Study Operations Research?
1.3 What is Mathematical Programming?
1.4 Applications
1.5 Types of Optimization Problems
1.6 Linear Programming (LP)
1.7 Mixed-Integer Linear Programming (MILP)
1.8 Non-Linear Programming (NLP)
1.8.1 Convex Programming
1.8.2 Non-Convex Non-linear Programming
1.8.3 Machine Learning
1.9 Mixed-Integer Non-Linear Programming (MINLP)
1.9.1 Convex MINLP
1.9.2 Non-Convex MINLP
1.10 Optimization Under Uncertainty
1.10.1 Stochastic Optimization
1.10.2 Robust Optimization
1.10.3 Applications
1.11 Exercises
I Linear Programming
2 Modeling: Linear Programming
2.1 Introductory LP Example
2.2 Modeling and Assumptions in Linear Programming
2.2.1 Assumptions
2.3 Examples
2.3.1 Knapsack Problem
2.3.2 Capital Investment
2.3.3 Transportation problem
2.3.4 Assignment Problem
2.4 Exercises
3 Software - Excel
3.1 Using Excel Solver
3.1.1 Useful Excel Functions and Techniques
3.1.2 How to Use Excel Solver
3.2 Exercises
4 Modeling with Compact Notation
4.1 Production Planning Models
4.2 Assignment Problem
4.3 Modeling Tricks
4.3.1 Maximizing a minimum
4.4 Network Flow Models and Applications
4.4.1 Graphs
4.4.2 Example: Minimum-Cost Flow in a Transportation Network
4.4.3 Minimum Cost Network Flow Problem
4.4.4 (Unstructured) Minimum Cost Network Flow Problem
4.4.5 Maximum flow
4.4.6 Multi-Commodity Minimum Cost Network Flow with Integrality Constraints
4.4.7 Multicommodity Flow: Source–Sink Formulation
4.5 Transportation Problem
4.6 Multi-Period Capital Investment
4.7 Exercises
5 Graphically Solving Linear Programs
5.1 Nonempty and Bounded Problem
5.2 Graphical Approach
5.3 Infinitely Many Optimal Solutions
5.4 Problems with No Solution
5.5 Problems with Unbounded Feasible Regions
5.6 Exercises
Exercises
Solutions
5.7 Extreme Directions
6 Formal Mathematical Statements
6.1 Mathematical Preliminaries
6.1.1 Vectors and Their Properties
6.1.2 Linear Combinations and Related Concepts
6.2 Algebraic Proof - Exists Optimal Solution at a Vertex
6.3 Convexity
6.3.1 Convex Sets
6.3.2 Unbounded Sets and Rays
6.4 Exercises
7 Simplex Method
7.1 Standard Form
7.1.1 Converting to Standard Form
7.1.2 Basic Feasible Solutions for Standard Form
7.2 Canonical Form
7.2.1 Augmenting system and Phase 1
7.3 Pivoting and the Simplex Algorithm
7.3.1 Transforming the LP to Standard Form
7.3.2 Simplex Assuming Feasible Start
7.3.3 Summarizing the steps taken
7.4 The Simplex Algorithm!
7.4.1 Simplex Algorithm Execution
7.5 No Feasible Initial Basis and the Big-M Method
7.5.1 Big-M Method Algorithm
7.5.2 Detecting Infeasibility via the Big-M Method
7.5.3 A second example: two artificial variables
7.6 Degeneracy, Cycling, and Bland’s Rule
7.6.1 Degeneracy and Unchanged BFS after Pivoting
7.7 Cycling in the Simplex Method
7.7.1 Cycling in the Simplex Method
7.7.2 Bland’s Rule
7.8 Simplex and Unbounded LPs
7.9 Exercises
8 Simplex - Matrix Calculations
8.1 Solutions to
A
x
=
b
8.1.1 Partitioning the Variables
8.1.2 Another Example
8.1.3 Selecting and Evaluating Different Bases
8.2 Optimality Conditions
8.3 Exercises
9 Simplex Method in Tableau Form
9.1 Building the tableau
9.2 One pivot, three colors
9.3 Optimality and reading the solution
9.4 Artificial Variables and the Big-M Method
9.4.1 A problem with no slack-basis start
9.4.2 Detecting infeasibility in tableau form
9.5 Exercises
10 Sensitivity Analysis
10.1 What can change, and what happens
10.1.1 Changing an objective coefficient
c
i
10.1.2 Changing a right-hand side
b
i
10.1.3 Changing a constraint coefficient
a
i
j
10.1.4 Summary
10.2 Ranging the right-hand side
10.2.1 Perturbing
b
2
: A Basic Slack Variable
10.2.2 Perturbing
b
1
: A Nonbasic Slack Variable
10.2.3 Perturbing
b
3
: Another Nonbasic Slack Variable
10.3 Ranging the objective coefficients
10.3.1 Perturbing
c
1
: Objective Coefficient of
x
10.3.2 Perturbing
c
2
: Objective Coefficient of
y
10.3.3 Summary
10.4 Sensitivity with Matrix Notation
10.4.1 Ranging
b
1
with the Basis Inverse
10.4.2 Ranging
c
x
via Reduced Costs
10.5 Sensitivity Reports in Software
10.6 Exercises
11 Duality
11.1 Duality Theory
11.2 Primal-Dual Pairs and Strong Duality
11.2.1 Economic Interpretation of the Dual
11.3 Different Primal–Dual Forms
11.4 Exercises
11.5 Complementary Slackness
11.5.1 Definition of Complementary Slackness
11.5.2 Interpreting Complementary Slackness
11.5.3 Using Complementary Slackness to Solve Problems
11.5.4 Summary of Key Takeaways
11.6 Exercises
Summary: Why Learn Duality?
12 Software - Python
12.1 Why Python for Optimization?
12.1.1 The Power of Python
12.1.2 Jupyter Notebooks: A Data Analyst’s Best Friend
12.2 Getting Started
12.2.1 Options for Running Python
12.2.2 Installing Packages
12.3 Python Basics
12.3.1 Variables and Data Types
12.3.2 Arithmetic Operations
12.3.3 Collections: Lists, Tuples, Dictionaries, and Sets
12.3.4 Indexing and Slicing
12.3.5 Control Flow: Conditionals
12.3.6 Control Flow: Loops
12.3.7 Functions
12.4 Python Essentials for Optimization
12.4.1 Lists: Ordered Collections
12.4.2 Dictionaries: Key-Value Mappings
12.4.3 For Loops: Iteration
12.4.4 List Comprehensions: Concise List Creation
12.4.5 Functions: Reusable Code
12.5 NumPy: Numerical Computing
12.5.1 Creating Arrays
12.5.2 Array Operations
12.5.3 Linear Algebra
12.5.4 Visualizing Array Operations
12.6 Pandas: Data Management
12.6.1 DataFrames: Tables of Data
12.6.2 Reading Data from Files
12.6.3 Accessing and Filtering Data
12.6.4 From DataFrame to Optimization Data
12.6.5 Analyzing Results
12.7 Matplotlib: Visualization
12.7.1 Bar Charts: Comparing Categories
12.7.2 Grouped Bar Charts: Comparing Multiple Series
12.7.3 Heatmaps: Visualizing Matrices
12.7.4 Plot Customization Reference
12.8 NetworkX: Graph Analysis
12.8.1 Why Graphs Matter for Optimization
12.8.2 Creating Graphs
12.8.3 Accessing Graph Data
12.8.4 Graph Algorithms
12.8.5 Visualization
12.9 GeoPandas: Geographic Visualization
12.9.1 Why Geographic Visualization?
12.9.2 Creating Geographic Data
12.9.3 Map Visualization
12.10 PuLP: Optimization Modeling
12.10.1 Installing PuLP
12.10.2 The PuLP Modeling Pattern
12.10.3 Example: Product Mix Problem
12.10.4 Variable Types
12.10.5 Creating Multiple Variables
12.10.6 The lpSum Function
12.10.7 Complete Transportation Example
12.11 Putting It All Together
12.12 Exercises
13 Multi-Objective Optimization
13.1 Introduction to Multi-Objective Optimization
13.2 Multi-Objective Optimization and the Pareto Frontier
13.2.1 Applications of Pareto Frontiers
13.3 Computational Tools for Multi-Objective Optimization
13.4 Exercises
II Discrete Algorithms
14 Graph Algorithms
14.1 Graph Theory
14.2 Graphs
14.2.1 Drawing Graphs
14.3 Definitions
14.4 Shortest Path
14.4.1 Run time improvements
14.5 Spanning Trees
14.5.1 Kruskal’s Algorithm for Minimum Cost Spanning Tree
14.6 Exercise Answers
14.6.1 Prim’s Algorithm for Minimum Cost Spanning Tree
14.7 Exercises
14.7.1 Notes
III Introduction to Integer Programming
15 Introduction to Integer Programming Formulations
15.1 Knapsack Problem
15.2 Capital Budgeting
15.3 Capacitated Lot Sizing Problem (CLSP)
15.4 Facility Location
15.4.1 Capacitated Facility Location
15.5 Set Covering
15.5.1 Covering (Generalizing Set Cover)
15.6 Graph Coloring
15.7 Basic Modeling Tricks - Using Binary Variables
15.7.1 Big M constraints - Activating/Deactivating Inequalities
15.7.2 Either Or Constraints
15.7.3 If then implications - opposite direction
15.7.4 Multi Term Disjunction with application to 2D packing
15.7.5 SOS1 Constraints
15.7.6 SOS2 Constraints
15.7.7 Piecewise linear functions with SOS2 constraint
15.7.8 Maximizing a minimum
15.7.9 Relaxing (nonlinear) equality constraints
15.7.10 Modeling the Exact Absolute Value
15.8 Job Shop Scheduling
15.8.1 JSSP Components
15.8.2 Mathematical Model
15.8.3 Job Shop Scheduling Variations
15.9 Exercises
15.10 Literature and Resources
A Linear Equations
A.1 Graphing a Linear Equation
A.2 Slope of a Line
A.3 Determining the Equation of a Line
A.4 Applications of Linear Equations
A.5 More Applications: Systems of Linear Equations
B Systems of Equations
B.1 Systems of Equations, Geometry
B.2 Systems Of Equations, Algebraic Procedures
B.2.1 Elementary Operations
B.2.2 Gaussian Elimination
B.2.3 Uniqueness of the Reduced Row-Echelon Form
B.2.4 Rank and Homogeneous Systems
C Matrices
C.1 Matrix Arithmetic
C.1.1 Addition of Matrices
C.1.2 Scalar Multiplication of Matrices
C.1.3 Multiplication of Matrices
C.1.4 The
i
j
t
h
Entry of a Product
C.1.5 Properties of Matrix Multiplication
C.1.6 The Transpose
C.1.7 The Identity and Inverses
C.1.8 Finding the Inverse of a Matrix
D
ℝ
n
D.1 Vectors in
ℝ
n
D.2 Algebra in
ℝ
n
D.2.1 Addition of Vectors in
ℝ
n
D.2.2 Scalar Multiplication of Vectors in
ℝ
n
D.3 Geometric Meaning of Vector Addition
D.4 Length of a Vector
D.5 Geometric Meaning of Scalar Multiplication
D.6 The Dot Product
D.6.1 The Dot Product
D.6.2 The Geometric Significance of the Dot Product
E Optimization Software Resources
E.1 Software by Problem Type
E.2 Recommended Solvers for This Book
E.3 Modeling Languages and Interfaces
E.4 Gurobi Tutorials and Resources
E Answers to Learning Checkpoints
E Further Reading and Resources
© 2026 Robert Hildebrand and contributors · Licensed
CC BY-SA 4.0
·
Sources and attribution
·
Book home