Questions Tagged With large-neighborhoodhttp://www.or-exchange.com/tags/large-neighborhood/?type=rssquestions tagged <span class="tag">large-neighborhood</span>enWed, 26 Jul 2017 04:17:13 -0400MIP formulation of TSP (recreation of LNS)http://www.or-exchange.com/questions/14874/mip-formulation-of-tsp-recreation-of-lns<p>Hello, dear experts,</p>
<p>I have a partial solution of TSP which is 0-1-2-4-6-0. Node 0 is the depot or starting node, while other nodes represent cities or customers that need to visit in this single route.</p>
<p>Now we have two new cities 3 and 5, originating from dynamic request or the ruin step of large neighborhood search. These two nodes need to insert into the existed route, respecting their sequence. That is, node 1 should be visited before node 2. But node 3 can be inserted between node 1 and node 2.</p>
<p>I want to formulate a mathematical model to exactly solve this problem via CPLEX or Gurobi. But I have no idea how to formulate it. A simple method is to model a standard TSP formulation and then add the sequence constraint, e.g., node 1 before node 2. But this will make the problem more difficult than the standard TSP, which is not the instinct idea of large neighborhood search.</p>
<p>Do you have some ideas how to formulate the repair problem? thank you very much.</p>
<p>Best</p>LinYuanWed, 26 Jul 2017 04:17:13 -0400http://www.or-exchange.com/questions/14874/mip-formulation-of-tsp-recreation-of-lnsmipformulationslarge-neighborhoodtspHow local does Local Search have to be?http://www.or-exchange.com/questions/3043/how-local-does-local-search-have-to-be<p><strong>Background:</strong> 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.</p>
<p>So my question is: <strong>Does this count as a "local" search algorithm?</strong>
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. <strong>But</strong>, some people we have spoken to object to the use of the term "local" search in this context.</p>
<p>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?</p>timchippingtonderrickTue, 14 Jun 2011 14:53:41 -0400http://www.or-exchange.com/questions/3043/how-local-does-local-search-have-to-belocal-searchlarge-neighborhood