Search for tag: "vertices"


Archetypal analysis is an unsupervised learning method that uses a convex polytope to summarize multivariate data. For fixed k, the method finds a convex polytope with k vertices, called archetype…

From  Stefan Schonsheck on April 22nd, 2021 0 likes 0 plays 0  

2020-12-07: Stable set problem, induced face dimension (MAT 168 Optimization)

Determining the dimension of the face induced by a valid inequality for the stable set problem: Cycle inequality, lifted cycle inequality, clique inequality, edge inequality. notes-2020-12-07.pdfThe…

From  Matthias Koeppe on December 7th, 2020 0 likes 19 plays 0  

2020-12-04: Stable set problem, formulations/cuts (MAT 168 Optimization)

The stable set (independent set) problem: Integer programming formulations, Chvátal–Gomory cuts. notes-2020-12-04.pdf Videos and all other materials are copyright 2020 Matthias…

From  Matthias Koeppe on December 4th, 2020 0 likes 16 plays 0  

2020-11-18: Traveling salesperson problem (TSP)

Back to modeling: The (symmetric, metric) traveling salesperson problem (TSP) in the natural IP formulation. Subtour elimination constraints. Modeling with exponentially many constraints. Constraint…

From  Matthias Koeppe on November 18th, 2020 0 likes 19 plays 0  

ECS-175: 2020-11-10 11:00

ECS-175 Lecture 2020-11-10 at 11:00

From  Bernd Hamann on November 10th, 2020 0 likes 119 plays 0  

2020-10-30: Directed graphs, transportation models (MAT 168 Optimization)

Directed simple graphs. Generalizing the assignment model to transportation models. notes-2020-10-30.pdf Videos and all other materials are copyright 2020 Matthias Köppe and shared as Open…

From  Matthias Koeppe on October 30th, 2020 0 likes 25 plays 0  


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