Магистратура
2023/2024
Прикладная количественная логистика
Статус:
Курс по выбору (Науки о данных (Data Science))
Направление:
01.04.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Прогр. обучения:
Науки о данных
Язык:
английский
Кредиты:
6
Контактные часы:
56
Course Syllabus
Abstract
This course covers chapters from Discrete Mathematics, Game Theory, and Epistemic Logics to find market equilibriums and handle uncertainty. Programming skills are very important for this course. It also includes basic quantitative logistics models and algorithms for Allocation, Transportation, and Vehicle Routing Problems including the sensitivity and stability analysis applied to the Minimum Spanning Tree Problem (MSTP) and its variations, Shortest Path, Traveling Salesman and Vehicle Routing Problems (Capacitated, Time Windows, Pick Up and Delivery, etc.), Preempted Single Machine Scheduling Jobs (Operations) with Arbitrary Processing Times, Release and Due Dates will be studied in this course.
Learning Objectives
- Students who complete this course successfully will learn or acquire: <ul><li>Basic concepts of computational complexities for problems and algorithms (both exact and heuristic), which are necessary for further learning supply chain management models and algorithms, computational methods, algorithms for big data, algorithms and computational complexity, machine learning, operations research, game theory, and combinatorial optimization.</li> <li>Skills in design, implementation, and analysis of mathematical models and algorithms for solving applied quantitative logistics problems.</li> <li>Individual presentation of research activities following a pre-defined pattern including the corresponding research report.</li> </ul>
Expected Learning Outcomes
- Able to find mathematical structures defined on graphs and transportation networks related to location, sequencing and scheduling problems.
- Able to find mathematical structures defined on graphs and transportation networks related to location, sequencing and scheduling problems.
- Basic skills to design and implement exact and heuristic (approximation) algorithms in quantitative logistics.
- Basic skills to design and implement exact and heuristic (approximation) algorithms in quantitative logistics.
- Learn basic notions of models and algorithms to solve computationally intractable problems in quantitative logistics, scheduling algorithmsand computer science.
- Learn basic notions of models and algorithms to solve computationally intractable problems in quantitative logistics, scheduling algorithmsand computer science.
Course Contents
- The Minimum Spanning Tree (Kruskal and Prim’s Algorithms), 1-Tree, and Linear Assignment Problems - LAPs including problems based on patterns in LAP (Hungarian Algorithm).
- The Preempted Single Machine Scheduling Problems with different objective functions: Total Weighted Completion Time, Total Weighted Tardiness, Maximum Lateness, Makespan, Weighted Number of Tardy Jobs, Total Weighted Earliness, Total Weighted Earliness and Tardiness, Total Weighted Non-Linear Function depending on the key arguments (completion time, tardiness, earliness and tardiness, etc.
- The Traveling Salesman Problem (TSP): Symmetric and Asymmetric Cases of TSP.
- The Branch and Bound Algorithms for the Symmetric TSP (STSP).
- The Branch and Bound Algorithms for the Asymmetric TSP (ATSP).
- Upper, Lower, and Bottleneck Tolerances in Applied Quantitative Logistics.
- Upper Tolerances Based Algorithm for the ATSP.
- Lower Tolerances Based Algorithm for the ATSP.
- Data Correcting Approach for Real-Valued Functions.
- Data Correcting Approach for ATSP.
- Heuristics for solving the TSP: greedy (nearest neighbor), tolerance based greedy, nearest insertion, 2, 3-opt.
- Introduction to Submodular Functions: Local, Global Maxima on Hasse Diagram and Their Components.
- Supermodular Functions Applied to the Simple Plant (Uncapacitated Facility) Location Problem (SPLP).
- Cherenin-Khachaturov’s Theorem. Excluding vs Preservation Rules. Dichotomy (Preliminary Preservation) Algorithm.
- Branch-and-Bound (BnB) Algorihm for Supermodular Function Minimization Problem and Its Applications to the SPLP.
- Non-binary branching rules applied to the pseudo-Boolean formulation of the SPLP. The branching rule: Make Quadratic Terms Linear.
- The Quadratic Cost Partition Problem (QCP) - an example for maximization of a submodular set function.
- Cherenin’s Theorem (quasi-concavity of submodular functions).
- The greedy algorithm for submodular set functions.
- Pseudo-Boolean polynomials for the Simple Plant Location (SPLP).
- Truncation Theorem for the p-Median problem.
- Exact and Heuristic Algorithms for the SPLP.
- Decision-making support systems
Interim Assessment
- 2023/2024 4th module0.05 * Homeworks + 0.05 * Homeworks + 0.2 * Project presentation + 0.5 * Project presentation + 0.05 * Review + 0.05 * Review + 0.05 * Tests + 0.05 * Tests
Bibliography
Recommended Core Bibliography
- Goldengorin, B., & Pardalos, P. M. (2012). Data Correcting Approaches in Combinatorial Optimization. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=538347
- Goldengorin, B., Pardalos, P. M., & Krushinsky, D. (2013). Cell Formation in Industrial Engineering : Theory, Algorithms and Experiments. Springer.
Recommended Additional Bibliography
- Gerard Sierksma, & Diptesh Ghosh. (2010). Networks in Action. Springer.