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
329 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 (...
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 ...
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 ...
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 ...
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 ...
314 views

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 ...
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+...
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 ...