Tag Info

Hot answers tagged bounds

26

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 very large “unnatural” face where your search is trapped for a long while. Essentially you lose the objective function grip, and do not gain anything. Let me ...

19

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 formulation and a route formulation for a vehicle routing problem (minimization). Typically, the folllowing argument can be made: Given (fractional) values for the route ...

15

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 problem (UFLP), the most common Lagrangian approach relaxes the assignment constraints ($\sum_j y_{ij} = 1 \ \forall i$), uses the Lagrangian subproblem to calculate ...

15

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 have both an upper bound and a lower bound on the optimal objective value, using a method called reduced cost fixing (see e.g. Atamtürk, Nemhauser & ...

15

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" is in the eye of the beholder. The most obvious criteria for computational comparisons are that they use the same test problems (not selected because they ...

13

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=-1$ at optimality. The sum of remaining variables is bounded by $1-k$ (indeed has to be equal to $1-k$) and since variables with lower indices have higher value ...

12

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 of variables is not really huge) you can declare the LP to be a MIP with no integer variables (or add a fictitious one), start with few randomly-chosen constraints and use lazycallback to add the ...

11

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 than another one. When comparing two different (yet equivalent) formulation for the same problem, I often use three criteria: (1) LP relaxation/tightness, (2) ...

11

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.

11

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 have to explore a different number nodes until finding an optimal solution, and proving its optimality. For concreteness imagine a simple depth $4$ binary search ...

9

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 branching order. I wouldn't explicitly impose an objective constraint/explicitly feed the bound to the solver, because if your relaxations at each node can't ...

9

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 & convergence issues to consider depending on the number that is chosen, so setting smaller bounds might be preferable if we are certain that it's safe from a ...

8

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 optimality, which will make cut generation more aggressive and do some other similar things. Another approach is to explicitly apply reduced-cost fixing to fix ...

7

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 bound to make the lemma more general. In the bound that you proposed the following assumption for the number of nodes must be true: $$|X|\ge 2$$ But in the ...

6

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 make is that writing $2(a+b)$ instead of $3a/2+2b$ means that $T^*(X)$ can be succinctly expressed in terms of the perimeter of a rectangle, as in the case in ...

6

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, on more than one benchmark. Then, the metrics can be: Number of feasible solutions, Number of best found solutions, Number of optimal solutions, Gap to the ...

6

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 the feasible set. I guess this is equivalent to finding the "worst" objective function and could probably be posed as a bilevel problem with LP subproblem.

6

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 bounds by bound-propagation once a feasible solution is available. As an example (assuming you have some bound, otherwise an indefinite problem will be unbounded), ...

5

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 seen by simply setting $n=2$, which reduces the above to $$\frac{3}{2}a + 2b$$ then setting $a=6,b=1$. If we put our 2 points of $X$ into ends of a side of ...

5

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 guarantee. For instance, in max-cut we can construct an LP relaxation which provides a $0.5$ approximation ratio, or an SDP relaxation which provides a $0.878$...

5

Yes, because $\log$ is monotonic, it preserves inequalities. The tightness depends on your other constraints.

5

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}})$.

4

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 stronger than $B$ if every point of $P_A$ is also contained in $P_B$ whereas some points of $P_B$ are not contained in $P_A$. For example, you may prove the first ...

4

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&=\left\lceil h^*\right\rceil \end{align*} we have $h^*\leqslant h\leqslant h^*+1$, hence $$\frac{ah}{2}\leqslant\frac{a(h^*+1)}{2}=\frac{ah^*}{2}+\frac{a}{2},$$ ...

4

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$ that have $p(i,j)\le 0$.

4

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 exploit this idea to solve large TSPs when the edge costs are road distances. The number of pairs is too large to query Google for all of them, so geodetic ...

3

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 the (discrete) newsvendor cost function, $y^*$ is its optimizer, $g^* = g(s^*,S^*)$, and $g(s,S)$ is the expected cost function for the $(s,S)$ problem. In other ...

3

You could try loading the problem through AMPL. AMPL is blazing fast so size won't be an issue, and it has its own presolve, which is very good. I've seen it reduce problems from 100Kx100K to 5Kx5K. The way you would use this would be to use AMPL to produce an .nl file which is a dense format to describe the presolved model. You can then load that .nl file ...

3

You can also submit the solution to the MILP solver. The solver should then use the bound from it automatically. Further, it might use the solution values for various improvement heuristics (e.g. neighborhood searches).

2

Generally I see on the papers, at first comparison according to number of variables and equations, after then experimental performance comparison on test problems.

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