Max Gläser

Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation

  • Max Gläser
  • Marc E. Pfetsch
    • Categories Integer Programming

    This paper investigates linear programming based branch-and-bound using general disjunctions, also known as stabbing planes, for solving integer programs. We derive the first sub-exponential lower bound (in the encoding length \(L\) of the integer program) for the size of a general branch-and-bound tree for a particular class of (compact) integer programs, namely \(2^{\Omega(L^{1/12 -\epsilon})}\) for … Read more

    On the Complexity of Finding Shortest Variable Disjunction Branch-and-Bound Proofs

  • Max Gläser
  • Marc E. Pfetsch
    • Categories Branch and Cut Algorithms Tags , ,

    We investigate the complexity of finding small branch-and-bound trees using variable disjunctions. We first show that it is not possible to approximate the size of a smallest branch-and-bound tree within a factor of 2^(1/5) in time 2^(\delta n) with \delta < 1/5, unless the strong exponential time hypothesis fails. Similarly, for any \varepsilon > 0, … Read more