Study programme 2019-2020Français
Graph Theory and Combinatorial Optimization
Programme component of Master's in Computer Engineering and Management (Charleroi (Hor. décalé)) à la Faculty of Engineering

Students are asked to consult the ECTS course descriptions for each learning activity (AA) to know what assessment methods are planned for the end of Q3

CodeTypeHead of UE Department’s
contact details
UI-M1-IRIGIG-808-CCompulsory UETUYTTENS DanielF151 - Mathématique et Recherche opérationnelle
  • TUYTTENS Daniel

of instruction
of assessment
HT(*) HTPE(*) HTPS(*) HR(*) HD(*) CreditsWeighting Term
  • Français
Français36400044.002nd term

AA CodeTeaching Activity (AA) HT(*) HTPE(*) HTPS(*) HR(*) HD(*) Term Weighting
I-MARO-153Graph Theory and Combinatorial Optimization364000Q2100.00%
Programme component

Objectives of Programme's Learning Outcomes

  • Imagine, design, develop, and implement conceptual models and computer solutions to address complex problems including decision-making, optimisation, management and production as part of a business innovation approach by integrating changing needs, contexts and issues (technical, economic, societal, ethical and environmental).
    • Deliver a solution selected in the form of diagrams, graphs, prototypes, software and/or digital models.
    • Evaluate the approach and results for their adaptation (modularity, optimisation, quality, robustness, reliability, upgradeability, etc.).
  • Mobilise a structured set of scientific knowledge and skills and specialised techniques in order to carry out computer and management engineering missions, using their expertise and adaptability.
    • Master and appropriately mobilise knowledge, models, methods and techniques specific to computer management engineering.
    • Identify and discuss possible applications of new and emerging technologies in the field of information technology and sciences and quantifying and qualifying business management.
    • Assess the validity of models and results in view of the state of science and characteristics of the problem.
  • Communicate and exchange information in a structured way - orally, graphically and in writing, in French and in one or more other languages - scientifically, culturally, technically and interpersonally, by adapting to the intended purpose and the relevant public.
    • Argue to and persuade customers, teachers and boards, both orally and in writing.
    • Use and produce scientific and technical documents (reports, plans, specifications) adapted to the intended purpose and the relevant public.
  • Adopt a professional and responsible approach, showing an open and critical mind in an independent professional development process.
    • Exploit the different means available in order to inform and train independently.

Learning Outcomes of UE

Understand the fundamental notions and problems appearing in graph theory;study the corresponding algorithms;go deeply into algorithmic notions from the algorithm efficiency point of view;understand the fundamental problems and techniques of combinatorial optimization;illustrate some methods on some particular problems;show the utility of algorithms for solving practical problems in scheduling management, logistics,...

Content of UE

Basic notions of graph theory and data structure; study of classical graph theory problems : trees, shortest paths, connexity, flows;introduction to complexity theory : P and NP classes; study of classical combinatorial optimization problems : knapsack, set covering, travelling salesman; introduction to metaheuristics.

Prior Experience

Linear programming, notion of algorithm.

Type of Assessment for UE in Q2

  • Written examination
  • Practical test

Q2 UE Assessment Comments

Reports of practical works : 20%.   Written examination covering both parts of the course: Graph theory  : (theory and exercises)  40% Combinatorial optimization : (theory and exercises)  40%

Type of Assessment for UE in Q3

  • Written examination
  • Practical Test

Q3 UE Assessment Comments

Reports of practical works : 20%.   Written examination covering both parts of the course: Graph theory  : (theory and exercises)  40% Combinatorial optimization : (theory and exercises)  40%

Type of Teaching Activity/Activities

AAType of Teaching Activity/Activities
  • Cours magistraux
  • Ateliers et projets encadrés au sein de l'établissement

Mode of delivery

AAMode of delivery
  • Face to face

Required Reading

AARequired Reading
I-MARO-153Copie de présentation - Partie 2 - Optimisation combinatoire - D. Tuyttens
,Copie de présentation - Partie 1 - Théorie des graphes - D. Tuyttens
,Copie de présentation - Partie 3 - Métaheuristiques - D. Tuyttens

Required Learning Resources/Tools

AARequired Learning Resources/Tools
I-MARO-153Not applicable

Recommended Reading


Recommended Learning Resources/Tools

AARecommended Learning Resources/Tools
I-MARO-153Not applicable.

Other Recommended Reading

AAOther Recommended Reading
I-MARO-153P. Lacomme, C. Prins & M. Sevaux Algorithmes de graphes, Editions Eyrolles, 2003. J. Dréo, A. Pétrowski, P. Siarry & E. taillard Métaheuristiques pour l'optimisation difficile, Editions Eyrolles, 2003.

Grade Deferrals of AAs from one year to the next

AAGrade Deferrals of AAs from one year to the next
(*) HT : Hours of theory - HTPE : Hours of in-class exercices - HTPS : hours of practical work - HD : HMiscellaneous time - HR : Hours of remedial classes. - Per. (Period), Y=Year, Q1=1st term et Q2=2nd term
Date de génération : 13/07/2020
20, place du Parc, B7000 Mons - Belgique
Tél: +32 (0)65 373111