FUNDAMENTALS OF

OPTIMIZATION
Introduction

3
INTRODUCTION TO 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

4
INTRODUCTION TO OPTIMIZATION PROBLEMS

• 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

5
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Example
min f(x) = 3x1 – 5x2 + 10x3
x1 + x2 + x3 ≤ 10
2x1 + 4x2 – 5x3 = 9 (Linear Program)
x1, x2R+, x3  Z

min f(x) = 4𝑥12 + 3𝑥22 – 7𝑥1 𝑥3

x1 + 𝑥23 + 4x3 ≤ 10
2 𝑥12 + 4x2 – 5x3 = 7 (Nonlinear Program)
x1, x2R+, x3  Z

6
INTRODUCTION TO OPTIMIZATION PROBLEMS

• General optimization problems

• Very difficult to solve
• Some special cases
• Linear programming
• Least square problem
• Some shortest path problems on networks
• Etc.

7
INTRODUCTION TO OPTIMIZATION PROBLEMS

• 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

8
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Applications
• Production Planning
• Routing in transportation
• Scheduling
• Assignment
• Packing
• Time Tabling
• Network designs
• Machine learning
• ...

9
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Production Planning

SKU Chart Demand

Fields
10000

25000

32000

42500

10
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Construction Planning Task Duration Predecessors

1 30 6 1
2 20 1,4,8
3 15 6 2
5
4 25 5,6 6 7
5 20 1,6
6 45 4
7 40 2,8 8
3
8 30 3,4

11
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Routing in
transportation &
logistics

12

12
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Routing in transportation
& logistics

13
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Routing in transportation & logistics

• How to make a route plan for
delivering goods to customers from a
central depot?

14
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Routing in transportation & logistics

• How to make a route plan for
delivering goods to customers from a
central depot?

15
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Routing in transportation & logistics

• How to make a route plan for picking
up items in a very large warehouse?

16
INTRODUCTION TO OPTIMIZATION PROBLEMS

• 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

17
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Packing
• How to arrange items in a container in an optimal ways?

Container

18
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Time Tabling
• How to arrange courses into time slots?

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

19
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Machine learning
• Prediction
X Y
43 45
44 46
45 45
46 48
47 47
48 51
49 49
50 ?

20
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Machine learning
• Computer Vision

messi
ramos
bale
Mbappe

21
THANK YOU !

22