Optimization (WiSe 2014)

Welcome to the Wiki of the MSc lecture Optimization (VL: 19400701, UE: 19400702)

News

• Results of 2nd exam are online

General Information

SWS: 3+2 ECTS: 6
Lecturers: Alexander Bockmayr, Knut Reinert
Exercises: Annika Röhl
Language: English

Requirements for Aktive Teilnahme

You have to hand in 75% of the programming exercises. (You have to show reasonable programms and can explain them).
And you have to hand in solutions for the theoretical part. (It is sufficient to write something down, which shows you thought about the exercises and tried to solve it. You do not have to have an exact solution).
In addition, you need to reach a minimum of 50% of all points in both reviews.

Times and Places

Event	Day	Time	Address	Room
Lecture	Tue	10-12	Takustr. 9	SR006
Lecture	Thu	10-12	Takustr. 9	SR006
Exercise	Fri	12-14	Arnimallee 6	SR 032
Exercise	Fri	14-16	Arnimallee 6	SR 032 or SR 017

Content

• Linear optimization, polyhedra, Simplex algorithm, duality
• Integer linear optimization, branch and bound, cutting planes, branch and cut
• Constraint programming
• Local search and metaheuristics
• Polynomial approximation of NP-hard optimization problems

Schedule

Date	Lecture	Lecturer
09.12.-06.01.	Linear Optimization
09.12.2014	Lecture 1: Introduction to linear optimization	Bockmayr
11.12.2014	Lecture 2: Polyhedra and Simplex algorithm	Bockmayr
16.12.2014	Lecture 3: Simplex algorithm, application to metabolic networks	Bockmayr
18.12.2014	Lecture 4: Duality, complexity of LP	Bockmayr
06.01.-22.01.	Integer Linear Optimization
06.01.2015	Lecture 5: ILP - Introduction	Reinert
08.01.2015	Lecture 6: ILP - Modelling	Reinert
13.01.2015	Lecture 7: ILP - Branch-and-Cut I	Reinert
15.01.2015	Lecture 8: ILP - Branch-and-Cut II	Reinert
16.01.2015	Review 1 (during exercises)
20.01.2015	Lecture 9: ILP - Lagrange I	Reinert
22.01.2015	Lecture 10: ILP - Lagrange II	Reinert
27.01.-10.02.	Constraint Programming and Metaheuristics
27.01.2015	Lecture 11: Constraint programming I	Bockmayr
29.01.2015	Lecture 12: Constraint programming II	Bockmayr
03.02.2015	Lecture 13: Constraint and integer programming	Bockmayr
05.02.2015	Lecture 14: Local search and metaheuristics I	Bockmayr
06.02.2015	Review 2 (during exercises)
10.02.2015	Lecture 15: Local search and metaheuristics II	Bockmayr
19.02.2015	Exam

Additional Material

In this wiki you find additional material for the lectures and exercises (send your wiki login name to Rene Rahn to get access): AdditionalMaterial

2nd Exam (2. Klausur)

Matrikelnummer	points	mark
xxxx068	54	3,0
xxxx177	80	1,3
xxxx178	84,5	1,0
xxxx198	36	5,0
xxxx220	34,5	5,0
xxxx263	23,5	5,0
xxxx442	35,5	5,0
xxxx523	58	2,7
xxxx533	46,5	3,7
xxxx618	31	5,0

1st Exam (Klausur)

Matrikelnummer	points	mark
xxxx178	0	5,0
xxx2710	0	5,0
xxx8177	0	5,0
xxx7263	4	5,0
xxx3618	8,5	5,0
xxx1779	21	5,0
xxx2442	24	5,0
xxx4523	25,5	5,0
xxx2669	26,5	5,0
xxx8973	27,5	5,0
xxx6846	32,5	5,0
xxxx068	36	5,0
xxxx533	37	5,0
xxx6435	37,5	5,0
xxxx598	40	4,0
xxx3057	41	4,0
xxx4374	43	4,0
xxx9679	46,5	3,7
xxx3416	49	3,3
xxxx221	51	3,3
xxx9223	51,5	3,3
xxx7540	58,5	2,7
xxx8232	59	2,7
xxx2952	67,5	2,0
xxx9669	69,5	2,0
xxx3051	83	1,0

Exercises

Sign up for the mailing list https://lists.fu-berlin.de/listinfo/AlgoOptiWS14

Nr.	Link (alt / 2013)	Discussion
1	ex_0_2014.pdf	12.12.2014
2	ex_1_2014.pdf	19.12.2014
3	ex_2_2014.pdf	09.1.2015
4	ex_3_2014.pdf	16.1.2015
5	ex_4_2014.pdf	23.1.2015
6	ex_5_2014.pdf	30.1.2015
7	ex_6_2014.pdf	06.2.2015

PracticalExercises

Results Review 1

MatrNr	Pts
xxx3057	35,5
xxx2952	39,25
xxx0827	25
xxx2142	26,5
xxx9669	27,5
xxx2669	13
xxx8232	36
xxx9679	31,5
xxx3051	34,5
xxx0533	29,5
xxx8685	21
xxx0178	38,5
xxx4140	10,5
xxx7540	40,5
xxx3416	29,5
xxx9223	34,5
xxx6435	35,5
xxx0221	39,5
xxx1198	20
xxx0598	24,5
xxx8973	22
xxx8177	48
xxx4374	34
xxx1189	32
xxx0068	35
xxx2710	36
xxx6846	21,5
xxx7263	37
xxx1779	29
xxx3618	30
xxx0220	29,5

Results Review 2

MatrNr	Pts
xxx3057	32,5
xxx2952	39,75
xxx2142	20,5
xxx9669	34,5
xxx2669	19
xxx8232	32,5
xxx9679	32
xxx3051	47
xxx0533	24
xxx8685	16
xxx0178	25,5
xxx4140	25,5
xxx7540	26
xxx3416	33
xxx9223	27
xxx6435	30,5
xxx0221	27,5
xxx1198	28,5
xxx0598	26
xxx8973	21,75
xxx8177	37
xxx4374	36
xxx1189	25,5
xxx0068	22
xxx2710	25,5
xxx6846	29
xxx7263	23
xxx1779	21,5
xxx3618	25,5
xxx0220	26,5