Local

Search

Local

search

is

a

technique

that

takes

as

an

input

a

feasible

solution

to

a

combinatorial

optimization

problem,

and

tries

to

produce

a

better

solution.

The

idea,

at

a

high

level,

is

to

search

_

locally

_

in

a

_

neighborhood

_

of

the

input

point

for

a

solution

that

immediately

improves

the

objective

value.

If

no

such

solution

can

be

found,

our

input

is

_

locally

optimal

_

and

is

returned.

Otherwise,

we

recursively

call

our

local

search

algorithm

on

the

superior

point

found.

More

formally,

suppose

we

are

given

some

optimization problem

where

LaTeX Math Inline

and

LaTeX Math Inline

. In local search, for every

LaTeX Math Inline

, we must give some

LaTeX Math Inline

to be the neighborhood of

LaTeX Math Inline

. Then given some initial feasible solution

LaTeX Math Inline

, for

LaTeX Math Inline

, we let

To run a local search algorithm you begin with

LaTeX Math Inline

, and iterate the above process until it converges, i.e.

LaTeX Math Inline

.

The key to making local search work is how we choose

LaTeX Math Inline

. We need be able to efficiently optimize over

LaTeX Math Inline

, otherwise our local search heuristic will be no easier to solve than our original problem. However, if we define

LaTeX Math Inline

to be too small a set, then we may get stuck in a local optimum that isn't very good.

A few warnings about local search:

• Without special problem structure, local search provides no guarentee on the quality of the solution produced relative to the global optimum
• Generally speaking, we do not have a good upper bound on the number of iterations until local search converges. We have the trivial bounds of

  LaTeX Math Inline

  , which may be exponentially large, and (if the objective is guaranteed to be integer),

  LaTeX Math Inline

  , which can still often be exponential (assuming the problem has weights which are input in binary).

An example

TODO

Two-Opt for TSP

Two Opt is one of the simplest of many local search techniques for TSP. The idea is very simple: given a tour, choose any two (non-adjacent) edges, and swap the end points to make a new tour. For example, in the figure below, we begin with the tour given by the node ordering 1, 2, 3, 4, 5, 6, 7, 8, and we we pick the edge from 2 to 3 and the edge from 5 to 6 and swap, to produce the node ordering 1, 2, 5, 4, 3, 6, 7, 8.

For a given tour, the neighborhood is the set of tours that can be made with such a swap (if

The origin of the name is as follows. For any tour, we can represent it as a vector

More generally, one can consider swapping the end points of up to

Implementing Two-Opt for User Generated Solutions

We have provided you with a simple Two-Opt implementation, TwoOptSolver. As a minor optimization, it caches ever tour it has ever checked the neighborhood of, so it can abort the search as soon as it has been determined that it will end up in a local optimum that has already been visited. It has a simple interface

We are going to apply Two-Opt to the solutions we generate through Christofides algorithm when we set the MIP start and when we run our Heuristic Callback. First, we add a field and initialize it in the constructor:

	private ChristofidesSolver<V,E> christofides;//this was old
	private TwoOpt<V,E> twoOpt;//<- add this line!

and change this piece of existing code:

		if(options.contains(Option.christofidesApprox)){
			System.out.println("Beginning Christofides...");			
			List<E> christofidesApproxTour = christofides.approximateBestTour(new HashSet<E>());
			Set<E> submittedTour = new HashSet<E>(christofidesApproxTour);
			double[] edgeVals = inverseEdgesUsed(submittedTour);			
			cplex.addMIPStart(edgeVariablesAsArray, edgeVals);			
		}

to read:

		if(options.contains(Option.twoOpt)){
			twoOpt = new TwoOpt<V,E>(tspInstance);
		}
		if(options.contains(Option.christofidesApprox)){
			System.out.println("Beginning Christofides...");			
			List<E> christofidesApproxTour = christofides.approximateBestTour(new HashSet<E>());
			Set<E> submittedTour;
			if(options.contains(Option.twoOpt)){
				submittedTour = twoOpt.searchNeighborhoodEdgeList(christofidesApproxTour);
			}
			else{
				submittedTour = new HashSet<E>(christofidesApproxTour);
			}
			double[] edgeVals = inverseEdgesUsed(submittedTour);			
			cplex.addMIPStart(edgeVariablesAsArray, edgeVals);			
		}

Now Two-Opt will be run on the initially generated solution. Note that we do not need to make sure that the output of Two-Opt is non-null, since we cannot hit the same tour twice on our first run. Now try and modify ChristofidesCallback yourself!

Profiling on TSPLIB

Small instances

Using QuadraticWaiting as our BackOff functions for both user cut generation and heuristic solution generation and rerunning our code with two-opt in place, we get the following results:

We see that Two-Opt gives a significantly better initial solution. Running times and number of nodes visited are also reduced.

Large instances

We see similar results for large instances. However, as the majority of the solution time is spent closing the final few percentage points, and our heuristics don't help much in this regime, there still seems to be significant room for improvement.

Perhaps more impressively, we now can get a near optimal solution very quickly. On d493, in less than one minute and on only 5 nodes, we found a solution with 0.77% of optimal, and on d657, in 90 seconds and 142 nodes, we get within 2.02%, which is often good enough. However, on large problems, like d657, we still have no way of reaching optimality in a reasonable amount of time.

Complete Source

If all else fails, your code should like the code below.