Many problems of everyday (industrial) practice are de facto optimization
problems: in a set of feasible solutions (e.g., assigning tasks to workers or
processors, scheduling of trucks and their routes, design of layout of
electronic components at printed circuit boards) we search for a solution that
is optimal in some respect (like cost, time). These problems can be often
formulated as problems of combinatorial (or discrete) optimization, mostly in
the terms of graphs and (integer) linear inequalities. Some problems can be
satisfactorily solved by quick polynomial algorithms, at others (NP-hard
problems) we have to be satisfied with algorithms that only approximate
optimal solutions, or with other (heuristic) algorithms that give reasonable
outcomes though their quality is not guaranteed generally.
The goal of the course is to explain the area of combinatorial optimization,
the classification of problems that belong here, and the methods used for
their solving in practice.