MAT 168 Optimization (Matthias Köppe; Fall 2020)
MAT 168 Optimization (Matthias Köppe; Fall 2020)
The following topics are covered in this course:
- Modeling: Examples of optimization problems.
- Graphical method for solving linear programs with 2 variables
- AMPL: a software for modeling and solving linear programs
- Simplex method: dictionary of simplex method, pivoting, ratio test …
- Duality, complementary slackness, dual simplex method
- Phase 1 + 2 methods
- Degeneracy + finite termination; the perturbation method
- Transportation problem + network flow + shortest path problem + max flow problem
- Integer Programming modeling – fixed cost / network design, Boolean logic, 0-1 Knapsack
- Branch and bound method for solving general IP
Videos and all other materials are copyright 2020 Matthias Köppe and shared as Open Educational Resources subject to the Creative Commons Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) license.
-
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…