The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [bounds]

For questions about obtaining upper or lower bounds for certain values, usually for an optimization objective.

Filter by
Sorted by
Tagged with
11
votes
4answers
296 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 ...
11
votes
1answer
381 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
220 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 ...
14
votes
1answer
161 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
197 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 (...