Simple and hard problems (two lectures)

What distinguishes a simple optimization problem, or a difficult one? We will learn about some simple problems, such as linear optimization and classes of network flow problems. We also mention the definition of the related topics of matroid problems and greedy algorithms. Other examples of simple/hard problems are continuous/binary knapsack problems.

Literature:

- - - Chapter 3: "Well-Solved Problems" from "Integer Programming" (Wolsey, 2021, 2^nd ed)
    - Chapter 2.1–2.2 from the book "Knapsack problems—Algorithms and computer implementations" (Martello and Toth, 1990)

Lagrangean relaxation (six lectures, I–VI)

Literature: "Lagrangean duals and subgradient methods for linear and mixed-binary linear optimization" (A.-B. Strömberg, v0.2, 2022)

I–II: Lagrangean duality, polyhedral descriptions, and optimality conditions for linear optimization problems

Literature: Strömberg (2022), Sections 1–3

III: Lagrangean dualization of mixed-binary linear optimization and its convexified counterpart. Conditions for optimality and near-optimality.

Literature: Strömberg (2022), Section 4

IV: Subgradient optimization methods for solving the Lagrangean dual problem

Literature: Strömberg (2022), Section 5.1

V: Convergence of ergodic sequences of primal solutions to the optimal set of the convexified primal problem

Literature: Strömberg (2022), Section 5.2–5.5

VI: Recovery of (near-)optimal solutions to the primal mixed-binary optimization problem by the use of dual sequences, near-optimal dual solutions, Lagrangean heuristics, and core problems

Literature: Strömberg (2022), Section 6

Complementary literature on Lagrangean duality and subgradient methods

- Larsson, Patriksson, and Strömberg (1999) (reachable from Chalmers domain)
- A further developed averaging strategy: Gustavsson, Patriksson, and Strömberg (2015)
- On global optimality conditions for discrete optimization: Larsson and Patriksson (2006)
- Recovery of primal solutions from dual subgradient methods for mixed binary linear programming: Aldenvik and Schierscher (2015)
- Large-scale binary linear optimization solved by dual subgradient optimization, primal ergodic sequences, and core problems: Juneberg (2001)

Column generation (three lectures, I–III)

Development of cutting plane methods, column generation, and Dantzig-Wolfe decomposition. Application to linear optimization problems. Extension of the Dantzig-Wolfe decomposition to integer linear optimization. Application to the classic cutting stock problem as well as its combination with the branch–and–bound method, known as branch–and–price.

Literature: "A primer in column generation" by Desrosiers and Lübbecke (2005)

Complementary literature on column generation

- "Branch-and-price: Column generation for solving huge integer programs" by Barnhart et al. (1998) (reachable from Chalmers domain)

Benders decomposition (one lecture)

The dual equivalent to the Dantzig-Wolfe decomposition is a cutting plane method. While Dantzig-Wolfe decomposition does not extend to integer programming, the cutting plane method does, whence it is referred to as Benders decomposition. We derive it and discuss its applications.

Literature: Chapter 7.3: "Benders' Partitioning Algorithm for Mixed-Variable Programming Problems" from "Optimization Theory for Large Systems" (Lasdon, Macmillan 1970)

Combining decomposition principles (one lecture)

Finally, for a basic problem in the field of facility location, we take a closer look at the workings of a combination of several of the decomposition methods treated in this course.

Literature: Barcelo, Fernandez, and Jörnsten (1991): "Computational results from a new Lagrangean relaxation algorithm for the capacitated plant location problem" (reachable from Chalmers domain)

Summary of the course (one lecture)

During this final lecture, we will go through the solution of (part of) a previous exam.