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
17 votes
1 answer
5k 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 ...
Albert Schrotenboer's user avatar
15 votes
2 answers
185 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, ...
dourouc05's user avatar
  • 998
11 votes
4 answers
403 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 ...
ydubey7's user avatar
  • 579
11 votes
2 answers
391 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 ...
LarrySnyder610's user avatar
10 votes
1 answer
192 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(\...
ydubey7's user avatar
  • 579
5 votes
1 answer
161 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 ...
LarrySnyder610's user avatar
3 votes
2 answers
87 views

Coarse modelling - is there a name for this?

I'd like to produce a model that uses very coarse inputs and produces similarly coarse outputs. For example, if I were estimating personal sources of wealth I might say that in a given year: ...
P. Hopkinson's user avatar
-3 votes
2 answers
2k 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 <...
Cindy Paola Guzman Lascano's user avatar