Large neighborhood search - LNS

14 important questions on Large neighborhood search - LNS

What is the  idea behind LNS (Large Neighborhood Search)?

A neighbour solution is generated using destroy and repair heuristics

What is a destroy heuristic?

Select q variables and clear their value. Select q building blocks and remove them from the solution.

What is a repair heuristic?

Construct a feasible solution from a remaining solution. (After the destroy heuristic).
  • Higher grades + faster learning
  • Never study anything twice
  • 100% sure, 100% understanding
Discover Study Smart

If the number of variables removed from the current solution is too small what are [2] consequences?

  • Less diversification;
  • Effect Large neighbourhood is lost;

If the number of variables removed from the current solution is too large what are [3] consequences?

  • Less intensification;
  • Random re-optimization with poor solution qualities;
  • Time consuming;

What are possible destroy strategies considering the degree of destruction in LNS?

  • Constant degree;
  • Random degree;
  • Increasing degree;
  • Decreasing degree;
  • Increasing and decreasing degree;

Explain the destroy strategy, degree of destruction: increasing degree.

Increase the degree of destruction over time, after the search has stagnated in the current size, such that you only search a larger neighbourhood when the smaller neighbourhood is fully exploited.

Explain the destroy strategy, degree of destruction: decreasing degree.

The further you get in the algorihm the more you want to exploit promising solution areas.

What are [4] examples in destroy strategy, destroy heuristic?

  • Random removal;
  • Worst removal;
  • Shaw-removal;
  • History-based removal;

In destroy strategy, destroy heuristics what is the history-based removal?

Remove variables that were not removed in recent iterations until the degree of destruction is reached.

In insert strategy, repair heuristics what is meant with the greedy repair?

Add variables that add the least to the objective function.

Give [6] possible acceptance strategies considering LNS

  • SA;
  • Tabu search;
  • Local search';
  • Random accept;
  • Treshold accept;
  • Level accept;

In acceptance strategies in LNS, explain level accept;

Accepting solutions that are better than some preset level. This level can be decreased in every iteration or after an acceptance or increased after a rejection.

Explain the destroy strategy, degree of destruction: increase and decrease degree.

Based on past performance algorithm.

The question on the page originate from the summary of the following study material:

  • A unique study and practice tool
  • Never study anything twice again
  • Get the grades you hope for
  • 100% sure, 100% understanding
Remember faster, study better. Scientifically proven.
Trustpilot Logo