What is Local Search?

Local search is probably the oldest and most intuitive optimization technique. It consists in starting from a solution and improving it by performing (typically) local perturbations (often called moves). Local search has evolved substantially in the last decades with a lot of attention being devoted on which moves to explore. These notes are the ones we made after extensively studying local search from various sources: the the first exposure to LOCAL SEARCH via Pascal van Hatenryck Coursera Lectures and then exploring local search techniques in several research papers, online sources etc.

Types of problems

We can deal with 3 main types of problems:

1. Satisfaction problems: We have some constraints and we start with a config which doesn’t satisfy the constraints and we gradually move towards satisfiability
2. Pure optimization problems: We have a function which we want to optimize and we move towards the direction of optimization
3. Constrained optimization: This is the tougher class which needs to satisfy constraints as well as optimize a function at the same time

In simple words, local search is a technique that explores the space of possible solutions in sequential fashion, moving from a current solution to a “nearby” one.

Some local search assignments can thus violate the ‘constraints’ that you’d put in a constraint programming solution, unlike constraint programming where all intermediate states satisfy all constraints.

1.1 Satisfiability to Optimization

• Goal is to transform the satisfaction problem to an optimization problem
• Might try to minimise violations, assign a penalty for each violation
• In local search, all states are possible solutions to the problem. The solution may be good or bad. Eg: In an 8-queen problem, all the states which we will traverse through in local search wilutions (here, it means that they have same value for most of the decision variables).l have 8 queens on the board. So, instead of first placing 1st queen on the board, then 2nd and so on, we directly start with a solution irrespective of whether it is a high quality solution or a low quality solution.
• The intuition behind the local move is that two states which are neighbours have relatively similar sol