This page serves as a student support and contains course information, schedules, lecture notes, and project assignment information etc.

Notifications about how and when to sign-up for workshops, and project and bonus point presentations, possible changes in the schedule, etc will be communicated as announcements. To stay tuned, make sure that you allow notifications from this Canvas course.

Syllabus

The course is given simultaneously for Chalmers and GU students. The requirements are equivalent, but with different course codes and grading scales.

- Chalmers: TMA522 syllabus
- GU: MMA511 syllabus

For students having special educational needs

- - Link to Chalmers' student support
  - If you have been granted support, you are welcome to contact the examiner to inform about the type of support and discuss how this can best be provided.

Timeline and organisation

- The timeline of all teaching moments is found in the Course plan (version 251017)
  - NOTE: New version of the course plan 251104 (revised optional hours for Workshop 1)
- Deadlines for course moments are listed in the Syllabus section
- For the teaching rooms, see the TimeEdit schedule
- Practicalities around the project work, presentations, and workshops are summarised in the lecture notes of Lecture 1 (see the Files section)

Examination and requirements

The examination requirements of the course are in brief (i) two group project assignments, (ii) presence at two workshops, (iii) one project presentation and opposition (including presence), and (iv) a written exam. Plus a few collaboration reports.

The formal requirements for passing the course are found here: Course requirements and examination

The written exam
- A bonus point can be gained from activities during the exercise sessions. See the assignment Marks from exercises > possible bonus point.
- Here is a List of theorems that may occur
- A number of previous exams are found in the Files section
- Search dates for written exams

Mandatory occasions

In each of the study weeks 2, 4, and 6 (i.e., weeks 46, 48, and 50) there is mandatory presence at a workshop or a project presentation:

- - - There are optional dates/hours for the mandatory sessions. All optional dates are visible in TimeEdit and clearly indicated in the course plan (see above).
      - NOTE, however, that some of these options may be removed depending on the number of students that register for the course.
    - Each student/group must sign up for one optional occasion of each session. This will be handled via "choodles" in the respective preceding weeks, communicated via announcements.
    - In total, each student must be present and active during three (3) mandatory occasions.

Workshops and project assignments

For Workshop 1 in study week 2, and the two project assignments, instructions and descriptions are found on the links below.

- - - Workshop 1: The aim is to have a fruitful discussion on different models and relaxations and which every student should be able to follow. You need to prepare by reading the study material and elaborate on the questions.
    - Description of Project Assignment 1
    - Presentation of and opposition on Assignment 1
    - Description of Project Assignment 2
    - Workshop 2 is connected to Project Assignment 2. Each project group should present their suggested model(s) and discuss it with other groups.

On the use of AI tools

There is currently a rapid development of AI systems which can generate text and also write code, etc., often referred to as ‘chatbots’. The use of AI tools may reduce your learning of the course material as well as the possibility for the teacher to assess your knowledge in an examination.

Please, read Chalmers' text "Use of AI systems, known as chatbots, in your studies" on this topic ond note the following ethical guidelines (adapted from kth.se):

- - All members of a group are responsible for the group's work.
  - For any assessment, every student shall honestly disclose any help received and sources used.
  - It is not recommended use chatbots when solving the project assignments in this course.

Literature

The main course literature is a compendium, which is complemented by a few book chapters. The complete list is found here: Course literature

Teaching

The teaching includes lectures, problem solving sessions, advisement sessions, workshops, and project presentations.

The organisation of project assignments, workshops, presentations, and obtaining of bonus points in the course is handled within the Assignments section and notifications via Announcements.

Teachers

- - Examiner, main lecturer, and course responsible: Professor Ann-Brith Strömberg
  - Teaching assistant: PhD student Erik Karlsson Nordling

Overview of the lectures

Lecture notes are published prior to each lecture in the Files section

Overview of the lectures—topics	Reading

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.	Chapter 3: "Well-Solved Problems" from "Integer Programming" (Wolsey, 2021, 2^nd ed) Chapter 2.1–2.2 from "Knapsack problems—Algorithms and computer implementations" (Martello and Toth, 1990)

Lagrangean relaxation (six lectures, I–VI) Literature: A compendium by A.-B. Strömberg (2022). "Lagrangean duals and subgradient methods for linear and mixed-binary linear optimization" v0.2
I–II: Lagrangean duality, polyhedral descriptions, and optimality conditions for linear optimization problems	Sections 1–3
III: Lagrangean dualization of mixed-binary linear optimization and its convexified counterpart. Conditions for optimality and near-optimality.	Section 4
IV: Subgradient optimization methods for solving the Lagrangean dual problem	Section 5.1
V: Convergence of ergodic sequences of primal solutions to the optimal set of the convexified primal problem	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	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: "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 in: "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.

Exercise sessions: problem solving and bonus points

There are five problem solving sessions during the course, during which

1. 1. 1. the teacher solves a number of exercises on the board, in communication with the class, and
    2. the students may take the opportunity to gain one bonus point for the exam by presenting solutions to specific exercises on the board.

In the table below "Bonus exercises" are solved by students while "Exercises solved during the session" are solved on the black board (in guidance) by the teacher. The exercises are found ing the Collection_of_Exercises_v 0.3 2023.pdf

Session	Week no	Bonus exercises	Exercises solved during the session (may be adjusted)
#1	45	Ø	3.3, 3.4
#2	47	3.1 a–d	4.1, 4.2
#3	48	4.3 a–d	5.1
#4	49	5.2 a–c	6.2, 7.1
#5	50	6.3 a–d	7.3, 7.4

Advisement for the project assignments

There are booked occasions for project advisement, at times when we think there will be need for advisement. These occasions are denoted 'lab occasions' (datorlaboration) in TimeEdit.

- - Guides for connecting to the StuDAT computers at Chalmers

Course evaluation and changes in the course

Useful information about the course evaluation process and your role in the same is found here: https://www.chalmers.se/en/education/your-studies/plan-and-conduct-your-studies/course-evaluation/

Randomly chosen student representatives:

- - Erik Albinsson (MPENM)
  - Hadi Chouman (MPENM)
  - Eva María Hönnudóttir Sigurþórsdóttir (MPENM)
  - Sebastian Miles (MPENM)
  - Carl Tudén (MPENM)

Mid-course evaluation meeting

- - Chalmers' suggested agenda for the mid-course meeting.
  - Date and time for the mid-course evaluation meeting (TBD)
  - Notes from the mid-course evaluation meeting will be published here.

Changes in the course since last course round

- - No changes.