Search for tag: "constraint"

Week 1 Problem Set ARE100A

Week 1 Problem Set ARE100A Spring Quarter 2021 Covers Questions: 3, 6, 7, 8, and 9

From  Joseph Raymond on March 31st, 2021 0 likes 153 plays 0  

2020-12-09-b: Convex piecewise linear modeling (MAT 168 Optimization)

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 Matthias Köppe and shared as…

From  Matthias Koeppe on December 9th, 2020 0 likes 4 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-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-18: Traveling salesperson problem (TSP)

Back to modeling: The (symmetric, metric) traveling salesperson problem (TSP) in the natural IP formulation. Subtour elimination constraints. Modeling with exponentially many constraints. Constraint…

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

2020-11-02: Transportation, min-cost flow problems (MAT 168 Optimization)

Structure of the node-arc incidence matrix, rank deficiency. Generalizing the classic transportation problem to transportation problems with transshipment nodes, and to general (single commodity)…

From  Matthias Koeppe on November 2nd, 2020 0 likes 26 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 28 plays 0