FUNDAMENTALS OF

OPTIMIZATION
Modelling

3
Outline

• Modelling a Combinatorial Optimization Problem

• Combinatorial Optimization Problem
• N-Queen problem
• Sudoku problem
• Balanced Class Teacher Assignment Problem
• Class Allocation Problem
• Traveling Salesman Problem
• Exercise
• Backtracking algorithm

4
Combinatorial Optimization Problem

Find a solution (usually a combinatorial configuration) that satisfies a

given set of constraints while simultaneously optimizing one or more
specified objective functions.
• Constraint Satisfaction Problem (CSP) = (X, D, C)
• 𝑋 = {𝑥1 , … , 𝑥𝑛 }, set of variables
• 𝐷 = {𝐷1 , … , 𝐷𝑛 }, domains of the variables
• 𝐶 = {𝐶1 , … , 𝐶𝑘 }, set of constraints
• Combinatorial Optimization Problem (COP) = (X, D, C, f)
• 𝑋 = {𝑥1 , … , 𝑥𝑛 }, set of variables
• 𝐷 = {𝐷1 , … , 𝐷𝑛 }, domains of the variables
• 𝐶 = {𝐶1 , … , 𝐶𝑘 }, set of constraints
• 𝑓: objective function

5
Example: Constraint Satisfaction Problem

Problem N-Queen, 𝐶𝑆𝑃 = (𝑋, 𝐷, 𝐶)

• Variables: 𝑋 = {𝑥1 , … , 𝑥𝑛 }, in which 𝑥𝑖 is the
row of the queen in column 𝑖, ∀ 𝑖 ∈ {1, … , 𝑛}
• Domains: 𝐷𝑖 = 𝐷 𝑥𝑖 = {1, … , 𝑛}, ∀𝑖 ∈
{1, … , 𝑛}
• Constraints: For all pair 𝑖, 𝑗 , 1 ≤ 𝑖 < 𝑗 ≤
𝑛:
• 𝑥𝑖 ≠ 𝑥𝑗
• 𝑥𝑖 + 𝑖 ≠ 𝑥𝑗 + 𝑗
• 𝑥𝑖 − 𝑖 ≠ 𝑥𝑗 − 𝑗

6
Example: Constraint Satisfaction Problem

Sudoku Problem, CSP = (X, D, C)

• Variables: 𝑋 = {𝑥1,1 , … , 𝑥9,9 }, where 𝑥𝑖,𝑗 ​ is the value in
cell (𝑖, 𝑗), ∀ 𝑖, 𝑗 ∈ {1,2, … , 9}
• Domain: 𝐷 𝑥𝑖,𝑗 = 1, … , 9 , ∀𝑖, 𝑗 ∈ {1,2, … , 9}
• Constraints:
• The numbers in each column are pairwise distinct:
𝑥𝑖1𝑗 ≠ 𝑥𝑖2𝑗 for all 1 ≤ 𝑖1 < 𝑖2 ≤ 9, 1 ≤ 𝑗 ≤ 9
• The numbers in each row are pairwise distinct:
𝑥𝑗𝑖1 ≠ 𝑥𝑗𝑖2 for all 1 ≤ 𝑖1 < 𝑖2 ≤ 9, 1 ≤ 𝑗 ≤ 9
• The numbers in each 3x3 subgrid are pairwise distinct:
𝑥3𝑖+𝑖1,3𝑗+𝑗1 ≠ 𝑥3𝑖+𝑖2,3𝑗+𝑗2 for all 0 ≤ 𝑖, 𝑗 ≤ 2, 1 ≤ 𝑖1 , 𝑖2 , 𝑗1 , 𝑗2 ≤ 3
satisfying 𝑖1 , 𝑗1 ≠ (𝑖2 , 𝑗2 )

7
Balanced Class Teacher Assignment

• There are 𝑛 classes labeled 1, 2, … , 𝑛 that have already been scheduled

in a timetable, and they need to be assigned to 𝑚 teachers labeled
1,2, … , 𝑚
• Each class 𝑖 has 𝑇(𝑖), a list of teachers who can teach it (𝑖 = {1, … , 𝑛}),
and 𝑐(𝑖), the number of credits for the subject of that class.
• Since the timetable has been pre-arranged, there exists a set 𝑄 of pairs
of classes (𝑖, 𝑗) that are scheduled at the same time (these two classes
cannot be assigned to the same teacher).
• Find an assignment of classes to teachers such that the maximum total
number of credits assigned to any one teacher is minimized.

8
Balanced Class Teacher Assignment

 Example List Q
Class 0 1 2 3 4 5 6 7 8 9 10 11 12
Credit 3 3 4 3 4 3 3 3 4 3 3 4 4 0 2
0 4
Teacher List of classes that the teach can teach
0 8
0 0, 2, 3, 4, 8, 10
1 4
1 0, 1, 3, 5, 6, 7, 8
1 10
2 1, 2, 3, 7, 9, 11, 12
3 7
3 9
5 11
5 12
6 8
6 12
9

9
Balanced Class Teacher Assignment

 Example List Q
Class 0 1 2 3 4 5 6 7 8 9 10 11 12
Credit 3 3 4 3 4 3 3 3 4 3 3 4 4 0 2
0 4
Teacher List of classes that the teach can teach
0 8
0 0, 2, 3, 4, 8, 10
Assignment 1 4
1 0, 1, 3, 5, 6, 7, 8
solution 1 10
2 1, 2, 3, 7, 9, 11, 12
3 7
3 9
Teacher List of classes assigned to the teacher Total credits 5 11
0 2, 4, 8, 10 15 5 12
1 0, 1, 3, 5, 6 15 6 8
2 7, 9, 11, 12 14 6 12
10

10
 Balanced Class Teacher Assignment
• Input: maximum number of credits for a teacher;
• Set of classes: 𝑆 = 1, … , 𝑛 • Domains of variables:
• Set of teachers: 𝑇 = 1, … , 𝑚 • 𝐷 𝑥𝑖𝑗 = 0, 1 , ∀ 𝑖 ∈ 𝐶, 𝑗 ∈ 𝑇
• Set of conflict classes: 𝑄 = • 𝐷 𝑚𝑎𝑥𝑐𝑟𝑒𝑑𝑖𝑡 = {0, … , σ𝑖∈𝐶 𝑐 𝑖 }
𝑖1 , 𝑗1 , … , 𝑖𝑘 , 𝑗𝑘 𝑖1 , … , 𝑖𝑘 , 𝑗1 , … , 𝑗𝑘 ∈ 𝐶, 𝑖𝑡 ≠
𝑗𝑡 ∀𝑡 ∈ {1, … , 𝑘}} • Constraints:
• Set of teachers who can give some class 𝑇 = • Each class is assigned to one teacher σ𝑗∈𝑇𝑖 𝑥𝑖𝑗 =
{𝑇1 , … , 𝑇𝑛 }, in which 𝑇𝑖 is the set of teachers 1, ∀ 𝑖 ∈ 𝐶
who can give the class 𝑖 (𝑖 ∈ {1, … , 𝑛}) • Teacher is not assigned to a class that he
• For each class i 𝑖 ∈ 1, … , 𝑛 , 𝑐(𝑖) is its number cannot teach 𝑥𝑖𝑗 = 0, ∀ 𝑖 ∈ 𝐶, 𝑗 ∉ 𝑇𝑖
of credit (𝑐 𝑖 ∈ 𝑁)
• Teacher cannot give two classes in the conflict
• Variables: set 𝑥𝑖1 𝑗 + 𝑥𝑖2𝑗 ≤ 1, ∀ 𝑗 ∈ 𝑇, 𝑖1 , 𝑖2 ∈ 𝑄
• Binary variable 𝑥𝑖𝑗 (𝑖 ∈ 𝐶, 𝑗 ∈ 𝑇) is equal to 1 if • Relation between variable 𝑚𝑎𝑥𝑐𝑟𝑒𝑑𝑖𝑡 and
the class 𝑖 is assigned to the teacher 𝑗, workload of teacher
otherwise the value of this variable is equal to σ𝑖∈𝐶 𝑐 𝑖 𝑥𝑖𝑗 ≤ 𝑚𝑎𝑥𝑐𝑟𝑒𝑑𝑖𝑡 , ∀ 𝑗 ∈ 𝑇
0;
• Objective: 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑚𝑎𝑥𝑐𝑟𝑒𝑑𝑖𝑡
• Integral variable 𝑚𝑎𝑥𝑐𝑟𝑒𝑑𝑖𝑡 represents the

11
Class Allocation Problem

• 𝑛 classes labeled by 1, 2, … , 𝑛 need to be allocated in 𝑝 semesters

1, 2, … 𝑝. Each class 𝑖 has a credit value of 𝑐(𝑖), and its prerequisite
conditions are defined by a set 𝑄 of pairs (𝑖, 𝑗), where subject 𝑖 must be
taken before 𝑗. Given the constant 𝛼, 𝛽, 𝛿, 𝛾, it is necessary to
determine an allocation plan that satisfies the following:
• The total number of classes assigned to each semester must be greater than or
equal to 𝛼 and less than or equal to 𝛽.
• The total number of credits of the classes assigned to each semester must be
greater than or equal to 𝛿 and less than or equal to 𝛾
• For each pair (𝑖, 𝑗) ∈ 𝑄, class 𝑖 must be scheduled in a semester prior to the
semester in which class 𝑗 is scheduled.
• Objective: The maximum number of credits in any one semester must
be minimized.
12
Class Allocation Problem

• Example
Class 1 2 3 4 5 6 7 8 9 10 11 12 Set Q
Number 2 1 2 1 3 2 1 3 2 3 1 3 2 1
of credits
6 9
3 ≤ Number of classes in each semester ≤ 3 5 6
5 ≤ Number of credits in each semester ≤ 7 5 8
4 11
6 12
2 7
3 10
5 7
8 11
4 12

13
Class Allocation Problem

• Example
Class 1 2 3 4 5 6 7 8 9 10 11 12 Set Q
Number 2 1 2 1 3 2 1 3 2 3 1 3 2 1
of credits
6 9
3 ≤ Number of classes in each semester ≤ 3 5 6
5 ≤ Number of credits in each semester ≤ 7 5 8
Allocation 4 11
solution 6 12
2 7
3 10
Semester 1 2 3 4 5 7
List of classes 2, 5, 3 1, 6,10 4,7,8 9,11,12 8 11
4 12

14
 Class Allocation Problem
• Input: • Every class is allocated to some semester
σ𝑗∈𝑆 𝑥𝑖𝑗 = 1, ∀𝑖 ∈ 𝐶
• Set of classes: 𝐶 = {1, … , 𝑛}
• Set of semesters: 𝑆 = {1, … , 𝑝} • Number of classes in a semester must be in a
range of [𝛼, 𝛽] , it means that 𝛼 ≤
• Set of precedent classes: 𝑄 = σ𝑖∈𝐶 𝑥𝑖𝑗 ≤ 𝛽, ∀ 𝑗 ∈ 𝑆
𝑖1 , 𝑗1 , … , 𝑖𝑘 , 𝑗𝑘 𝑖1 , … , 𝑖𝑘 , 𝑗1 , … , 𝑗𝑘 ∈ 𝐶, 𝑖𝑡 ≠
𝑗𝑡 ∀𝑡 ∈ {1, … , 𝑘}} • Number of credits in a semester must be in a
• Constant 𝛼, 𝛽, 𝛿, 𝛾 range of 𝛿, 𝛾 , it means that 𝛿 ≤
σ𝑖∈𝐶 𝑐 𝑖 𝑥𝑖𝑗 ≤ 𝛾
• Variables: • For each pair (𝑖1 , 𝑖2 ) ∈ 𝑄, class 𝑖1 must be
• Binary variable 𝑥𝑖𝑗 (𝑖 ∈ 𝐶, 𝑗 ∈ 𝑆) is equal to 1 if scheduled in a semester prior to the semester
the class 𝑖 is assigned to the semester 𝑗, in which class 𝑖2 is scheduled
otherwise the value of this variable is equal to σ𝑗∈𝑆 𝑗𝑥𝑖1𝑗 < σ𝑗∈𝑆 𝑗 𝑥𝑖2𝑗 , ∀ 𝑖1 , 𝑖2 ∈ 𝑄
0; • Relation between variable 𝑚𝑎𝑥𝑐𝑟𝑒𝑑𝑖𝑡 and
• Integral variable 𝑚𝑎𝑥𝑐𝑟𝑒𝑑𝑖𝑡 represents the workload in a semester
maximum number of credits for a semester σ𝑖∈𝐶 𝑐 𝑖 𝑥𝑖𝑗 ≤ 𝑚𝑎𝑥𝑐𝑟𝑒𝑑𝑖𝑡 , ∀ 𝑗 ∈S
• Constraints: • Objective: 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑚𝑎𝑥𝑐𝑟𝑒𝑑𝑖𝑡

15
Traveling Salesman Problem

• A traveler starts from city 1 and needs to visit cities 2, 3, … , 𝑛, passing

through each city exactly once before returning to the starting city.
The cost of traveling from city 𝑖 to city 𝑗 is 𝑐(𝑖, 𝑗). Calculate the plan for
the traveler that results in the minimum total cost.

16
Traveling Salesman Problem

• Input:
• 𝑛 number of cities
• 𝑐(𝑖, 𝑗) traveling cost from the city 𝑖 to the city 𝑗
• Variables:
• Binary variable 𝑥𝑖𝑗 with 𝑖, 𝑗 ∈ 1, … , 𝑛 , 𝑖 ≠ 𝑗 is equal to 1 if the traveler go from the city 𝑖 to the
city 𝑗 in the optimal plan, otherwise the value of this variable is equal to 0;
• Constraints:
• For each city, the traveler goes in once and goes out once
෍ 𝑥𝑖𝑗 = ෍ 𝑥𝑗𝑖 = 1, ∀𝑖 ∈ {1, … , 𝑛}
𝑗∈{1,…,𝑛} 𝑗∈{1,…,𝑛}
• No subtour
෍ 𝑥𝑖𝑗 ≤ 𝑆 − 1 , ∀𝑆 ⊂ {1, … , 𝑛}
𝑖,𝑗∈𝑆,𝑖≠𝑗

• Objective: 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 σ𝑖,𝑗∈ 1,…,𝑛 ,𝑖≠𝑗 𝑐 𝑖, 𝑗 𝑥𝑖𝑗

17
Exercises

• Modelling the problem in your mini-project

18
Outline

• Modelling a Combinatorial Optimization Problem

• Combinatorial Optimization Problem
• N-Queen problem
• Sudoku problem
• Balanced Class Teacher Assignment Problem
• Class Allocation Problem
• Traveling Salesman Problem
• Exercise
• Backtracking algorithm

19
Backtracking Algorithm

• Backtracking is a problem-solving algorithmic technique that

involves finding a solution incrementally by trying different
options and undoing them if they lead to a dead end. It is
commonly used in situations where you need to explore
multiple possibilities to solve a problem, like searching for a
path in a maze or solving puzzles like Sudoku. When a dead
end is reached, the algorithm backtracks to the previous
decision point and explores a different path until a solution
is found or all possibilities have been exhausted.
• Backtracking can be defined as a general algorithmic
technique that considers searching every possible
combination in order to solve a computational problem.
20
 Backtracking Algorithm
• Candidate: A candidate is a potential choice • Feasible Solution: A feasible solution is a
or element that can be added to the current partial or complete solution that adheres to all
solution. constraints.
• Solution: The solution is a valid and complete • Dead End: A dead end occurs when a partial
configuration that satisfies all problem solution cannot be extended without violating
constraints. constraints.
• Partial Solution: A partial solution is an • Backtrack: Backtracking involves undoing
intermediate or incomplete configuration previous decisions and returning to a prior
being constructed during the backtracking decision point.
process. • Search Space: The search space includes all
• Decision Space: The decision space is the set possible combinations of candidates and
of all possible candidates or choices at each choices.
decision point. • Optimal Solution: In optimization problems,
• Decision Point: A decision point is a specific the optimal solution is the best possible
step in the algorithm where a candidate is solution.
chosen and added to the partial solution.
21
Backtracking Algorithm

22
Recursive Technique for Backtracking Algorithm

TRY(k)
Begin
Foreach v in Ak
if check(v,k) /* Check for feasibility of assigning v to 𝑥𝑘 */
Begin
xk = v;
[Update data structure D]
if(k = n) save a feasible solution;
else TRY(k+1);
[Recovery D]
End
End
Main()
Begin
TRY(1);
End

23
Generate binary string

24
Generate permutation of a set

25
THANK YOU !

26