
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 cuttingplane 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 nodearc 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. notes20201026.pdf Videos and all other materials are copyright…


Primal phase I of the simplex method. Definition of extreme points. notes20201019.pdf Videos and all other materials are copyright 2020 Matthias Köppe and shared as Open Educational…


I gave the following lecture in Zoom (COVID 19 era): Combinatorics in the Space of Monotone Paths of a Convex PolytopeAbstract Using a linear functional f on a convex polytope P induces an…
