Background: We have been doing some work on large MIP problems, some of which have maybe 1,000,000 binary variables. To solve these and get good solutions, we have been using some ideas borrowed from "local" or neighbourhood search. We explore "neighbourhoods" of the current solution and find improvements by focusing on just part of the problem at each step. Our experience shows that the best overall performance is when these "neighbourhoods" are quite large - including maybe 1000 to 10,000 binary variables.

So my question is: Does this count as a "local" search algorithm? A "neighbourhood" including 1000-10,000 binary variables is clearly quite a large neighbourhood, with a huge number of possible combinations of changes to the solution to evaluate. At the same time, it is only 0.1% - 1% of the whole problem, so that is also quite local - actually a smaller proportion of the whole problem than many of the "classic" local search examples. Many of these variables could change their value in each step, potentially all of them, but in practice only a tiny fraction of them actually change value. Maybe 20 binary variable values change (typically fewer change); that is only 0.002% of the total problem, so 99.998% of the solution is unchanged at each step. So the new solution is very "near" to the previous one, which sounds pretty local to me. But, some people we have spoken to object to the use of the term "local" search in this context.

So... How local does "Local Search" have to be? What are we missing here? What sort of search are we doing if it isn't local search? Please, what are your thoughts?

asked 14 Jun '11, 14:53

timchippingtonderrick's gravatar image

timchippingt...
1315
accept rate: 0%

retagged 26 Nov '11, 15:13

fbahr's gravatar image

fbahr ♦
4.6k716


This would be "Large Scale Local Search" in my book (sometimes written as "Very large scale local search". The idea of fixing much of the problem and optimizing over a subset of variables is a very good one, and works in lots of problems.

link

answered 14 Jun '11, 15:17

Michael%20Trick's gravatar image

Michael Trick ♦♦
4.1k41533
accept rate: 20%

I agree with Mike Trick that you are describing a local search approach. I also agree that you are using a large-scale neighborhood. When you use large-scale neighborhoods, a key to practical success is to efficiently search the neighborhood each iteration. By efficiency here, I mean practical efficiency, not theoretical efficiency.

Many very large-scale neighborhood search algorithms are therefore designed to use algorithms with polynomial worst-case complexity to search the neighborhood. However, it is not always necessary. We have used something we call integer-programming-based local search successfully for some large-scale network design problems, where IPs with time limits are used within the search. This sounds very similar to what you are doing, and we still call it local search!

link

answered 14 Jun '11, 15:34

Alan%20Erera's gravatar image

Alan Erera
1.0k37
accept rate: 12%

Handbook of Metaheuristics has a very nice chapter (all of the chapters are great) on Large Neighborhood Search, which it describes as a specific type of "very large scale neighborhood search" (VLSN) algorithm. The chapter has a lot of good references about various local search algorithms with large neighborhoods. It includes as a class of VLSN problems the algorithms with polynomial worst-case complexity to search a neighborhood that Prof. Erera referenced along with some other types. So I guess in short, I also agree with the other answers.

link

answered 16 Jun '11, 21:08

Luis%20de%20la%20Torre's gravatar image

Luis de la T...
4231612
accept rate: 11%

edited 16 Jun '11, 21:10

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×8
×2

Asked: 14 Jun '11, 14:53

Seen: 1,370 times

Last updated: 26 Nov '11, 15:13

OR-Exchange! Your site for questions, answers, and announcements about operations research.