Module also offered within study programmes:
General information:
Name:
Discrete optimisation
Course of study:
2018/2019
Code:
ZIPM-3-007-n
Faculty of:
Management
Study level:
Third-cycle studies
Specialty:
-
Field of study:
Industrial Engineering of Non-Ferrous Metals
Semester:
0
Profile of education:
Academic (A)
Lecture language:
English
Form and type of study:
Part-time studies
Course homepage:
 
Responsible teacher:
prof. zw. dr hab. inż. Sawik Tadeusz (sawik@zarz.agh.edu.pl)
Academic teachers:
prof. zw. dr hab. inż. Sawik Tadeusz (sawik@zarz.agh.edu.pl)
Module summary

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
M_K001 Understands the importance of advanced decision making methods in modern enterprise. IPM3A_K02 Examination
Skills
M_U001 Is able to interpret solutions of discrete optimisation problems. IPM3A_U01 Examination
Knowledge
M_W001 Knows basic models and algorithms of discrete optimisation. IPM3A_W02, IPM3A_W01 Examination
M_W002 Knows modelling techniques and tools applied in discrete optimisation. IPM3A_W03 Execution of a project
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
M_K001 Understands the importance of advanced decision making methods in modern enterprise. - - - - + - - - - - -
Skills
M_U001 Is able to interpret solutions of discrete optimisation problems. - - - - + - - - - - -
Knowledge
M_W001 Knows basic models and algorithms of discrete optimisation. - - - - + - - - - - -
M_W002 Knows modelling techniques and tools applied in discrete optimisation. - - - - + - - - - - -
Module content
Conversation seminar:

Discrete Optimization is an advanced course on combinatorial optimization and mixed integer programming applications in the area of production engineering and operations management.

The course consists of two parts:

  1. Mixed integer programming models and algorithms.
  1. Combinatorial optimization and optimization on graphs.

Highlights

  • The most important production and operations management problems can be modeled as mixed integer linear programs or combinatorial and graph optimization problems.
  • A comprehensive knowledge in discrete and combinatorial optimization is required to build efficient mathematical models for production and operations management problems.

Topics

  1. Introduction to combinatorial optimization and mixed integer programming.
  2. Problems with indivisibilities: binary vs, integer knapsack problem, bin packing problem vs. cutting stock problem. Applications of greedy and FFD heuristics.
  3. Mixed integer programs for linear and quadratic assignment problems.
  4. Traveling salesman problem. Subtour elimination constraints: Miller–Tucker–Zemlin vs. Dantzig–Fulkerson–Johnson formulations. Symmetric vs. asymmetric problem, vehicle routing vs. multiple traveling salesman.
  5. Set covering/partitioning problem.
  6. Resource and task allocation problems. Mixed integer programs for machine loading, assembly line balancing and routing problems.
  7. Fixed charge problems. Mixed integer programs for location, production and inventory planning, robotized assembly cell design and loading problems.
  8. Optimization on graphs: introduction to the theory of graphs and basic definitions.
  9. Network flow problems. Linear programs and graph-theoretic algorithms.
  10. Minimum spanning tree, maximum matching, minimum covering. Integer programs and graph-theoretic algorithms.
  11. Arc routing problems. Mixed integer programs and graph-theoretic algorithms: undirected and directed chinese postman problems.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 42 h
Module ECTS credits 2 ECTS
Participation in conversation seminars 14 h
Realization of independently performed tasks 28 h
Additional information
Method of calculating the final grade:

Assessment (1 ECTS):
Written test. Requirements: Understanding of a few basic problems and models.

Exam (3 ECTS):
Written exam. Requirements: Understanding of all considered problems and models.

Prerequisites and additional requirements:

Prerequisites and additional requirements not specified

Recommended literature and teaching resources:
  1. T. Sawik (1998): Badania operacyjne dla inżynierów zarządzania. (Operations Research for Industrial Engineers). AGH University Press, Kraków. (textbook in Polish).
  2. T. Sawik (1999): Production Planning and Scheduling in Flexible Assembly Systems. Springer, Berlin.
  3. T. Sawik (2011): Scheduling in Supply Chains Using Mixed Integer Programming. John Wiley & Sons, Inc., Hoboken, NJ (USA).
Scientific publications of module course instructors related to the topic of the module:
  1. T. Sawik (1999): Production Planning and Scheduling in Flexible Assembly Systems. Springer, Berlin.
  2. T. Sawik (2011): Scheduling in Supply Chains Using Mixed Integer Programming. John Wiley & Sons, Inc., Hoboken, NJ (USA).
Additional information:

None