Suppose there is a optimization problem that aims at minimizing an objective function $X$ but we can't develop a mathematical model for minimizing $X$. However, there are two objective functions $Y$ and $Z$, where $Y$ and $Z$ are a lower bound and an upper bound of $X$ respectively. We can develop a mathematical model for minimizing either $Y$ or $Z$. Then $X$ is calculated for the output solution hoping that the solution with $Y_\min$ (or $Z_\min$) will have an $X$ value with a good deviation from $X_\min$ (which is unknown).

Is there any theoretical theory that states which is better: to minimize w.r.t $Y$ (the lower bound) or w.r.t $Z$ (the upper bound) if we can't minimize w.r.t to $X$?

  • 1
    $\begingroup$ Does your procedure for minimizing $Z$ always product a feasible solution? Having an upper or lower bound on the optimal objective value isn't much use by itself if you actually need a feasible solution. $\endgroup$ Commented Feb 20, 2021 at 19:14

1 Answer 1


Both might provide useful approximations, but minimizing the underestimator $Y$ is a relaxation in the sense that an optimal solution yields a lower bound on the minimum $X$. Bill Cook and his team exploit this idea to solve large TSPs when the edge costs are road distances. The number of pairs is too large to query Google for all of them, so geodetic distance is used as a lower bound, and only the edges that appear in a solution are actually queried. This approach (which you can think of as Benders decomposition with optimality cuts only) can take several rounds but reduces the overall number queries substantially while still yielding an optimal tour with respect to road distances. See http://www.math.uwaterloo.ca/tsp/uk/index.html

If you were maximizing $X$ instead, the overestimator $Z$ would provide a relaxation.


Your Answer

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

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