9

The number of lazy constraints that have to be used, depends on the algorithm that is used. I will discuss two algorithms: The cutting-plane method: solve the problem to optimality for a subset of constraints. If any lazy constraints are violated, add some of the violated constraints and solve again. Stop when the solution satisfies all lazy constraints. ...


9

I'm looking at the algorithm as it's described in Hochbaum (1982), which works like this: Suppose we have enumerated all $2^n-1$ subsets of the customers. Subset $P_m$ has cost $$C_m = \min_{j\in J} \left(\sum_{i\in P_m} c_{ij} + f_j\right),$$ i.e., the fixed plus transportation cost if we choose the best facility for the set $P_m$ of customers. At each ...


8

Only the EOQB approximation (approximation 2) has a fixed worst-case error bound. Zheng (1992) proved an error bound of $\frac18$, and Axsäter (1996) proved a stronger bound of $(\sqrt{5}-2)/2 \approx 0.118$, which is tight. The EOQ+SS approximation (approximation 1) does not have a fixed worst-case error bound; for any $m$, we can find a problem instance ...


8

To my knowledge, there is yet no known constant worst-case error bound $\eta$ for farthest insertion nor a proof that no constant bound exists. The results you mention here require symmetric TSP instances with costs that satisfy the triangle inequality, if I am not mistaken. Nearest and cheapest insertion benefit from the fact that it can be shown that ...


5

If the problem you are solving is in $P$, I guess you can construct a branch-and-bound algorithm that only produces a polynomial number of nodes, since you can use your polynomial time algorithm to make a perfect prediction which branch to explore first, and produce perfect bounds that allow you to prune away every node in the tree except the ones that lead ...


5

Unless you use the ellipsoid method, it is very difficult to find a bound on the number of constraints that need to be generated. A recent review paper on cutting planes mentions only a single paper that develops a polynomial cutting plane algorithm, namely Chandrasekaran, Végh and Vempala (2016), who propose a tailored cutting plane approach for the minimum-...


4

I refer you to this question in which I mentioned some of the related papers investigated the performance of the Branch-and-Bound method by estimating the size of the BB tree. The old paper1 by Lai et al. investigated the performance of the parallel BB in which several nodes with least lower bounds are expanded simultaneously. In addition Lobjois et al. in ...


4

While these equations have many interpretations in OR (e.g. robust optimization), in this case I like to understand what happens here using a Game Theory perspective. These two equations can be interpreted as a Stackelberg game, sometimes referred two as leader follower games. Consider a two player zero sum game, where player 1 has to pick an element from $X$...


2

Unfortunately the answer is that we can't know a priori how many nodes we'll have to explore, at least as far as we know today. Because the problem is NP-Hard (assuming we resort to BnB because we have to), determining how many nodes we will explore is as hard as solving the problem itself. This is unlikely to change in the future because it's intrinsically ...


2

The question is still open and interesting. In my contribution to IPCO-2, Pittsburgh, 1992, I provided a family of examples of a Euclidean instance with a worst case ratio approaching $2.43$ and a non-Euclidean one with ratio approaching $6.5$. An easy example of a Euclidean instance with a bad Farthest Insertion result is constructed by considering an ...


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