fathoming rules

Branch-and-bound for biobjective mixed-integer linear programming

  • Nathan Adelgren
  • Akshay Gupte
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Multi-Criteria Optimization Tags , , , ,

    We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the … Read more

    A branch-and-bound algorithm for biobjective mixed-integer programs

  • Pietro Belotti
  • Banu Soylu
  • Margaret Wiecek
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization Tags , , ,

    We propose a branch-and-bound (BB) algorithm for biobjective mixed-integer linear programs (BOMILPs). Our approach makes no assumption on the type of problem and we prove that it returns all Pareto points of a BOMILP. We discuss two techniques upon which the BB is based: fathoming rules to eliminate those subproblems that are guaranteed not to … Read more