optimisation

Question 1

what do optimisation problems consists of

Answer 1

variables, domains and objective functions

Question 2

definition of an optimisation problem

Answer 2

search problem with preferences
(i.e) objective functions

Question 3

describe the different objectives in an optimisation problem

Answer 3

Single-objective optimisation problems, e.g., Travelling Salesman
Problem (TSP): minimising the cost of the travelling.
Multi-objective optimisation problems, e.g., TSP with an additional
objective: minimising the time of the travelling.

Question 4

describe the different constraints in an optimisation problem

Answer 4

◆ Unconstrained optimisation problems.
◆ Constrained optimisation problems.

Question 5

can tree search problems works for optimisation problems

Answer 5

Tree search methods may not work for optimisation problems,
e.g. in some continuous search space

Question 6

can local search problems works for optimisation problems

Answer 6

Local search methods can be effective for optimisation
problems

Question 7

describe local search in optimisation problems

Answer 7

Generally fast and memory efficient.
Can deal with problems where the search state is difficult to
represent/formulate.
Can be used in an online setting when the problem changes,
e.g., in airline scheduling problem

Question 8

what are some local search methods used in optimisation

Answer 8

Hill climbing, e.g. gradient descent.
Simulated annealing, tabu search (keep a small list of
recently visited solutions and forbid the algorithm to return
to those solutions).
Population-based local search: evolutionary computation
(e.g., genetic algorithms)