Optimization Approaches (Meta-heuristic, Graph-based, MILP)

Question

I am very new to algorithms, now working on some route optimization problems and came across some papers on the following approaches:

• Meta-heuristics Approach Population Based (Genetic Algorithm, Ant Colony Optimization etc.) Single-solution Based (Iterative Local Search)

• Graph-based Approach for example A* Algorithm

• Mixed-Integer Linear Programming Approach

I am a little bit confused as to the relationships between these approaches, do we use for example use GA to solve MILP or they are all just separate approaches?

Thanks in advance!!

Answer 1

Mixed-Integer Linear Programming is more a class of problems than an algorithm. It consists of all problems that boil down to maximizing a cost function that is linear and has integer values. These assumptions make it easier to create algorithms that tackle this very specific problem, and I think that is what you are referring to by "MILP Approach". Implementation can vary a lot though, because problem-specific optimizations might be applicable on top of a good general solution.

Graph-based is more difficult to define, because all algorithms involving graph theory do not make it explicit that they are using a graph, but proof of correctness or optimality might require using some non-trivial theorems on graphs.

Meta-heuristics are a class of algorithms that intend to extend heuristics. A heuristic is a "practical" approach to a problem, that does not guarantee to be optimal, but that is sufficient for the immediate goal. Meta-heuristics take the abstraction level one step higher : instead of reasoning directly on a problem, you will be building solutions for the problem (i.e. individuals in GA) and reasoning about them (i.e. evolving your population in GA).

---

Route optimization might fall under any of the three categories, you would need to be more precise before I can answer properly, but here are a few examples:

• Flow maximization problems : Linear Programming.

  ex: each route of your network can be used by at most k trucks and you want to take your sand from point A to point B in the smallest time possible, how many trucks can you send on each path? One path might split into two more restricted path, or shrink and let your trucks stuck in the middle of a path, or even merge, etc. (Note how it is still graph-based)

• Shortest path, longest path, number of paths : Pure Graph-based.

  Depth-first and Breadth-first searches (I assume you know that already) can solve a huge number of graph-based problems without the need for any more complicated approach. A* for instance is "only" an extend version of DFS. With route optimization, you most likely have the routes network represented as a graph, so this might be a good starting point.

• Traveling Salesman Problem : Meta-heuristics

  TSP is basically finding a path that visits all cities exactly once. It is much more difficult than it looks like (NP-complete, if that rings a bell). Meta-heuristics are very efficient here, because no efficient solution is known. Genetic algorithms, Ant-colony optimization and Simulated annealing all give pretty good results, if properly implemented. Iterative local search, as you quoted, might be used for local individual-based optimizations between each global optimization round for instance, yielding better results.

I'm sorry my three examples fall into graph-related problems, but it also shows that graphs can help solve an incredible number of problems, even when the term graph is not explicitly quoted in the problem statement.

All three also happen to be route optimization problems, it all depends on what optimization you are looking for. Your problem might be best solved with one of these three methods, or maybe by combining two (local LP optimization for Meta-heuristics for instance).