Linear Programming

Linear Programming#

Contents#

Sections#

Linear Programming (LP) is a type of mathematical optimization problem in which the constraints and optimization function are represented by linear functions.

Integer Programming (IP) is a type of mathematical optimization problem in which at least one variable is an integer.

Mixed-Integer Programming (MIP) involves problems in which not all variables are constrained to be integers (and so at least one variable is a non integer).

Integer Linear Programming (ILP) and Mixed-Integer Linear Programming (MILP) involve problems in which the non integer constraints (and optimization function) are linear.

Zero-One Linear (or Binary Integer) Programming involves problems in which the variables are restricted to be 0 or 1.

Resources#

YouTube

  • [ y ] 05-16-2019 MIT OpenCourseWare. “24. Linear Programming and Two-Person Games”.

  • [ y ] 03-04-2016 MIT OpenCourseWare. “15. Linear Programming: LP, reductions, Simplex”.

  • [ y ] 07-04-2023 Tom S. “The Art of Linear Programming”.

  • [ y ] 06-29-2020 wenshenpsu. “Math484 Linear Programming Short Videos, summer 2020”.

  • [ y ] 12-07-2022 wenshenpsu. “Math484, Linear Programming, fall 2016”.

more

Texts#

  • Beck, Amir. (2017). First-Order Methods in Optimization. Society for Industrial and Applied Mathematics.

  • [ P ][ Y ] Bubeck, Sébastien. (2015). Convex Optimization: Algorithms and Complexity.

  • Chong, Edwin K. P. & Stanislaw H. Zak. (2001). An Introduction to Optimization, 2nd Ed. Wiley.

  • Dantzig, George B. & Mukund N. Thapa. (1997). Linear Programming 1: Introduction. Springer Series in Operations Research and Financial Engineering.

  • Dantzig, George B. & Mukund N. Thapa. (2003). Linear Programming 2: Theory and Extensions. Springer Series in Operations Research and Financial Engineering.

  • Morse, Philip M. & George E. Kimball. (2003). Methods of Operations Research. Dover Books on Computer Science.

  • Nesterov, Yurii. (2018). Lectures on Convex Optimization. 2nd Ed. Springer: Springer Optimization and Its Applications.

  • Nocedal, Jorge & Stephen Wright. (1999). Numerical Optimization. Series in Operations Research and Financial Engineering.

  • Pardalos, Panos M., Varvara Rasskazova, & Michael N. Vrahatis. (2021). Black Box Optimization, Machine Learning, and No-Free Lunch Theorem. Springer: Springer Optimization and Its Applications.

  • Thie, Paul R. Gerard E. Keough. (2008). An Introduction to Linear Programming and Game Theory. 3rd Ed. Wiley.

Figures#

  • [ w ] 1920-1984 Bellman, Richard

  • [ w ] --------- Bland, Robert

  • [ w ] 1914-2005 Dantzig, George

  • [ w ] --------- Karmarkar, Narendra

  • [ w ] 1952-2005 Khachiyan, Leonid

  • [ w ] 1903-1987 Kolmogorov, Andrey

  • [ w ] 1941-2014 Padberg, Manfred

  • [ w ] 1903-1957 Von Neumann, John

  • [ w ] --------- Dinitz, Yefim

  • [ w ] 1934----- Edmonds, Jack

  • [ w ] 1927-2017 Ford Jr., L. R.

  • [ w ] 1924-1976 Fulkerson, D. R.

  • [ w ] 1919-2005 Harris, Ted

  • [ w ] 1935----- Karp, Richard

Terms#

  • [ w ] Dinitz’s Algorithm

  • [ w ] Edmonds-Karp Algorithm

  • [ w ] Flow Network

  • [ w ] Ford-Fulkerson Algorithm

  • [ w ] Max-Flow Min-Cut Theorem

  • [ w ] Maximum Flow Problem

  • [ w ] Minimum-Cost Flow Problem

  • [ w ] Network Simplex Algorithm

  • [ w ][ wm ] Affine Function/Map/Transformation

  • [ w ] Approximation Algorithm

  • [ w ] Basic Feasible Solution

  • [ w ] Bauer’s Maximum Principle

  • [ w ] Bland’s Rule

  • [ w ] Block Matrix

  • [ w ] Boundedness

  • [ w ] Calculus of Variations

  • [ w ] Closedness

  • [ w ] Combinatorial Optimization

  • [ w ] Compactness

  • [ w ] Constrained Optimization

  • [ w ] Constraint

  • [ w ] Constraint Programming

  • [ w ] Constraint Satisfaction

  • [ w ] Constraint Satisfaction Problem (CSP)

  • [ w ] Convex Cone

  • [ w ] Convex Optimization

  • [ w ] Convex Polytope

  • [ w ] Convex Set

  • [ w ] Criss-Cross Algorithm

  • [ w ] Cunningham’s Rule

  • [ w ] Devex Algorithm

  • [ w ] Directional Derivative

  • [ w ] Dual Linear Program

  • [ w ] Duality

  • [ w ] Duality Gap

  • [ w ] Dynamic Programming

  • [ w ] Ellipsoid Method

  • [ w ] Farkas’ Lemma

  • [ w ] Feasible Region/Set

  • [ w ] Fourier-Motzkin Elimination

  • [ w ] Game Theory

  • [ w ] Gradient

  • [ w ] Hyperplane

  • [ w ] Hypersurface

  • [ w ] Integer Programming

  • [ w ] Interior Point Methods

  • [ w ] Iterative Method

  • [ w ] Karmarkar’s Algorithm

  • [ w ] Lagrange Multiplier

  • [ w ][ wm ] Level Set

  • [ w ] Line

  • [ w ] Linear Equality/Equation

  • [ w ] Linear Inequality

  • [ w ] Linear Function/Map/Transformation

  • [ w ] Linear Programming

  • [ w ] Mathematical Model

  • [ w ] Mathematical Optimization

  • [ w ] Max-Min Inequality

  • [ w ] Minimax Theorem

  • [ w ] Network Flow Problem

  • [ w ] Newton’s Method

  • [ w ] Non Linear Programming

  • [ w ] Objective Function

  • [ w ] Operations Research

  • [ w ] Optimization Problem

  • [ w ] Plane

  • [ w ] Point

  • [ w ] Quadratic Programming

  • [ w ] Relaxation

  • [ w ] Revised Simplex Method

  • [ w ] Sequential Quadratic Programming

  • [ w ] Simplex

  • [ w ] Simplex Algorithm

  • [ w ] Slack Variable

  • [ w ] Stochastic Programming

  • [ w ] Surface

  • [ w ] Unconstrainted Optimization

  • [ w ] Zadeh’s Rule

Acknowledgments#

Byrne, Christopher. MATH 484 Linear Programs and Related Problems - Linear Programs I: A Clear, Concise, and Practical Introduction to Linear Programs and Duality Theory with Applications to Return On Investment (ROI). The Pennsylvania State University.

Contents