Questions tagged [bounds]
For questions about obtaining upper or lower bounds for certain values, usually for an optimization objective.
12
questions
2
votes
2answers
130 views
How to use tight upper and lower bounds to get to the optimal value via branch and bound?
I have algorithms that get me a tight upper (UB) and lower (LB) bound to a maximization binary integer program (a routing problem). My formulation is non-compact and requires the addition of sub-tour ...
1
vote
0answers
58 views
Ways to improve lower bounds while solving MIPs
What are the ways to improve lower bounds while solving a minimization problem (MILP)?
10
votes
2answers
130 views
How to exploit known solution in MILP
I have an MILP model to which I get an integer feasible solution as a result of a heuristic search. In this particular example, the initial solution turns out to be the optimal solution, which I prove ...
7
votes
1answer
62 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
128 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 ...
17
votes
3answers
627 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
331 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+...
23
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 ...
16
votes
1answer
831 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})$
Conjecturally the expanded partial sums of the Möbius transform of the Harmonic numbers have two out of three properties in ...
20
votes
5answers
266 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
295 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 ...
25
votes
3answers
303 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 (...
