# Week 3 Flashcards Preview

## Operations Management > Week 3 > Flashcards

Flashcards in Week 3 Deck (31)
1
Q

Objective function

A

Function that needs to be maximized or minimized

2
Q

Travelling salesman problem (TSP)

A

Find the hamiltonian path with minimal cost of a given set of points

3
Q

What are real-life applications of the TSP?

A

Last-mile delivery routing
Drilling of printed circuit boards
Computer wiring
The order-picking problem in warehouses

4
Q

What are real-life applications of the knapsack?

A

Investment portfolio optimisation

Ordering in a restaurant

5
Q

What is exhaustive search?

A

Perform complete enumeration of all possible solutions after which the best one is selected

6
Q

What is an exact method?

A

Method that finds the optimal solution using exhaustive search or by excluding subsets of solutions

7
Q

What is a heuristic?

A

technique designed for solving a problem more quickly when exact methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution

8
Q

What is the optimality gap?

A

Difference of optimal solution and solution found by heuristics

9
Q

What is a stopping criterion?

A

Criterion that defines when the heuristic should stop its search

10
Q

What does problem-dependent search procedures mean?

A

The need to tailor the rules of the heuristic to the specific problem

11
Q

What is a metaheuristic?

A

A high-level problem-independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimisation techniques

12
Q

What are the four metaheuristic frameworks?

A

Constructive metaheuristics
Local search metaheuristics
Population-based metaheuristics
Hybrid metaheuristics

13
Q

What is a constructive metaheuristic?

A

Metaheuristic that constructs solutions from their constituting elements, by adding moves to partial solution e.g. greedy algorithm

14
Q

What is the nearest neighbour?

A

Greedy algorithm finds nearest neighbour from points which has not been added to solution, can add randomness by restricted candidate list

15
Q

A

Methods that evaluate the elements that can be added by considering not only the effect of the next move, but of several moves into the future

16
Q

What are local search metaheuristics?

A

Metaheuristics that find good solutions by iteratively making changes to a single solution, called the current solution

17
Q

What are neighbourhood?

A

Set of solutions that can be obtained by applying a single move to the current solution

18
Q

What is move strategy / search strategy?

A

rule used to select new current solution

1. Decide on a move type
2. Decide on the strategy
19
Q

What is a local optimum?

A

No solutions in the neighbourhood improve the current solution

20
Q

What are hill-climbers?

A

Best improvement option after performing a local search metaheuristic

21
Q

What is peturbation?

A

A large random change to the current solution

22
Q

What is iterated local search?

A

Metaheuristic that iteratively performs local serach and peturbation

23
Q

What is multistart local serach?

A

Metaheuristic that iteratively performs local serach and restart

24
Q

What is variable neighbourhood search algorithms?

A

Metaheurstic that define different move types and change the move type used once a local optimum has been reached

25
Q

What are tabu search algorithms?

A

Strategy that uses information on the past progress of the search and record this information in memory structures

26
Q

What is simulated annealing?

A

local search with probability that accept inferior solution

27
Q

What are population-based metaheuristics?

A

Metaheuristics that find good solutions by iteratively selecting and then combining existing solutions from a set, usually called the population

28
Q

What are the steps of a genetic algorithm?

A
1. Initialize population
2. Evaluate current solutions
3. Parent selection
4. Recombination (Cross-over operator)
5. Repair operator
6. Mutation
7. Reinsertion of offsprings in population
8. Check stopping criterion
29
Q

What are hybrid metaheuristics?

A

Metaheuristic that use more than one of the previously discussed metaheuristics

30
Q

What is GRASP?

A

1. Construct an initial solution using a randomized greedy algorithm
2. Apply local search on the constructed solution
3. Update the current best solution