Christopher Morris > Teaching WS 22/23 > Seminar (Master): Machine Learning for Combinatorial Optimization

Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolation, ignoring that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning, especially graph neural networks (GNNs), as a key building block for combinatorial tasks, either directly as solvers or by enhancing exact solvers. The inductive bias of GNNs effectively encodes combinatorial and relational input due to their invariance to permutations and awareness of input sparsity. This seminar discusses recent progress at the intersection of combinatorial optimization and machine learning, with a specific focus on GNNs.

Requirements for Passing

To pass the seminar, you need to fulfill the following:
  1. Give a 30-minute-long talk about your assigned paper.
  2. Write a 12- to 15-page (excluding title page) detailed report about your assigned paper.
  3. Peer-review your fellow students' reports.
  4. Attend all meetings and actively participate; see below for dates.

Talks

At the end of the semester, each student will give a 30-minute-long talk about their assigned paper. You should provide an overview of your assigned paper and highlight the most important concepts and ideas. Ideally, your presentation should give the audience (i.e., your fellow students) a good understanding of your assigned paper.

Reports

The report gives a detailed overview of the assigned paper. The required report length is 12 to 15 pages, using the provided LaTeX template. This means that after you get your paper assigned, you write your report and submit it for "peer review" by your fellow students. You will receive constructive feedback to improve the paper; afterward, you will receive additional feedback from the seminar organizers. You can then submit an updated, final version, which will be graded. Note that this means that you will also have to write some short reviews on the reports by your fellow students.

Organization

  1. More details are given during the mandatory kick-off meeting.
  2. Papers will be assigned after the kick-off meeting.
  3. The long talks will be presented in day-long block seminar.
  4. All meetings (kick-off and final talks) will take place in Room 228, Theaterstraße 35 - 39.

Dates

Date
11.10.2022, 10:00   Kick-off meeting (in person), slides
10.11.2022, 24:00 Submission of report drafts
01.12.2022, 24:00 Submission of reports for peer review
14.12.2022, 24:00 Submission of peer reviews
20.12.2022, 10:00 Discussion of peer reviews (in person)
09.01.2023, 24:00 Submission of reports
16.01.2023, 24:00 Feedback by the organizers
31.01.2023, 24:00 Submission of final reports
15.02.2023, 24:00 Submission of of presentation slides
23.02.2023, 10:00 Talks (in person)

Papers

The papers can be chosen from the following list.
  1. One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction
    2. (Tilman Hoffbauer)
  2. Exact Combinatorial Optimization with Graph Convolutional Neural Networks
    3. (Nhan Thanh Le)
  3. MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers
  4. Learning Combinatorial Optimization Algorithms over Graphs
  5. Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning
    6. (Jürgen Lentz)
  6. Erdos Goes Neural: An Unsupervised Learning Framework for Combinatorial Optimization on Graphs