Equivalence between polyhedral projection, multiple objective linear programming and vector linear programming

Abstract

Let a polyhedral convex set be given by a finite number of linear inequalities and consider the problem to project this set onto a subspace. This problem, called polyhedral projection problem, is shown to be equivalent to multiple objective linear programming. The number of objectives of the multiple objective linear program is by one higher than the dimension of the projected polyhedron. The result implies that an arbitrary vector linear program (with arbitrary polyhedral ordering cone) can be solved by solving a multiple objective linear program (i.e. a vector linear program with the standard ordering cone) with one additional objective space dimension.

arXiv commentIn version 5, some typos have been corrected

References in corpus (2)

• The vector linear program solver Bensolve -- notes on theoretical background
• On the Dual of the Solvency Cone

Cited by in corpus (9)

• The vector linear program solver Bensolve -- notes on theoretical background
• A vector linear programming approach for certain global optimization problems
• On the Approximation of Unbounded Convex Sets by Polyhedra
• Computing Convex Hulls of Trajectories
• Solving DC programs with a polyhedral component utilizing a multiple objective linear programming solver
• Existence of solutions for polyhedral convex set optimization problems
• A Benson-Type Algorithm for Bounded Convex Vector Optimization Problems with Vertex Selection
• On the approximation error for approximating convex bodies using multiobjective optimization
• A set optimization approach to zero-sum matrix games with multi-dimensional payoffs