Project L
  • Preface
  • Part 1
    • Introduction
    • Before We Begin
      • Pythonic things
    • Basic Data Structures
      • Array and String
        • Math
          • Plus One
          • Move Zeroes
          • Rotate Matrix
          • Sparse Matrix Multiplication
          • Missing Numbers
          • Find All Numbers Disappeared in an Array
          • Drop Eggs
        • Sorted Array
          • Median of Two Sorted Arrays
          • Two to K Sum
        • Unsorted Array
          • Partition Array
          • Kth Largest Element
          • Sort Colors
        • Subarray
          • Maximum Subarray
        • Two Pointers
          • L/R Pointers
            • Reverse String
            • Valid Palindrome
            • Trapping Rain Water
          • F/S Pointers
          • P1/P2 Pointers
            • Implement strStr()
            • Intersection of Two Arrays
            • Merge Two Sorted Arrays
          • Window
            • Window Sum
            • Minimum Size Subarray Sum
            • Longest Substring Without Repeating Characters
            • Minimum Window Substring
            • Longest Substring with At Most K Distinct Characters
        • String Builder
          • Reverse Words in a String
        • Rotated Array
      • Hashing
        • Hash Function
        • Group Anagrams
        • Rolling Hash
        • LSH
        • Hash Heap
      • Linked List
        • Singly Linked List
          • Plus One Linked List
          • Partition List
          • Rotate List
          • Palindrome Linked List
          • Reverse Nodes in k-Group
          • Insertion Sort List
          • Sort List
          • Merge K Sorted Lists
          • Copy List with Random Pointer
        • Doubly Linked List
          • BST To DLL
          • LRU Cache
        • Circular Linked List
          • Insert into a Cyclic Sorted List
      • Stack
        • Valid Parenthesis
        • Min Stack
        • 📊Next Greater Element I
        • 🏙️Largest Rectangle in Histogram
      • Queue
        • Moving Average from Data Stream
        • Double-ended Queue
          • Sliding Window Maximum
      • Binary Tree
        • Tree Traversal
          • Binary Tree Paths
          • Binary Tree Path Sum
          • Iterative
            • Flatten List Iterator
            • Flatten Nested List Iterator
            • Flatten 2D Vector
            • Binary Tree to Linked List
            • Zigzag Iterator
        • Divide and Conquer
          • Subtree Max Avg
          • Max Depth of Binary Tree
          • Balanced Binary Tree
          • Lowest Common Ancestor
          • Longest Univalue Path
          • Binary Tree Maximum Path Sum
          • Binary Tree Leaves
        • Binary Search Tree
          • Search in a Binary Search Tree
          • Insert into a Binary Search Tree
          • Delete Node in a BST
          • Binary Search Tree Iterator
          • Convert Binary Search Tree to Sorted Doubly Linked List
          • Convert Sorted Array to Binary Search Tree
          • Convert Sorted List to Binary Search Tree
          • Search Range in Binary Search Tree
          • LCA in BST
          • Validate BST
          • Kth Smallest Element in a BST
        • BFS
          • Binary Tree Level Order Traversal
          • Binary Tree Vertical Order Traversal
          • Binary Tree Serialization
      • Priority Queue
        • Top K Largest Numbers
        • Top K Frequent Elements
        • K Closest Points
        • Kth Smallest Element in a Sorted Matrix
        • Find Median from Data Stream
        • Ugly Number
        • Merge K Sorted Arrays
        • Sliding Window Median
        • 🧵Reorganize String
  • Part 2
    • Divide and Conquer
      • Recursion
        • Recurrence
      • Binary Search
        • Search First/Last Position
        • Search Insert Position
        • Find Closest Number in a Sorted Array
        • First Bad Version
        • Search in a Big Sorted Array
        • Search for a Range
        • Search a 2D Matrix
        • Search a 2D Matrix II
        • Find Trough/Peak Element
        • Search in Rotated Sorted Array
          • Find Minimum in Rotated Sorted Array
        • Recover RSA
        • Square Root
      • Sorting
        • Bubble Sort
        • Selection Sort
        • Insertion Sort
        • Merge Sort
        • Quick Sort
        • Heap Sort
    • Graph Search
      • Search in a Grid
        • Shortest Knight Path
        • Number of Islands
        • Word Search
        • The Maze
        • Shortest Path in a Changing Maze
        • Walls and Gates
      • Exhaustive Search
        • Subsets
        • Partition to K Equal Sum Subsets
        • Combinations
        • Combination Sum
        • Factor Combinations
        • Letter Combinations of a Phone Number
        • Nested List Weight Sum
        • Generate Parentheses
        • Permutations
        • Next Permutation
          • Iterator for Combination
        • N-Queen
        • 8 Puzzle
      • Graph Theory
        • Graph Data Structure
          • Search Nearest Target Node
          • Six Degrees
          • Graph Valid Tree
          • Clone Graph
        • Graph Traversal
          • Word Ladder
          • Word Ladder II
          • Sliding Puzzle
        • Topological Sort
          • Course Schedule
          • Alien Dictionary
          • Cycle Detection
        • Connected Component
          • Strongly Connected Components
          • Number of Islands II
        • Bipartite Graph
          • Is the Graph Bipartite?
        • Subgraph Matching
    • Greedy Algorithm
      • Longest Palindrome
      • Meeting Rooms
      • Merge Intervals
      • Non-overlapping Intervals
      • 🚰Minimum Number of Taps to Open to Water a Garden
      • Minimum Spanning Tree
      • CPU Task Scheduling
      • Teemo Attacking
    • Dynamic Programming
      • Coordinate DP
        • Fibonacci Numbers
        • Climbing Stairs
        • House Robber
        • Unique Paths
        • Longest Increasing Subsequence
        • Minimum Path Sum
        • Manhattan's Map
        • Maximal Square
        • Jump Game
        • Frog Jump
      • Single Sequence DP
        • Paint Fence
        • Wood Cut
        • Rod Cutting
        • Word Break
        • Longest Palindromic Subsequence
        • Maximum Profit in Job Scheduling
        • Russian Doll Envelopes
      • Double Sequence DP
        • Longest Common Subsequence
        • Edit Distance
        • Regex Matching
        • Wildcard Matching
        • Interleaving String
      • Partition DP
        • Best Time to Buy and Sell Stock
        • Word Break
        • Text Justification
        • Decode Ways
      • Substring DP
        • Longest Palindromic Substring
        • Scramble String
        • Parenthesis Correction
        • Matrix Multiplication Parenthesization
        • Burst Balloons
      • Knapsack
        • 📐Subset Sum
        • 🪙Coin Change
        • Coin Change 2
        • ⏹️Perfect Sqaures
        • 0/1 Knapsack
        • 0/1 Knapsack with Benefits
        • K Sum
        • Combination Sum IV
        • Infinite Knapsack
        • Fractional Knapsack
        • M-d Knapsack
        • Backpack IV
      • Tree DP
        • House Robber III
        • Tree Vertex Cover
        • Longest String Chain
        • K Edit Distance
      • Game DP
        • Blackjack
        • Biased Coins K heads
        • Coins in a Line
        • Stone Game
  • Part 3
    • Advanced Topics
      • Concurrency
        • Coroutine
        • Goroutine
          • Equivalent Binary Trees
        • Mutex
          • Web Crawler
      • Scientific Computing
        • 0 Computer Arithmetic
        • 1 Root Finding
        • 2 Numerical Linear Algebra
        • 3 Least Square Approximation
      • Computational Complexity
        • Asymptotic Analysis
        • NP-completeness
        • Classic NPC Problems
        • Proving Problems NPC
      • Linear Programming
        • Integer Linear Programming
      • Randomized Algorithms
      • Machine Learning
        • Learning Theory
          • Consistency Model
          • PAC Learning Model
          • PAC Examples
          • Unions of Intervals
  • Part 4
    • Advanced Data Structures
      • Set Data
        • Union Find
      • Multidimensional Data
        • Binary Tree
          • K-dimensional Tree
          • Segment Tree
            • Interval Sum
            • Range Sum Query
            • Range Sum Query 2D
            • The Skyline Problem
            • Count of Smaller Numbers After Self
        • Quadtree
          • Point Quadtree
          • Matrix Quadtree
          • Point-Region Quadtree
        • B-tree
          • R-Tree
      • Text Data
        • Prefix Tree
        • Suffix Tree
        • Inverted Index
      • Graph Data
        • Union Find
      • Cache Replacement
        • LRU Cache
        • LFU Cache
  • Part 5
    • System Design
      • Mini Twitter
      • Design TinyURL
      • Object Oriented Design
    • References
Powered by GitBook
On this page
  • Intro
  • Application
  • Example
  • Reference
  1. Part 3
  2. Advanced Topics

Linear Programming

PreviousProving Problems NPCNextInteger Linear Programming

Last updated 5 years ago

Intro

This topic is more practical and less theoretical in nature. We will follow of the tone of this topic and approach it in a way that is geared toward problem solving instead of rigorous theory building. We won't dive too deep into the underlying algorithm (aka ). It does some matrix magic revisit after math401.

Note: While a polynomial algorithm for LP does exist, simplex is still faster in practice (with worse case being exponential).

Linear Programming (LP) is a method to solve the problem of maximizing or minimizing a linear objective function subject to some linear (inequality) constraints. Naturally, it heavily utilizes linear algebra such as matrices and vectors.

Application

LP is widely used in business ,economics, and engineering to solve optimization problems. Lagrange multipliers do not scale very well. LP models are also very popular in the industry such as food (nutrition), transportation, energy, telecommunications, and manufacturing (Amazon warehouse supply).

Example

Maximize Chocolate Profit

Reference

  • 6.046

  • UBC ECON594

simplex
Lecture 15 Notes
Ch10 Linear Programming
Lagrange Multiplier vs Simplex