Linear Programming

Linear Programming#

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.

Quadratic Programming

Resources#

https://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit

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”.

Texts#

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

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

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

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

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

  • 2003 Dechter, Rina. Constraint Processing. Morgan Kaufmann. [ home ].

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

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

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

  • 2012 Oki, Eiji. Linear Programming and Algorithms for Communication Networks: A Practical Guide to Network Design, Control, and Management. CRC Press.

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

  • 2008 Thie, Paul R. Gerard E. Keough. 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 ] --------- 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 ] --------- Karmarkar, Narendra

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

  • [ w ] 1952-2005 Khachiyan, Leonid

  • [ w ] 1903-1987 Kolmogorov, Andrey

  • [ w ] 1941-2014 Padberg, Manfred

  • [ w ] 1903-1957 Von Neumann, John

  • [ w ] 1927-2016 Wolfe, Philip

Terms#

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

  • [ 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 ] Column Generation

  • [ w ] Combinatorial Optimization

  • [ w ] Compactness

  • [ w ] Constrained Optimization [ wolfram ]

  • [ w ] Constraint

  • [ 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 ] Dantzig-Wolfe Decomposition

  • [ w ] Decomposition Method

  • [ w ] Devex Algorithm

  • [ w ] Dinitz’s Algorithm

  • [ w ] Directional Derivative

  • [ w ] Dual Linear Program

  • [ w ] Dual Problem

  • [ w ] Duality

  • [ w ] Duality Gap

  • [ w ] Edmonds-Karp Algorithm

  • [ w ] Ellipsoid Method

  • [ w ] Farkas’ Lemma

  • [ w ] Feasible Region/Set

  • [ w ] Flow Network

  • [ w ] Ford-Fulkerson Algorithm

  • [ 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 ] Level Set [ wolfram ]

  • [ 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-Flow Min-Cut Theorem

  • [ w ] Max-Min Inequality

  • [ w ] Maximum Flow Problem

  • [ w ] Minimax Theorem

  • [ w ] Minimum-Cost Flow Problem

  • [ w ] Network Flow Problem

  • [ w ] Network Simplex Algorithm

  • [ w ] Newton’s Method

  • [ w ] Non Linear Programming

  • [ w ] Objective Function

  • [ w ] Operations Research

  • [ w ] Optimization Problem

  • [ w ] Plane

  • [ w ] Point

  • [ w ] Reduced Cost

  • [ w ] Relaxation

  • [ w ] Revised Simplex Method

  • [ w ] Simplex

  • [ w ] Simplex Algorithm

  • [ w ] Slack Variable

  • [ w ] Surface

  • [ w ] Unconstrainted Optimization

  • [ w ] Zadeh’s Rule

  • [ w ] Comparative Statics

  • [ w ] Envelope Theorem

  • [ w ] Gorman Polar Form

  • [ w ] Hicksian Demand Function

  • [ w ] Indirect Utility Function

  • [ w ] Shadow Price

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