Course detail

Network Flows in Logistics

FSI-SNF-AAcad. year: 2024/2025

The course focuses on basic network models and methods for solving logistic problems. It follows linear programming ideas and deepens and concretizes the understanding of the following general principles of mathematical optimization: understanding the network problem, constructing a network model and taking into account possible integer variables, finding, analyzing and interpreting the optimal solution. The course covers in particular the problem of network flows  (typical problems, LP model formulation, graph formulation, specialized solution algorithms). The course also includes an introduction to related issues in integer programming (problem formulation, integer flows, network design, indicator variables, selected algorithms and their software implementations). The course has been designed based on the author's experience with similar courses at foreign universities.

 

Language of instruction

English

Number of ECTS credits

5

Mode of study

Not applicable.

Guarantor

RNDr. Pavel Popela, Ph.D.

Department

Institute of Mathematics (ÚM)

Entry knowledge

Basic knowledge of principal concepts of linear programming is assumed.

Rules for evaluation and completion of the course

The exam is written and includes model formulation, algorithmic calculations and theoretical questions. The written work is accompanied by an oral debate.


The attendance at seminars is required as well as active participation. Passive or missing students are required to work out additional assignments.

Aims

The goal is to gain a deep knowledge of models and methods for solving network optimization problems with an emphasis on logistic applications. The objectives are focused on problem analysis, building of mathematical models including their  formal descriptiion, finding appropriate reformulations, selection, modification and implementation of algorithms. The models and methods presented are supported by the interpretation of selected theory.


The course is designed for logistics students and may also be useful for applied science and engineering students. Students will gain an in-depth understanding of network flow and integer programming models in relation to logistics problems. They will also learn about real-world applications of discussed network  models.

Study aids

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Ghiani, G. et al. Introduction to Logistics Systems Management, 3rd edition, Wiley, 2022. (EN)
Bazaraa, M.S. et al. Linear Programming and Network Flows, 4th edition, Wiley, 2010. (EN)
Wolsey, L. Integer Programming, 2nd Edition, Wiley, 2020. (EN)
Williamson, D.P. Network Flow Algorithms, Cambridge University Press, 2019. (EN)
Garcia-Diaz A. and Phillips, D.T. Fundamentals of Network Analysis and Flow Optimization, Virtualbook Publishing, 2022. (EN)

Recommended reading

Ghiani, G. et al. Introduction to Logistics Systems Management, 3rd edition, Wiley, 2022. (EN)

Bazaraa, M.S. et al. Linear Programming and Network Flows, 4th edition, Wiley, 2010.

(EN)
Sofer, A. et al. Linear and Nonlinear Optimization (Chapter 8 Network Problems), 2nd Edition, Society for Industrial and Applied Mathematics, 2009. (EN)
Williams, H.P. Model Building in Mathematical Programming, 5th edition, Wiley, 2013. (EN)
Nemhauser, G.L. and Wolsey, L.A. Integer and Combinatorial Optimization, 1st Edition, Wiley, 1988.  (EN)

Classification of course in study plans

  • Programme N-LAN-A Master's, 1. year of study, summer semester, compulsory

Type of course unit

 

Lecture

26 hours, optionally

Teacher / Lecturer

RNDr. Pavel Popela, Ph.D.

Syllabus

1. Motivating problems and basics of network flow modeling.

2. Transportation and transhipment problems, their LP modelling and (software) solutions.

3. LP models of minimum network flow problems and their (software) solutions.

4. Special minimum network flow problems (LP models for  shortest path search and for asignment problem). Maximum network flow problem.

5. Pitfalls of solving network problems by LP simplex method and their solutions.

6.-7. Efficient methods for solving selected network problems.

8. Integer solutions in network problems.

8. Modelling changes in network structure using binary variables.

9. Fundamentals of integer optimization.

10. Branch and bound method and its software implementation.

11. Indicator variables and their applications.

12.-13. Selected logistics applications in the areas of allocation, distribution and scheduling.

Exercise

26 hours, compulsory

Teacher / Lecturer

RNDr. Pavel Popela, Ph.D.

Syllabus

1. Examples of logistic problems and their modelling by networks.

2. Examples of transportation problems, their LP modelling and their (software) solution in a modelling language.

3. Examples of LP models of minimum flow network tasks and their (software) solution in a modelling language.

4. Examples of special network minimum flow problems (LP models for shortest path search and for the assignment problem). Examples for maximum network flow.

5. Examples of bottlenecks while solving network problems by simplex method and their solutions.

6.-7. Efficient methods for solving selected network problems and examples of their application in logistics.

8. Examples of integer solutions in network problems.

8. Examples of modelling changes in network structure using binary variables.

9. Fundamentals of integer optimization with examples.

10. Examples for the branch and bound method and their software implementations.

11. Indicator variables and their application in logistic examples.

12.-13. Selected logistics applications in the areas of allocation, distribution and scheduling - examples.