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

Discrete Mathematics 2

2019/2020
Academic Year
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

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

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

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

Assessment Elements

  • non-blocking 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.
  • non-blocking 2 in-class Tests
    There will be two written tests. Tests will be announced at least one week in advance.
  • non-blocking Student’s Presentation
    Each presentation takes at most 10 min = 8min + 2 min for questions. Presentations will be based on team (individual) reports.
  • non-blocking Final Exam
Interim Assessment

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
Bibliography

Bibliography

Recommended Core Bibliography

  • Boros, E., & Hammer, P. L. (2002). Pseudo-Boolean optimization. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.5E6D740E
  • Rosen, K. H., Shier, D. R., & Goddard, W. (2017). Handbook of Discrete and Combinatorial Mathematics (Vol. Second edition). Boca Raton, FL: Chapman and Hall/CRC. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1617301

Recommended Additional Bibliography

  • Discrete mathematics, Biggs, N. L., 2004