FUNDAMENTALS OF OPTIMIZATION

Introduction

2
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
• Minimize f(x) = 2sin(x)cos(3x) + x2
• A shipper need to find the shortest route to deliver packages to customers 1, 2, …, N

3
10 7
6
0 1
4
8

2 5
9

3
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

4
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

5
INTRODUCTION TO OPTIMIZATION PROBLEMS

• General optimization problems

• Very difficult to solve
• Some special cases can be solved easily (well-known algorithms)
• Linear programming
• Least square problem
• Some shortest path problems on networks
• Etc.

6
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
• Combinatorial optimization:
• Solutions can be an arrangement, a permutation, a subset of a given set
• Solution space is finite
• Routing, Bin Packing, Scheduling, Timetabling, Coloring
• A combinatorial optimization problem is a discrete optimization problem, but some discrete optimization problems are not
combinatorial optimization
• Example: min f(𝑥1 , 𝑥2 , 𝑥3 ) = 4𝑥12 + 3𝑥22 – 7𝑥1 𝑥3
𝑥1 + 𝑥23 + 4 𝑥3 ≤ 10
2 𝑥12 + 4 𝑥2 – 5 𝑥3 = 7
𝑥1 , 𝑥2 , 𝑥3  Z

Discrete optimization but not combinatorial optimization

7
INTRODUCTION TO OPTIMIZATION PROBLEMS

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

8
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Production Planning

SKU Chart Demand

Fields
10000

25000

32000

42500

9
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

10
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Routing in transportation
& logistics

11

11
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Routing in transportation &

logistics

12
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Routing in transportation & logistics

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

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 picking up items
in a very large warehouse?

15
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

16
INTRODUCTION TO OPTIMIZATION PROBLEMS

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

Container

17
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Timetabling: How to arrange courses into time slots?

• [IT3011, 3, 100], [IT3020, 4, 120], [IT4663, 3, 60], [IT3220, 4, 90], [IT3030, 3, 100], [IT3170, 2, 120]

18
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Machine learning
• Prediction

X Y
43 45
44 46
45 45
46 48
47 47
48 51
49 49
50 ?

19
INTRODUCTION TO OPTIMIZATION PROBLEMS

• Machine learning
• Computer Vision

messi
ramos
bale
Mbappe

20
 MODELLING

• Transform the problem description to a mathematical model

• Define variables and domains of variables
• State constraints and objective functions

Problem description
A company must decide to make a plan to produce 2 products
P1, P2.
• The revenue received when selling 1 unit of P1 and P2
are respectively 5$ and 7$
• The manufacturing cost when producing P1 and P2 are
respectively 5$ and 3$
• The storage cost in warehouses for 1 unit of P1 and P2
are respectively 2$ and 3$
Compute the production plan so that
• Total manufacturing cost is less than or equal to 200$
• Total storage cost is less than or equal to 150$
• Total revenue is maximal

21
 MODELLING

• Transform the problem description to a mathematical model

• Define variables and domains of variables
• State constraints and objective functions

Problem description Mathematical model

A company must decide to make a plan to produce 2 products • Variable definition
P1, P2. • X1, X2: amount of P1 and P2 to be produced
• The revenue received when selling 1 unit of P1 and P2 • Domains: X1, X2 R and nonnegative
are respectively 5$ and 7$
• Constraints
• The manufacturing cost when producing P1 and P2 are
respectively 5$ and 3$
• 5X1 + 3X2 ≤ 200
• The storage cost in warehouses for 1 unit of P1 and P2 • 2X1 + 3X2 ≤ 150
are respectively 2$ and 3$ • Objectives
Compute the production plan so that • Maximize 5X1 + 7X2
• Total manufacturing cost is less than or equal to 200$
• Total storage cost is less than or equal to 150$
• Total revenue is maximal

22
MODELLING

• Worker Task Assignment

• Given 2 tasks 1, 2 and 2 workers 1, 2. The cost of assigning a task to a worker is described by the matrix c below in which
c(i, j) is the cost of assigning task i to worker j (i, j = 1, 2) 1 2
• Find the assignment solution such that
1 4 2
• Each task is assigned to exactly one worker
• Each worker is assigned to exactly one task 2 7 1
• The total cost is minimal

23
MODELLING

• Worker Task Assignment

• Given 2 tasks 1, 2 and 2 workers 1, 2. The cost of assigning a task to a worker is described by the matrix c below in which
c(i, j) is the cost of assigning task i to worker j (i, j = 1, 2) 1 2
• Find the assignment solution such that
1 4 2
• Each task is assigned to exactly one worker
• Each worker is assigned to exactly one task 2 7 1
• The total cost is minimal
• Modelling
• Variable definition
• Binary variable X(i, j) in which X(i, j) = 1 means that task i is assigned to worker j, and X(i, j) = 0 means that task i is not
assigned to worker j (i, j = 1, 2)
• Constraints
• X(1, 1) + X(1, 2) = 1; X(2, 1) + X(2, 2) = 1
• X(1, 1) + X(2, 1) = 1; X(1, 2) + X(2, 2) = 1
• Objectives
• Minimize f(X) = 4X(1, 1) + 2X(1, 2) + 7X(2, 1) + X(2, 2)

24
SOFTWARE TOOLS

• CPLEX
• Gurobi
• SCIP
• OR-Tools

25
 SOFTWARE TOOLS

Mathematical model OR-Tools

• Variable definition from ortools.linear_solver import pywraplp
• X1, X2: amount of P1 and P2 to be produced
• Domains: X1, X2 R and nonnegative solver = [Link]("GLOP")
X1 = [Link](0, [Link](), "X1")
• Constraints X2 = [Link](0, [Link](), "X2")
• 5X1 + 3X2 ≤ 200
• 2X1 + 3X2 ≤ 150 [Link](5*X1 + 3*X2 <= 200)
• Objectives [Link](2*X1 + 3*X2 <= 150)
• Maximize 5X1 + 7X2
[Link](5 * X1 + 7 * X2)

status = [Link]()
if status == [Link]:
print("Solution:")
print(f"Objective value = {[Link]().Value():0.1f}")
print(f"x = {X1.solution_value():0.1f}")
print(f"y = {X2.solution_value():0.1f}")
else:
print("The problem does not have an optimal solution.")

26
THANK YOU !

27