Search for tag: "simplex"

LP Polyhedra-Lec13

perturbation method, complexity of simplex method, primal and dual dictionaries.

From  Jesus De Loera on March 7th, 2021 0 likes 11 plays 0  

2020-11-23: Cutting plane algorithms (MAT 168 Optimization)

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…

From  Matthias Koeppe on November 23rd, 2020 0 likes 17 plays 0  

2020-11-16: LP duality, complementarity (MAT 168 Optimization)

Dual (complementary) basis; dual dictionary, negative transpose property of the dictionary pair; complementarity of primal and basic dual solutions; dual simplex method; complementary slackness…

From  Matthias Koeppe on November 16th, 2020 0 likes 22 plays 0  

2020-11-02: Transportation, min-cost flow problems (MAT 168 Optimization)

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)…

From  Matthias Koeppe on November 2nd, 2020 0 likes 26 plays 0  

2020-10-28: LP pivot rules, fundamental theorem (MAT 168 Optimization)

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…

From  Matthias Koeppe on October 28th, 2020 0 likes 21 plays 0  

2020-10-26: Simplex method with perturbations (MAT 168 Optimization)

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…

From  Matthias Koeppe on October 26th, 2020 0 likes 21 plays 0  

2020-10-19: Primal simplex method, phase I (MAT 168 Optimization)

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

From  Matthias Koeppe on October 19th, 2020 0 likes 49 plays 0  

berkeley-combinatoricsseminar-April2020

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…

From  Jesus De Loera on April 28th, 2020 0 likes 17 plays 0