Facts about the course
- ECTS Credits:
- 7.5
- Responsible department:
- Faculty of Logistics
- Lecture Semester:
- Spring
- Teaching language:
- English
- Duration:
- ½ year
LOG734 Heuristics in Analytics (Spring 2019)
About the course
The course focuses on using heuristic optimization methods to solve computationally challenging optimization problems, with use both in prescriptive and predictive analytics. An understanding of heuristics is built from the ground up, starting from classical construction heuristics and improvement heuristics. The course then proceeds with a thorough treaty of metaheuristics. Formal definitions are used to clarify the structure of the algorithms, and examples are given regarding their use to solve well-known optimization problems. Attention is drawn towards the implementation of heuristics using a suitable programming language. Examples of using heuristics in prescriptive analytics (solving hard combinatorial optimization problems) and in predictive analytics (using metaheuristics for classification and prediction problems in data mining) are discussed at the end of the course.
The course is connected to the following study programs
Recommended requirements
LOG716 Mathematical modelling in logistics is highly recommended. Some knowledge of exact optimization methods is highly recommended, for example by taking LOG733 in parallel.
The student's learning outcomes after completing the course
After having completed the course, the students should be able to:
Explain the difference between exact algorithms, approximation algorithms, and heuristic algorithms
Define what is meant by primal and dual bounds and how they can be obtained
Give an account of how construction heuristics work, and give examples of known construction heuristics
Explain what is meant by a greedy construction heuristic, and contrast this with regret based heuristics
Give an account of how improvement heuristics work, based on the concept of neighborhoods
State a definition of metaheuristics, and discuss the different meanings that this term may have
Describe and define local search based metaheuristics, including simulated annealing and tabu search
Describe and define construction based metaheuristics, including grasp and squeaky wheel optimization
Describe and define population based metaheuristics, including genetic algorithms and scatter search
Discuss the dangers of using metaphors when working with metaheuristics, and to give an account of the historical significance that metaphors have played for metaheuristics
Design and implement a metaheuristic for a given optimization problem and evaluate the appropriateness of choices made during design and implementation
Discuss the concepts of intensification and diversification, and classify known components of metaheuristics in relation to those two concepts
Explain the concept of matheuristics and to provide examples of how they have been used to solve combinatorial optimization problems
Present the challenges associated to parameter tuning and how they can be handled, both on-line (hyper-heuristics and robust heuristics) and off-line (using iRace, SMAC, or ParamILS)
Discuss how metaheuristics can be analyzed and improved using target analysis and fitness landscape analysis
Implement efficient heuristics in a programming language such as C++
Forms of teaching and learning
Three hours of lectures per week
Examination
Form of assessment:Oral Examination
Proportion: 100%
Grouping:Individual
Grading scale:Letter (A - F)
Support material:All written and printed aids allowed for the mandatory assignments. In the final oral examination, the students are allowed only to bring their reports written for the mandatory assignments.
Comment:Consists of three mandatory assignments that each count 10 % of the final grade. A final oral examination counts for the remaining 70 % of the grade.
Course evaluation
There will be three mandatory assignments, together accounting for 30 % of the final grade.