Duality of nonscalarized multiobjective linear programs: Dual balance, level sets, and dual clusters of optimal vectors

A new concept of duality is proposed for multiobjective linear programs. It is based on a set expansion process for the computation of optimal solutions without scalarization. The duality qualifications are investigated; the primal–dual balance set and level set equations are derived. It is demonstrated that the nonscalarized dual problem presents a cluster of optimal dual vectors that corresponds to a unique optimal primal vector. Comparisons are made with linear utility, minmax and minmin scalarizations. Connections to Pareto optimality are studied and relations to sensitivity and parametric programming are discussed. The ideas are illustrated by examples.