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.
-
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…
2020-12-11: Non-convex piecewise linear modeling…
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…
2020-12-09-b: Convex piecewise linear modeling…
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…
2020-12-09-a: Modeling with convex multipliers…
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…
2020-12-07: Stable set problem, induced face…
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…
2020-12-04: Stable set problem, formulations/cuts…
From Matthias Koeppe
-
Review: mixed 0/1 modeling. Facility location: Aggregated vs. disaggregated formulation. Strengthening the no-good formulation of logical AND using a…
2020-12-02: Facility location, Chvatal-Gomory…
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…
2020-11-30: Logical and mixed 0/1 modeling (MAT…
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…
2020-11-25: Undirected min-cut formulations (MAT…
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…
2020-11-23: Cutting plane algorithms (MAT 168…
From Matthias Koeppe
-
Traveling salesperson problem: Separation of the subtour elimination constraints as a combinatorial optimization problem. TSP formulation using cutset constraints,…
2020-11-20: TSP formulations: strength,…
From Matthias Koeppe
-
Back to modeling: The (symmetric, metric) traveling salesperson problem (TSP) in the natural IP formulation. Subtour elimination constraints. Modeling with exponentially…
2020-11-18: Traveling salesperson problem (TSP)
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;…
2020-11-16: LP duality, complementarity (MAT 168…
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…
2020-11-13: Strong LP duality theorem (MAT 168…
From Matthias Koeppe
-
2020-11-09: Weak LP duality theorem (MAT 168… 14 of 15
2020-11-09: Weak LP duality theorem (MAT 168…
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…2020-11-09: Weak LP duality theorem (MAT 168…
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…
2020-11-06: Multi-commodity flow, transformations…
From Matthias Koeppe
Search for ""