Column basis reduction, and decomposable knapsack problems
Bala Krishnamoorthy, Gábor Pataki · arXiv (Cornell University) · 2008
We propose a very simple preconditioning method for integer programming feasibility problems: replacing the problem b' 0$ and $r$ integral vectors, and $M$ a large integer. If the parameters are suitably chosen in DKPs, we prove 1) hardness results for these problems, when branch-and-bound branching on individual variables is applied; 2) that they are easy, if one branches on the constraint $px$ instead; and 3) that branching on the last few variables in either the rangespace- or the AHL-reformulations is equivalent to branching on $px$ in the original problem. We also provide recipes to generate such instances. Our computational study confirms that the behavior of the studied instances in practice is as predicted by the theoretical results.