Questions tagged [bounds]
For questions about obtaining upper or lower bounds for certain values, usually for an optimization objective.
9
questions
7
votes
1answer
56 views
An upper-bound on the value of $S$ in $(s,S)$ policy
I recently have come across a problem which can be categorized as a stochastic optimization. The problem seems simple, but I haven't been able to solve it yet. It has a major impact on algorithm ...
5
votes
1answer
84 views
Solving a variant of multiple knapsack problem/ generalized assignment problem
Consider $m$ knapsack and $n$ items. With each knapsack $j$ associated a capacity $c(j)$ and with each item $i$ associated a profit $p(i,j)$ (that depends on the knapsack, so it's not exactly the ...
16
votes
3answers
542 views
Variable fixing based on a good feasible solution
Suppose you have a combinatorial optimization problem that is formulated as a mixed integer linear program (minimization). The problem size is denoted $n$ and the expected $n$ is around $100$. The ...
11
votes
4answers
327 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
630 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 ...
20
votes
5answers
238 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
212 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 ...
23
votes
3answers
210 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 (...
