Search for tag: "inequalities"

LP Polyhedra-Lec9

Weyl-Minkowski's theorem proved using Fourier Motzkin elimination and Polarity of cones.

From  Jesus De Loera on March 2nd, 2021 0 likes 31 plays 0  

LP Polyhedra-Lec8

Weyl-Minkowski's theorem proved using Fourier Motzkin elimination and Polarity of cones.

From  Jesus De Loera on March 2nd, 2021 0 likes 34 plays 0  

Lecture168-Algorithms2

This is the second section of the course MAT 168, we explain how solvers work. We cover topics such as Branch and bound, cutting planes, heuristics, and computational complexity.

From  Jesus De Loera on January 25th, 2021 0 likes 69 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-12-02: Facility location, Chvatal-Gomory cuts (MAT 168 Optimization)

Review: mixed 0/1 modeling. Facility location: Aggregated vs. disaggregated formulation. Strengthening the no-good formulation of logical AND using a Chvátal–Gomory cut. General…

From  Matthias Koeppe on December 2nd, 2020 0 likes 17 plays 0  

2020-11-30: Logical and mixed 0/1 modeling (MAT 168 Optimization)

Modeling logical AND using 4 no-good inequalities from the truth table; or using 3 facet-defining inequalities. Mixed 0/1 modeling: Extended formulations of models with fixed charge costs or…

From  Matthias Koeppe on November 30th, 2020 0 likes 23 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-20: TSP formulations: strength, relaxations (MAT 168 Optimization)

Traveling salesperson problem: Separation of the subtour elimination constraints as a combinatorial optimization problem. TSP formulation using cutset constraints, strengthened cutset constraints,…

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

2020-11-09: Weak LP duality theorem (MAT 168 Optimization)

Introduction to linear optimization duality. Weak duality theorem. notes-2020-11-09.pdf Videos and all other materials are copyright 2020 Matthias Köppe and shared as Open Educational Resources…

From  Matthias Koeppe on November 9th, 2020 0 likes 20 plays 0