scaling

Learning To Scale Mixed-Integer Programs

  • Timo Berthold
  • Gregor Hendel
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Optimization Software Design Principles Tags , , , , , ,

    Many practical applications require the solution of numerically challenging linear programs (LPs) and mixed-integer programs (MIPs). Scaling is a widely used preconditioning technique that aims at reducing the error propagation of the involved linear systems, thereby improving the numerical behavior of the dual simplex algorithm and, consequently, LP-based branch-and-bound. A reliable scaling method often makes … Read more

    Solving MIPs via Scaling-based Augmentation

  • Pierre Le Bodic
  • Marc E. Pfetsch
  • Sebastian Pokutta
  • Jeffrey W. Pavelka
    • Categories (Mixed) Integer Linear Programming Tags , ,

    Augmentation methods for mixed-integer (linear) programs are a class of primal solution approaches in which a current iterate is augmented to a better solution or proved optimal. It is well known that the performance of these methods, i.e., number of iterations needed, can theoretically be improved by scaling methods. We extend these results by an … Read more