interactive resource
lpviz
Explore feasible regions and compare several linear-programming algorithms in the browser.
Open resourceISE 5405 · Optimization I
Linear-programming theory, geometry, algorithms, modeling, and computation.
course materials
Course logistics, instructional team, materials, assessment, policies, key dates, and first-week setup.
Why optimization matters, LP language and modeling, graphical solution concepts, canonical forms, and piecewise-linear reformulations.
Logical implication, proof techniques, counterexamples, mathematical writing, and a practical introduction to LaTeX.
Convexity, polyhedra, extreme points, vertices, basic feasible solutions, and adjacency.
Standard-form bases, degeneracy, existence and optimality of extreme points, convex hulls, and Fourier–Motzkin elimination.
Basis partitions, equality-preserving feasible directions, maximum feasible steps, reduced costs, and the basis optimality test.
Cycling, lexicographic pivoting, Bland’s rule, and finite termination, with a complete three-dimensional worked example.
Find an initial feasible basis with Phase I, remove artificial variables, restore the original objective, and complete the two-phase method.
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.
Build objective bounds from weighted constraints, form LP duals, and use weak duality to verify optimality certificates.
Connect strong duality, complementary slackness, and simplex reduced costs through complete numerical optimality certificates.
Interpret optimal dual variables as marginal costs, track valid ranges, and use the dual simplex method to restore primal feasibility while preserving dual feasibility.
Use Farkas’ lemma to certify infeasibility, collect LP optimality conditions, and apply duality to fractional knapsack and finite-state arbitrage.
Compute valid ranges for right-hand sides and objective coefficients, handle simultaneous and model changes, and interpret solver sensitivity reports.
Use duality for airline revenue management and robust linear optimization with uncertain coefficients, right-hand sides, and uncertainty budgets.
Use dual prices to add useful variables, solve a cutting-stock LP through column generation, and add violated constraints through separation.
Model shipments and shared capacities as continuous network LPs, find augmenting paths including reverse residual arcs, and certify maximum flow using a minimum cut.
Trace Dijkstra and Bellman–Ford for shortest routes, then compare Prim and Kruskal for minimum spanning trees, with complete graph states and practice answers.
Build and certify an assignment with a complete Hungarian trace, alternating paths, and dual adjustments. Optional auction example in the appendix.
Connect node balances, incidence matrices, spanning-tree bases, dictionaries, reduced costs, and one complete network-simplex pivot.
Work through capacity-limited pivots, bound flips, zero-length pivots, artificial-root initialization, and the integrality of network LPs.
Visualize a central path, construct logarithmic barriers, compute a Newton step, and connect the barrier equations to primal–dual optimality certificates.
Compute a complete primal–dual Newton update, choose a positive step, check stopping conditions, and explore a first-order method for large linear programs.
explore
Optional visual tools supplement the native lecture decks. External resources open on their own sites.
interactive resource
Explore feasible regions and compare several linear-programming algorithms in the browser.
Open resourcepresenting