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.
8
questions
3
votes
2
answers
84
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:
...
- 203
11
votes
4
answers
297
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 ...
- 762
-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
<...
- 1,865
11
votes
2
answers
359
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 ...
- 5,312
17
votes
1
answer
4k
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 ...
- 2,070
10
votes
1
answer
182
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(\...
- 5,312
15
votes
2
answers
172
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, ...
- 2,285
5
votes
1
answer
136
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 ...
- 12.9k