1 Basic Information

Lecture time:	Monday 8:00-10:00 / Thursday 10:00-12:00
Lecture room:	HS 002, Campus E 13
Lecturers:	Khaled Elbassioni and Julián Mestre
Textbook:	"Introduction to Linear Optimization" by Bertsimas and Tsitsiklis
Tutorial time:	Thursday 18:00-20:00
Tutorial room:	024 E 14
Tutor:	Mahmoud Fouz

More Courses of the Algorithms and Complexity Group.

2 Lectures

Date	Topic	Book chapter	Lecturer	Handouts
Apr 20	Introduction to Linear Optimization	1	Julian
Apr 23	Vertices, extreme points and basic solutions	2.1-2	Julian	HW 1
Apr 27	Representation of bounded polyhedra Fourier-Motzkin elimination	2.7 2.8	Julian
Apr 30	Deriving the Simplex algorithm Polyhedra in standard form	3.1 2.3	Julian	HW 2
May 4	The Simplex algorithm	3.2	Julian
May 7	Tableau implementation Finding an initial solution	3.3 3.5	Julian	HW 3
May 11	Anti-cycling rules Linear programming duality	3.4 4.1-2	Julian
May 14	The duality theorem Zero-sum games	4.3 notes	Julian	HW 4
May 18	The assignment problem		Julian
May 25	Popular mixed matchings	paper	Julian
May 28	Midterm		Julian
June 4	The network simplex algorithm	7.1-7.3	Khaled
June 8	The maximum flow problem	7.5	Khaled	HW 5
June 15	The max-flow min-cut theorem	7.5	Khaled	HW 6
June 18	The Ellipsoid method	notes	Khaled
June 22	The Ellipsoid method		Khaled	HW 7
June 25	The Ellipsoid method		Khaled
June 29	Separation oracles Affine scaling algorithm	8.5 9.1	Khaled	HW8
July 2	Affine scaling algorithm	9.1	Khaled
July 6	The potential reduction methodtopic	9.3	Khaled	Hw9
July 9	The potential reduction methodtopic	9.3	Khaled
July 13	Integer programming	10	Khaled
July 16	Integer programming formulations	10.3	Julian	HW 10
July 20	Integer programming methods	11.1-2	Julian
July 23	Review		Khaled

3 Ground Rules

This is a 9-credit-point class. There will be two lectures and one exercise session per week.

Your final grade will be based on your performance in the midterm and final exams---each is worth half of the final grade. You need to get at least 50% of the exercise credit to be able to take the final exam. We will have the exams in our usual classroom (HS 002). There will be a make-up exam; this exam is comprehensive. Your final grade will be the best of the average of your midterm and final exams scores, and the make-up exam. Here are the dates of the exams:

Midterm:	Thusday 28 May at 10:00-12:00
Final:	Monday 27 July at 8:00-10:00
Make-up:	Monday 5 October at 10:00-12:00

4 Grades

Below are the grades based on you preformance on the midterm, final, and re-exam. These grades are final. If you have any question regarding your grade, please get in touch with us. In order to preserve your privacy we only display the last four digits of your matriculation number.

Matr #	Grade
0519	--
8685	--
1517	--
2561	3.7
5727	2.0
6340	3.3
9180	2.3
9206	4.0
9291	2.3
9500	2.0
9517	2.3
9540	1.3
9697	2.0
2771	2.3
4138	2.0
1581	1.7
3555	1.7
4341	2.3
4854	1.7
4859	2.3
4875	2.3
5341	3.3
5413	1.0
5741	2.7
5754	2.0
5755	1.7
5909	1.7