Hi, except in the case your function has a particular property (quadratic, ...) it is not possible to compute its lower bound. You can simply run different global optimuzation algorithms ( GA, PSO, SA, ...) and analyze the results

Dear Kishore Shaurya,

finding any Lower Bound for an Objective Function in Combinatorial Optimization is very important problem to be resolved. In my opinion, this problem is a million times more important than finding any Approximate Solution by using any Metaheuristic Algorithms or others. I want to observe, that finding any Lower Bound is REAL SCIENCE while finding any Heuristic Solution is ONLY CRAFT. Yes, finding a Lower Bound is not easy problem to solve immediately but you should strive to find this Bound in any way.

Dear Richard Epenoy.

I don't agree with your phrase "... it is not possible to compute its lower bound".  As example, any Optimal Solution is the best Lower Bound of Objective Function. Thus, at least we can run Exhaustive Search to find this Bound. But it is not a good idea in practice. As to me, I use the Branch & Bound method for finding a Lower Bound for a problem F >= A within a given Limit Time T1 seconds, where A is a given threshold, F is Objective Function. Solving this problem for T1 seconds, I will get a Lower Bound LB(T1) > A, where A T1 and so on.

Thus, we you can find any Lower Bound always, If you have enough time.

Please have a look at the discussion

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

Finding good lower bounds is tricky, and if you are determined to use metaheuristics you are basically doomed. Why? (a) With a metaheuristic you will never know if you have found an optimal solution to the (primal) Lagrangian relaxation problem for a given multiplier guess. And you really need tp locate global optima for those Lagrangian problems, as you otherwise cannot know that the result is a lower bound on the optimal value of the original problem. Mixing theoretically sound methods (Lagrangian relaxation) with theoretically unsound methods (metaheuristics) does not produce good medicine. :-)

The standard way to compute a lower bound for a minimisation problem is to solve some kind of tractable (preferably convex and continuous) relaxation of the problem.  Such relaxations can be derived in many different ways.  See, e.g., these papers:

Ryoo, H. S. and N. V. Sahinidis, A branch-and-reduce approach to global optimization, Journal of Global Optimization, 8(2), 107-139, 1996.

Tawarmalani, M. and N. V. Sahinidis, A polyhedral branch-and-cut approach to global optimization, Mathematical Programming, Ser. B, 103, 225-249, 2005.

S. Burer & A.N. Letchford (2012) Non-convex mixed-integer nonlinear programming: a survey. Surveys in Oper. Res. and Mgmt. Sci., 17(2), 97-106.

There also exist more specialised methods for the case in which the function is quadratic (or, more generally, a polynomial).

Dear Adam N. Letchford,

now I want to argue a little bit with you about your phrase "The standard way to compute a lower bound for a minimisation problem is to solve some kind of tractable (preferably convex and continuous) relaxation of the problem". My question to you: What do you intend to do if your task does not belong to the class of tractable problems? In my opinion, the vast majority of tasks of combonatorial optimization are not tractable (preferably convex and continuous) to use any relaxation as Linear Programming or others relaxation methods. I believe, currenly, that the method Branch &Bound is more practical method to find a Lower Bound within a given Time Limit.

Dear Gennady,

I'm not sure what you mean.  There is a vast literature (thousands of papers) on tractable relaxations of intractable problems.  I couldn't possibly do a survey here, so I will just refer you to a few textbooks.

http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0471359432.html

http://www.springer.com/us/book/9780792354871

http://www.springer.com/us/book/9781402010316

http://www.springer.com/us/book/9781461407683

http://www.springer.com/us/book/9783319110073

These methods are very informative. Thanks for sharing them. I have another query. If the function is not known in concrete form, for example given an input vector, i pass it through a black box that generates a scalar output. In those cases how should i compute the lower bound for such a black box function which i can only study by collecting its outputs for several inputs. Will branch and bound work even then? Are there papers that do that?

Dear Kishore Shaurya,

if your problem is really given by a blackbox function and you have no information about properties (such as convexity, (Lipschitz-)continuity, differentiablility) I see no way to find a relaxation for the computation of a lower bound.

I have no idea why you would be interested in upper bounds for a minimization problem.

If you know your function is nondifferentiable but convex and subgradients could be determined by the blackbox, a lower bounding model and approximate solutions could be constructed by a bundle method. This would in the convex case be a good substitute for the metaheuristics you used. See e.g. ConicBundle by Christoph Helmberg (TU Chemnitz).

The discussion about Branch&Bound concerned discrete variables - are your variables (inputs to the blackbox function f) integer or continuous ones and furthermore are all of these bounded in finite intervals? You gave no information about that.

Best regards

Ralf

Dear Ralf Gollmer

Inputs to the function are nx1 vectors, each element is bounded in [0,1] and these vary continuously. The output is a single positive integer number. I am not interested in upper bound as you correctly pointed out.

Best regards

Kishore

Dear Kishore Shaurya,

your description of the problem under consideration makes clear, that your function f is neither differentiable nor convex (as long as it is not constant). So the idea of a bundle method is not applicable - and I got no idea how to determine a valid lower bound for it.

A domain decomposition approach like that of BARON for global optimization requires the ability to solve local minimization - but without further knowledge about the function f I see no way of doing that.

With such kind of problem you are really just left with search methods without any guarantee for the solution quality.

If n is small you could just try to evaluate f on a grid over the unit cube to get an idea how f behaves.

Even the search algorithm DIRECT

http://www4.ncsu.edu/~ctk/Finkel_Direct/DirectUserGuide_pdf.pdf

needs Lipschitz continuity, which is not fulfilled by an integer-valued function f with jumps.

Best regards

Ralf