
Topics of courses taught by the Department of Operations Reseach
(for thirdyear programmer students)
Goals: To exhibit the fundamental models of operational research and
their computational methods.
Prerequisities: linear algebra, basic topics of graph theory.
Topics:
 Brief survey of applications. Optimizations models.
 Linear programming: Convex polyhedra. Linear programming
problems. The simplex method and its variants. Efficiency
considerations. Duality theorems of linear programming. Farkas
theorem, Farkas lemma. Matrix games. Von Neumann's theorem.
Sensitivity analysis. Parametric programming. Methods of
multiobjective programming.
 Nonlinear programming: Necessary and sufficient
conditions for optimality. KuhnTucker theorems. Problems with convex
separable objective function. Convex quadratic programming.
 Discrete programming: Basic methods for discrete
programming: cutting planes, branch and bound, dynamic programming.
Knapsack problem.
Assigment problem and its solution by the Hungarian method.
Networks, maximal flow, minimal cost flow. The network simplex
algorithm.
Transportation problems. Cutting stock problems.
(Specialization course for
informatics students)
Goals: To exhibit the algorithmic techniques for the combinatorial optimization.
Prerequisities: basics of graph theory and linear algebra.
Topics:

Different versions of the greedy algorithm for finding a minimum weight
spanning tree. Matroids and the greedy algorithm finds an
optimal set for any nonnegative weighting.
Reachability, shortest paths in case of conservative weightings, Dijkstra
algorithm. Critical path method,
maximum matching algorithm in bipartite graphs, Hall theorem, König
theorem, weighted matching algorithm in bipartite graphs,
Edmonds theorem on the
existence of $k$ edge disjoint spanning arboresences with root $s$, algorithm
for finding a minimum weight spanning arboresence with root $s$. Dynamic
programming: multiterminal shortest paths, Steiner trees, Dilworth theorem.
Circulation, Hoffman theorem, application. Network flows, its
equivalence to via circulation model, MaxflowMincut theorem, FordFulkerson
algorithm, EdmondsKarp algorithm, Menger theorems. Minimum cost flows, Tutte
theorem, Edmonds' algorithm for maximum matching,
GallaiEdmonds structure theorem. Approximation algorithms; finding a strongly
connected subgraph, set packings and coverings.
(for secondyear mathematics
students)
Goals: To exhibit the fundamental ideas of linear programming along
with applications in geometry, combinatorics and game theory.
Prerequisities: linear algebra and graph theory.
Topics:

Basic notions: convex sets, convex combination, affine subspace,
cone, polyhedron, polytope etc. Farkas Lemma and its versions, proof
with the simplex method and with the elimination method. Theorem of
Motzkin on strict inequalities. Theorems of Weyl and Minkowski.
Theorem of Charathèodory. Characterizations for unboundedness. The
duality theorem. Totally unimodular matrices. Network matrices.
Uniform colourings. Application: Theorem of König and
Egerváry. The Hungarian Method. The polar cone. Two descriptions
of polyhedral cones. Theorems of Helly and of Kirchberger, separation
of polyhedra by hyperplanes.
Vertices, faces and facets of polyhedra. Dimension of a face.
Characterization of a minimal face. Equivalent definitions of
vertices. Every polytope is the convex combination of its vertices.
The description of a fulldimensional polyhedron by linear
inequalities is essentially unique.
Hoffman's theorem on feasible circulations, Strongly polynomial
algorithm of Edmonds and Karp for maximal flows. The algorithm of
Ford and Fulkerson fo minimum cost flows.
The simplex method with Bland's rule. The minmax theorem of game
theory.
(Specialization course for mathematics)
Goals: To exhibit the basic notions and
techniques with special emphasis on the applicability in
optimization.
Prerequisities: basics of linear algebra and graph theory.
Topics:

Equivalent systems of axioms, basic notions (basis, circuit, rank,
closed sets) dual matroid, direct sum, submodular functions.
Examples. Partition matroid, Transversal matroid, matching matroid,
circuit matroid,
matrix matroid.
The greedy algorithm.
Deriving the formula of Berge and Tutte.
Relationship between matroids and polymatroid functions, Rado's
theorem, homomorphic image, sum of matroids, induced matroid, the
intersection theorem, algorithms, Shannon's switching game.
(Specialization course for mathematics)
Goals: To survey the linear programming methods in
combinatorial optimization.
Prerequisities: basics of linear
programming, graph theory, matroid theory (the course can be taken
parallel to the course on Matroid theory)
Topics:
(Specialization course for mathematics)
Goals: To describe the most important algorithmic
techniques in combinatorial optimization.
Prerequisities: Matroid
theorey, polyhedral combinatorics, graph theory.
Topics:

Reachability, traversals of graphs and applications, computing the
minimum cut: algorithm of Nagamochi and Ibaraki. The simplicial
ordering of chordal graphs: computing the maximum weight stable set.
Shortest paths, Dijkstra algorithm, determining negative circuits,
minimal mean circuits, longest paths in acyclic graphs. the critical
path method. Multiterminal shortest paths: Warshall algorithm.
Maximal flows and their computations, feasible circulations. The
algorithm of Edmonds and Karp. The GomoryHu tree.
The Hungarian method. Minimum cost flows, the algorithm of Ford and
Fulkerson and of Goldberg and Tarjan. Applications to chains and
antichains of partially ordered sets.
The matching algorithm of Edmonds, minimum cost perfect matchings.
Tjoins, Tcuts.
Approximation algorithms.
(Specialization course for mathematics)
Goals: To exhibit recent results of the area and to
analyze some advanced topics. The selection may change year to year.
Prerequisities: Matroid theory, polyhedral combinatorics, graph
theory, the course on Combinatorial Algorithms should be taken
previously or parallel.
Topics: (in 1995)

Connectivity augmentation problems. The theorem of Watanabe and
Nakamura and its extension. Mader's "splitting off" theorems.
Edmonds' theorem on disjoint arborescences. Properties of polymatroids
and their applications.
Making a digraph strongly connected by contracting a minimum cost of
edges.
The weighted matroid intersection algorithm.
Disjoint paths problems.
(Specialization course for mathematics)
Goals: To widen the knowledge on linear programming.
Prerequisities: basics of linear programming, linear algebra.
Topics:

Extremal points of convex polyhedra. The simplex method, the lexicographic
simplex method, Bland's rule, computational problems of the simplex method.
The duality theory, Farkas theorem, the equivalence the the duality and
Farkas theorems, theorems of complementary slackness, the canonical form
of convex polyhedra,
theorems of alternatives; the theorem of Carathèodory.
The KarushKuhnTucker theorem. Lagrange multipliers. The dual simplex method,
the lexicographic dual simplex method. The primaldual method. Explicit
upper bounds. The network simplex method. DantzigWolfe decomposition.
Benders decomposition. Parametric programming. Sensitivity analysis.
Quadratic programming. The linear complementarity problem. Linear fractional
programming.
(Specialization course for mathematics, PhDcourse)
Goals: To exhibit the theoretical background and solution methods for integer programming.
Prerequisities: linear programming, basics of graph theory.
Topics:

Types of integrality conditions. Sperner systems. Hilbert bases. The
complexity
of integer hulls. Sets of integer vectors defined by inequalities, set of
integer vectors defined by one inequality, monotonity of discrete sets.
Sets of integer vectors defined by equations, Bradley's theorem, threshold
graphs. Cutting plane methods, Gomory cut, allinteger cut, mixed integer cut,
cuts determined by subadditive functions. The application of dynamic
programming
in integer programming, Bellman's principle, the general frame of shortest
path methods, the solution of knapsack problems and the Frobenius problem.
The branch and bound method. Generalized Lagrange multipliers. Heuristic
methods of integer programming, the greedy method. The method of enumeration.
The asymptotic method.
(Specialization course for mathematics, PhDcourse)
Goals: To complete the knowledge on the convex structures used in
operational research.
Prerequisities: linear algebra, analysis.
Topics:
 Convex sets: Definition and properties of convex sets.
Convex hull. Simplex. Carathèdory's theorem. Theorems of Helly. Covex
cones. Polyhedral cones. Theorem of Minkowski. Theorem of Weyl.
Separation of convex sets and convec cones. Support function. Extreme points. Theorem
of KreinMilman. Convex polyhedra. Adjoint cones. Theorem of
Duboviczki and Miljutin on convex cones.
 Convex functions: Convex, strong and uniformly strong
convex functions. Quasiconvex and pseodoconvex functions. Continuity
of convex functions. Subgradient, subdifferential. Conjugate
function. Theorem of Fenchel and Moreau.
 Systems of convex inequalities: Theorems of alternatives.
(Specialization course for mathematics, PhDcourse)
Goals: Theoretical foundation of nonlinear programming.
Prerequisities: linear algebra, analysis, convex analysis.
 Unconstrained optimization: Necessary and sufficient
conditions of optimality.
 Constrained optimization: Feasible, tangent and
decreasing directions and their forms for differentiable and
subdifferentiable functions. Theorem of Duboviczki and Miljutin on
the necessary condition of optimality. EulerLagrange equation.
Theorem of Lagrange multipliers. The theorem of KuhnTucker.
Necessary and sufficient optimality conditions for convex
programming. Saddlepoint theorem. Sensitivity function. Weak and
strong duality. Fenchel duality. Minimax theorems.
(Specialization course for mathematics, PhDcourse)
Goals: Theoretical foundation and solution methods of the
multiobjective optimization.
Prerequisities: basic elements of linear and nonlinear programming, analysis.
Topics:
 Vectoroptimization: Relations on $R^n$. Weak and strong
preferences. Pareto, Slater, Gioffrion and Borwein optimality.
Charactereization of the different optimal solutions. Pareto,
Slater, Gioffrion and Borwein optimality for convex problems.
 Multicriterial mathematical programming: Scalarizations.
The problem of the weigh\ted objective functions. The problem of the $k$th
objective Lagrangian problem. The $k$th objective
$\varepsilon$constrained problem. Connections between the scalarized
problems. Faithfully convex problems. Multiobjective linear
programming. Simplexbased methods.
(Specialization course for mathematics)
Goals: To exhibit the most important algorithmic
techniques for the implementation of linear programming algorithms.
Prerequisities: numerical methods of linear algebra, programming.
 MPS input and output formats. Sparse matrix techniques.
Inversation technics. Different methods for storing the inverse.
Numerical stability. Scaling, tolerances. Presolvers.
(Specialization course for mathematics)
Goals: To exhibit the programpackages useful for individual practice
in linear programming.
Prerequisities: linear programming, programming.
Topics:
 MINOS and CPLEX programcsomagok. The Gams modelling language.
Programming in MATLAB. Toolboxes to MATLAB.
(Specialization course for mathematics,
PhDcourse)
Goals: To exhibit the fundamental methods of nonlinear programming.
Prerequisities: theory of nonlinear programming, convex analysis, numerical
analysis.
Topics:
 Unconstrained optimization: Line search. Methods
of minimization on $R$. Gradient method. Conjugate direction methods.
Newton's method. QuasiNewton methods.
 Constrained optimization: Penalty and barrier function
methods, Methods of Lagrange multipliers. Methods of feasible
directions. Method of reduced gradient. Method of projected gradient.
Method of linearization. Interior point methods
(Specialization course for mathematics,
PhDcourse)
Goals:
To introduce the basic stochastic programming models and their mathematical backgrounds.
Prerequisities:
probability theory, theory of real functions.
Topics:
 Logconcave functions and their applications to probability distributions. Moment problems. Bounding and approximation of probabilities. Approximation of multivariate normal, gamma and Dirichlet probability integrals.
Programming under probabilistic constraints. Maximizing probabilities under constraints. Penalized recourse problems.
(Specialization course for mathematics,
PhDcourse)
Goals:
To exhibit different stochastic programming models and their solution methods.
Prerequisities:
probability theory, linear programming, basics of stochastic programming.
Topics:
 Static stochastic programming models. Probability maximization. Programming under probabilistic constraints. Penalty functions. Utility functions.
Twostage stochastic programming problems. Decomposition techniques. Discretization. Sublinear upper bound technique.
Multistage stochastic programming problems. Probabilistic constrained formulation. Decomposition technique. Lshape technique. Scenario aggregation.
(Specialization course for mathematics)
Goals: Mathematical foundation of the decision making methods.
Prerequisities: analysis, probability theory, mathematical logic.
Topics:
 Classical decision analysis: Decision tables. Criteria
of Wald, Hurwitz, Savage and Laplace. Criteria of maximal
likelihoods, expected monetary value, expected opportunity loss and
critical value. Ordinal value theory. Ordinal value and value
difference functions. Multiattributes value theory. Existence of
additive representation. Utility function. Subjective utility
function. Existence theorems.
 Logical decision analysis: Choice functions and their logical
representation. Multivalued choice functions. Reasoning based
decision making. Semantic consequence. Wellformed inference.
Forward and backward reasoning. Resolution principle. Semantic tree.
Inference rules based on multivalued and fuzzy logic. Possibilistic
logic. Approximate reasoning.
(Specialization course for mathematics, PhDcourse)
Goals: to exhibit the methods of production control of computer or industrial systems.
Prerequisities: basics of operational research.
Topics:

Introduction to production systems; how to modelize scheduling problems;
classification of scheduling problems; one machine problems; scheduling
on parallel machines; the flowshop problem; the jobshop problem;
introduction to flexible manufacturing systems, exact and heuristic methods of
scheduling of flexible manufacturing systems.
(Specialization course for mathematics,
PhDcourse)
Goals: Mathematical foundation of the analytical and decision making
methods used in expert systems.
Prerequisities: Theory of probability, mathematical logic.
Topics:
 Knowledge representation. First order predicate calculus.
Reasoning based decision making. Decision tables. Backward and forward
reasoning. Resolution principle. Semantic nets. Bayesian inference
networks. Evidence theory. Degrees of belief, doubt and
plausability and their propagation. DempsterShafer theory.
Possibilistic logic. Approximate reasoning.
(PhDcourse)
Goals: To exhibit nonstandard logical structures.
Prerequisities: mathematical logic.
Topics:
 Fuzzy logic as multivalued logic. Algebraic background:
Properties of residual lattices. The syntax and semantics of the first
order fuzzy logic. Fuzzy theories of the first order. Completeness
theorems. Approximate reasoning based on fuzzy logic.
 Possibilistic logic. Measures of necessity and possibility.
Generalized resolution principles. Approximate reasoning based on
possibilistic logic.
