6 - Primal heuristics

Question 1

Why heuristics?

Answer 1

Usefel when B&B is slow or struggles to find a feasible solution
-> find a good (hopefully) feasible integer solution

Question 2

2 different classes of heuristics

Answer 2

1 Construction heuristics produce a feasible solution from scratch

2 Improvement heuristics try to improve a given feasible solution (x’, y’)

Question 3

Overview of all heuristics

Answer 3

General heuristics:
1. Truncated MIP
2. Diving

Construction heuristics:
3. LP-and-Fix or Cut-and-Fix
4. Relax-and-Fix

Improvement heuristics:
5. Relaxation induced neighborhood search (RINS)
6. Local branching (LB)
7. Combinations
8. Exchange (EXCH)

Question 4

Truncated MIP

Answer 4

Run a B&B algorithm for a fixed amount of time

The best solution obtained when the time limit is reached is the MIP heuristic
solution

Used both as construction and improvement heuristic

Question 5

Diving

Answer 5

Question 6

LP-and-Fix or Cut-and-Fix

Answer 6

Question 7

Relax-and-Fix

Idea and Notation

Answer 7

Question 8

Relax-and-Fix

Example and mathematical model

Answer 8

Question 9

Relax-and-Fix

Obersavation on role of the set U_r and graphic

Answer 9

Question 10

Relaxation induced neighborhood search (RINS)

Answer 10

Question 11

Relaxation induced neighborhood search (RINS)

Example and Cases

Answer 11

Question 12

Local branching (LB)

Answer 12

Question 13

Local branching (LB)

Example and Cases

Answer 13

Question 14

Combinations

(Primal Heuristics)

Answer 14

Question 15

Exchange (EXCH)

Answer 15

Question 16

Exchange (EXCH)

Cases and Example

Answer 16