Heuristics in Optimization
by Mehmet Başdere
The increasing abundance of data over the last few decades has enabled businesses to develop more sophisticated models than ever before, resulting in unprecedentedly efficient operations. Unfortunately, this sophistication often makes the resulting models vastly more complicated to solve. This difficulty is often attributed to two main factors: increased problem size, like when your favorite streaming service optimizes its recommendation engine using huge sets of historical data; and time limitations, like the ones your navigation app faces when it dynamically updates your route after a wrong turn. Given the difficulty of solving such complex problems, compromises are sometimes necessary.
In broad terms, solutions to optimization problems are created in two different ways: using exact methods or heuristic methods. The beauty of exact methods in optimization comes from their guaranteed identification of the best solution (well, technically, an optimal solution). But depending on the problem setting, optimality can be very costly, sometimes impractically so. In such cases, it’s better to use heuristic methods, which can usually provide good enough solutions in a short period of time.
However, it’s not an either/or. Heuristic methods shouldn’t necessarily replace exact methods. In fact, they show their true power when used in conjunction with exact optimization. As a person who has spent more than ten years solving various optimization problems and developing exact solution approaches, I realized most operations researchers tend to belittle the concept of heuristics due to the threat of suboptimalities when used alone. However, heuristics are often the key to solving your most difficult business problems in constrained timeframes, even when an optimal solution is required.
Why Use Heuristics?
Let’s assume that we are trying to solve the infamous Traveling Salesman Problem (TSP). TSP is an integer linear problem with a straightforward objective: given a set of cities and the distances between each pair thereof, construct the minimum-length cycle (known as a tour) wherein each city is visited only once.
What makes solving TSP so difficult is its computational complexity, which grows exponentially as the number of cities visited increases (see our blog post on the vehicle routing problem [VRP], a problem closely related problem to TSP, which shows how the number of potential solutions increases in such problems). Problems with this degree of complexity demand at least some usage of heuristics in order to be solvable in practical timeframes.
Heuristic methods can be integrated into standard optimization procedures in three ways, broken out by the stage in which they’re employed: pre-optimization, post-optimization, and during optimization.
Pre-Optimization
The idea behind using pre-optimization heuristics is to find good solutions to warm-start the optimization procedure. For TSP, we can run constructive heuristics such as nearest neighbor or Christofides to construct a decent initial tour. In this distance-minimization setting, this initial tour provides a readily available upper bound (i.e., maximum tour distance) to the optimization procedure, which enables the solver to eliminate complete or incomplete solutions whose distance exceeds this upper bound. In this case, the optimization procedure can focus more on reducing the optimality gap (i.e., the gap between the theoretical shortest tour and the current best feasible solution) rather than searching for an initial solution. When feasible solutions are scarce or difficult to obtain, this kind of heuristic can be very helpful.
Furthermore, apart from the obvious benefit of having a feasible solution for your problem, initial solutions are helpful when checking the correctness of the formulation. If you investigate your initial solution and notice that it’s infeasible for your problem, then you automatically know to check for violated constraints and fix the formulation instead of wasting time on long optimization runs. Such preliminary checks can save a lot of time and effort when the solver takes hours (sometimes even days) before returning a solution or concluding that the problem is infeasible. In some very rare instances, providing an initial solution may throw the optimization procedure off and create longer run times, but it’s almost always better to provide an initial solution.
Post-Optimization
The other end of the spectrum is post-optimization. In this setting, we take the best solution obtained by the optimization procedure and apply improvement heuristics to make the best solution even better. Post-optimization heuristics can only be used when the optimization procedure terminates prematurely without proving optimality, usually due to time and/or memory restrictions. In TSP, potential post-optimization heuristics could be as simple as making pairwise swaps of two connections on the route (known as 2-opt), or Or-opt, which moves a single node (or segment of nodes) to a different position on the route to improve the current tour.
In post-optimization heuristics, we can measure the changes we make more accurately than in other cases, as our optimization procedure has already given us upper and lower bounds (from the best and worst solutions it found). Knowing the existing range of solutions allows us to contextualize the gains from heuristic approaches, and makes it easy to gauge their respective impacts.
Integrated Heuristics
While both pre- and post-optimization heuristics are quite useful, one common drawback is that they don’t interact with the optimization procedure in a strong sense. They cannot guide the optimization procedure (or be guided by it), as they only come into play at the very beginning and end of the optimization. This brings us to integrated heuristics, which are executed during the optimization procedure by using information from the partial and/or current best solution obtained so far.
Integrated heuristics are generally more powerful than pre- or post-optimization heuristics, as they can actively communicate with the optimization procedure. The most common way they do so is through callbacks. Callbacks are custom functions that the optimization procedure can use while it’s crunching away at the problem. Some examples of useful callbacks might include identifying new inequalities to strengthen existing formulations, adding violated constraints to a relaxed version of the current problem, constructing heuristic solutions from partial solutions, or running improvement heuristics on the current best solution.
Integrated Heuristics: An Example
Let’s demonstrate the power of integrated heuristics on a 500-node TSP instance with random coordinates in a square. We’ll use the generic subtour formulation (originally proposed by Dantzig, Fulkerson & Johnson), which includes a subtour elimination constraint. This means that any solutions that involve tours that don’t cover all nodes are disallowed. However, this naturally results in many constraints. In our 500-node setting, this condition means that there must be a constraint that prevents nodes 1, 2 & 3 forming a 3-node subtour, as well as a constraint that prevents nodes 37, 41, 99, 183, 215 & 499 to form a 6-node subtour, and so on.
Since we need one constraint to eliminate each possible subtour, this formulation needs exponentially many such constraints (2⁵⁰⁰ — 2, to be precise). Therefore, instead of manually coding and adding all these subtour elimination constraints, we start with a relaxed model that has only a select few of them. As the optimization procedure continues to solve, we allow the formulation to create subtours, and then add each subtour’s corresponding elimination constraint during the solution procedure with a callback (the Gurobi website has a concise explanation of this formulation along with implementation details).
In addition to generating subtour elimination constraints, we can integrate a simple subtour merge heuristic that connects subtours to form a feasible solution (see Figure 1). If the newly found solution is better than the current best solution, we provide it to the solver, which can process this information without having to restart.
The table below shows the time it takes (in seconds) for ten 500-node TSP instances to reach both (a) the first feasible solution within 10% of optimality, and (b) the optimal solution itself. Each instance is solved using Gurobi 8.1, both with and without the heuristic described above. When searching for the optimal solution, the subtour merging heuristic reduces the total runtime in 9 of 10 instances, resulting in an average improvement of 40%. Furthermore, the heuristic takes only 20–40 seconds to find a feasible solution within 10% of optimality, while the corresponding duration without the heuristic can climb to 45 minutes. On average, this integrated heuristic makes finding a feasible solution within 10% of optimality about 40 times faster, which can be crucial in settings with tight time limits.
When the exact procedure takes a long time to generate initial feasible solutions, the branch-and-bound tree can grow really quickly; in these situations, pre-optimization heuristics are best. Post-optimization heuristics can provide additional improvements, but only when the original formulation terminates before proving optimality. Finally, while more complicated to implement compared to the alternatives, integrated heuristics are the most powerful option, as they interact with and actively navigate the optimization procedure.
Conclusion
Heuristic methods are generally considered inferior to exact methods, as they find good enough solutions rather than the best solution possible. However, they can be extremely helpful in speeding up and/or scaling exact approaches for today’s most difficult business problems.
_________________________________________________________________
If you liked this blog post, check out more of our work, follow us on social media (Twitter, LinkedIn, and Facebook), or join us for our free monthly Academy webinars.
