Linear and Integer Programming.

Explore 29 formal proofs and analytical renders within the discipline of Linear and Integer Programming.

The Convexity of the Feasible Region of a Linear Program

Exploring the cinematic intuition of The Convexity of the Feasible Region of a Linear Program.

The Fundamental Theorem of Linear Programming: Existence of an Optimal Extreme Point Solution

Exploring the cinematic intuition of The Fundamental Theorem of Linear Programming: Existence of an Optimal Extreme Point Solution.

Study Proof →

Intermediate

Proof of Correctness of the Simplex Algorithm: Convergence to an Optimal Solution

Exploring the cinematic intuition of Proof of Correctness of the Simplex Algorithm: Convergence to an Optimal Solution.

Study Proof →

Advanced

Proof of Finite Termination of the Simplex Algorithm (Assuming Non-Degeneracy)

Exploring the cinematic intuition of Proof of Finite Termination of the Simplex Algorithm (Assuming Non-Degeneracy).

Study Proof →

Advanced

Bland's Rule: A Proof of Anti-Cycling for the Simplex Algorithm

Exploring the cinematic intuition of Bland's Rule: A Proof of Anti-Cycling for the Simplex Algorithm.

Study Proof →

Advanced

The Lexicographic Rule: Visual Anti-Cycling Intuition in Simplex

A deep visual intuition of the Lexicographic Rule and how it prevents cycling in the Simplex algorithm for linear programming.

Study Proof →

Advanced

Visual Proof: Convergence of the Two-Phase Simplex Method

A rigorous visual proof demonstrating why the Two-Phase Simplex method is guaranteed to converge for linear programming problems.

Study Proof →

Advanced

Big M vs. Two-Phase Simplex: A Geometric Intuition

Understanding the geometric equivalence between the Big M and Two-Phase methods for finding an initial basic feasible solution in linear programming.

Study Proof →

Intermediate

The Weak Duality Theorem: Linear Programming Intuition

A visual guide to the Weak Duality Theorem in linear programming and its role as a fundamental bound for optimization.

Study Proof →

Advanced

Visual Proof: The Strong Duality Theorem in Linear Programming

An institutional visual proof of the Strong Duality Theorem, revealing the deep symmetry between primal and dual linear programs.

Study Proof →

Intermediate

Sensitivity Analysis: Geometric Intuition for Resource Changes

Visualizing how changes in resource availability affect the optimal solution in linear programming through sensitivity analysis.

Study Proof →

Advanced

Proof that the Dual of a Dual LP is the Primal LP

Exploring the cinematic intuition of Proof that the Dual of a Dual LP is the Primal LP.

Study Proof →

Advanced

Proof that if the Primal is Unbounded, the Dual is Infeasible (and vice-versa)

Exploring the cinematic intuition of Proof that if the Primal is Unbounded, the Dual is Infeasible (and vice-versa).

Study Proof →

Advanced

Branch and Bound: Integer Programming Visual Intuition

Visualizing the Branch and Bound algorithm for integer programming and how it prunes the search space using optimality bounds.

Study Proof →

Advanced

Proof that Valid Cuts Do Not Remove Any Integer Feasible Solutions

Exploring the cinematic intuition of Proof that Valid Cuts Do Not Remove Any Integer Feasible Solutions.

Study Proof →

Advanced

Visual Proof: Gomory's Cutting Plane Algorithm for Integer Programming

A formal visual derivation of Gomory's Cutting Plane algorithm and its finite termination for integer linear programming.

Study Proof →

Intermediate

The Relationship Between an Integer Program and its LP Relaxation Optimal Values

Exploring the cinematic intuition of The Relationship Between an Integer Program and its LP Relaxation Optimal Values.

Study Proof →

Advanced

Characterization of the Convex Hull of Integer Feasible Solutions

Exploring the cinematic intuition of Characterization of the Convex Hull of Integer Feasible Solutions.

Study Proof →

Advanced

The Relationship Between Extreme Points and Directions of Unboundedness

Exploring the cinematic intuition of The Relationship Between Extreme Points and Directions of Unboundedness.

Study Proof →

Advanced

Proof that Optimal Dual Variables Represent Shadow Prices

Exploring the cinematic intuition of Proof that Optimal Dual Variables Represent Shadow Prices.

Study Proof →

Advanced

Sensitivity Analysis: The Impact of Objective Function Coefficient Changes on Optimality

Exploring the cinematic intuition of Sensitivity Analysis: The Impact of Objective Function Coefficient Changes on Optimality.

Study Proof →

Advanced

Proof of Karush-Kuhn-Tucker (KKT) Conditions for Linear Programming Optimality

Exploring the cinematic intuition of Proof of Karush-Kuhn-Tucker (KKT) Conditions for Linear Programming Optimality.

Study Proof →

Advanced

Correctness and Finite Termination of the Branch and Bound Algorithm for Integer Programming

Exploring the cinematic intuition of Correctness and Finite Termination of the Branch and Bound Algorithm for Integer Programming.

Study Proof →

Advanced

Proof of Validity for Gomory Fractional Cuts

Exploring the cinematic intuition of Proof of Validity for Gomory Fractional Cuts.

Study Proof →

Advanced

Detecting and Proving Infeasibility in Linear Programs

Exploring the cinematic intuition of Detecting and Proving Infeasibility in Linear Programs.

Study Proof →

Intermediate

Proof that All Optimal Solutions to a Linear Program Form a Convex Set

Exploring the cinematic intuition of Proof that All Optimal Solutions to a Linear Program Form a Convex Set.

Study Proof →

The Convexity of the Feasible Region of a Linear Program

The Fundamental Theorem of Linear Programming: Existence of an Optimal Extreme Point Solution

Equivalence of Basic Feasible Solutions and Extreme Points

Characterization of Unboundedness in Linear Programming

Proof of Finite Number of Basic Feasible Solutions

Proof of Correctness of the Simplex Algorithm: Convergence to an Optimal Solution

Proof of Finite Termination of the Simplex Algorithm (Assuming Non-Degeneracy)

Bland's Rule: A Proof of Anti-Cycling for the Simplex Algorithm

The Lexicographic Rule: Visual Anti-Cycling Intuition in Simplex

Visual Proof: Convergence of the Two-Phase Simplex Method

Big M vs. Two-Phase Simplex: A Geometric Intuition

The Weak Duality Theorem: Linear Programming Intuition

Visual Proof: The Strong Duality Theorem in Linear Programming

Sensitivity Analysis: Geometric Intuition for Resource Changes

Proof that the Dual of a Dual LP is the Primal LP

Proof that if the Primal is Unbounded, the Dual is Infeasible (and vice-versa)

Branch and Bound: Integer Programming Visual Intuition

Proof that Valid Cuts Do Not Remove Any Integer Feasible Solutions

Visual Proof: Gomory's Cutting Plane Algorithm for Integer Programming

The Relationship Between an Integer Program and its LP Relaxation Optimal Values

Characterization of the Convex Hull of Integer Feasible Solutions

The Relationship Between Extreme Points and Directions of Unboundedness

Proof that Optimal Dual Variables Represent Shadow Prices

Sensitivity Analysis: The Impact of Objective Function Coefficient Changes on Optimality

Proof of Karush-Kuhn-Tucker (KKT) Conditions for Linear Programming Optimality

Correctness and Finite Termination of the Branch and Bound Algorithm for Integer Programming

Proof of Validity for Gomory Fractional Cuts

Detecting and Proving Infeasibility in Linear Programs

Proof that All Optimal Solutions to a Linear Program Form a Convex Set