Do you >have< to define the upper and lower bound? (context: traveling salesman)
If you want to compute X (whatever X is), then you just need to compute&nbsp;X, and whatever intermediate results are required by your method for computing&nbsp;X.  If your method doesn't need upper and lower bounds, there's no need to compute them.

The point of upper and lower bounds is that they're usually easier to compute than the actual answer, and they may be enough to answer your question. For example, as a typical student, you don't need to know the exact price of a helicopter to know that you can't afford one: helicopters surely cost at least \$100,000 and you don't have \$100000. Conversely, if you're a millionaire, you don't need to know the exact price of a chocolate bar to know that you can afford to buy one: surely a chocolate bar doesn't cost more than \$100 and you definitely have \$100.


  Can we say for sure that the cost of the optimal route is a number in the interval [between the lower bound and upper bound]?


Yes. That's what "upper bound" and "lower bound" mean.


  Is it possible to find a route whose cost is not within the interval?


Again, by definition of "lower bound" and "optimal", no route can be shorter than any lower bound on the length of an optimal route. Depending on what upper bound you use, it might be possible to find a route that is longer than an upper bound on the optimal route. For example, on upper bound on the length of a TSP route is to say that, since the optimal route must leave each vertex exactly once, the total length can't be longer than the sum of the longest edge from each vertex. But, if you think about it, that's actually an upper bound on any route, whether the route is optimal or not. So it's not possible to exceed this upper bound. However, it's possible that you could come up with a smarter upper bound such that the optimal route is definitely not longer than your bound, but suboptimal routes might be.