6. Primal heuristics

Question 1

Construction heuristics

Answer 1

produce a feasible solution from scratch

Question 2

Improvement heuristics

Answer 2

try to improve a given feasible solution (x, y)

Question 3

Truncated MIP

Answer 3

• 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 4

Diving

Answer 4

• At each node, all the y variables taking value 0 or 1 in the LP solution are frozen at that value
• Then, create one branch by fixing one of the y variables that is fractional to an integer value

Question 5

LP-driven dives

Answer 5

• use the latest LP solution (ˆx, yˆ) and fix a variable closest to integer
• Set yk = 0 if yˆk ≤ 0.5 and yk = 1 otherwise
  -> Construction heuristic

Question 6

IP-driven or guided dives

Answer 6

• use the incumbent solution (x^, y^)
• Choose the variable yk to be fixed next
• The branching direction is fixed by setting y_k = y_k^_
  → Improvement heuristic

Question 7

LP-and-Fix or Cut-and-Fix

Answer 7

1 Solve the LP relaxation of the (sub)problem to be solved and let the solution be represented by (ˆx, yˆ)
2 Solve the following Mixed Integer Program called MIP^LP−FIX
- The highlighted constraint fixes the variables which resulted integer in the solution of the LP relaxation

Question 8

Relax-and-Fix

Answer 8

iteratively solve a MIP in which some variables are fixed to specific values (obtained from previous iterations), other are required to be binary, and other are relaxed

Question 9

Relax-and-Fix Notation

Answer 9

R: number of disjoint sets in which we divide our variables
Q: the disjoint sets of variables
U: subsets of variables

Question 10

Relax-and-Fix 1. iteration

Answer 10

• binary restrictions only on the variables belonging to the first group Q1 and on the variables belonging to U1 (the first subset containing one or more of the next variables groups)
• all the remaining variables (not belonging to these two previous groups) are relaxed (i.e., in the solution of this iteration, they can assume continuous values between 0 and 1)

Question 11

Relax-and-Fix 2. iteration

Answer 11

• fix the values of the variables of the groups r from the previous iterations to the values obtained in the previous solution (if r = 2, we fix the variables belonging to Q1 to the values obtained from the solution r = 1, i.e., solution from MIP1)
• impose the binary restrictions only on the variables belonging to the group Qr and on the variables belonging to Ur (the subset containing one or more of the next variables groups)
• all the remaining variables (not belonging to any of the previous groups) are relaxed (in the solution of this iteration, they can assume continuous values between 0 and 1)

Question 12

Relax-and-Fix 3. iteration

Answer 12

MIP in which none of the variables are relaxed

Question 13

Fig. Example of iterations during the relax and fix heuristic

Answer 13

Question 14

Fig. Production planning problem with 200 time periods

Answer 14

Question 15

Improvement heuristics

Answer 15

• try to improve a given feasible solution (x, y)
  1 Relaxation induced neighborhood search (RINS)
  2 Local branching (LB)
  3 Combinations
  4 Exchange (EXCH)

Question 16

Relaxation induced neighborhood search (RINS)

Answer 16

• Idea: compare the neighborhoods of the LP relaxation solution (ˆx, yˆ) and of the feasible solution we are starting from (x_, y_). If a variable has the same binary value in both solutions, then this value is fixed
• Given: LP solution at the root node (ˆx, yˆ) and best known feasible solution (x_, y_)
• Common idea: use MIP to explore some promising neighborhood for a limited amount of time

Question 17

RINS Steps

Answer 17

1 Solve the LP relaxation of the MIP ((ˆx, yˆ))
2 Get a feasible solution (for example, by using a constructive primal heuristic) (x_, y_)
3 Compare them and solve the following MIP^RINS

Question 18

Local branching (LB)

Answer 18

• Idea: Starting from a feasible solution (¯x, y¯), solve the model by imposing that no more than k variables should have a different value with respect to the values assumed in the feasible solution
• The neighborhood consists of those y vectors that do not differ from y in more than k values

Question 19

LB Steps

Answer 19

1 Get/start from a feasible solution (x, y) (for example, by using a constructive primal heuristic)
2 Solve the following MIP^LB

Question 20

Exchange (EXCH)

Answer 20

• Improvement version of relax-and-fix heuristic
• Idea: at each iteration, all variables which are required to be binary are fixed to the values obtained in the best feasible solution found so far, except for a group of variables for which the binary constraint is imposed (but the model is free here to decide about the value).

Question 21

EXCH Steps

Answer 21

• Qr and U r with 1 ≤ r ≤ R
• At each step r (1 ≤ r ≤ R) of the heuristic, we solve the following MIP^EXCH,r
• All integer variables fixed at their values in the best solution (x, y) found so far (or in the last solution)
• except for variables in the set Qr (or Qr ∪ Ur) which are restricted to integer values