Questions tagged [error-bounds]

For questions related to empirical or computational bounds that quantify how far the objective function value of a given solution is from the optimal objective function value.

Filter by
Sorted by
Tagged with
-3 votes
2 answers
467 views

No value for uninitialized NumericValue object

I'm working on an optimization model in python with the pyomo library. However I'm getting an error message in python that I cannot seem to understand. The code and error message is below. My code is <...
user avatar
11 votes
4 answers
232 views

Theoretical results on performance of branch-and-bound

Are there any theoretical results on the performance of branch-and-bound, even for a subset of instances of a particular discrete optimization problem? As an example, does there exist a result of ...
user avatar
  • 569
15 votes
2 answers
156 views

Bound on the number of constraints to be generated (lazy constraints)

I am working on a very large optimisation problem. All variables are continuous, the objective is linear and the constraints convex, but I have many such constraints (on the order of $2^n$ — actually, ...
user avatar
  • 938
10 votes
1 answer
166 views

Algorithmic gap for Hochbaum's (greedy) algorithm for (metric) uncapacitated facility location

In Jain et al. (2003)1, at the bottom of page 801, they construct an instance of (metric) uncapacitated facility location for which they claim the greedy (Hochbaum's) algorithm has gap $\Omega\left(\...
user avatar
  • 569
5 votes
1 answer
107 views

Which EOQ-based $(r,Q)$ approximation has a fixed worst-case error bound?

There are two common approximations for the $(r,Q)$ inventory optimization problem that use the EOQ model. It is well known that one of them has a fixed worst-case error bound, but there is confusion ...
user avatar
11 votes
2 answers
234 views

Is there a fixed worst-case error bound for farthest-insertion?

For some insertion-type heuristics for the traveling salesman problem, we have a fixed worst-case error bound of the form: $$\frac{z^H}{z^*} \le \eta,$$ where $z^H$ is the objective value of the ...
user avatar
17 votes
1 answer
2k views

The difference between max-min and min-max

I am solving two-stage optimization problems in the form of $$\max_{x \in X}\min_{y \in Y} f(x,y),$$ where $f(x,y)$ is the solution of a mixed integer linear program (MIP). As the constraints of the ...
user avatar