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
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 ...
15
votes
2
answers
186
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, ...
11
votes
4
answers
411
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 ...
11
votes
2
answers
395
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 ...
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(\...
5
votes
1
answer
162
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 ...
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:
...
-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
<...