Jiaxiang Li

ISE 5405 · Optimization I

Fall 2026

Linear-programming theory, geometry, algorithms, modeling, and computation.

Instructor
Jiaxiang (Jason) Li
Meetings
Tuesdays and Thursdays, 9:30–10:45 a.m.
Location
Durham Hall 261

course materials

Lectures

  1. lecture 0

    Syllabus & Logistics

    Course logistics, instructional team, materials, assessment, policies, key dates, and first-week setup.

    • syllabus
    • course logistics
    • policies
  2. lecture 1

    Introduction & Linear Optimization

    Why optimization matters, LP language and modeling, graphical solution concepts, canonical forms, and piecewise-linear reformulations.

    • linear programming
    • standard form
    • modeling
    • geometry
  3. lecture 2

    Proof Techniques & LaTeX

    Logical implication, proof techniques, counterexamples, mathematical writing, and a practical introduction to LaTeX.

    • proofs
    • logic
    • LaTeX
  4. lecture 3

    The Geometry of Linear Programming I

    Convexity, polyhedra, extreme points, vertices, basic feasible solutions, and adjacency.

    • geometry
    • polyhedra
    • basic feasible solutions
  5. lecture 4

    The Geometry of Linear Programming II

    Standard-form bases, degeneracy, existence and optimality of extreme points, convex hulls, and Fourier–Motzkin elimination.

    • bases
    • degeneracy
    • extreme points
  6. lecture 5

    Simplex I: Basis Directions and Reduced Costs

    Basis partitions, equality-preserving feasible directions, maximum feasible steps, reduced costs, and the basis optimality test.

    • simplex
    • basis directions
    • reduced costs
  7. lecture 6

    Simplex II: Cycling and Anticycling

    Cycling, lexicographic pivoting, Bland’s rule, and finite termination, with a complete three-dimensional worked example.

    • simplex
    • cycling
    • lexicographic rule
    • Bland’s rule
    • 3D geometry
  8. lecture 7

    Simplex III: Two-Phase Simplex

    Find an initial feasible basis with Phase I, remove artificial variables, restore the original objective, and complete the two-phase method.

    • simplex
    • two-phase method
    • initial basis
  9. lecture 8

    Simplex IV: Column Geometry and Efficiency

    Column geometry and a geometric pivot, the textbook long-path example, Dantzig’s rule on the n-dimensional Klee–Minty family, the Hirsch counterexample, and an introduction to ellipsoid and interior-point methods.

    • simplex
    • column geometry
    • computational efficiency
    • LP algorithms
  10. lecture 9

    Duality I: Bounds and the Dual Problem

    Build objective bounds from weighted constraints, form LP duals, and use weak duality to verify optimality certificates.

    • duality
    • objective bounds
    • weak duality
  11. lecture 10

    Duality II: Optimality and Complementary Slackness

    Connect strong duality, complementary slackness, and simplex reduced costs through complete numerical optimality certificates.

    • strong duality
    • complementary slackness
    • optimality certificates
  12. lecture 11

    Duality III: Marginal Costs and Dual Simplex

    Interpret optimal dual variables as marginal costs, track valid ranges, and use the dual simplex method to restore primal feasibility while preserving dual feasibility.

    • duality
    • marginal costs
    • dual simplex
  13. lecture 12

    Duality IV: Farkas’ Lemma and LP Optimality Conditions

    Use Farkas’ lemma to certify infeasibility, collect LP optimality conditions, and apply duality to fractional knapsack and finite-state arbitrage.

    • Farkas lemma
    • KKT
    • fractional knapsack
    • arbitrage
  14. lecture 13

    Sensitivity Analysis: Ranges and Reoptimization

    Compute valid ranges for right-hand sides and objective coefficients, handle simultaneous and model changes, and interpret solver sensitivity reports.

    • sensitivity analysis
    • reoptimization
    • parametric LP
  15. lecture 14

    Applications of Duality: Revenue Management and Robust Optimization

    Use duality for airline revenue management and robust linear optimization with uncertain coefficients, right-hand sides, and uncertainty budgets.

    • duality
    • revenue management
    • robust optimization
  16. lecture 15

    Column Generation and Constraint Generation

    Use dual prices to add useful variables, solve a cutting-stock LP through column generation, and add violated constraints through separation.

    • column generation
    • cutting stock
    • constraint generation
  17. lecture 16

    Network Models and Maximum Flow

    Model shipments and shared capacities as continuous network LPs, find augmenting paths including reverse residual arcs, and certify maximum flow using a minimum cut.

    • network models
    • maximum flow
    • minimum cut
  18. lecture 17

    Shortest Paths and Spanning Trees

    Trace Dijkstra and Bellman–Ford for shortest routes, then compare Prim and Kruskal for minimum spanning trees, with complete graph states and practice answers.

    • shortest paths
    • Dijkstra
    • Bellman–Ford
    • spanning trees
  19. lecture 18

    Assignment and the Hungarian Method

    Build and certify an assignment with a complete Hungarian trace, alternating paths, and dual adjustments. Optional auction example in the appendix.

    • assignment
    • Hungarian
    • auction
  20. lecture 19

    Network Simplex I: Tree Bases and Pivots

    Connect node balances, incidence matrices, spanning-tree bases, dictionaries, reduced costs, and one complete network-simplex pivot.

    • network simplex
    • minimum-cost flow
  21. lecture 20

    Network Simplex II: Bounds, Initialization, and Integrality

    Work through capacity-limited pivots, bound flips, zero-length pivots, artificial-root initialization, and the integrality of network LPs.

    • network simplex
    • minimum-cost flow
  22. lecture 21

    Interior-Point Methods I: Barriers and the Central Path

    Visualize a central path, construct logarithmic barriers, compute a Newton step, and connect the barrier equations to primal–dual optimality certificates.

    • interior point
    • central path
    • Newton method
  23. lecture 22

    Interior-Point Methods II and an Introduction to PDHG

    Compute a complete primal–dual Newton update, choose a positive step, check stopping conditions, and explore a first-order method for large linear programs.

    • interior point
    • primal–dual methods
    • PDHG

explore

Practice and demos

Optional visual tools supplement the native lecture decks. External resources open on their own sites.

interactive resource

lpviz

Explore feasible regions and compare several linear-programming algorithms in the browser.

  • geometry
  • simplex
  • interior point
Open resource

presenting

Keyboard at a glance

← →
previous / next step
Space
reveal / advance
Home
first slide
End
last slide
F
fullscreen
Esc
close activity
Tab
move through controls
Print
all final-state slides