Valid for: 2015/16
Decided by: Education Board A
Date of Decision: 2015-04-10
Elective for: C4-ks, D4-ks, E4-ks, I4, I4-pvs, Pi4
Language of instruction: The course will be given in English on demand
The purpose of the course is to give an introduction to discrete event simulation, basic optimization approaches, and heuristic methods such as simulated annealing, tabu search, evolutionary algorithms and GRASP.
Knowledge and understanding
For a passing grade the student must
Competences and skills
For a passing grade the student must
Judgement and approach
For a passing grade the student must
In the course we start by studying discrete event simulation. Students learn to write process-oriented and event-scheduling simulation programs in general programming languages. Estimation of accuracy, random number generation, methods for studying rare events, verification and validation are also covered.
Then we proceed to optimization techniques. We study convex problems and their duals. Further, we go to linear programs (LP), the simplex algorithm, and the column generation technique. We show how to model non-linearity. After that we consider integer programming (IP), its relation to LP, and the branch-and-bound method for IP. We also mention the cutting plane method for IP and sketch the computational complexity theory, including the notions of polynomial problems and NP-hardness.
Finally, we consider heuristic methods for combinatorial optimization problems viewed as optimization through simulation. We explain the local search and the role of randomness. We explain the basic meta-heuristics such as simulated annealing, evolutionary algorithms, and GRASP. We also illustrate the Monte Carlo techniques.
Grading scale: TH
Assessment: To pass the course the student must pass the laboratory lessons, the home assignments and a written exam.
Parts
Code: 0115. Name: Examination.
Credits: 5,5. Grading scale: TH. Assessment: Written examination Contents: Written examination
Code: 0215. Name: Home Assignments and Laboratory Lessons.
Credits: 2. Grading scale: UG. Assessment: Home assignments well done and passed the laboratory lessons Contents: Home assignments and laboratory lessons
The number of participants is limited to: No
The course overlaps following course/s: ETS060, ETS120
Course coordinator: Christian Nyberg, Christian.Nyberg@eit.lth.se
Course homepage: http://www.eit.lth.se/course/ets061