28
votes
Feeding known lower bounds to solvers
Interesting topic (the question was raised several times by my students as well).
My short answer is that adding the lower bound through a cut seems a good idea at first glance, but it creates a ...
- 1,656
20
votes
Accepted
How to compare two different formulations of a problem?
Even if the decision variables differ, you may still be able to prove that one of the formulations is stronger than the other by introducing an appropriate mapping.
Take for example a flow ...
- 6,063
15
votes
Variable fixing based on a good feasible solution
A similar idea as suggested by @ RolfvanLieshout uses Lagrangian duals instead of LP duals, in a Lagrangian-based branch-and-bound scheme. For example, in the uncapacitated fixed-charge location ...
- 13.1k
15
votes
Accepted
Variable fixing based on a good feasible solution
As far as I know, it is not possible to fix any variables solely based on a feasible solution without compromising the exactness of your solution method. However, variable fixing is possible when you ...
- 2,305
15
votes
How to compare two different formulations of a problem?
I'm not sure there is a single, definitive best way to compare models, and if there is I likely have never seen it applied. I lean toward computational comparisons if properly done, but "properly done"...
- 37.9k
13
votes
Accepted
Prove that these linear programming problems are bounded by $O(k^{1/2})$
Your linear program is similar to a mathematical formulation of a bounded Knapsack problem and has a similar linear relaxation.
First note that $x_1$ is only restricted by $x_1\geq -1$ and thus $x_1=-...
- 2,705
12
votes
Accepted
How to get the best bound of large LP problems in CPLEX?
One option I think is to use CPXbaropt (barrier method) that produces intermediate dual (lower, for minimization) bounds.
If you are brave enough (and the number ...
- 1,656
12
votes
Feeding known lower bounds to solvers
Branch-and-bound solvers often use node lower bounds to select the next node to process, e.g. in a best-first search. An external lower bound can lead to a different search order, and thus you may ...
- 2,705
11
votes
How to compare two different formulations of a problem?
I agree with most of the comments here; Even if the decision variables are different, you may use proof by construction, for example, with appropriate mapping to prove that a formulation is stronger ...
- 111
11
votes
Tightness of an LP relaxation without using objective function
If the integer feasible set is finite and the LP polyhedron is bounded (a polytope), you could compare the volumes of the integer hull and this polytope.
- 30.5k
10
votes
Feeding known lower bounds to solvers
To add to Marcus's answer: you can use a callback to prune parts of the tree when your external bound proves that this part of the tree does not contain an optimal solution, without affecting the ...
- 1,112
9
votes
Accepted
How do Quadratic Programming solvers handle variables without bounds?
Unless we can derive bounds during presolving, the standard way is to set a default variable range instead (e.g. $\pm1.e16$) so that we can generate the McCormick constraints.
There are numerical &...
- 11.9k
8
votes
Accepted
How to exploit known solution in MILP
Many solvers have an option to control the "emphasis" (feasibility versus optimality) of the tree search. If you suspect that your initial solution is already optimal, set this option to emphasize ...
- 30.5k
7
votes
Proof of bound on optimal TSP tour length in rectangular region
I went over all the math included in the proof and confirmed that your claim which is:
$$\frac{3a}2+2b+\sqrt{2(n-2)ab}\le\sqrt{2(n-1)ab}+2(a+b)$$
is true. But I think they didn't use the tighter ...
- 8,622
7
votes
Accepted
Binary decision variable to indicate whether a continous decision variable is equal to its upper bound
Let $\epsilon > 0$ be a small constant tolerance.
The following linear constraints enforce $y=0 \implies 0 \le x \le T-\epsilon$ and $y=1 \implies x=T$:
$$0(1-y) + Ty \le x \le (T-\epsilon)(1-y) + ...
- 30.5k
6
votes
How do Quadratic Programming solvers handle variables without bounds?
Besides simply adding a large bound (which can cause numerical issues and lead to poor branching) or presolve from constraints involving the unbounded variable, the solver might be able to derive ...
- 1,702
6
votes
Accepted
Proof of bound on optimal TSP tour length in rectangular region
As @OguzToragay has mentioned, writing $\sqrt{2(n-1)ab}$ instead of $\sqrt{2(n-2)ab}$ allows for the trivial case of one point in the Euclidean plane since $|X|\ge1$ in section 2.
The other point to ...
- 5,342
6
votes
How to compare two different formulations of a problem?
I would like to add some criteria for the computational comparison, that I think is appropriate and common. As mentioned, the experiments should be performed on standard benchmarks, and if available, ...
- 2,086
6
votes
Tightness of an LP relaxation without using objective function
If (for small dimensions) it is feasible to enumerate the vertices of the polyhedron of the relaxation, as well as the actual feasible set, one could try to find a vertex with the highest distance to ...
- 2,316
6
votes
Accepted
How to convexify log(convex) function?
You are maximizing a convex quadratic (the monotonic log is irrelevant) so the maximum is attained at the border, i.e. either $0$ or $\min(1,\sqrt{1-\text{constant}})$.
- 1,702
5
votes
Tightness of an LP relaxation without using objective function
Another way of looking at this is to construct randomized-rounding algorithms from both relaxations, and select the relaxation which yields a randomized rounding algorithm with the best approximation ...
- 1,112
5
votes
Tightness of an LP relaxation without using objective function
Let us say that we have two MILP formulations $A$ and $B$ on the same variables, each with the corresponding LP relaxations defining polyhedra $P_A$ and $P_B$, respectively. We say that $A$ is ...
- 671
5
votes
Proof of bound on optimal TSP tour length in rectangular region
The book seems to have left out a few steps. It's important to realize that
$$\frac{3}{2}a + 2b + \sqrt{2(n-2)ab}$$
is not a valid upper bound on the longest tour, even for $n\ge 2$. That can be ...
- 151
5
votes
Accepted
Which is better to minimize w.r.t a lower bound or an upper bound of an objective function?
Both might provide useful approximations, but minimizing the underestimator $Y$ is a relaxation in the sense that an optimal solution yields a lower bound on the minimum $X$. Bill Cook and his team ...
- 30.5k
5
votes
Find an upper bound for an objective function
Yes, because $\log$ is monotonic, it preserves inequalities. The tightness depends on your other constraints.
- 30.5k
5
votes
Accepted
Upper and lower bounds of a variable equal
Unless you turn off the presolve step, CPLEX will eliminate the variables that are locked at zero during presolve. So the answer to your second question is that presolve may take slightly longer (but ...
- 37.9k
4
votes
Proof of bound on optimal TSP tour length in rectangular region
Set
\[f(h)=\frac32a+2b+\frac{ah}{2}+\frac{(n-2)b}{h}.\]
Then $T^*(X)\leqslant f(h)$ for every positive integer $h$. For $n\geqslant 3$ and
\begin{align*}
h^* &= \sqrt{2(n-2)b/a}, & h&=\...
4
votes
Solving a variant of multiple knapsack problem/ generalized assignment problem
It looks like there is no relationship between different knapsacks, so you can solve this exactly as $m$ independent 0-1 knapsack problems. Also, for knapsack $j$, you can eliminate any items $i$ ...
- 30.5k
4
votes
What is an acceptable gap for a lower-bound?
First off, I endorse Mark L. Stone's comment (which should be the answer).
That said, what is considered an acceptable gap is likely to depend not only on the nature (and perhaps dimension) of the ...
- 37.9k
3
votes
An upper-bound on the value of $S$ in $(s,S)$ policy
There is (sort of) such a bound. Zheng and Federgruen (1991) prove that for a single-node system with discrete demands and fixed costs,
$$S^* \le \max\{y \ge y^*|g(y) \le g^*\},$$
where $g(y)$ is ...
- 13.1k
Only top scored, non community-wiki answers of a minimum length are eligible