MAT 168 Optimization (Matthias Köppe; Fall 2020)
MAT 168 Optimization (Matthias Köppe; Fall 2020)
-
From Matthias Koeppe
Modeling non-convex piecewise linear functions with convex multipliers and SOS 2 constraints. notes-2020-12-11.pdf Videos and all other materials are copyright 2020… -
From Matthias Koeppe
Modeling convex piecewise linear functions in a data science application (ℓ1 regression). notes-2020-12-09-b.pdf Videos and all other materials are copyright 2020… -
From Matthias Koeppe
Modeling with convex multipliers. notes-2020-12-09-a.pdf Videos and all other materials are copyright 2020 Matthias Köppe and shared as Open Educational Resources… -
From Matthias Koeppe
Determining the dimension of the face induced by a valid inequality for the stable set problem: Cycle inequality, lifted cycle inequality, clique inequality, edge… -
From Matthias Koeppe
The stable set (independent set) problem: Integer programming formulations, Chvátal–Gomory cuts. notes-2020-12-04.pdf Videos and all other materials are… -
From Matthias Koeppe
Review: mixed 0/1 modeling. Facility location: Aggregated vs. disaggregated formulation. Strengthening the no-good formulation of logical AND using a… -
From Matthias Koeppe
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… -
From Matthias Koeppe
Integer programming formulation of the undirected min cut problem. No-good inequalities, facet-defining inequalities. notes-2020-11-25.pdf Videos and all other… -
From Matthias Koeppe
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… -
From Matthias Koeppe
Traveling salesperson problem: Separation of the subtour elimination constraints as a combinatorial optimization problem. TSP formulation using cutset constraints,… -
From Matthias Koeppe
Back to modeling: The (symmetric, metric) traveling salesperson problem (TSP) in the natural IP formulation. Subtour elimination constraints. Modeling with exponentially… -
From Matthias Koeppe
Dual (complementary) basis; dual dictionary, negative transpose property of the dictionary pair; complementarity of primal and basic dual solutions; dual simplex method;… -
From Matthias Koeppe
Negative transpose property; the dual of the dual LP is the primal LP. Strong duality theorem (with proof). notes-2020-11-13.pdf Videos and all other materials are… -
From Matthias Koeppe
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… -
From Matthias Koeppe
Transforming network problems with lower bounds. Transforming node-capacitated problems to arc-capacitated problems. Multi-commodity flow problems. notes-2020-11-06.pdf…