Optimization in Intelligent Systems

Lecturer:

Tutor:

Supervisor:

Department of Control Engineering

Synopsis:

The goal is to show the algorithms for several combinatorial optimization problems. Following the subject on algorithms, we show optimisation techniques based on graphs, integer linear programming, heuristics, approximation algorithms and state space search methods. We focus on application of optimization in stores, ground transport, flight transport, logistics, planning of human resources, scheduling in production lines, message routing, scheduling in parallel computers.

Requirements:

Linear algebra

Agorithmisation

Syllabus of lectures:

Lectures

1.Combinatorial Optimization and its Applications

2.Time Complexity of Algorithms

3.The Shortest Path and Communication Problems

4.Network Flows

5.Linear Programming

6.Integer Linear Programming

7.Branch and Bound Technique and its Applications

8.Heuristics and Metaheuristics

9.Dynamic Programming

10.The Traveling Salesman Problem

11.The Knapsack Problem

12.Scheduling on Monoprocessor

13.Scheduling on Parallel Processors

14.The Job Shop Problem

Labs

1.Introduction to the Scheduling Toolbox

2.Spanning Tree and Clustering

3.The Shortest Path Problem

4.Applications of Network Flows

5.Integer Linear Programming

6.Scheduling and Branch and Bound Technique

7.Approximation Algorithms and the SAT Problem

8.Test

9.Assignment of Term Projects

10.Solving Term Projects - Algorithm Design

11.Solving Term Projects - Algorithm Implementation

12.Solving Term Projects - Experiments

13.Giving over Term Projects

14.Credits

Syllabus of tutorials:

The goal of the lectures is to present the basic building block of the combinatorial optimization. In order to experiment with optimization problems, like scheduling on parallel processors, store optimization, production optimization, students get familiar with experimental environment and optimization library in the labs. In the second part of the lab sessions, the students will work on their individual project.

Study Objective:

Study materials:

Main textbook

[1] B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms. Springer, third ed., 2006.

Some parts of:

[2] J. Demel, Grafy a jejich aplikace. Academia, second ed., 2002.

[3] J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer, second ed., 2001.

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans:

• Inteligentní systémy (compulsory course)