bound sets

An algorithm for generating Lagrangian bound sets in Multiobjective Integer Programming

  • Lavinia Amorosi
  • Mariagrazia Cairo
  • Paolo Dell’Olmo
  • Serpil Sayin
    • Categories Integer Programming, Multi-Criteria Optimization Tags , , ,

    Lagrangian relaxation is a well-established technique for deriving strong bounds in single-objective discrete optimization. Its generalization to the multiobjective setting is not straightforward, as preserving the multiobjective structure leads to bound sets rather than scalar bounds. Recent studies show the existence of Lagrange multipliers that can yield tighter bound sets than those obtained from convex … Read more

    Paving and computing the set of nondominated points for the bi-objective 0/1 uncapacitated facility location problem

  • Xavier Gandibleux
  • Anthony Przybylski
    • Categories Combinatorial Optimization, Multi-Criteria Optimization Tags , , , , ,

    The paper presents a three-phase algorithm to compute the set of nondominated points for the binary version of the uncapacitated facility location problem with two objectives. The first phase constructs a paving in objective space which is a collection of boxes that covers all nondominated points. The paving procedure is a branch and bound algorithm … Read more

    Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems

  • Audrey Cerqueus
  • Xavier Gandibleux
  • Anthony Przybylski
    • Categories Combinatorial Optimization, Multi-Criteria Optimization Tags , , , ,

    The paper deals with the definition and the computation of surrogate upper bound sets for the bi-objective bi-dimensional binary knapsack problem. It introduces the Optimal Convex Surrogate Upper Bound set, which is the tightest possible definition based on the convex relaxation of the surrogate relaxation. Two exact algorithms are proposed: an enumerative algorithm and its … Read more