• A
• A
• A
• ABC
• ABC
• ABC
• А
• А
• А
• А
• А
Regular version of the site

# Discrete Mathematics 2

2019/2020
ENG
Instruction in English
4
ECTS credits
Course type:
Compulsory course
When:
2 year, 1, 2 module

#### Instructor

Goldengorin, Boris I.

### Course Syllabus

#### Abstract

The objective of this course is to make students familiar with basic models of linear and integer linear programming (discrete optimization models) and enumeration (branch-and-bound type) algorithms for solving а general mixed-integer linear programming problem as well as its special cases (minimum spanning tree and its variations, linear assignment, and traveling salesman problem). A special attention of this course will be paid to the informal understanding of duality theory for linear programming problems including total dual integrality theory, and totally unimodular matrices. The algorithmic line of this course will be represented by the introduction to the theory and algorithms (exact and approximation) for pseudo-Boolean polynomials and their applications to data analysis problems. Pre-requisites: Discrete Mathematics 1, basic linear algebra, matrices and vectors manipulation, systems of linear equations, local and global minima and maxima within elementary calculus.

#### Learning Objectives

• Students will learn basic concepts, models and methods of discrete optimization, which are necessary for further learning computational methods, algorithms for big data, machine learning, algorithms and computational complexity, operations research, game theory, and combinatorial optimization.
• Students will acquire skills in using discrete math 2 models and methods to formalize and solve applied problems in data analysis.

#### Expected Learning Outcomes

• Students will be able to model, solve and make conclusions based on the problems and solution methods including exact and heuristic algorithms.
• Students will be able to find mathematical structures in the object they work with.
• Students will acquire basic math skills for learning advanced courses in applied data analysis and computer science.
• Students will learn basic math notions that are needed to work in broad areas of applied data analysis.

#### Course Contents

• The linear programming (LP) problem and its applications.
• The simplex method in graphical and tabular forms.
• Shadow prices and their interpretations.
• Sensitivity analysis in LP.
• The primal and dual problems in LP and their properties.
• The transportation problem, northwest and Vogel’s heuristics.
• The assignment problem (AP) and its applications.
• The Hungarian algorithm for solving the AP.
• The shortest path (SP) problem and its applications.
• The SP algorithm for finding an optimal solution.
• The minimum spanning tree (MST) problem, its variations and applications.
• The bottleneck MST.
• The Kruskal’s and Prim’s algorithms for finding a MST.
• The max-flow-min-cut problem (MFP) and its applications.
• The Ford-Fulkerson’s algorithm for solving the MFP.
• The traveling salesman problem (TSP) and its applications.
• Computation of upper and lower tolerances for the following problems: LP, SP, MST, AP, MFP, TSP.
• Applications of upper tolerances to the uniqueness (nonuniqueness) of optimal solution(s) for the LP, SP, MST, AP, MFP, TSP.
• The branch and bound algorithm for the Asymmetric TSP (ATSP) based on the AP.
• The branch and bound algorithm for the Symmetric TSP based on the 1-tree problem.
• The following heuristics for solving the TSP: greedy (nearest neighbor), tolerance based greedy, nearest insertion, 2, 3-opt.
• The integer LP (ILP) and its applications.
• The branch and bound algorithm for the ILP based on the LP.
• Pseudo-Boolean polynomials: theory and algorithms.

#### Assessment Elements

• Homework Assignments
Homework problems will be assigned starting from second week just once a week. Each student is expected to solve the problems individually. Each homework will be represented by the mini-group printed report containing an abstract, introduction, individual solutions by every member of the mini-group, summary, and conclusion, and references. The sections of an assignment will be discussed by all members of the mini-group and reflecting the mini-group consensus.
• 2 in-class Tests
There will be two written tests. Tests will be announced at least one week in advance.
• Student’s Presentation
Each presentation takes at most 10 min = 8min + 2 min for questions. Presentations will be based on team (individual) reports.
• Final Exam

#### Interim Assessment

• Interim assessment (2 module)
0.2 * 2 in-class Tests + 0.4 * Final Exam + 0.3 * Homework Assignments + 0.1 * Student’s Presentation