Topic outline

  • MS-EV0022 Combinatorial Optimization

    Overview

    Mathematical optimization is a subfield from Applied Mathematics in which one seeks to find variable values (representing decisions) within a domain that maximise (or minimise) the value of a given function (a performance measure). Its applications lie even beyond mathematics and engineering, reaching transportation, air traffic control and bioinformatics. A special branch called combinatorial optimization regards problems in which the optimal solution is found from a finite set of potentially feasible solutions. It is a framework composed of problems in network modelling, greedy algorithms, heuristics, meta-heuristics and many others.

    In this course, the student will learn the fundamentals of combinatorial optimization theory and practice and how they can be applied to real-world optimization problems. By the end of the course, it is expected that the student will be capable of analysing the main characteristics of an optimization problem, modelling using standard techniques and deciding the most suitable method for its solution.

    Learning Outcomes:

    Upon completing this course, the student should be able to:

    • Apply the theory and the algorithm from the course as a tool to solve real and more complex problems involving combinatorial and integer optimization;
    • Familiarise themselves with classical problems involving graphs;
    • Learn the difference between approximation, heuristics and greedy algorithms and know where to apply them wisely;
    • Learn complexity theory and its application;
    • Understand whether a given combinatorial optimization problem can be solved efficiently (in polynomial time);
    • Know the main techniques for modelling and solving different combinatorial problems and how to apply them in practice;
    • Know how to use optimization software for implementing and solving combinatorial optimization problems

    Additional Materials

    Lecture notes, lecture slides and exercises.

    Book: Korte, B., and Vygen, J. (2011). Combinatorial optimization, volume 1. Springer.


    Grading

    The course is graded on a scale of 0-5 based on 3 assignments (45 %) and 1 project (60%). 

    Course Staff:

    Lecturer:  Fernando Dias (forename.surname@aalto.fi)

    Assistant: Piyalee Pattanaik (forename.surname@aalto.fi)

    Reception hour:
    Lecturer:  Wednesdays at 12:00 - 13:00 in room Y214 (Otakaari 1). Please confirm the appointment by contacting me via email first.  

    Zulip chat invitation link: https://combinatorics.zulip.aalto.fi/join/rvokxapzlkyrg47smlwjrjya/