FUNDAMENTALS OF

OPTIMIZATION
MODELLING

3
CONTENT

• Modelling
• Constraint linearization
• Examples

4
MODELLING

• Modelling consists of specifying

• Decision variables
• Constraints
• Objective functions
• A problem can be modelled in different ways (how to define variables)
• Take into account the modelling languages of software tools
• Constraint Programming solvers: constraints can be stated in flexible ways

5
CONSTRAINT LINEARIZATION

• Motivation
• Linear Programming solvers are very efficient
• Examples
• How to model X = min{x1,x2} ?

6
CONSTRAINT LINEARIZATION

• Motivation
• Linear Programming solvers are very efficient
• Examples
• How to model X = min{x1,x2} ?

Solution: define an auxiliary binary variable y, use big constant M

• x1  X
• x2  X
• X  x1 - M(1-y)
• X  x2 - My

7
CONSTRAINT LINEARIZATION

• Examples
• How to model (x = 1)  (z  y) where x is binary variable, y and z are real variables ?

8
CONSTRAINT LINEARIZATION

• Examples
• How to model (x = 1)  (z  y) where x is binary variable, y and z are real variables ?

Solution: use big constant M

• M(x-1) + y ≤ z

9
CONSTRAINT LINEARIZATION

• Example
• (x > 0)  (z  y) in which x, y and z are real variables (and x >=0) ?

10
CONSTRAINT LINEARIZATION

• Example
• (x > 0)  (z  y) in which x, y and z are real variables (and x  0) ?

Solution:
• Let M be a very big constant,
• Introduce a binary variable t  {0,1}:
• t = 1 indicates that x > 0, and t = 0 indicates that x = 0
• Equivalent linear constraints
• x ≤ M.t
• z + (1-t)M  y

11
EXAMPLES

• Balanced Course Assignment Problem

• At the beginning of the semester, the head of a computer science department D have to assign
courses to teachers in a balanced way. The department D has m teachers T={0, 2, ..., m-1} and n
courses C={0, 2,..., n-1}.
• Each teacher tT has a preference list which is a list of courses he/she can teach depending
on his/her specialization. The preference information is represented by a 0-1 matrix Am x n in
which A(t,c) = 1 indicates that teacher t can teach the course c and A(t,c) = 0, otherwise
• We know a set B of pairs of conflicting two courses that cannot be assigned to the same
teacher as these courses have been already scheduled in the same slot of the timetable.
• The load of a teacher is the number of courses assigned to her/him. How to assign n
courses to m teacher such that each course assigned to a teacher is in his/her preference
list, no two conflicting courses are assigned to the same teacher, and the maximal load
among teachers is minimal.

12
EXAMPLES

• Balanced Course Assignment Problem

Course 0 1 2 3 4 5 6 7 8 9 10 11 12 Conflict courses
credits 3 3 4 3 4 3 3 3 4 3 3 4 4
0 2
Teachers Preference Courses 0 4
0 0, 2, 3, 4, 8, 10 0 8
1 0, 1, 3, 5, 6, 7, 8 1 4
2 1, 2, 3, 7, 9, 11, 12 1 10
3 7
3 9
5 11
5 12
6 8
6 12

13
EXAMPLES

• Balanced Course Assignment Problem

Course 0 1 2 3 4 5 6 7 8 9 10 11 12 Conflict courses
credits 3 3 4 3 4 3 3 3 4 3 3 4 4
0 2
Teachers Preference Courses 0 4
0 0, 2, 3, 4, 8, 10 0 8
1 0, 1, 3, 5, 6, 7, 8 1 4
2 1, 2, 3, 7, 9, 11, 12 1 10
3 7
Teacher Assigned courses Load 3 9
0 2, 4, 8, 10 15 5 11
1 0, 1, 3, 5, 6 15 5 12
2 7, 9, 11, 12 14 6 8
6 12

14
EXAMPLES

• Balanced Course Assignment Problem: A Constraint Programming model

• Decision variables
• X(i): teacher assigned to course i, i  C, domain D(X(i)) = {t T | A(t,i) = 1}
• Y(i): load of teacher i, domain D(Y(i)) = {0,1,…,n-1}
• Z: maximum load among teachers
• Constraints
• X(i)  X(j), (i,j)  B
• Y(i) = σ𝑗 C(𝑋 𝑗 = 𝑖), i  T
• Z  Y(i), i  T
• Objective function to be minimized: Z

15
EXAMPLES

• Balanced Course Assignment Problem: An Integer Linear Programming model

• Decision variables
• X(i,j) = 1: teacher i is assigned to course j, and X(i,j) = 0, otherwise,  i  T, j  C, domain
D(X(i,j)) = {0,1}
• Y(i): load of teacher i, domain D(Y(i)) = {0,1,…,n}
• Z: maximum load among teachers
• Constraints
• σ𝑖T 𝑋 𝑖, 𝑗 = 1, , j  C
• X(t,i) + X(t,j) ≤ 1, (i,j)  B, t  T
• Y(i) = σ𝑗 C 𝑋 𝑖, 𝑗 , i  T
• Z  Y(i), i  T
• Objective function to be minimized: Z

16
EXAMPLES

• Travelling Salesman Problem (TSP)

• A salesman departs from point 1, visiting N-1 points 2, …, N and comes back to the point 1. The
travelling distance from point i and point j is d(i,j), i,j = 1,…, N. Compute the route of minimal
total travelling distance

17
EXAMPLES

• Travelling Salesman Problem (TSP): An Integer Linear Programming model

• Decision variables
• Binary variable X(i,j) = 1 if the route traverses from point i to point j, and X(i,j) = 0,
otherwise.
• Constraints
• σ𝑁𝑗=1 𝑋 𝑖, 𝑗 = σ𝑗=1 𝑋 𝑗, 𝑖 = 1, i{1,2,…,N}
𝑁

• σ(𝑖,𝑗)𝑆 𝑋 𝑖, 𝑗 ≤ |S| - 1,  S  {1,2,…, N} and |S| < N

• Objective function to be minimized
𝑓 𝑋 = σ𝑁 σ 𝑁
𝑗=1 𝑖=1 𝑑(𝑖, 𝑗)𝑋 𝑖, 𝑗

18
EXAMPLES

• Capacitated Vehicle Routing Problem

• A fleet of K trucks 1, 2, …, K must be scheduled to visit N customers 1, 2, …, N for collecting
items
• Customer i located at point i and requests to be collected r(i) items, i = 1, 2, …, N
• Truck k (k = 1,…, K)
• Departs from point N+k and terminates at point N + K + k (N+k and N+K+k might refer
to the central depot)
• has capacity c(k) which is the maximum number of items it can carry at a time
• Travel distance from point i to point j is d(i,j), i,j = 1,…, N + 2K
• Compute the delivery solution such that the total travelling distance is minimal
• Satisfy capacity constraints
• Each customer is visited exactly once by exactly one truck

19
EXAMPLES

• Capacitated Vehicle Routing Problem

5 7 1 0 2 3 4 3 3 3 3
1 3 2 4 0 2 6 1 1 1 1
3 2 4 0 2 1 1 1 1
4 5 7 7 0 4 4 4 4
4 2
5 3 1 5 7 0 0 0 0
6 8 6 3 1 5 7 0 0 0 0
7 3 1 5 7 0 0 0 0
8 3 1 5 7 0 0 0 0

1 2 1 2 3 4
c 10 10 r 4 3 6 5

20
EXAMPLES

• Capacitated Vehicle Routing Problem

• Notations
• B = {1,…, N+2K}
• F1 = {(i, k+N) | i  B, k  {1,…,K}}
• F2 = {(k+K+N, i) | i  B, k  {1,…,K}}
• F3 = {(i, i) | i  B}
• A = B2 \ F1\ F2 \ F3
• A+(i) = { j | (i, j)  A}, A-(i) = { j | (j, i)  A}
• Decision variables
• X(k,i,j) = 1 if truck k travel from point i to point j, k = 1,…,K, (i,j) A
• Y(k,i): number of items on truck k after leaving point i, k = 1,…,K, i = 1,…,N+2K
• Z(i): index of truck visiting point i,  i = 1,2,…, N+2K

21
EXAMPLES

• Capacitated Vehicle Routing Problem

• Constraints
• σ𝐾𝑘=1 σ𝑗A+(𝑖) 𝑋(𝑘, 𝑖, 𝑗) = σ𝑘=1 σ𝑗A−(𝑖) 𝑋(𝑘, 𝑗, 𝑖, ) = 1,  𝑖 = 1,…, N
𝐾

• σ𝑗A+(𝑖) 𝑋(𝑘, 𝑖, 𝑗) =σ𝑗A−(𝑖) 𝑋(𝑘, 𝑗, 𝑖), i = 1,…,N, k = 1,…, K

• σ𝑁𝑗=1 𝑋(𝑘, 𝑘 + 𝑁, 𝑗) = σ𝑗=1 𝑋(𝑘, 𝑗, 𝑘 + 𝐾 + 𝑁) = 1, k = 1,…, K
𝑁

• M(1-X(k,i,j)) + Z(i)  Z(j),  (i,j)  A, k = 1,…,K

• M(1-X(k,i,j)) + Z(j)  Z(i),  (i,j)  A, k = 1,…,K
• M(1-X(k,i,j)) + Y(k,j)  Y(k,i) + r(j),  (i,j)  A, k = 1,…, K
• M(1-X(k,i,j)) + Y(k,i) + r(j)  Y(k,j),  (i,j)  A, k = 1,…, K
• Y(k,k+K+N) ≤ c(k), k = 1,…,K
• Y(k,k+N) = 0, k = 1,…,K
• Z(k+N) = Z(k+K+N) = k, k = 1,…, K
• Objective function
• 𝑓 𝑋, 𝑌, 𝑍 = σ𝐾 𝑘=1 σ(𝑖,𝑗)A 𝑋 𝑘, 𝑖, 𝑗 𝑑(𝑖, 𝑗) → min

22
EXAMPLES

• MultiCast Routing Problem

• Given a network V = {1,…, N} is the set of nodes, E  V2 is the set of links between nodes. A
node s  V is the source node which will transmit a package to others nodes. A node receiving
the package can continue transmit this package to adjacent nodes.
• t(i,j) and c(i,j) are transmission time and transmission cost when transmitting the package
from node i to node j
• Compute the set of links used for broadcasting the package from the source node to all other
nodes such that
• Total transmission time from s to any node cannot exceed a given value L1 2
• Total transmission cost is minimal
7
4 3

6
5

23
EXAMPLES

• MultiCast Routing Problem

• Denote A(i) = {j  V | (i,j) E }, M is a big constant
• Decision variables
• Binary variable X(i,j) = 1 if the package is transmitted from node i to node j, and X(i,j) = 0,
otherwise, (i,j)E
• Y(i): time-point when the package arrives at node i, iV
• Constraints
• σ𝑖𝐴(𝑗) 𝑋(𝑖, 𝑗) = 1, jV\{s}
1 2
• Y(i) + t(i,j) + M(1-X(i,j))  Y(j), (i,j)E
• Y(i) + t(i,j) + M(X(i,j)-1) ≤ Y(j), (i,j)E
7
• Y(i) ≤ L, jV\{s} 4 3
• Y(s) = 0
• Objective function to be minimized 5
6
f(X) = σ(𝑖,𝑗)𝐸 𝑐 𝑖, 𝑗 𝑋(𝑖, 𝑗)

24
EXAMPLES

• Facility Location Problem

• There are M sites 1, 2, …, M that can be used to open facility for servicing N customers 1, 2, …,
N.
• f(i) is the cost for opening the site i
• Q(i) is the capacity of site i (maximum amount of good it can serve customers)
• c(i,j) is the cost for transporting unit of good from site i to customer j
• d(j) is the total demand (amount of goods) of customer j
• Compute a planning (which site to be opened and amount of good each opened site serves a
customer) such that
• Capacity constraint is satisfied
• Total cost is minimal

25
EXAMPLES

• Facility Location Problem

• Decision variables
• Y(i) – binary variable, Y(i) = 1 means that the site i is opened, and Y(i) = 0, otherwise
• X(i,j) – amount of good site i serves customer j
• Constraints
• σ𝑀𝑖=1 𝑋(𝑖, 𝑗) = d(j),  j = 1,…, N
• σ𝑁𝑗=1 𝑋(𝑖, 𝑗) ≤ Q(i)Y(i),  i = 1,…, M
• 0 ≤ X(i,j) ≤ d(j)Y(i),  i = 1,…, M,  j = 1,…, N
• Objective functions
σ𝑀𝑖=1 𝑓 𝑖 𝑌(𝑖) + σ𝑖=1 𝑗=1 𝑐 𝑖, 𝑗 𝑋(𝑖, 𝑗) → min
𝑀 σ𝑁

26
THANK YOU !

27