Can Local Search Operators be formulated as a Mixed Integer Program?

Question

Consider the situation of Vehicle Routing. Once we have an initial solution, one can apply various local search moves to improve it.

For example:

• Removing a single customer from a route and inserting it into another route. (Relocate)
• Removing a subsegment of customers from one route and inserting it into another. (Or-Exchange)
• Swapping two customers of different routes. (Swap)
• Exchanging subsegment of customers between two different routes. (Cross-exchange)
• 2-opt

Has there been any work in modelling local search moves as MIP?. Is it even possible?

Answer 1

What you describe is a special case of Large Neighborhood Search.

Large Neighborhood search is an optimization method that consists in destroying a part of a solution and recreating it with a constructive approach. The constructive approach can be a greedy algorithm, a constraint programming model... or a MILP model.

When the constructive part is a MILP, it is often called "Kernel search", and the destruction part takes the form of unfixing some variables (possibly restraining their domain). Here is an example for an Inventory Routing Problem:

• Archetti C, Guastaroba G, Huerta‐Muñoz DL, Speranza MG (2021) A kernel search heuristic for the multivehicle inventory routing problem. International Transactions in Operational Research n/a: https://doi.org/10.1111/itor.12945

In this case, the neighborhood considered is larger than the neighborhood of a classical Local Search algorithm. Indeed, to explore a 2-opt neighborhood, it's faster to do a manual loop than to solve a MILP model.

This approach is attractive for problems with continuous variables (such as Inventory Routing Problems) since it's not straightforward to design a classical Local Search algorithm in these cases

Answer 2

I'm not aware of any work on modeling local search heuristics as MIPs. It is certainly possible to come up with a MIP model for each heuristic you mentioned. What is not clear is whether it is worth doing.

First, you would need to decide whether your model would look for a single feasible move (feasible here meaning produces a better feasible solution than the starting point) or would look for an "optimal" move (the single move of its type that produces the biggest improvement in the objective). Second, you would have to decide whether the MIP result was sufficiently better than the "standard" approach (using loops, say) to warrant want I am fairly certain would be a longer (possibly substantially longer) computation time. In that vein, the third question would be whether running one of these MIPs repeatedly (once per step in the parent heuristic) would be faster than just solving the entire problem once using a MIP model.