The "Knapsack problem" is solved absolutely exactly by the dynamic programming method for O(bn) in the worst case, where b is the size of the backpack and n is the number of items from which you need to find a subset of items to put into the Knapsack . If people are incompetent in this, then it is difficult for them to explain anything. As for the buzzword "metaheuristics",   it does much more harm than good, because as you rightly noticed

"metaheuristics is a "fraudelent" science" - or pseudo-science"

https://www.researchgate.net/post/Can_anyone_tell_me_the_formula_to_compute_average_standard_deviation_from_optimal_solution_for_the_RCPSP_problem_using_metaheuristics

and we need to repeat this every time so that young people understand this well.

For the case of duscrete tasks character, the evaluation of the clossness to the optimal solution of a concrete metaheuristic solving a concrete model must be done as a function of the parameters adopted in the stop criterion (for example,: a predetermined number of followed times without improving the objective) function .

The evaluation should be carried out for the studied task for task dimensions from very small until an optimal solution solution could be obtaned (by exhaustive search or for a well-known exact algorithm). The parameters of the stop criterion are looked for by a statistical function of the dimension of the task. When facing non soluble tasks for exact methods should settled down the parameters of the stop criterion by means of its calculation by the found function.

On the other hand, generally it is not required to reach optimal solutions, but just close to them ones because the model of the real task to be solved is always more complex that the used optimization model. For example, in the solution of the task it can be required of the employment, besides the basic optimization model, the evaluation of the individual solutions obtained helped by simulation and graphical representation procedures, between others.

Hi. Please see the benchmark instances of 0/1 knapsack problem. Different techniques are compared. Large literature is available on sciencedirect. When the problem becomes NP then we need heuristic algorithms.

Amol: No, we don't. We need to devise better algorithms, through expanding our knowledge of the associated theory. That's how progress is made - the use of metaheuristics is in fact, to some extent, detrimental to this development, seeing the thousand upon thousand reinventions of a metaheuristic with a presumably cool name, carrying with it very little theory.

Dear Amol C Adamuthe,

The "Knapsack problem" can be solved within 1 + є for O(n^3 / є) , where 0 < є < 1 http://web.cs.iastate.edu/~cs511/handout08/Approx_Knapsack.pdf .

Thank for sharing. Please share other simple combinatorial problems for which heuristic are not required.

You probably already are aware of the simple combinatorial problems associated with minimum-cost flows of varying complexity - the assignment problem, the transshipment problem, the shortest path problem, the linear single-commodity network flow problem, the linear multi-commodity network flow problem, and more. Most of them are solved very fast by special simplex-like procedures, but there are also others.

Thanks for sharing.

Some additions: the semi-assignment problem; the continuous knapsack problem; sorting; the minimum spanning tree problem.

Indeed, it seems that many in the (meta-)heuristics community are unaware of the tremendous progress that has been made in the field of exact algorithms. The fact is, quite a few NP-hard problems, such as knapsack, TSP and set partitioning, can now be solved surprisingly easily in practice (to proven optimality or near-optimality).

Having said that, I am convinced that there is still a place for research on (meta-)heuristics. This is for two reasons. First, there are many NP-hard problems (like max-clique and job shop scheduling) that are still extremely challenging for exact methods. Second, it is actually possible to analyse heuristics in a rigorous manner. For example, a paper that proves that a particular heuristic has a performance guarantee, or proves asymptotic optimality of a heuristic, or shows that an exponentially large neighbourhood can be searched in polynomial time, could be of great interest.

In my opinion, what we really need to eliminate are the papers of the type "We applied the ant/bat/bees/water droplet/harmony search heuristic to problem X for no apparent reason". :-)

Indeed, Adam, that last paragraph contains the point we need to emphasise.

Dear Adam N. Letchford,

your phrase "For example, a paper that proves that a particular heuristic has a performance guarantee, ..." sounds very optimistic. Please send me a link to this document for analysis. I am very interested to understand the technology for obtaining such a guarantee. Thank you in advance.

@Gennady: a good place to start would be the book "The Design of Approximation Algorithms" by Williamson and Schmoys.  Also conferences like STOC, FOCS and SODA often feature works on that topic.

Dear Adam N. Letchford,

To be properly understood, I want to detail my question a little. In my understanding, there is a difference between Approximation Algorithm and Heuristic Algorithm. An Approximation Algorithm, by definition, can guarantee to produce an approximate solution with a predetermined accuracy, that is, A(D) / OPT(D)

@Gennady, as far as I know, any heuristic that has a known guarantee on the solution quality qualifies to be called an "approximation algorithm". I have seen a few papers which show that fairly simple local search heuristics are in fact approximation algorithms for some specific combinatorial optimisation problems.

Quickly bouncing on the responses of Michael and Gennady. I would recommend to take this question with a grain of salt, and not to make too straightforward conclusions about metaheuristics in general and promote a witch hunt. The researcher who asked how to apply "bat algorithm for knapsack" was certainly new to this area, and this is why questions exist. Obviously, it does not make sense (except possibly for a home exercise) to develop a new metaheuristic for knapsack, and especially a nature-inspired one, since this problem is fairly well solved by exact and approximation algorithms. Still, let me just give a couple of good arguments for metaheuristics, as they had a rough time in this discussion given some previous answers.

• In first place, there are many beautiful papers focused on the computational complexity of local searches and metaheuristics, focusing on how to systematically search a wider set of solutions (possibly exponential) for a smaller complexity. There are fascinating open research questions related to these areas, and here are some related papers:

Chandra, B., Karloff, H., & Tovey, C. (1999). New results on the old k-opt algorithm for the traveling salesman problem. SIAM Journal on Computing (Vol. 28).

Deineko, V. G. V. L., & Woeginger, G. J. G. J. (2000). A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem. Mathematical Programming, 87(3), 519–542.

Englert, M., Röglin, H., & Vöcking, B. (2014). Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica, 68(1), 190–264.

De Berg, M., Buchin, K., Jansen, B. M. P., & Woeginger, G. (2018). Fine-grained complexity analysis of two classic TSP variants.

• There have also been many efforts to formalize the behavior of metaheuristics (e.g. into Markov Chains), but these are complex beasts with a huge number of states. Most metaheuristics which can be represented and analyzed in these frameworks are also too simplistic to be useful in practice. This is the same issue as approximation algorithms: basically what is simple enough to be fully analyzed and explained often fails to be efficient on more complex problems and applicable in more general situations.

• Metaheuristics are essential to give upper bounds for exact methods for CO problems. I will mainly focus on the class of vehicle routing problems, as this is a literature which is very familiar to me. Without the tremendous research made over the last 20 years on metaheuristics, and the upper bounds (UBs) that they allowed to find, the recent improvements on exact methods (now solving routinely problem instances with 200-250 customers) would have been impossible. The discovery pattern has always been the same: whenever an exact methods proves optimality for a solution, the same solution was in fact obtained a decade ago by metaheuristics. This may not even be a coincidence: the same exact method, started with an initial upper bound that is, say 0.2% off the optimal, would very often fail, illustrating the critical role of good UBs in the search. In this scope, since the UB generation procedure is so critical to the method, should we consider it as part of the exact solution search process ? Finally, most techniques used to help raising LBs or decreasing UBs result from some heuristic design choices. We surely have a well-grounded theory regarding formulation strength, duality, decomposition methods. But when its time to design an efficient branch-cut-and-price algorithm for an intricate CO problem, we must pick between several classes of valid inequalities, separation procedures, and choose which one to use in relation to their computational impact on separation or pricing. These design choices are purely heuristic and experimental, no theory will tell you if a given class of valid inequalities improves your LB sufficiently enough to be worth the extra computational effort that it may induce. Again its all a question of trade-offs and experimentation, with no theorem to help us. So, with this regards, I don't even see a large difference into serious heuristic research, and research on exact methods: one gives you solutions of non-controllable quality in a controllable time, another gives you solutions of controllable quality in a non-controllable time, both are experimental.

Now, having defended metaheuristics, I definitely recognize that there is a very serious problem in the field. Combine the lack of a firm theoretical ground, a line of research that is experimental with all the reproducibility issues that go with it, some fascination for small animals, and publication pressure for researchers... and you get the current situation with a wide majority of absurd papers. Still, looking at the title already helps quite a bit to separate the good grain from the bad one. Finally, part of the responsibility comes from the publishing companies, which actually followed this trend by opening journals dedicated to nature-inspired optimization and "soft" computing to attract papers, generate volume, citations and subscriptions. The citation indices get higher, the universities recognize them, and this gives an incentive to researchers to go or stay in these fields, fostering micro-communities focused on the study of hybrid intelligent water droplets that ride frogs (please don't steal my idea). At this point I unfortunately don't see what else we can do other than simply highlighting these issues again and again. A good news still, the field of deep learning is also strongly experimental and faces similar challenges at an even larger scale... this will perhaps help to leave bats, crocodiles and cockroaches in peace.

Dear Thibaut Vidal,

since you touched on a few points of principle in the discussion, justice requires to discuss.

1. "Finally, UBs result from some heuristic design choices"

If I understood correctly, in order to raise the Lower Bound (LB), I need to use "result from some heuristic design choices". I always believed and believe that the Lower Boundary is a strict proof of the statement OPT(D) >= LB(D) without using any heuristics. Clarify this point, please, maybe I something be wrong to interpret in your phrase. Since you touched on the topic of Lower Bound, I want to ask: Why this topic is almost not paid attention. In my understanding, the search for qualitative Lower Bounds is of great importance for science, since it makes it possible to evaluate heuristic solutions by their degree of closeness to the optimal solution.

However, this is not done as before. Because this is a very difficult problem compared to one or two pages describing a heuristic algorithm. That is why eurity and metaheuristics are especially popular with young researchers. However, there is no science, one bare craft and nothing more. I want to emphasize - now no one will be surprised by the search for heuristic solutions, even if they are very good solutions, which, as you know, are not known in advance to be good solutions.

2. "It gives you the controllable time, the controllable quality in a non-controllable time, both are experimental"

Here you don’t even mention about the search for the Lower Bound, although this may not be such a time consuming procedure.

If it turns out that your found heuristic decision A(D) = LB(D) in this case A(D) is the exact solution without an exhaustive search, that is, by finding a heuristic solution you proved that this solution is already the optimal solution OPT(D). In other words, even at a controlled time you can find the exact solution.

3. I set out some of my suggestions in my question https://www.researchgate.net/post/Should_be_revised_todays_Complexity_Theory . Please give your opinion. Thank you in advance.

Dear all, as a researcher, I love the challenges of exact solutions and approximation algorithms. However, let me disagree about the value of heuristics. In most of practical situations in which a problem must be solved repeatedly and in a very short time, heuristics are the best choice and exact solutions or approximation algorithms (AA) are out of the question. The challenge is to design AAs that are fast enough ...

@Gennady, with regard to your point 1, I think that Thibaut is right.  One of the most popular procedures for computing lower bounds (for minimisation problems) is to formulate the problem as an integer linear program (ILP), and then solve its continuous relaxation.  Since the ILP is often very large (even exponentially large), one usually needs to use dynamic generation of rows (cutting planes) and/or columns (variables). To make this work effectively, one usually has to use subroutines that are of a heuristic nature.  For example, (a) a heuristic for selecting the initial set of rows and columns to include in the LP, (b) heuristics for generating violated cutting planes (commonly called "separation heuristics"), (c) heuristics for generating columns with negative reduced cost (commonly called "pricing heuristics").  Not only that, but if one wants to generate upper bounds as well, then one may well use (d) a heuristic for converting fractional solutions to integral ones (commonly called "rounding heuristics").

A great example of this approach can be found in this paper:

Article Robust Branch-and-Cut-and-Price for the Capacitated Vehicle ...

For an example of the use of a meta-heuristic to generate cutting planes, see this paper:

Article “Separating Capacity Constraints in the CVRP Using Tabu Search”

Dear Adam N. Letchford,

Your phrase "One of the most popular procedures for computing lower bounds (for minimisation problems) is to formulate the problem as an integer linear program (ILP), and then solve its continuous relaxation" claims to be the only approach to search for Lower Bounds. However, we can use other effective solution approaches to search for Lower Bounds, which are much more practical than Linear Programs. For my class of problems, I used the "branch & bound method" to establish the fact LB (D) >= x for a limited time, where x is a given threshold, and this approach worked well. By the way, it is not always possible to reduce the problem to the Linear Model to search for the Lower Bound. Now I want to ask: If the Linear Model is so popular for computing lower bounds, then why is this procedure not used to evaluate heuristic solutions? Now I'm asking again: What we should to do if the problem cannot be described as a linear model? In my opinion, special approaches are needed. I raised this issue a long time ago in the discussion https://www.researchgate.net/post/How_to_evaluate_the_quality_of_metaheuristic_algorithms_without_any_benchmarks

@Gennady, here is my response to your two main points.

1. I did not claim that LP relaxation is the only approach, I said only that it was one of the most popular approaches.  (To see that this is true, just do a search for the phrases "branch-and-cut" and "branch-and-price".) There are of course many other approaches for computing lower bounds (e.g., Lagrangian, surrogate and composite relaxation; dual ascent and dual adjustment; additive bounding; Lagrangian decomposition; state-space relaxation; truncated branch-and-bound). But, my main point (that heuristics can be useful even when computing lower bounds) still stands. For example, even if you apply Lagrangian relaxation, you may need to use a heuristic to find good Lagrangian multipliers. (And dual ascent and dual adjustment can themselves be viewed as heuristics for solving a dual problem.)

2. "It is not always possible to reduce the problem to the Linear Model". That is true, but one can easily construct LP relaxations of nonlinear problems, and even non-convex ones. Nice examples of this include the "branch-and-reduce" approach of Tawarmalani and Sahinidis, and the "reformulation-linearization technique" (RLT) of Sherali and Adams. Moreover, even if LP relaxations turn out to be too weak, one may be able to use other convex relaxations, such as semidefinite programming (SDP) relaxations. Heuristics are useful even in these contexts. (A famous example is the Goemans-Williamson approximation algorithm for the max-cut problem, which begins by solving an SDP to provide an initial upper bound, and then uses a randomized rounding heuristic to compute a lower bound.)

I do however agree with you that many papers on meta-heuristics could be improved substantially if the authors compared their upper bounds with some kind of lower bound.

@Adam N. Letchford,

All your reduced methods (Lagrangian relaxation, and others) are, first of all, strict solutions, which in any case will give a strict result with any Lagrange multipliers,  which may turn out to be good for some source data and not very good for other source data, however strict solutions for this data will eventually be found, only this is a question of the length of time it takes to find this solution. For example, I use the branch and bound method to search for Lower Bounds. Here the main role is played by the "Block of circumcision of unpromising branches of decision tree". This block may work well for some source data and work poorly for other source data, but in both cases a strict result is guaranteed to be found, the only question is the duration of the solution time. In other words, these rigorous methods are above all guaranteed methods. As for heuristic algorithms for finding approximate solutions, there is no guarantee that the approximate solution will be close to the optimal solution after the expiration of a given time limit, even a very long time limit. Here I see the difference.

Dear Gennady Fedulov , I'm not sure I understand what you were trying to say in your last post. The only point that I am trying to make is that heuristics can be embedded within exact algorithms, to good effect. (This is the same point made by Thibaut.)

Let me direct you to some more papers in which heuristic techniques are used very effectively inside an exact algorithm.

First, see this paper by Padberg and Rinaldi:

Article Facet Identification for the Symmetric Traveling Salesman Polytope.

The authors use heuristics to generate cutting planes within an exact branch-and-cut algorithm for the TSP. These heuristics were the key to helping them solve a real-life instance with over 2000 cities.

Second, see this paper by Gu, Nemhauser and Savelsbergh:

Article Lifted Cover Inequalities for 0-1 Integer Programs: Computation

The authors use heuristics to generate cutting planes within an exact branch-and-cut algorithm for general 0-1 linear programs.

Third, see this one by Erlenkotter:

https://pubsonline.informs.org/doi/abs/10.1287/opre.26.6.992?journalCode=opre

This one is concerned with a facility location problem. His lower-bounding procedures, called "dual ascent" and "dual adjustment", are heuristic in nature. (In fact, dual ascent is a constructive heuristic, and dual adjustment is a local search heuristic.) These lower-bounding procedures are embedded within an exact algorithm, which turns out to be remarkably effective.

I can supply other examples if needed.

Hope that helps.

Adam.

Dear Gennady Fedulov ;

As I know, despite the performance of the exact algorithm can be understanding easily, understanding the behavior of meta-heuristic algorithms is so difficult. However, as I know, there are some remarkable papers and efforts about this difficult subject such as the following:

Watson, J. P., Barbulescu, L., Whitley, L. D., & Howe, A. E. (2002). Contrasting structured and random permutation flow-shop scheduling problems: search-space topology and algorithm performance. INFORMS Journal on Computing, 14(2), 98-123.

Watson, J. P., Beck, J. C., Howe, A. E., & Whitley, L. D. (2003). Problem difficulty for tabu search in job-shop scheduling. Artificial Intelligence, 143(2), 189-217.

All the answers are great

Let me pour some water into the wine. Have you ever solved a shortest path problem? Yes. And you know, it is polynomially solvable. But what happens if you are a public transport company and you need to answer passenger information requests in real time (did you ever ask that yourself)? That is probably done with a shortest path algorithm. Now, I do not only want to have real-time information for going from an origin to a destination in my city; may be I want to go from an origin in one city to a destination in another city and we even need to care about interoperability of more than one information system of one provider. (Do not tell me that Google can do that; of course there are (public transport, information service etc.) providers who can do that. But why and how?) How long do you want to wait for an answer? How good is your own Dijkstra implementation to do the job? Ahh, now we even need heuristics or preprocessing and logical observations to solve a well-known shortest path problem. I am not fighting for any metaphor-based metaheuristic; many, may be even most of them are crab (oh, is that a new one? I do not know;-) - but man, some of them are really good. I want to open up your eyes for a bit of a different view on real problems that we find in our everday life. Some of them are even easier than knapsack. I know that the story is somewhat different if you talk to practitioners. I remember a talk that I gave on passenger information in 1996 in Washington DC (yes, more than 20 years ago). There was a guy from the federal highway administration who really said: "Why should I care? We are a democracy,; if we need a highway, we vote for it:" Ok, I probably cannot reach that guy due to his ignorance. But here, you might follow me in not being ignorant. There may be reasons (may be not for the case that you mentioned but for others). Think about options. And again: do not blame everything and everybody across-the-board. There may be a reason.

Dear all,

Sorry to disagree, Mohamed. Being not a fan of obscure metaheuristics with funny names (I like Thibaut's), these methods are sometimes required for two more reasons:

1. A company does not want to spend thousands of dollars for an optimization package that will be dedicated to this one problem.

2. Even if a problem does not need to be solved every minute, if one wants to discuss different solutions to a problem with a manager, one better has solutions in less time that it takes having a small coffee. Otherwise, it is impossible to attract the attention of a busy businessman

:-)

Cheers,

Vlad

Adding to Vladimirs answer and using the earlier example from Mohamed:

The block(s) relocation probem and the premarshalling problem are NP-hard problems and current state-of-the-art exact algorithms have difficulties to deal with problem instances of size, say, 10 x 6 (bays with 10 containers wide and six containers high). Now, is a problem instance with up to 60 containers large? Probably not if you consider that a container terminal may have a five digit number of containers stored in the yard. Moreover, the currently largest container vessels carry well over 20000 TEU (twenty foot equivalent units). With this the same question again: Is an instance with 60 containers large? I would call it small. But anyway, we need good heuristics and metaheuristics for these problems. Even more so, if we need to solve them in (almost) real time.

That ties in with some industry experience I've had, for example in the aircraft industry: a very complex mixed-integer program - NP-hard indeed! - is to be solved in order to produce a production schedule of a batch of steel parts, using a machine park the size of a soccer field, and the requirement is that the waiting time for the solution of these optimization problems - before the actual production can start - is "less than a coffee break". I think that is somewhat similar to what Stefan relates.

In this instance we want a "good enough" solution fast, which I am sure many other industries would like, too.

The proposition of meta-heuristics is usually for difficult problems (NP-hard and so on) not for easy problems (for which we can find a polytime algorithm). Therefore, even though the 0/1 knapsack problem looks simple, it is proven to be NP-hard, which means we may have recourse to some meta-heuristic algorithm. However, many problems may look very complex at first sight, but in deep it may turn out to be easy to solve (there exists a polytime algorithm to solve it). It is like we say "Never judge a book by its cover!"

The knapsack problem is pseudo-polynomial - and therefore in most cases extremely easy. You have in general no real motivation to use a metaheuristic.

If there is an easier way you do not have to use metaheuristics all the time