Course syllabus

# Simulering

Simulation

## EITN95, 7,5 credits, A (Second Cycle)

## General Information

## Aim

## Learning outcomes

## Contents

## Examination details

## Admission

## Reading list

## Contact and other information

Simulation

Valid for: 2017/18

Decided by: PLED C/D

Date of Decision: 2017-04-03

Elective for: C4-ks, D4-ks, E4-ks, I4, I4-pvs, M4, 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

- Have some knowledge on different kinds of dynamic models that are used in engineering
- Describe the event-scheduling and the process-oriented approach to writing simulation programs
- Know how to estimate the accuracy of simulation results
- Know the basic notions in optimization theory
- Know how to solve linear and integer optimization problems
- Know the most common heuristic methods for optimization

Competences and skills

For a passing grade the student must

- Write well-structured simulation programs in a general programming language
- Estimate the accuracy of simulation results
- Be able to verify and validate simulation programs
- Know the basic concepts of a Linear Program (LP), convexity, and duality
- Be able to apply the simplex algorithm to linear programming problems
- Know the basic concepts of combinatorial optimization, Integer Program (IP), a Mixed Integer Program (MIP), their applications, and the connection between IP and LP
- Be able to apply the branch-and-bound method to IP
- Have a thorough knowledge of the most common heuristic and meta-heuristic methods including local search and its variations, simulated annealing, tabu search and evolutionary algorithms
- Be able to implement heuristic and meta-heuristic methods, and configure the parameters involved in these methods
- Know the concepts of Monte Carlo method, and be able to implement it for a given optimization problem.

Judgement and approach

For a passing grade the student must

- Show knowledge of the possibilities and limitations of simulation experiments
- Be able to independently construct models for optimization problems and to apply an optimization package (such as MATLAB or alike) for solving them with full understanding of the solution process and output data
- Be able to choose and apply a heuristic method to solve an optimization problems

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 linear programs (LP) and the simplex algorithm. After that we consider integer programming (IP) and Mixed Integer Programming (MIP), the relation between IP and LP, and the branch-and-bound method for IP.

Finally, we consider heuristic and meta-heuristic methods for combinatorial optimization problems viewed as optimization through simulation. We explain the local search and its most common variations. We explain the basic meta-heuristics such as simulated annealing, tabu search and evolutionary algorithms. We also illustrate the Monte Carlo techniques.

Grading scale: TH - (U,3,4,5) - (Fail, Three, Four, Five)

Assessment: Approved home assignments, which are graded, gives grade 3. An approved take-home examination is required for grades 4 and 5.

The examiner, in consultation with Disability Support Services, may deviate from the regular form of examination in order to provide a permanently disabled student with a form of examination equivalent to that of a student without a disability.

Required prior knowledge: Programming, Basic probability, Statistical methods, Mathematical analysis.

The number of participants is limited to: No

The course overlaps following course/s: ETS060, ETS120, ETS061

- Nyberg, C, Compendium in simulation.
- Michal Pioro: Network Optimization Techniques, Chapter 18 in E. Serpedin, E., Chen, T., and Rajan, D. (eds.): Signal Processing, Communications, and Networking,. CRC Press, 2012, ISBN: 978-1-4398-5513-3.

Course coordinator: Björn Landfeldt, bjorn.landfeldt@eit.lth.se

Course homepage: http://www.eit.lth.se/course/eitn95