Skip to main content
29 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 ...
Matteo Fischetti's user avatar
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 ...
Kevin Dalmeijer's 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 ...
LarrySnyder610's 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 ...
Rolf van Lieshout's 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"...
prubin's user avatar
  • 39.3k
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=-...
Marcus Ritt's user avatar
  • 2,725
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 ...
Matteo Fischetti's 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 ...
Marcus Ritt's user avatar
  • 2,725
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 ...
Karmel Shehadeh's 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.
RobPratt's user avatar
  • 32.3k
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 ...
Ryan Cory-Wright's 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 &...
Nikos Kazazakis's 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 ...
RobPratt's user avatar
  • 32.3k
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 ...
Oguz Toragay's user avatar
  • 8,652
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) + ...
RobPratt's user avatar
  • 32.3k
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 ...
Johan Löfberg's 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 ...
TheSimpliFire's user avatar
  • 5,412
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, ...
Mostafa's user avatar
  • 2,104
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 ...
Robert Schwarz's 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}})$.
Johan Löfberg's 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 ...
Ryan Cory-Wright's 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 ...
Thiago Serra's 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 ...
Ingix's 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 ...
RobPratt's user avatar
  • 32.3k
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.
RobPratt's user avatar
  • 32.3k
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 ...
prubin's user avatar
  • 39.3k
5 votes
Accepted

Upper bound on length of solution of linear program

Based on the clarification that we are assuming exact arithmetic, and assuming $m>1,$ I think the bound is likely to be $m\cdot (k + \log_2(m))$ bits ... but the following bears careful checking. ...
prubin's user avatar
  • 39.3k
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&=\...
Thomas Kalinowski's 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$ ...
RobPratt's user avatar
  • 32.3k
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 ...
prubin's user avatar
  • 39.3k

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