Hot answers tagged

27 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 ...
user avatar
19 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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"...
user avatar
  • 31.1k
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=-...
user avatar
  • 2,685
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 ...
user avatar
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 ...
user avatar
  • 2,685
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 ...
user avatar
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.
user avatar
  • 22.7k
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 ...
user avatar
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 &...
user avatar
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 ...
user avatar
  • 22.7k
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 ...
user avatar
  • 8,350
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) + ...
user avatar
  • 22.7k
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 ...
user avatar
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 ...
user avatar
  • 5,191
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, ...
user avatar
  • 2,054
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 ...
user avatar
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}})$.
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 22.7k
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.
user avatar
  • 22.7k
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 ...
user avatar
  • 31.1k
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&=\...
user avatar
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$ ...
user avatar
  • 22.7k
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 ...
user avatar
  • 31.1k
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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible