Learn
/
OR
Operations Research
199 topics
Graph view
1
Linear Programming Foundations
LP Formulation
Introduction to Linear Programming
Anatomy of an LP: Decision Variables, Objective, Constraints
Formulating Resource Allocation Problems as LPs
Formulating Diet and Blending Problems as LPs
Formulating Transportation Problems as LPs
Standard Form Conversions
Standard Form of a Linear Program
Converting Inequalities to Equalities with Slack Variables
Handling Free Variables via Variable Splitting
Converting Max to Min and Other Reformulations
Full Conversion of an LP to Standard Form
Geometry of LP
Polyhedra and Half-Spaces
Convexity of the Feasible Region
Extreme Points, Vertices, and Basic Feasible Solutions
Why the LP Optimum Lives at a Vertex
Unbounded, Infeasible, and Degenerate LPs
Graphical Solution of 2-Variable LPs
Bases and BFS
Bases and Basic Variables
Computing a Basic Feasible Solution from a Basis
Correspondence Between BFS and Vertices
2
The Simplex Method
Simplex Mechanics
The Simplex Idea: Walking Vertex to Vertex
Reduced Costs and the Optimality Criterion
Selecting the Entering Variable
The Minimum Ratio Test and the Leaving Variable
Pivoting Between Adjacent Bases
Simplex Tableau
The Simplex Tableau Layout
Tableau Simplex on 2-Variable Problems
Tableau Simplex on 3-Variable Problems
Detecting Unboundedness During Simplex
Recognizing Multiple Optimal Solutions
Initialization
Finding an Initial BFS: The Two-Phase Method
The Big-M Method for Initialization
Degeneracy and Cycling in Simplex
Bland's Rule and Anti-Cycling
Computational Simplex
The Revised Simplex Method in Matrix Form
Why Real Solvers Use Revised Simplex
Reading a Simplex Solver Log
3
LP Duality
Dual Formulation
Motivating Duality: Bounding the Primal Objective
Constructing the Dual of a Standard-Form LP
Dual of an LP with Mixed Constraint Types
The Primal-Dual Correspondence Table
The Dual of the Dual is the Primal
Duality Theorems
Weak Duality Theorem
Strong Duality Theorem
Duality Outcomes: Optimal, Unbounded, Infeasible
Farkas' Lemma and Theorems of the Alternative
Complementary Slackness
Complementary Slackness Conditions
Verifying Optimality via Complementary Slackness
Recovering a Dual Solution from a Primal Solution
Economic Interpretation
Economic Interpretation of Dual Variables
Shadow Prices as Marginal Resource Values
Interpreting Reduced Costs as Opportunity Costs
Reading Binding vs. Slack Constraints in a Solution
4
Sensitivity and Post-Optimal Analysis
Sensitivity Foundations
Local vs. Global Sensitivity in LP
Sensitivity Range for an Objective Coefficient
Sensitivity Range for a Right-Hand Side
100% Rule for Simultaneous Changes
Structural Changes
Adding a New Variable to an Optimal LP
Adding a New Constraint to an Optimal LP
Parametric Programming: Tracing the Optimal Basis
Practical Sensitivity
Reading a Solver Sensitivity Report
Distinguishing Real Sensitivity Analysis from Re-Solving Under Perturbations
Auditing an LP Formulation for Correctness
5
Integer Programming Foundations
IP Formulation
From LP to Integer Programming: Why Integrality Matters
Pure IP, Mixed IP, and Binary IP
The LP Relaxation of an IP
The Integer Hull and the Integrality Gap
Modeling with Binaries
Modeling Yes/No Decisions with Binary Variables
Modeling Logical Constraints with Binaries (AND, OR, NOT)
Modeling At-Most-K and Exactly-K Constraints
Modeling Mutual Exclusion with Binaries
Modeling Fixed Charges and Setup Costs
Big-M and Indicators
Big-M Constraints: Linking Binary to Continuous Variables
Indicator Variables for On/Off Activities
Choosing the Tightest Big-M Value
Capacity as a Natural Big-M in Flow Models
Disjunctive Constraints via Big-M
Piecewise-Linear Functions via SOS Variables
6
Branch and Bound
B&B Foundations
Enumeration is Hopeless: The Size of the Integer Search Space
LP Relaxation as a Lower Bound
Incumbent Solutions and Upper Bounds
Branching
Branching on a Fractional Variable
The Branch-and-Bound Tree
Branch and Bound on Small Binary IPs
Branch and Bound on Small Mixed-Integer Programs
Bounding and Pruning
Pruning by Bound
Pruning by Infeasibility
Pruning by Integrality
Solver Behavior
Branching Strategies: Most Fractional, Pseudocost, Strong Branching
Node Selection: Best-First, Depth-First, Best-Estimate
MIP Gap and Solver Termination Criteria
Reading a MIP Solver Log
7
Formulation Strength and Cuts
Formulation Strength
Strong vs. Weak Formulations of the Same MIP
Comparing LP Relaxations of Equivalent Formulations
Aggregated vs. Disaggregated Constraints
Ideal Formulations and the Convex Hull
Extended Formulations: Trading Variables for Tightness
Valid Inequalities
What is a Valid Inequality?
Cover Inequalities for Knapsack-Type Constraints
Flow Cover Inequalities for Fixed-Charge Networks
Cutting Planes
Cutting Planes: Concept and Loop
Gomory Fractional Cuts
Branch-and-Cut: Integrating Cuts with Branching
Total Unimodularity
Totally Unimodular Matrices
When LP Solutions are Automatically Integer
Recognizing TU Structure in Practice
Auditing MIPs
Auditing a MIP Formulation for Correctness
Assessing Whether a MIP Could Have Been an LP
8
Network Flows
Graph Foundations
Graph Terminology for Network Flows
Directed Networks with Capacities and Costs
Flow Conservation at a Node
The Node-Arc Incidence Matrix
Shortest Paths
Shortest Path: LP Formulation
Dijkstra's Algorithm for Non-Negative Weights
Bellman-Ford for Negative Weights
Resource-Constrained Shortest Path
Max Flow and Min Cut
Max Flow: LP Formulation
Augmenting Paths and Ford-Fulkerson
Min Cut and the Max-Flow Min-Cut Theorem
Menger's Theorem and Network Connectivity
Push-Relabel Algorithm (Concept Level)
Min-Cost Flow
Min-Cost Flow: LP Formulation
Network Simplex Method
Successive Shortest Paths for Min-Cost Flow
Transportation and Assignment Problems as Min-Cost Flow
Integrality of Single-Commodity Network Flow
9
Multi-Commodity Flow and Time-Expanded Networks
Multi-Commodity Flow
Multi-Commodity Flow: Problem Definition
Node-Arc Formulation of Multi-Commodity Flow
Why Multi-Commodity Flow Breaks Total Unimodularity
Integer Multi-Commodity Flow is NP-Hard
Path-Based Formulation of Multi-Commodity Flow
Time-Expanded Graphs
Dynamic Problems on Static Graphs: The Time Dimension
Constructing a Time-Expanded Network
Holding Arcs, Movement Arcs, and Throughput Arcs
Flow Conservation in Time-Expanded Networks
Tracing Cargo Through a Time-Expanded Multi-Commodity Network
Time Discretization Choices and Their Trade-Offs
Column Generation
Column Generation: The Master/Subproblem Pattern
Restricted Master Problem and Pricing Subproblem
Pricing via Shortest Path with Dual Values
Column Generation Termination and Optimality
Practical Auditing
Auditing a Time-Expanded Multi-Commodity Flow MIP
Recognizing When Column Generation is the Right Tool
10
Constraint Programming
CP Foundations
The Constraint Programming Paradigm
Variables, Domains, and Constraints
Constraint Propagation: Domain Reduction by Inference
Arc Consistency and Bound Consistency
Backtracking Search with Propagation
CP-SAT Modeling Basics
Setting Up Your First CP-SAT Model in OR-Tools
Integer Variables and Linear Constraints in CP-SAT
Boolean Variables and Clauses in CP-SAT
The AllDifferent Constraint
Channeling Between Integer and Boolean Variables
Interval Variables
Interval Variables: Start, Size, End
Fixed-Size vs. Variable-Size Intervals
Optional Intervals and Presence Literals
Modeling Activities with Earliest-Start and Latest-End
Scheduling Constraints
AddNoOverlap for Single-Machine Scheduling
AddNoOverlap with Optional Intervals
AddCumulative for Capacity-Limited Resources
Job Shop Scheduling in CP-SAT
Modeling Setup Times and Precedences
AddNoOverlap2D for Bin-Packing in Time and Space
Logical Constraints
Reification: OnlyEnforceIf
Implications and Equivalences Between Booleans
Element Constraints for Variable Indexing
Conditional Constraints Without Big-M
Objectives and Search
CP Objectives: Makespan, Tardiness, Weighted Sums
Lexicographic and Multi-Objective Optimization in CP
Search Strategies and Decision Heuristics
CP-SAT Internals
Inside CP-SAT: SAT Translation and CDCL
LP Relaxation Inside CP-SAT
Reading a CP-SAT Solver Log
CP vs. MIP
Auditing a CP-SAT Scheduling Model
CP vs. MIP: When to Choose Which
11
Stochastic and Robust Optimization
Stochastic Programming Concepts
Uncertainty in Optimization: Why Deterministic Models Fail
Two-Stage Stochastic Programs: Here-and-Now vs. Wait-and-See
First-Stage Decisions and Recourse
Scenario Trees and the Extensive Form
Non-Anticipativity Constraints
Value of Information
Expected Value of Perfect Information (EVPI)
Value of the Stochastic Solution (VSS)
Deciding Whether Deterministic Reoptimization Suffices
Robust Optimization
Robust Optimization: Worst-Case over an Uncertainty Set
Box, Ellipsoidal, and Budgeted Uncertainty Sets
Stochastic vs. Robust: When to Use Which
Auditing Informal Scenario-Based Fragility Analyses
12
Decomposition Methods
Decomposition Concepts
Why Decompose: Block Structure in Large Problems
Master-Subproblem Communication Patterns
Benders Decomposition
Benders Decomposition: The Idea
Benders Optimality and Feasibility Cuts
Benders for Mixed-Integer Problems
The L-Shaped Method for Two-Stage Stochastic Programs
Dantzig-Wolfe and Column Generation
Dantzig-Wolfe Decomposition: Reformulating with Extreme Points
Column Generation for Dantzig-Wolfe Masters
Branch-and-Price: Column Generation Inside Branch and Bound
Lagrangian Relaxation
Lagrangian Relaxation: Dualizing Complicating Constraints
Subgradient Methods for the Lagrangian Dual
The Lagrangian Duality Gap and Integer Problems
Auditing Decomposition
Verifying Correctness of a Benders or Column Generation Implementation
Loading index…
↑
↓
navigate ·
Enter
open ·
Esc
close ·
⌘K
/
Ctrl K
toggle