Relaxations and duality for multiobjective integer programming (Q6608043)

The paper analyzed relaxations and developed a duality framework for Multiobjective integer programs (MOIPs) by leveraging results from single-objective integer programming. Presented an MOIP Lagrangian dual that generalizes the single-objective counterpart, relying on the idea of finding the best upper bound over all Lagrangian relaxations. In particular, authors formulated the Lagrangian relaxation of an MOIP and compared it with the continuous and convex hull relaxations. The convex hull relaxation is tight at supported efficient solutions of the MOIP but not at unsupported solutions. Showed via an example that a Lagrangian relaxation can provide a tighter upper bound at unsupported nondominated points. In addition also introduced two superadditive duals, namely, a set-valued formulation and a vector-valued variant. In this paper, the main goal is to present continuous, convex hull and Lagrangian relaxations for MOIPs and examine the relationship among them.