Прикладная количественная логистика

Магистратура 2020/2021

Статус: Курс по выбору (Науки о данных)

Направление: 01.04.02. Прикладная математика и информатика

Кто читает: Департамент анализа данных и искусственного интеллекта

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Преподаватели: Федянин Денис Николаевич

Прогр. обучения: Науки о данных

Язык: английский

Кредиты: 4

Контактные часы: 60

Full Syllabus Ask Question

Abstract

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> <li>High quality reports will be recommended for publication in top international scientific journals in Optimization, Operations Research, Computer Science, Algorithms, Mathematical Modeling, etc. (Q2 or Q1, see scimago for details) among them Journal of Global Optimization, Journal of Combinatorial Optimization, Computers and Operations Research just to mention a few.</li></ul>

Expected Learning Outcomes

Able to find mathematical structures defined on graphs and transportation networks related to location, sequencing and scheduling problems.
Learn basic notions of models and algorithms to solve computationally intractable problems in quantitative logistics, scheduling algorithmsand computer science.
Basic skills to design and implement exact and heuristic (approximation) algorithms in quantitative logistics.

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.

Assessment Elements

Homework and Assignments
In-class test
Midterm tеst will be announced at least one week in advance.
Personal presentation of team reports
Final exam (comprehensive)
Экзамен проводится на платформе Skype (https://www.skype.com/). К экзамену необходимо подключиться согласно расписанию ответов, высланному преподавателем на корпоративные почты студентов накануне экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Skype. Для участия в экзамене студент обязан: поставить на аватар свою фотографию, явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено: выключать камеру, пользоваться конспектами и подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи менее минуты. Долговременным нарушением связи во время экзамена считается нарушение минута и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи подразумевает использование усложненных заданий.

Interim Assessment

Interim assessment (4 module)
0.4 * Final exam (comprehensive) + 0.3 * Homework and Assignments + 0.2 * In-class test + 0.1 * Personal presentation of team reports

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.

Course Syllabus