# Questions tagged [bounds]

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

12 questions
Filter by
Sorted by
Tagged with
832 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 ...
134 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 ...
60 views

### Ways to improve lower bounds while solving MIPs

What are the ways to improve lower bounds while solving a minimization problem (MILP)?
131 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 ...
63 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 ...
134 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 ...
638 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 ...
332 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+...
271 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 ...
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 ...