Combinatorial Optimization
Lecture 1: Introduction to Operations Research
Le Hai Yen, Institute of Mathematics, VAST
Master IATOM, USTH, Hanoi
2024
Lecture 1: Introduction to Operations Research 1 / 30
Table of contents
1 Course informations
2 What is Operations Research
Definitions
Principles
3 Introduction to Optimization
Lecture 1: Introduction to Operations Research 2 / 30
Course informations
Course name: Combinatorial Optimization
Lecturers:
✉ Lê Xuân Thanh
✉ Lê Hải Yến (
[email protected])
Course length: 30 hours
Course structure:
➢ Introduction to Operations Research (2 hours)
➢ Linear Programming (10 hours)
➢ Integer Programming (6 hours)
➢ Classical combinatorial optimization problems (12 hours)
Course materials:
B. Korte and J. Vygen. Combinatorial Optimization Theory and
Algorithms, 6th edition. Springer Berlin, Heidelberg, 2018.
G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial
Optimization. Wiley, 1988.
Lecture 1: Introduction to Operations Research 3 / 30
Rules
Exams without any document
Attend all sessions
Arrive in class on time
During sessions:
no cell phone
open to discussion
practice on exercises
At home:
learn the course
practice on homeworks
Lecture 1: Introduction to Operations Research 4 / 30
Table of contents
1 Course informations
2 What is Operations Research
Definitions
Principles
3 Introduction to Optimization
Lecture 1: Introduction to Operations Research 5 / 30
Terminologies
Lecture 1: Introduction to Operations Research 6 / 30
History
Lecture 1: Introduction to Operations Research 7 / 30
History
Lecture 1: Introduction to Operations Research 8 / 30
Definition
Lecture 1: Introduction to Operations Research 9 / 30
Hình: Source: http://modelmath.onmason.com/math-modeling/
Lecture 1: Introduction to Operations Research 10 / 30
Process of OR
Lecture 1: Introduction to Operations Research 11 / 30
Process of OR
Lecture 1: Introduction to Operations Research 12 / 30
Process of OR
Lecture 1: Introduction to Operations Research 13 / 30
Process of OR
Lecture 1: Introduction to Operations Research 14 / 30
Process of OR
Lecture 1: Introduction to Operations Research 15 / 30
Process of OR
Lecture 1: Introduction to Operations Research 16 / 30
OR Tools
Lecture 1: Introduction to Operations Research 17 / 30
Table of contents
1 Course informations
2 What is Operations Research
Definitions
Principles
3 Introduction to Optimization
Lecture 1: Introduction to Operations Research 18 / 30
Optimization models
Decision variables,
An objective function,
Constraints.
Lecture 1: Introduction to Operations Research 19 / 30
The optimization problem
Minimize/Maximize f (x)
subject to x ∈S
where:
f : objective function
S : feasible domain typically represented by a set of inequalities
ci (x) ≤ 0, i = 1, 2, ..., m.
Lecture 1: Introduction to Operations Research 20 / 30
Example 1: The diet problem
Goal: Minimize cost of food subject to providing sufficient daily
nutrition (Fat > 35g, Carbohydrates> 130g, Protein> 76g).
3 food items: peanut butter, bananas and chocolate.
Peanut butter Banana Chocolate
Price 20 cents 10 cents 15cents
Fat 130g 1g 12g
Carbohydrates 51.6g 51g 22g
Protein 64.7g 2g 2g
Lecture 1: Introduction to Operations Research 21 / 30
Example 1: The diet problem
Variables: x1 servings of peanut butter, x2 servings of bananas, x3
servings of chocolate;
Cost of food: 20x1 + 10x2 + 15x3 ;
Constraints: x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 and
130x1 + 1x2 + 12x3 ≥ 35;
51.6x1 + 51x2 + 22x3 ≥ 130;
64.7x1 + 2x2 + 2x3 ≥ 76.
Lecture 1: Introduction to Operations Research 22 / 30
The diet problem
min 20x1 + 10x2 + 15x3
subject to 130x1 + 1x2 + 12x3 ≥ 35
51.6x1 + 51x2 + 22x3 ≥ 130
64.7x1 + 2x2 + 2x3 ≥ 76
x1 , x2 , x3 ≥ 0.
Lecture 1: Introduction to Operations Research 23 / 30
Mathematical formulation of an optimization problem
Distinguish:
1 Parameters (defining the problem): given data
2 Decision variables through which we control the solution: unknowns
3 steps:
1 Definition of the Decision variables (or optimization variables)
(x ∈ Rn or xi ∈ {0, 1} . . .)
2 “Expression“ of the objective function(s),f (x), in terms of these
decision variables
3 “Expression” of the constraints in terms of these decision variables
(typically represented by a set of inequalities
ci (x) ≤ 0, i = 1, 2, ..., m).
Lecture 1: Introduction to Operations Research 24 / 30
Black-box problems
objective/constraint functions given by a computer (or an experimental)
simulation:
no closed analytic form for f
derivatives not available
costly evaluations of f
Lecture 1: Introduction to Operations Research 25 / 30
Optimization : Classification
continuous optimization: S ⊆ Rn
discrete (or combinatorial) optimization: S finite or countable
optimal control: S = set of functions
stochastic optimization: random data
multi-criterion optimization:f : S ⇒ Rm (several objective functions)
Lecture 1: Introduction to Operations Research 26 / 30
Traditional Courses in Optimization
Continuous (convex) optimization: f and S convex, functions ∈ C 2
algorithms based on 1st-order necessary conditions (KKT) in order to
find a local optimum
software: requires subroutines x 7→ f (x) and x 7→ ∇f (x)
Combinatorial optimization:
linear programming: f linear and S polyhedral
Integer linear programming (ILP): f linear + S polyhedral + x ∈ Nn
Graph theory (ex: shortest path, traveling salesman problem etc.)
Lecture 1: Introduction to Operations Research 27 / 30
Combinatiorial Optimization vs Continuous Optimization
Lecture 1: Introduction to Operations Research 28 / 30
Modeling an Optimization problem
Homework 1: Rolling mill
Lecture 1: Introduction to Operations Research 29 / 30
Modeling an Optimization problem
Homework 2: Knapsack
Lecture 1: Introduction to Operations Research 30 / 30
