Study points:
7.5
Responsible department:
Faculty of Logistics
Lars Magnus Hvattum
Lecture Semester:
Spring
Teaching language:
English
Duration:
½ year

LOG734 Heuristics in Analytics (Spring 2019)

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.

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