# 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
Filter by
Sorted by
Tagged with
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 ...
• 1,859
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, ...
• 998
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 ...
• 579
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 ...
• 13.1k
192 views

• 13.1k