Optimization terminology: "Exact" v. "Approximate"

Question

In optimization literature, I frequently see solution methods termed "exact" or "approximate". (I use the term "method" here because I suspect exactness, or its lack, is a function of both algorithm and model.) My understanding is that "exact" translates to "produces a provably optimal solution" and "approximate" translates to "may or may not find an optimal solution but will not provide proof of optimality". I'd like to know how others view the terms.

The motivation is a review of recent paper submission. In it, we posed a binary linear programming model and a solution procedure that used branch-and-cut with a variant of Benders decomposition. We called the combination an exact method for solving the underlying problem. We also provided computational examples, all but one of which we solved to optimality. In the one remaining case, I cut off the run at 10 hours with an optimality gap of around 12%. The reviewer pointed to that case as an indication the procedure was not "exact". My initial inclination is to dismiss the comment, since branch-and-cut on a bounded ILP will always reach proven optimality given enough resources (time and memory). On the other hand, from a practical standpoint, if you're not going to get a proven optimal solution within your lifetime, perhaps the method really should not be considered exact.

I know we're not supposed to ask for opinions here, so instead I'll ask which is the proper interpretation of "exact" (or whether I'm completely off base in my interpretation of the term).

Answer 1

Exact: algorithm will eventually provide a provably optimal solution.

Approximate: algorithm will eventually produce a solution with some guarantees (e.g. a tour being at most twice as long as the shortest tour)

Heuristic: Algorithms that do not give any worst-case guarantee whatsoever.

Finite convergence and runtime are separate from "exactness" properties of an algorithm.

Answer 2

An exact method will (typically within a bounded number of steps) provide a proven optimal solution. This is, a solution x* and a guarantee that no other feasible solution has an objective better than that of x*. Typically, exact methods compute two types of bounds: lower (L) and upper (U) bounds. Optimality is then proven whenever both bounds coincide.

In contrast to exact methods that provide a guarantee of optimality, heuristics provide no such guarantee. In the OR literature, it is common to refer to those methods as heuristics rather than approximate methods. The latter is more commonly used to refer to algorithms with a proof of solution quality, although not necessarily exact. For instance, the TSP admits a 1.5-approximate algorithm (Christofides method), this is a method that will construct a solution whose cost is at most 1.5x that of an optimal TSP solution.

With respect to the reviewer comment, it is indeed a little odd. Using the same rationale, one would argue that Dijkstra's method is not exact because it will fail at solving shortest path problems containing trillions of points. The CONCORDE solver for the TSP is another remarkable example of exact method. Like any other method for a reasonably difficult optimization problem, it will fail at solving extremely large problems. No one would argue that CONCORDE is not exact though. It seems to me that you need to make your point using such type of argument. As I pointed before, an exact algorithm is one that constructs, within a finite number of steps, a solution x* and a guarantee that no other feasible solution of better objective value exists (usually by computing lower and upper bounds). No such algorithm will scale to solve every single possible instance on earth, unless of course the problem is trivial.

Answer 3

Exact: Provably optimal

Approximate: offers an upper bound on the gap

I would add heuristics: procedures that, as you described, may or may not provide an optimal solution (with out any proof or guarantee).

Answer 4

In addition to the other answers posted already, I'll add that the term approximation algorithm means an algorithm with a provable worst-case error bound that (as @MarcoLubbecke reminded me in the comments) has polynomial runtime. But the term is often misused to refer to a heuristic that may or may not have such a provable bound.

I would have interpreted the term approximate algorithm as roughly equivalent to heuristic, with or without error bounds. From others' answers, it seems they would disagree, and that they would argue that approximate algorithm = approximation algorithm. From a purely linguistic point of view, that certainly seems preferable; it would be really annoying if -e and -ion meant two very different things. But I am not sure I have seen the terms used this way consistently.

Answer 5

• According to L. Jourdan, et. al.[1], "NP-hard problems are difficult to solve and no polynomial-time algorithms are known for solving them. Most combinatorial optimization problems are NP-hard. Two approaches can be considered to solve this kind of problems depending on their size. For small instances, researchers usually use exact methods. Exact methods find the optimal solution and assess its optimality. There exist numerous exact methods such as the family of Branch and X, LP, DP and etc. Exact methods are known to be time expensive, so they can not be applied to large NP-hard problems or difficult ones. When instances become too large for exact methods, heuristics and in particular metaheuristics are often used".

• Authors of [2] are also mentioned the "solving-time" of the method for combinatorial optimization problem as the only disjunctive difference between Exact and Approximate methods saying that: "The available techniques for COPs can roughly be classified into two main categories: exact and heuristic methods. Exact algorithms are guaranteed to find an optimal solution and to prove its optimality for every instance of a COP. The run-time, however, often increases dramatically with the instance size, and often only small or moderately-sized instances can be practically solved to provable optimality. In this case, the only possibility for larger instances is to trade optimality for run-time, yielding heuristic algorithms. In other words, the guarantee of finding optimal solutions is sacrificed for the sake of getting good solutions in a limited time.

Last two sentences of the above paragraph explain exactly the approach that you followed in your paper.

So my interpretation is: "ALL exact methods can solve the large instances of COPs optimally if there are no limitations on their resources in terms of time and computational power, on the other hand, No method can be considered Exact unless the optimality of its solution can be proven."

[1]: Jourdan, Laetitia, Matthieu Basseur, and E-G. Talbi. "Hybridizing exact methods and metaheuristics: A taxonomy." European Journal of Operational Research 199.3 (2009): 620-629.

[2]: Puchinger, Jakob, and Günther R. Raidl. "Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification." International Work-Conference on the Interplay Between Natural and Artificial Computation. Springer, Berlin, Heidelberg, 2005.