How to Solve It:
Modern Heuristics 
Zvigniew Michalewicz and David Fogel

pp. 64 ff -- local search.
Focus on a transformation of the given solution to try to improve it. 
Suppose you are doing satisfiability.
Local search says:
loop
  make a flip of a variable
  if improve then keep  and stop if done
  else reject
until tired

For travelling salesman, the trick is to do local switches.
Take 2 non-adjacent edges and swap them.
e.g. take 
(a,b) and (c,d) and suppose there is a path between b and c and between
a and d so we have
a-b-x1..x2- c-d-x3..x4-a

Now we swap so we get
d-b-x1..x2-c-a-x4..x3-d

If that is an improvement then we take it, else choose another.

The Lin-Kernighan algorithm does a clever search for k-opts and
can get within a few percent of the optimal.
In the basic method, k remains 2.
It uses a construct that is one away from a tour called a delta-path.
A delta-path is a sequence of nodes such that each node appears once
except the last one.
e.g. figure 3.7 on page 67. 
a-b-c-d-e-c would be an example.
To repair this to a tour, just replace e-c by e-a.
Alternatively, replace c-d by a-d.
We might also do a "switch" by replacing e-c by e-b say.
Since there are two ways to make a delta-path into a tour,
there is the possibility of moving around the search space.

Figure 3.8 shows what to do but the gotos make it hard to read.
Start with a tour.
If there is a cheaper delta-path, then take it.
Look then for a cheaper switch.
Create a new tour. If that is an improvement, then make that the new tour.
To limit the search space, don't retry a switch that has already
been tried.

lin-kernighan [slightly rewritten from the book]
begin
  generate a tour T
  best_cost = cost(T)
  for each node k of T do
    for each edge (i k) of T do
    begin
	if there is a j != k such that cost(i,j) < cost(i,k)
	then create a delta-path p by removing (i k) and adding (i j)
	  flag:= true
	  haveimproved:= false
	  while{flag // plus bookeeping to avoid redoing work
 	    flag:= false
            construct a tour T from p (but keep p around)
	    if cost(T) < best_cost
		best_cost:= cost(T)
		remember T
		haveimproved:= true
	    end if
	    if there is a switch of p resulting in a delta-path
		whose cost <= cost(T)
	    then 	
		make the switch to get the new path and call that p
		flag:= true
	 end while
	 if(haveimproved) then call lin-kernighan on best T so far
	end if
    end
end
	

p. 70
non-linear programming: 
Linear programming is of the form.
optimize some function f(X) given the following constraints
h1(X), h2(X), etc.
If all the functions and constraints are linear, then there
are solvers that will solve it in polynomial time.
Otherwise, must use heuristics.

74 -- gradient method for finding zeros.
Take two points and find the slope and then estimate where
the zero is.

101 -- branch and bound. The idea is to give an estimate of
what the best solution could be in order to bound the answer.
So you don't go off and look at useless paths.
Because if you have a partial solution and then best possible
continuation is more expensive than a solution you already have,
then there is no reason to look at it.
(go to A* notes).

120-124 -- simulated annealing

Annealing is the process of slowly cooling a molten element
in order to make it form a crystal rather than a higher energy state
glob. At high temperatures, many non-greedy moves get taken.
As the temperature cools, fewer and fewer are taken.

Simulated annealing carries this idea to optimization problems:

Figure 5.3:
take an initial solution s1
initialize temperature T to a high value
loop until temperature is low enough or you have found some answer
  take  a random change to the solution s2
  if s2 is better than s1 then take it
  else if s2 is worse than s1 then take it with probability
	e^((cost(s1)-cost(s2))/T)
	// so the exponent is always negative
	// the higher T, the closer the exponent is to 0 so prob is high
	// The bigger the cost difference, the more negative the exponent
	// and the probability approaches 0.
  decrease the temperature
end loop


/ A generic simulated annealing function.
/ This requires an exchange function  tryexchange
/ that returns a pair, first element is a delta which
/ will be accepted if positive but will be accepted if negative
/ only with a probability that depends on temperature.
/ The second component is how to change the state if the exchange
/ is accepted.
/ It also requires a changestate function that takes that second
/ argument.
/ Thus, this is totally generic.
simannealing:{[hightemp; stepswithintemp]
    currenttemp: hightemp
    while[currenttemp > 0
                / prob that you will take a bad move
        do[stepswithintemp
                pair: tryexchange[]
                delta: pair[0]
                if[~ delta < 0
                        x: changestate[pair[1]]
                ]
                if[delta < 0
                        probbad: 2 ^ ((delta*hightemp%currenttemp))
                        if[((*1 _draw 0) < probbad) / then take the change
                                x: changestate[pair[1]]
                        ]
                ]
        ]
        currenttemp-: 1
    ]
}

There is a lot of tuning of the parameters.
Initial temperature. How long at each temperature?
Halting condition. Selection of neighbor.

p. 125: tabu searching:
memory forces the search to explore new areas of the search space.
Certain areas of the search space become taboo at least for the moment.
If we are varying a number of variables, e.g. in satisfiability.
At some point we vary variable xj and that worked well.
Then for some time we might say that xj can't be varied again.
Helps with neighbor searching.