GIMAS7AH

Discrete Optimization

ECTS Credits: 2

Duration: 21 hours

Semester: S7

Person(s) in charge:

Bernardetta ADDIS, Associate Professor, bernardetta.addis@univ-lorraine.fr

Keywords: Discrete Optimisation

Prerequisites: None

Objective:

Complete the basic knowledge and techniques studied in the operations research course (core curriculum)

Program and contents:

The goal of this course is to complete the basic knowledge and techniques studied in the core curriculum operations research course.  The course begins with an overview of modeling techniques for real problems (localization, personnel assignment, timetabling, production, etc.) using integer programming. In the second part, we introduce different tools used in graph theory, which will allow us to model and optimize real problems such as finding the minimum weight spanning tree in a graph. The third part of this course concerns the primal-dual notion in linear programming and how we can exploit it to solve different problems that arise in a network, such as minimum flow problem, flow with minimum cost problem, assignment and transportation problems. We finish this course with an introduction to the study of the complexity of problems.   

Contents

• Introduction to discrete optimisation and decision-making
• Modeling with linear and integer programming
• Advanced tools in graph theory, and optimisation problem in graphs.
• Flow in networks and it applications
• Basic knowledge of algorithm and the complexity of problems.

Abilities: 

Levels

Description and operational verbs

Know 

Understand 

Apply 

Analyze 

Summarise

Assess

Evaluation:

• Written test

• Continuous Control

• Oral report

• Project

• Written report