14
$\begingroup$

I am from a machine learning (ML) background and am interested in how ML is applied to Combinatorial Optimisation. As such, as I have been reading around the area and have come across the statement that essentially states 'designing heuristics requires considerable domain knowledge'.

For instance, in this paper they make the statement "Nonetheless, the design process of such heuristic methods requires specialized domain knowledge and involves trial-and-error as well as tuning".

Further, in this paper they say "However, the effectiveness of general algorithms is dependent on the problem being considered, and high levels of performance often require extensive tailoring and domain-specific knowledge".

Neither of these papers provide references to support such a statement so I am wondering what kind of domain knowledge they are referring to? Based on the papers that I have read where new CO heuristics are introduced, it seems that the 'domain knowledge' is a good understanding of the problem (e.g. TSP) and being good at the math required to prove bounds on the solution qualities, search strategies, etc.

Also, it doesn't seem like any extra requirement on domain knowledge is required compared to if you were developing an algorithm for some other field (e.g. an ML algorithm!); in general I would argue that to develop an algorithm to solve a problem you would have to have pretty good knowledge of the area you're developing the algorithm for, that shouldn't be specific to CO.

I was wondering if anyone could provide some insight into these comments, please.

$\endgroup$
1
  • 2
    $\begingroup$ Real world problems are often very complex. Any model of a real world problem is already an approximation. The domain specific knowledge is required to be able to define a model that takes enough constraints into account to make the solutions useful, but remains simple enough to be solved. This is how I understand these quotes $\endgroup$
    – fontanf
    Nov 4, 2021 at 16:46

3 Answers 3

17
$\begingroup$

The following is largely opinion/conjecture on my part. Many (though not all) heuristics involve neighborhood search. For that type of heuristic to be effective, you need "neighborhood" to be defined in a way that is both computationally convenient (moving from one solution to a "neighboring" solution is straightforward and does not involve solving an NP-nasty subproblem) and meaningful in terms of the objective. The latter boils down to defining neighborhoods so that a neighborhood of a good solution is likely to contain a better solution. If good and bad solutions are uniformly scattered around neighborhoods, neighborhood search is no better than random search. The ability to figure out a good definition of "neighborhood" may require some domain knowledge (understanding of the particular problem).

Similarly, the efficacy of evolutionary metaheuristics such as genetic algorithms depends on how solutions are encoded (the "chromosome" in a GA), and possibly on how crossover, mutation and other operators are defined. You want crossover of two "good" solutions to be likely to produce a better solution, and mutation of a "good" solution to have a decent chance of producing a better solution. Otherwise, again, the metaheuristic just turns into an overengineered version of random search. Finding an effective encoding can require some understanding of how the objective value depends on "chunks" of the solution, which again is a form of domain knowledge.

$\endgroup$
4
  • 1
    $\begingroup$ $(NP)^{max}$ (whatever, exactly, that means) for your comments on GA. $\endgroup$ Nov 4, 2021 at 15:19
  • 1
    $\begingroup$ That is a fantastic answer, thank you. $\endgroup$
    – David
    Nov 4, 2021 at 16:53
  • $\begingroup$ The subset of heuristics described above are those that use surrogate-modeling, correctly noting that domain-knowledge can help improve the quality of surrogate-models. $\endgroup$
    – Nat
    Nov 5, 2021 at 0:11
  • $\begingroup$ I'm not sure I agree. Consider heuristics such as 2-opt and 3-opt for the TSP. They are neighborhood search heuristics (where the neighborhood of a tour is defined in terms of tours that reachable by a certain number of edge swaps), but to me they operate directly on the original model/problem and not on a surrogate. $\endgroup$
    – prubin
    Nov 5, 2021 at 21:44
6
$\begingroup$

tl;dr Having relevant knowledge can help folks come up with better techniques, including heuristic techniques.


Relevant knowledge can be useful in problem-solving.

Heuristic techniques are those that're somehow fuzzy/approximate/unreliable. The term "heuristic" is basically a disclaimer, qualifying that a technique isn't ideal.

Relevant knowledge (domain-knowledge) can help folks come up with better problem-solving techniques, including heuristic problem-solving techniques.


Example: Heuristic for video-games.

Say you're playing a video-game that you really like and a newbie asks you for advice. Without considering their exact situation, could provide them with some general advice that'd help guide in the right direction?

That'd be a heuristic, and presumably having known about the video-game helped enable you to provide a better one. The more you know about what's possible, various benefits/costs, gains/risks, etc., the more tools you have to help craft better heuristics (better advice).

Unless it's a solved game, where you can recommend a perfect strategy. Then you'd be giving them a non-heuristic solution rather than a heuristic solution.

$\endgroup$
5
  • $\begingroup$ This is a nice analogy, thanks! $\endgroup$
    – David
    Nov 5, 2021 at 10:40
  • $\begingroup$ In my terminology heuristics also deliver solutions. Just usually with unknown quality. $\endgroup$ Nov 5, 2021 at 14:57
  • $\begingroup$ @ErwinKalvelagen: Good point; tweaked the terminology a bit. $\endgroup$
    – Nat
    Nov 5, 2021 at 15:53
  • $\begingroup$ I would say heuristics deliver solutions that are not proven optimal. As such they might reasonably be considered approximate, although it's entirely possible that one generates a solution that is optimal. $\endgroup$
    – prubin
    Nov 5, 2021 at 21:39
  • $\begingroup$ Even for formal proofs of guarantees there is a lot of room for partial guarantees. For example, maybe we cannot guarantee optimality, but perhaps we can prove an approximation ratio. Maybe the solution is only bad if some specific feature of the input is big. Maybe we can get guarantees for only a small subset of the theoretical input space, but actually only apply the method outside of this subset. $\endgroup$ Nov 6, 2021 at 6:13
3
$\begingroup$

Heuristics are "rules of thumb" that in some cases try to estimate some quantity without explicitly computing it. The better the estimate, the better the algorithmic performance, so good heuristics are important. Domain knowledge can help to improve estimates by understanding what is possible or reasonable. Take A* search, for example, which can be used to find a minimum-length path between two points, which requires a heuristic estimate of the remaining distance to the goal. The closer the estimate is the true remaining distance, the faster the algorithm will run, but the heuristic should not overestimate. A decent place to start with the heuristic is the straight-line Euclidean distance between two points. But if you know the agent can only move along a grid, one can use that domain knowledge to instead use the Manhattan distance for a more accurate estimate. Maybe there are spots on the grid that are hard to traverse and come with extra cost, further allowing you to tune the heuristic. The more you know about your domain, the closer the heuristic will reflect the situation it actually describes.

Other simple heuristics come from knowing where to look in the first place. Machine learning in high-dimensional data is often difficult, can be prone to overfitting, and can have issues with multiple hypothesis testing. But if your domain knowledge allows you to exclude many features as irrelevant, the problem becomes muh simpler. Poor prior knowledge will have you eliminate truly meaningful features, but good domain knowledge will allow you to reduce the features space to a smaller number of useful dimensions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.