Combinatorial Optimization

Vrije Universiteit Amsterdam

Course Description

  • Course Name

    Combinatorial Optimization

  • Host University

    Vrije Universiteit Amsterdam

  • Location

    Amsterdam, The Netherlands

  • Area of Study

    Computer Programming, Computer Science

  • Language Level

    Taught In English

  • Prerequisites

    Operations Research

  • Course Level Recommendations

    Upper

    ISA offers course level recommendations in an effort to facilitate the determination of course levels by credential evaluators.We advice each institution to have their own credentials evaluator make the final decision regrading course levels.

    Hours & Credits

  • ECTS Credits

    6
  • Recommended U.S. Semester Credits
    3
  • Recommended U.S. Quarter Units
    4
  • Overview

    COURSE OBJECTIVE
    In this course you will learn about the theory of combinatorial optimization problems. Also, you will apply the theory to model and solve complex problems using the available software. In particular, we consider performance measures for algorithms for combinatorial problems such as the running time and the quality of solutions.

    Objectives:
    - To obtain knowledge on the theory of combinatorial optimization
    - To apply the theory to specific optimization problems. For example, by analyzing the running time or performance guarantee of a given algorithm or by constructing an own algorithm.
    - To model problems (for example by integer linear programming) and to solve them using optimization software.

    COURSE CONTENT
    Subjects: Graph theory, integer linear programming, network optimization algorithms, (matching, maximum flow, minimum cost flow, traveling salesman problem, vehicle routing), complexity of optimization (NP-hardness) approximation algorithms, local search, online optimization, randomized algorithms.

    TEACHING METHODS
    Lectures + Tutorials

    TYPE OF ASSESSMENT
    Written exam (50%) + assignments (50%) For both parts, a minumum score of 5.0 (out of 10) is required.

    RECOMMENDED BACKGROUND KNOWLEDGE
    Mathematical Optimization, Data Structures and Algorithms

Course Disclaimer

Courses and course hours of instruction are subject to change.

Some courses may require additional fees.