split disjunctions

Improved strategies for branching on general disjunctions

  • Gérard Cornuéjols
  • Leo Liberti
  • Giacomo Nannicini
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms Tags , ,

    Within the context of solving Mixed-Integer Linear Programs by a Branch-and-Cut algorithm, we propose a new strategy for branching. Computational experiments show that, on the majority of our test instances, this approach enumerates fewer nodes than traditional branching. On average, on instances that contain both integer and continuous variables the number of nodes in the … Read more

    Column basis reduction and decomposable knapsack problems

  • Bala Krishnamoorthy
  • Gabor Pataki
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    We propose a very simple preconditioning method for integer programming feasibility problems: replacing the problem b’   ≤   Ax   ≤   b,   x ∈ Zn with b’   ≤   (AU)y   ≤   b,   y ∈ Zn, where U is a unimodular matrix computed via basis reduction, to make the … Read more