Responsible instructor: György Dósa, DSc (dosa.gyorgy@mik.uni-pannon.hu)
The subject assumes knowledge of the following subject and builds on it:
Linear and non-linear programming
Thematics:
Integer programming (IP), relaxation of the IP, IP models, solution methods, methods based on Branch and Bound (B&B).
Network programming: network models, network flow problem and its variants as integer programming.
Integer and mixed integer programming problems and their model-based description.
Cutting plane methods for solving integer and mixed-integer programming problems.
Application of heuristics and meta-heuristics to solve IP problems (lower and upper bounds, Local Searsh, Genetic Algorithm, Tabu Search, Simulated Annealing).
The Travelling Salesman Problem (TSP), its versions. Heuristics for solving the TSP.
The Assignment Problem and its variants. The Hungarian method with its slave algorithms: Greedy algorithms and the Konig Algorithm
The Set Cover Problem: mathematical models and heuristics.
Scheduling roblems and algorithms, approximation ratio.
The Bin Packing Problem (various versions).
Case studies for (large) integer problems and their solutions.
Literature:
Nemhauser, G. L. and L. A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, New York, 1988.
Schrijver, A., Theory of Linear and Integer Programming, John Wiley & Sons, New York, 1986.
Rockafellar, R. T., Network Flows and Monotropic Optimization, John Wiley & Sons, New York, 1984.
Papadimitriou C. H. and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall Inc., New Jersey, 1982.
Winston, W.L.: Operations Research : Applications and Algorithms.:, Duxbury Press, 2004
Laurence A. Wolsey: Integer Programming, Wiley, 2021, 2nd edition