Topics of courses taught by the Department of Operations Reseach

Operational research

(for third-year 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. Kuhn-Tucker 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.

Combinatorial optimization

(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 non-negative 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, Max-flow-Min-cut theorem, Ford-Fulkerson algorithm, Edmonds-Karp algorithm, Menger theorems. Minimum cost flows, Tutte theorem, Edmonds' algorithm for maximum matching, Gallai-Edmonds structure theorem. Approximation algorithms; finding a strongly connected subgraph, set packings and coverings.

Linear programming

(for second-year 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 full-dimensional 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 min-max theorem of game theory.

Matroid 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.

Polyhedral combinatorics

(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:

  • Fundamentals of linear programming: Theorems of Carathèodory, Farkas, the duality theorem, polyhedra, and their faces. Total unimodular matrices and their properties, network matrices, Theorems of Köonig-Egervári and Hoffman. Computing minimum cost arborescences. The uncrossing technique. Theorem of Lucchesi and Younger, the orientation theorem of Nash-Williams. Matroid polyhedron, the polymatroid greedy algorithm. The matroid intersection polyhedron.

    Submodular flows and their feasibility. The matching polyhedron, TDI-ness. Perfect graphs. The stable set polyhedron.

Combinatorial algorithms

(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 Gomory-Hu 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. T-joins, T-cuts. Approximation algorithms.

Selected topics in combinatorial optimization

(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.

Linear programming

(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 Karush-Kuhn-Tucker theorem. Lagrange multipliers. The dual simplex method, the lexicographic dual simplex method. The primal-dual method. Explicit upper bounds. The network simplex method. Dantzig-Wolfe decomposition. Benders decomposition. Parametric programming. Sensitivity analysis. Quadratic programming. The linear complementarity problem. Linear fractional programming.

Integer programming

(Specialization course for mathematics, PhD-course)

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, all-integer 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.

Convex analysis

(Specialization course for mathematics, PhD-course)

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 Krein-Milman. 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.

Theory of nonlinear programming

(Specialization course for mathematics, PhD-course)

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. Euler-Lagrange equation. Theorem of Lagrange multipliers. The theorem of Kuhn-Tucker. Necessary and sufficient optimality conditions for convex programming. Saddle-point theorem. Sensitivity function. Weak and strong duality. Fenchel duality. Minimax theorems.

Multiobjective optimization

(Specialization course for mathematics, PhD-course)

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. Simplex-based methods.

Computational methods in linear programming

(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.

Linear programming packages

(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.

Numerical methods of nonlinear programming

(Specialization course for mathematics, PhD-course)

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. Quasi-Newton 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

Stochastic programming

(Specialization course for mathematics, PhD-course)

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.

Stochastic modelling

(Specialization course for mathematics, PhD-course)

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. Two-stage stochastic programming problems. Decomposition techniques. Discretization. Sublinear upper bound technique. Multi-stage stochastic programming problems. Probabilistic constrained formulation. Decomposition technique. L-shape technique. Scenario aggregation.

Decision analysis

(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. Multi-attributes 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. Well-formed inference. Forward and backward reasoning. Resolution principle. Semantic tree. Inference rules based on multivalued and fuzzy logic. Possibilistic logic. Approximate reasoning.

Scheduling theory

(Specialization course for mathematics, PhD-course)

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 flow-shop problem; the job-shop problem; introduction to flexible manufacturing systems, exact and heuristic methods of scheduling of flexible manufacturing systems.

Mathematical backgrounds of expert systems

(Specialization course for mathematics, PhD-course)

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. Dempster-Shafer theory. Possibilistic logic. Approximate reasoning.

Fuzzy logic

(PhD-course)

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.