FUNDAMENTALS OF
OPTIMIZATION
Introduction
CONTENT
• Optimization problems
• Optimization problem classification
• Applications
• Topics
Optimization problems
• Maximize or minimize some function relative to some set (range of
choices)
• The function represents the quality of the choice, indicating which is the
“best”
• Example
• A shipper need to find the shortest route to deliver packages to
customers 1, 2, …, N
0 3 4 2 5 6 8 7
3 0 3 6 7 2 1 6
0 3 1 6
4 3 0 4 7 1 1 9
3 0 2 4
2 6 4 0 2 8 3 4
1 2 0 5
5 7 7 2 0 6 5 1
6 4 5 0
6 8 1 8 6 0 9 3
8 1 1 3 5 9 0 2
7 6 9 4 1 3 2 0
Notations
• x Rn : vector of decision variables xj, for j = 1, 2, …, n
• f : Rn → R is the objective function
• gi : Rn → R is the constraint function defining restriction on x, i = 1, 2, …,
m
minimize f(x) over x = (x1, x2,…, xn) X Rn satisfying a property P:
gi(x) ≤ bi, i = 1, 2, …, s
gi(x) = di, i = s + 1, 2, …, m
Examples
min f(x) = 3x1 – 5x2 + 10x3
x1 + x2 + x3 ≤ 10
2x1 + 4x2 – 5x3 = 9 (Linear Program)
x1, x2R+, x3 Z
min f(x) = 4𝑥12 + 3𝑥22 – 7𝑥1 𝑥3
x1 + 𝑥23 + 4x3 ≤ 10
2 𝑥12 + 4x2 – 5x3 = 7 (Nonlinear Program)
x1, x2R+, x3 Z
Solving optimization problems
• General optimization problems
• Very difficult to solve
• Some special cases
• Linear programming
• Least square problem
• Some shortest path problems on networks
• Etc.
0 3 4 2 5 6 8 7
• Example TSP
3 0 3 6 7 2 1 6
4 3 0 4 7 1 1 9
0 3 1 6
2 6 4 0 2 8 3 4
3 0 2 4
5 7 7 2 0 6 5 1
1 2 0 5
6 8 1 8 6 0 9 3
6 4 5 0
8 1 1 3 5 9 0 2
7 6 9 4 1 3 2 0
Classification
• Linear Programming (LP): f and gi are linear
• Nonlinear Programming (NLP): some function f, gi are nonlinear
• Continuous optimization: f and gi are continuous on an open set
containing X, X is closed and convex
• Integer Programming (IP): X {0,1}n or X Zn
• Constrained optimization: m > 0, X Rn
• Unconstrained optimization: m = 0, X = Rn
Applications
• Production Planning
• Routing in transportation
• Scheduling
• Assignment
• Packing
• Time Tabling
• Network designs
• Machine learning
• ...
Agriculture Production Planning
SKU Chart Demand
Fields
10000
25000
32000
42500
Construction Planning
Planning
beams
piles
Task Duration Predecessors
1 30 6 bases
2 20 1,4,8 1
3 15 6
4 25 5,6 2
5
5 20 1,6 6 7
6 45
7 40 2,8 4
8 30 3,4 8
3
Logistics & Transportation
13
Logistics & Transportation
Logistics & Transportation
How to make a plan for delivering goods to customers
Logistics & Transportation
How to make a plan for delivering goods to customers
Logistics & Transportation
How to pick items in a very large warehouse?
Assignment
How to assign tasks to workers in an optimal way
workers tasks
4 6 8
2 6 7
5 6
1 4
6 3
Time tabling
How to assign classes into slots of the timetable
Monday Tuesday Wednesday Thursday Friday
Data Python Statistics, Technical Networkings
structure & Programmin B1-203 writing, B1- , B1-404
Algorithms, g, D9-302 202
TC-305
Fundamenta Java
l of advanced,
optimization, Machine B1-204 Image
B1-402 learning, processing,
D6-302 Software Operating D6-303
engineering, systems,
D5-102 D9-101
Machine learning
Prediction
X Y
43 45
44 46
45 45
46 48
47 47
48 51
49 49
50 ?
Computer vision
messi
ramos
bale
Mbappe
Topics of the course
• Unconstrained convex optimization
• Constrained convex optimization
• Linear programming
• Linear integer programming
• Constraint Programming
• Modelling
• Heuristic methods
References
• Stephan Boyd and Lieven Vandenberghe . Convex optimization. Cambridge University
Press 2004
• David G. Luenberger and Yinyu Ye. Linear and Nonlinear Programming. Springer 2008
• Laurence A. Wolsey. Integer Programming. Wiley-Interscience; 1st edition (September 9,
1998)
• Francesca Rossi Peter van Beek Toby Walsh. Handbook of Constraint Programming 1st
Edition. Elsevier Science, 2006
• El-Ghazali Talbi El-Ghazali Talbi. Metaheuristics: From Design to Implementation. Wiley
2009
Thank you
for your
attentions!
