|
|
|
Continuation of modern geometric descriptions of polyhedrons. Included are definitions of convex polyhedron, half spaces, hyperplanes, affine dimension, and some connections to Linear Programming.
|
|
Discussion of simplex method with respect to convergence, degeneracy of pivots, pivot rules, and optimality. Improvement of theorems in previous lectures so now we can guarantee that the simplex…
|
|
Phase 1 of simplex method and examples with pivot tools.
|
|
Terminology and notation for the simplex method. Dictionaries, basis, slack variables, basic feasible solutions and the relationship between these. Certification of results in terms of the objective…
|
|
|
|
|
|
|
|
perturbation method, complexity of simplex method, primal and dual dictionaries.
|
|
|
|
See https://sites.google.com/view/maddd/ for the details.
|
|
Separation of constraints within a cutting-plane algorithm for solving an LP with exponentially many constraints. Warm starts: Adding a valid inequality to a dictionary by rewriting it in the…
|
|
Dual (complementary) basis; dual dictionary, negative transpose property of the dictionary pair; complementarity of primal and basic dual solutions; dual simplex method; complementary slackness…
|
|
Structure of the node-arc incidence matrix, rank deficiency. Generalizing the classic transportation problem to transportation problems with transshipment nodes, and to general (single commodity)…
|
|
Pivot rules. Unboundedness. The simplex method with lexicographic perturbation and a deterministic pivot rule as an algorithm. Fundamental theorem of linear optimization. Preview of LP development…
|
|
Resolving degeneracy using lexicographic perturbations. Finite termination of the simplex method with lexicographic perturbations. notes-2020-10-26.pdf Videos and all other materials are copyright…
|