Supply Chain

Language

English

Prerequisites

Students are expected to have a solid undergraduate background in mathematics and quantitative methods, including:
• Calculus (differentiation, basic multivariable concepts)
• Linear algebra (matrices, vectors, systems of linear equations)
• Basic discrete mathematics
• Elementary proof techniques and mathematical reasoning
• Elements of data structures and algorithms in Python. 
The prerequisite(s) for this Teaching Unit (Unité d’enseignement – UE) for the programmes/courses that offer this Teaching Unit are specified at the end of this sheet.

Main themes

This course introduces the theoretical foundations, modeling principles, and algorithmic methods of linear and integer optimization. It provides students with a rigorous understanding of optimization problems involving linear objectives and constraints, together with the mathematical structures that underpin modern optimization theory and practice.
The course begins with essential mathematical preliminaries, including key concepts from linear algebra and number theory that are fundamental to optimization. It then develops the formulation of linear optimization models and the geometric interpretation of feasible regions through convexity and polyhedral theory. Students learn optimality conditions, the structure of extreme points, and the principles underlying the Simplex algorithm, followed by a systematic treatment of duality theory and its theoretical and practical implications.
The second part of the course focuses on an introduction to optimization over integer variables, including problems defined by Diophantine inequalities with nonnegativity constraints. Emphasis is placed on linear relaxations, families of relaxations, and the relationships among bounds. Students are introduced to efficiently solvable combinatorial optimization problems and to the basic notions of computational complexity needed to distinguish tractable from intractable problems, and the general branch-and-bound algorithmic framework to solve integer problems. 

Learning outcomes

At the end of this learning unit, the student is able to :

Upon successful completion of this course, students will be able to: • Formulate real-world decision problems as linear and integer optimization models using appropriate variables, objective functions, and constraints. • Analyze the geometric structure of linear programs, including feasible regions, convexity properties, extreme points, and polyhedral representations. • Explain and apply optimality conditions for linear optimization problems and interpret solutions both algebraically and geometrically. • Execute and justify the steps of fundamental algorithms such as the Simplex method and basic branch-and-bound procedures. • Derive and interpret dual optimization problems and use duality theory to obtain bounds, sensitivity insights, and structural understanding. • Compare different relaxations of integer optimization problems and reason about the relationships among bounds produced by these relaxations. • Distinguish between tractable and intractable optimization problems using basic notions of computational complexity. • Recognize classes of efficiently solvable combinatorial optimization problems and explain the structural properties that make them polynomially solvable. • Construct and analyze proofs of fundamental results in linear and integer optimization. • Communicate optimization models, algorithms, and theoretical arguments clearly using correct mathematical language.

Content

• Mathematical Preliminaries; 
• Fundamental problems in linear algebra and number theory; 
• Formulation of linear optimization problems; 
• Feasible regions and extreme points; 
• Convexity, polyhedra, and basic geometric concepts; 
• Optimality conditions; 
• The Simplex algorithm;  
• Duality theory; 
• Optimizing over diophantine inequalities with positivity constraints; 
• Optimality, relaxations families and relationships among relaxations, and type of bounds; 
• Efficiently solvable combinatorial optimization problems; 
• Rudiments of computational complexity; 
• General solution approach to optimization over integers: the Branch-and-Bound algorithm.

Teaching methods

The course combines rigorous theoretical instruction with modeling practice and algorithmic insight. Teaching activities include:
• Lectures presenting theory, proofs, and structural results
• Guided problem-solving sessions focused on modeling and analytical reasoning
• Board derivations of algorithms and theoretical properties
• Worked examples illustrating geometric and combinatorial interpretations
• Exercises designed to reinforce conceptual understanding and mathematical maturity.

Evaluation methods

Written final examination (closed-book).
The exam is designed to rigorously evaluate theoretical understanding, modeling ability, and problem-solving skills. It typically includes:
• Proof-based questions on theoretical properties
• Modeling exercises requiring formulation of optimization problems
• Analytical questions on polyhedral structure, duality, or relaxations
• Algorithmic reasoning tasks (e.g., Simplex pivots, branch-and-bound steps)
• Conceptual questions on complexity and tractability
No multiple-choice questions are used. Calculators, notes, and electronic devices are not permitted unless explicitly stated.

Faculty or entity

> ESPO