Search for tag: "inequality"

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  

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 21 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 18 plays 0  

2020-10-12: LP dictionaries, basic solutions (MAT 168 Optimization)

Linear optimization problems in standard form. Linear algebra review: Rank of a matrix. Introducing slack variables. Dictionary, basic and nonbasic variables, basic solution. notes-2020-10-12.pdf …

From  Matthias Koeppe on October 12th, 2020 0 likes 31 plays 0  

2020-10-07: Production planning case study (MAT 168 Optimization)

Public transport case study: Equality constraint, objective function. Production planning example: Variables, constraints. Review: normal equation of lines in the plane; plotting the feasible region.…

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