2010/06/15 by Benjamin A. Burton, Burton, Benjamin A., Melih Ozlen +1
Mathematics · #52B05 #90C05 #FOS: Mathematics #Optimization and Control (math.OC) #Primary 90C29 #Secondary 51A05 #math.OC #msc:51A05 #msc:52B05 #msc:90C05 #msc:90C29
paper · pdf · doi:10.48550/arxiv.1006.3085
27 pages, 12 figures
arxiv created 2010/06/15 · arxiv updated 2010/06/17
A key problem in multiobjective linear programming is to find the set of all efficient extreme points in objective space. In this paper we introduce oriented projective geometry as an efficient and effective framework for solving this problem. The key advantage of oriented projective geometry is that we can work with an "optimally simple" but unbounded efficiency-equivalent polyhedron, yet apply to it the familiar theory and algorithms that are traditionally restricted to bounded polytopes. We apply these techniques to Benson's outer approximation algorithm, using oriented projective geometry to remove an exponentially large complexity from the algorithm and thereby remove a significant burden from the running time.