Seminar: Cutting Planes in Mixed-Integer Optimization

Summer Semester 2023

PD Dr. Timo Berthold

Content Requirements Dates Organization Contact

Content

The practice of solving optimization problems over integer variable is inextricably linked to the theory of cutting planes. Thr first algorithm described to solve MIPs (mixed-integer programs) was Gomory's general cutting plane method. The branch-and-cut algorithm was a breakthrough for the solvability of many combinatorial optimization problems.
In this seminar, we concentrate on cutting planes which can be applied to general mixed-integer (linear) programs, with little to no knowledge about specific problem structures. Examples include Gomory cuts, mixed-integer rounding cuts, {0,½}-cuts, knapsack cover cuts. Each student will receive a research paper on a particular cut generation algorithm. You will have to prepare a presentation and be able to answer questions on the topic. Additionally, you will have to prepare a written summary plus a short review of the paper.

Requirements

Basic knowledge in mathematical optimization is a requirement; specifically, linear programming and the simplex algorithm should be known. Knowledge of integer programming methods, in particular the concepts of the general cutting plane method and branch-and-bound, are a plus but not required.

Dates

First meeting: Introduction and paper assignment

27.04.2023, 16:30-18:00 in room 4359, at ZIB, FU campus.

Second meeting: Short talks

07.06.2023, 16:00-18:00 in room MA212, TU Berlin.

Third meeting: Seminar talks

12.07.2023, 9:00-18:00, in room 2006, at ZIB, FU campus. Ground floor, round building, main entrance.

Organization

At the first meeting we will shortly discuss the topic in general and distribute the assignments, i.e., papers.
At the second meeting, you are supposed to give a short, introductory talk (at most 5 minutes) on your topic.
To pass, you are required to hand in a short summary of your talk (LaTeX, 5 pages). The summary has to be sent to your advisor by e-mail two weeks before the third meeting. It will be graded and handed back to you before the final meeting in order to provide a first feedback. The seminar itself will take place on one or two days (depending on the number of attendees) during the end of the semester. Talks should be prepared for 45 minutes, such that 15 minutes remain for questions and discussions. Having submitted the summary on time is a requirement for giving the final presentation. Your final grade will be composed of 60% from the evaluation of your presentation and 40% of the quality of your summary. It should go without saying that attendance at all meetings, including all other presentations, is mandatory.

Assignment

The paper selection is not yet finalized. The below papers are examples of what will be covered at the seminar; you might use the abstracts to compile a shortlist of papers to make your final choice from.

Candidate	Topic	Supervisor
LW	Solving linear programming problems in integers Gomory cuts revisited	MT
FB	Strengthening Chvátal-Gomory cuts and Gomory fractional cuts	TB
IM	Aggregation and mixed integer rounding to solve MIPs	MT
AZ	Embedding {0,½}-Cuts in a Branch-and-Cut Framework: A computational study	AC
MM	On optimizing over lift-and-project closures	SB
FG	Split cuts from sparse disjunctions	MB
GT	V-Polyhedral Disjunctive Cuts	MT
JH	Theoretical challenges towards cutting-plane selection	AC
DR	Approximating polyhedra with sparse inequalities	SB
TT	Lifting and separation procedures for the cut polytope	TB

Contact

	Sprechstunde	Raum	Telefon	email
PD Dr. Timo Berthold	n.V.	ZIB 4351	84185-425	timo.berthold(guess what character)campus.tu-berlin.de

Last updated: 13. February 2023