About this course
The course is on integer programming methods and structural results in (specific problem formulation) in integer programming. Specifically, the outline of the course is as follows:
 Formulation of problems as integer programs.
 A short introduction to polyhedral theory.
 Integral polyhedra: TDI, network matrices, totally unimodular matrices, network matrices, balanced and totally balanced matrices, and perfect graphs.
 Valid inequalities and strong valid inequalities.
 Duality in integer programming.
 Algorithms like Branch and Bound, Cutting planes, and Column generation.
At the end of the course the student will:

understand the quality of different modeling of integer programming problems.

understand the definition of a polyhedron and its algebraic properties.

be able to solve integer programing problems with various solution methods.
SEMESTER START DATE: March 30, 2025
Contact Hours per Week: 3
Day & Time: TBD (will be announced by midDecember)
Learning outcomes
At the end of the course the student will accomplish the following:
 To formulate combinatorial optimization problems as integer (linear) programs.
 To understand definitions related to polyhedral theory of integer programming.
 To prove and use the integrality properties of polytopes defined using constraint matrices satisfying the definitions of TDI matrices, network matrices, totally unimodular matrices, balanced matrices, totally balanced matrices, and perfect graphs.
 To prove that a given inequality for a new optimization problem is a valid inequality or strong valid inequality.
 To compute the dimension of a face (for a given polytope).
 To understand and use different notions of duality for integer programming.
 To use general purpose algorithms like Branch and Bound, Cutting planes, Column generation and their mixtures.
Examination
Attending virtual lectures and submitting homework assignment via electronic form.
There will be regular homework exercises that will be posted on the moodle website of the course. The plan is to have 5 homework assignments during the semester. The exercise is due to two weeks after the lecture (and the scanned solutions of the exercises will be submitted on the moodle website). Each student submits his/her own solutions to the homework assignments. An exercise that will be submitted late (or not submitted at all) will have a score of 0.
The final grade will be the grade on the homework assignments.
Course requirements
Basic knowledge of linear programming
Resources
Activities
Attending virtual lectures and submitting homework assignment via electronic form
Additional information
 Contact a coordinator
 CreditsECTS 4
 LevelMaster
 Contact hours per week3
 InstructorsProfessor Asaf Levin
 Mode of instructionHybrid
Offering(s)
Start date
30 March 2025
 Ends13 July 2025
 Term *Spring Semester 2024/25
 LocationHaifa
 Instruction languageEnglish
 Register between29 Oct  29 Nov 2024
Enrolment openApply now