In the absence of benchmark functions, one should collect as many real-world optimization problems as possible and test the efficiency of his/her algorithm with those problems.

A good book in the aforementioned respect is the following:

Floudas, C.A., Pardalos, P.M. "A Collection of Test Problems for Constrained Global Optimization Algorithms", Springer Verlag, 1990.

http://www.springer.com/chemistry/book/978-3-540-53032-9

Dear Athanasios, I thank you for your answer.

I want to explain my question in detail a little more.

Assume, you developed a metaheuristic algorithm (e.g. a genetic

algorithm (GA) ) in order to solve your problem. You use your algorithm to find an approximate solution A(D), where A is your algorithm, D is concrete data of your problem. Assume, you found an approximate solution A (D, t) for a moment t. I want to ask: How close A(D, t) to an optimal solution OPT(D)? But OPT(D) is not known. This problem is very important for understanding the measure of closeness of A(D, t) to OPT(D) as a metric q(t) = 100% * ( A(D, t) - OPT(D) ) / OPT(D) where t is a moment of time. Let's assume you were told: A(D, t) will be accepted if q(t) will be not more than 5%. If appears that q(t)

In my humble opinion, the measure of closeness you are referring to, is relative to two things:

1. The degree of precision and/or accuracy of the solutions derived from the meta-heuristic under test.

2. The underlying physics of the real-world optimization problem to be solved in relation to both the precision and accuracy of the derived solutions.

In view of the above, you should read the following excellent paper:

Marcio Schwaab, Evaristo Chalbaud Biscaia, Jr., José Luiz Monteiro, José Carlos Pinto

"Nonlinear parameter estimation through particle swarm optimization"

Chemical Engineering Science, Volume 63, Issue 6, March 2008, Pages 1542–1552.

http://www.sciencedirect.com/science/article/pii/S0009250907008755

It seems to me that what you are asking is actually about approximation algorithms. Briefly, an approximation algorithm is a heuristic with a performance guarantee.

For example, I am not sure if you are familiar with Christofides's heuristic [1] for the TSP. The idea is to construct a minimum spanning tree on all nodes, then find a minimum cost match among all vertices of odd degree, and finally do an Eulerian tour over the union of the match and the tree. It has been proven that the solution has to be within 1.5 * OPT(D) (i.e. A(D)

I agree with Athanasios Kakalis.

if you cannot access to benchmarks you cannot compare your results with other authors. Therefore, the only why to evaluate the "performance" of your approach is to consider a real problem and to solve it with your approach. Of course, to conclude that your approach is "good" you should also implement/adapt other algorithms previously proposed to this problem to see whether or not your approach obtain the best results.

I want to underline again: You try to solve your individual (concrete) problem for your individual (concrete) data D. I want to ask: How close your approximate solution A(D) to an optimal solution OPT(D) ? Assume, that you found A(D1) = 120 for the data D1 and you was said that OPT(D) = 100. Then the measure of closeness q = 100% *

(120 - 100) / 100 = 20%. Assume now, that you found A(D2) = 220 for the other data D2 but OPT(D2) is not known. I want to ask now: What is q% for A(D2)? What do you will say? OK, assume you used the other approximation algorithms in order to solve your problem. These algorithms produced approximate solutions as A1(D2), A2

(D2), A3(D2), ... etc. Assume that your solution is the best one , i.e. A(D) = min{A(D), A1(D2), A2(D2), .A3(D2), ... etc}. I want to ask again: Is A(D) a good solution? Can you prove to me that your solution A(D) is the good solution? In conclusion, I want to

formulate the following problem: Find such value p (within a given time limit) that q% would be not more than p% (i.e. q%

"Find such value p (within a given time limit) that q% would be not more than p% (i.e. q%

Dear Mihai Banciu,

you are right, the smaller p is, the better your approximation

algorithm is. Goal is to find minimal value for p. I didn't want to force

events before. But now time came. I want to cite my text from

question "Compare the complexity of metaheuristic algorithms"

where I gave my comment.

= q, LB(D)

Hello Gennady,

One of my graduate school professors used to say that Operations Research is the science of finding best lower bounds, so what you are saying is indeed a fundamental idea, which has been around since the 1950s (see the seminal work of Dantzig, Wolfe, Fulkerson, and later Gomory on cutting planes for integer programming). I guess that what the discussion comes down to is the theoretical versus empirical (observed) performances of your proposed algorithm and whether you can say something definitive about said performance in either setting.

From a theoretical point of view, there is a lot of work that has been done in the theory of approximation algorithms specifically on proving that for certain approximation algorithms geared to solving certain problems p cannot be improved upon (that is, it's the smallest it can be). In that case, p is called a "sharp (or tight) bound" for the algorithm. So, if you are interested in this, you can start thinking as to how you'd go about proving that your algorithm can be no worse than x% from the optimal solution, regardless of what instance you are trying to solve.

From an empirical point of view, things are not as clear cut. For once, you necessarily depend on a sample to do your analysis, and inference based on samples comes with usual caveats: sample size issues, biases, etc. Everything that Athanasios says above would apply.

Hello Mihai,

Now I will try to answer your questions.

Any approximate solution A(D) is an Upper Bound of objective

function, i.e. OPT(D)

I want to answer questions of Raul Banos.

Question 1: "if you cannot access to benchmarks you cannot compare

your results with other authors"

Answer 1: I don't consider a problem of comparing my results with

other authors. OK, if you insist, assume my result are worse than the

best result A(D) of the other authors. So, let A (D) = min{A1(D),

A2(D), ... An(D)}, where A1(D) is my result and A2(D), ... An(D) are

results of other authors. I want to ask: Is A(D) a good solution? From

my point of view, the best solution doesn't mean to be good.

Question 2: "Therefore, the only why to evaluate the "performance" of

your approach is to consider a real problem ..."

Answer 2: So, let we consider a combinatorial problem P. Assume

there are n benchmarks as real-life instances D1, D2, ... Dn. Assume,

you proposed an approximation algorithm 'A' in order to solve P. Let

A(D1), A(D2), ... A(Dn) will be approximate aolutions for D1, ... Dn.

Assume that these solutions are near-optimal solutions. I want to ask:

Is 'A' a good algorithm? Assume you say to me: 'A' is the good

algorithm since 'A' produced near-optimal solutions for real-life

instances. OK, assume I will use the algorithm 'A' in order to solve P

for my data D. Let A(D) produced an approximate solution A(D). I

want to ask: Is A(D) a good solution? How close A(D) to an optimal

solution OPT(D) for my data D? You can say to me now: we know

nothing about "how close A(D) to OPT(D)" but A(D) is the good

solution since 'A' produced near-optimal solutions for benchmarks

D1, ... Dn. But I will not agree with you. What do you say if I propose

an algorithm B that will get the results B(D) < A(D) for all my test

data D within a given Time Limit. I want to underline: a Time Limit

factor can strongly influence to A(D). I don't know, maybe I'm wrong.

Question 3: " ... and to solve it with your approach"

Answer 3. This approach is not my idea. I didn't tell anything new.

Until u or someone else design another algorithm B "that will get the results B(D) < A(D) for all your test data D", the algorithm Awill be considered as best for problem P, as per the descriptions u told. And there is no standard measure available by which u can say how good ur solution is if the optimum results for the instances are not known. But researchers follow the strategy, which u mentioned here. Til now this is the best.... as it has produced for best thing for known results... and for unknown they will simply tell that that is the best solution of that instance, but they will not tell how good that solution is as the optimum is unknown.

I want to answer question of Anindya Pal.

Question. "Until your algorithm B "that will get the results

B(D) < A(D) for all your test data D", the algorithm A will be

considered as best for problem P, as per the descriptions you told."

Answer. You want to claim that A(D) is the best solution since there

are not found a better solution yet. I want to confirm my opinion that I

expressed before: "From my point of view, the best solution doesn't

mean to be good". In my view, finding an approximate solution A(D)

is not self-goal. OK, let us consider the following hypothetical

situation. Assume, I asked you to solve my problem P. You found a

solution A(D) and want to offer me. Now I'm asking you: How is good

A(D)? You say me: my solution A(D) is the best at the moment, since

I didn't find a better solution yet. But I will be satisfied with your

answer: there are uncertainty exists. I say to you: please, I will take

your solution if you prove me that at least the metric

q = 100% * ( A(D) - OPT(D) ) / OPT(D)

Hello Gennady,

What you are writing above has been done for many years in the integer programming research community. The "p%" metric is simply the so-called "relaxation gap". If you examine the logs from any of the mainstream MILP solvers (e.g. CPLEX, Gurobi, GLPK) you will notice that this gap is reported, usually as the last column of the output. Moreover, there are IDEs for optimization (e.g. OPL Studio from IBM-CPLEX) which have visual tools that track the evolution of the search process exactly how you mention: you have a plot of the lower bound that is monotonically increasing and a plot of the upper bound that is stepwise decreasing, eventually converging. That's when you get the optimal answer OPT(D).

In this area of research, there are usually two main directions geared toward raising LB(D):

1. Improve the quality of the formulation of the mathematical program, so that the initial LP relaxation is as close to the optimal solution as possible (this is called finding a "sharp" formulation), or

2. Adding valid inequalities in a branch-and-bound scheme that chop off fractional points of the polyhedron and thus forcing a new value for the relaxation (this adaptation of the branch-and-bound is called a branch-and-cut scheme).

To answer your question, "why don't more people do research in finding better lower bounds?" Well, consider that a lower bound is a relaxation of the original problem, which means that some constraints are broken, which means that your solution is not feasible. If you do not work in academia, explain to your boss that you found a solution for him, but the solution will not work if implemented :) On the other hand, an upper bound is in fact a feasible solution, so even if the answer is wrong, at least that answer could be implemented.

Example: network design. You have found that the lower bound is 1.5, with arc(1,2) = 0.7, arc(2,3) = 0.5 and arc(1,3) = 0.3. Can you really say "Hey, let's build half a road from city 2 to city 3"? Of course not. You're really looking for arc(1,2) = arc(2,3) = 1, solution is 2, all cities are connected. BUT, you could have said "let's connect all these cities and pay 3 units".

I am attaching a screenshot from a cplex output. Notice that p% metric at the right.

Finally, one note about your formula: you say that p = (A - LB) / LB, whereas in the screenshot it is actually (A - LB) / A. The reason for that is a trivial lower bound is 0, which would make your formula infinity, and thus not saying anything about the quality of A.

Hello Gennady,

I want to say few points in respect to ur answer. First thing is whatever u have mentioned , that's basically the definition of approximate algorithm. we call it eps-approximation, where the value of eps is % or whatever the value u have mentioned. Yeah u can design some algorithm which will consider this parameter and try to lower it and finally decalre that this algorithm is eps approximate algorithm, guranteed. But the main problem of this approach is for most of NP-hard or NP-complete problems, OPT(D) for lot of instances including benchmark instances are not known. Then what will u do? In that case people try to achive til now best known result.

Hello Mihai,

Now I will try to answer your questions.

Question 1.

"To answer your question, "why don't more people do research in

finding better lower bounds?" Well, consider that a lower bound is a

relaxation of the original problem, which means that some constraints

are broken, which means that your solution is not feasible. If you do

not work in academia, explain to your boss that you found a solution

for him, but the solution will not work if implemented :) On the other

hand, an upper bound is in fact a feasible solution, so even if the

answer is wrong, at least that answer could be implemented."

Answer 1.

Assume, we want to solve an optimization problem P "to minimum".

Let a metaheuristic algorithm 'A' produced an approximate solution

A(D), D is the Data of P. Let A(D) is the best of solutions A1(D), A2

(D), ... An(D), where A1, ... An are known approximation algorithms

you used to compare your algorithm 'A', i.e. A(D) = min{A(D), A1

(D), A2(D), ... An(D)}. Question is: How close is A(D) to an optimal

solution OPT(D)? Is A(D) a good solution? From my point of view,

the best solution doesn't mean to be good. The best solution A(D)

doesn't mean that there is no better solution B(D) < A(D).

What is a LB-algorithm? The LB-algorithm is a SEVERE algorithm in

order to produce a SEVERE LOWER BOUND LB(D). It means that

there DOESN'T EXIST feasible solutions with x < LB(D), where x is a

value of objective function of P. A negative result of algorithm LB

for value x will prove to us that "DOESN'T EXIST feasible solutions

with x". The goal is not to solve P in order to get a feasible solution

for value x, but the goal is to get a NEGATIVE RESULT for x. Thus,

you use the LB-algorithm in order to get the NEGATIVE RESULT for

x < LB(D). Here I don't propose any concrete procedure to get LB

(D). Each researcher must choose own LB-algorithm to get LB(D).

I don't speak that my "lower bound is a relaxation of the original

problem, which means that some constraints are broken, which means

that your solution is not feasible." (your phrase). I don't use the LP-

approach (Linear Programming approach) to find lower and upper

bounds. The LP-approach is absolutely impractical for my List of

Models http://fedulov.ge/BPClass.aspx (see attachment Results.doc as a part of Dataset on ResearchGate). Please, don't hesitate to click the link http://www.fedulov.ge to solve these models for your data. Currently, this site is hosted by a well-known company "AccuWebHosting" (USA, Denver).

Question 2.

Finally, one note about your formula: you say that p = (A - LB) / LB,

whereas in the screenshot it is actually (A - LB) / A. The reason for

that is a trivial lower bound is 0, which would make your formula

infinity, and thus not saying anything about the quality of A.

Answer 2.

OK, in case of LB = 0 we can use only an absolute difference A - LB

to evaluate the quality of A. I want to observe, that same problem will

arise in a formula (A - LB) / A in case of A = LB = 0.

A good paper that gives some answers with respect to the initial question posed in this thread is the following:

http://www.tops-scidac.org/papers/DM_benchmark.pdf

Dear Gennady

I read this discussion completely. However, I think Mihai answers are true. Assume you have a practical problem., and you find a best-known solution from some approximation algorithms. A LB is obtained from an algorithm (such as LR, B&C, etc.). The gap between the best-known and the LB is more than 5%. What do you do? Moreover, this practical problem should be solved every day such as some scheduling or routing problems. What is your idea about this problem?

Dear Hossein,

I thank you for returning to this very important topic.

Please have a look at the discussions:

1. Is the area of metaheuristics moving away from scientific rigor? https://www.researchgate.net/post/Is_the_area_of_metaheuristics_moving_away_from_scientific_rigor

2. What are the (near) universal components of metaheuristics and what are the key transcendant strategies to improve them? https://www.researchgate.net/post/What_are_the_near_universal_components_of_metaheuristics_and_what_are_the_key_transcendant_strategies_to_improve_them

In these discussions I expressed my point of view on your question. Please read my answers. I'd be glad to get any comments from you.

Thank you again

Dear Gennady,

I read the mentioned topic and your comments about them. However, I can not find my answers. I want to know what do you do in the situation which described in my previous comment?

Dear Hossein,

If I have understood you correctly, you want to get fast LB, is not ? If you will be use the Branch & Bound method then you can get a LB within a given time limit T: the more T the more can be LB. If your "a best-known solution" A(D) gives p = (A(D) - LB(D) ) / LB(D) >= 5% it doesn't mean that A(D) is not optimal solution OPT(D). Please, send me your more detailed question to understand you more correctly. I very apologize for my asking. I'm ready to answer on any your question.

IMHO, in some practical problem such as scheduling, production planning, routing etc., the time is so important. Therefore, the researchers want to obtain a feasible answer in a reasonable time. In some cases, the time is less than 24 hours. Moreover, the size of these problems is large. Hence, the researchers propose the approximation algorithm to the problems. I ask you a question with this circumstance. What is your idea in these cases? I know, if a good LB can be available in a reasonable time, the researches will achieve to good results.

A limit time T can be shared to two parts. T1 = a * T and T2 = b * T, where 0

The answer is right. I know the LB is more important the UP to claim about optimality. But, some researchers like me in my first researches, did not consider the LB to check the performance of the UB methods. How many methods do you know to achieve a LB? I know the following methods:

1) Linear relaxation

2) Lagrangian relaxation

3) Using pre-processing and valid inequalities

4) Cutting plane

5) Dual methods

If I understand the question correctly, it is how can we measure the quality of a solution using a heuristic algorithm with respect to the unknown optimal solution.

Using the knowledge of LB (it means we are interested in minimization) will force you to focus on global optimal solutions. However, there are possibilities that your algorithm may stuck in local solutions as well. So how will u know that even though the algorithm gave you a solution far away from the LB, but obtains local solution?

It is not possible to know, our solution is a global solution or up to what level it away from it unless and otherwise we have global solution..

Standard deviations and similar function can show precession not accuracy 

I suggest referring section seven of the following paper:

https://www.researchgate.net/publication/344324283_Sea_Lion_Optimization_Algorithm_for_Solving_the_Maximum_Flow_Problem

Dear Nidhal El-omari El-Omari,

I thank you for your interest in this thread, but you did not understand the main goal of this thread is to find effective lower LB(D) bounds for the unknown optimal solution OPT(D). Heuristics and metaheuristics do not look for lower bounds. In general, I believe that heuristics and metaheuristics are not a science, they are only a craft, they are only an engineering approach.

Please have a look at the:

https://www.researchgate.net/post/Why_is_RG-of_all_places-a_haven_for_metaheuristics Why is RG - of all places - a haven for metaheuristics?

https://www.researchgate.net/post/Metaheuristics_and_the_Emperors_new_clothes-why_do_I_care_and_worry Metaheuristics and the Emperor's new clothes - why do I care, and worry?

https://www.researchgate.net/post/Metaheuristics_for_the_simplest_combinatorial_problems-why Metaheuristics for the simplest combinatorial problems - why??