Questions tagged [bounds]
For questions about obtaining upper or lower bounds for certain values, usually for an optimization objective.
6
questions
11
votes
4answers
319 views
Proof of bound on optimal TSP tour length in rectangular region
Lemma 3 in Haimovich and Rinnooy Kan (1985) (Math of OR 10(4):527–542) says:
If $X$ [the set of nodes] is contained in a rectangle with sides $a$ and $b$, then
$$ T^*(X) \le \sqrt{2(n-1)ab} + 2(a+...
20
votes
6answers
1k views
How to compare two different formulations of a problem?
I somewhat know how to compare two MILP formulations of a problem that both use the same set of decision variables (as in the classical MTZ vs DFJ formulations of the TSP). I was wondering how two ...
14
votes
1answer
531 views
Prove that these linear programming problems are bounded by $O(k^{1/2})$
Prove that these linear programming problems are bounded by $O(k^{1/2})$
The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this ...
19
votes
5answers
227 views
Tightness of an LP relaxation without using objective function
How can we measure the tightness of a linear programming relaxation for a mixed integer linear program without using the objective value? I would like to get a measure in terms of the feasible set and ...
15
votes
1answer
183 views
How to get the best bound of large LP problems in CPLEX?
When using the C callable library to solve a large LP, how can I get the best bound after calling the method CPXXlpopt? Does it depend on the algorithm used to ...
22
votes
3answers
202 views
Feeding known lower bounds to solvers
Given an optimization problem that aims at minimizing some objective function, a lower bound that is valid for all optimal solutions, and your solver of choice:
For what theoretical and/or practical (...
