Benson's algorithm

<h2 id="idea-of-algorithm">Idea of algorithm</h2>
<p>Consider a vector linear program
</p>

min
          
            C
          
        
        P
        x
        
        
           subject to 
        
        A
        x
        ≥
        b
      
    
    {\displaystyle \min _{C}Px\;{\text{ subject to }}Ax\geq b}

<p>for 
  
    
      
        P
        ∈
        
          
            R
          
          
            q
            ×
            n
          
        
      
    
    {\displaystyle P\in \mathbb {R} ^{q\times n}}
  
, 
  
    
      
        A
        ∈
        
          
            R
          
          
            m
            ×
            n
          
        
      
    
    {\displaystyle A\in \mathbb {R} ^{m\times n}}
  
, 
  
    
      
        b
        ∈
        
          
            R
          
          
            m
          
        
      
    
    {\displaystyle b\in \mathbb {R} ^{m}}
  
 and a polyhedral convex ordering cone 
  
    
      
        C
      
    
    {\displaystyle C}
  
 having nonempty interior and containing no lines. The feasible set is 
  
    
      
        S
        =
        {
        x
        ∈
        
          
            R
          
          
            n
          
        
        :
        
        A
        x
        ≥
        b
        }
      
    
    {\displaystyle S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}}
  
. In particular, Benson's algorithm finds the <a href="/facts/Extreme_point/szg0j6an">extreme points</a> of the set 
  
    
      
        P
        [
        S
        ]
        +
        C
      
    
    {\displaystyle P[S]+C}
  
, which is called upper image.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p><p>In case of 
  
    
      
        C
        =
        
          
            R
          
          
            +
          
          
            q
          
        
        :=
        {
        y
        ∈
        
          
            R
          
          
            q
          
        
        :
        
          y
          
            1
          
        
        ≥
        0
        ,
        …
        ,
        
          y
          
            q
          
        
        ≥
        0
        }
      
    
    {\displaystyle C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}}
  
, one obtains the special case of a multi-objective linear program (<a href="/facts/Multiobjective_optimization/1Hb4gjGJ">multiobjective optimization</a>).
</p>
<h2 id="dual-algorithm">Dual algorithm</h2>
<p>There is a dual variant of Benson's algorithm,<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> which is based on geometric duality<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> for multi-objective linear programs.
</p>
<h2 id="implementations">Implementations</h2>
<p>Bensolve - a free VLP solver
</p>
<ul><li><a href="http://bensolve.org">www.bensolve.org</a></li></ul>
<p>Inner
</p>
<ul><li><a href="https://github.com/lcsirmaz/inner">Link to github</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Harold P. Benson (1998). "An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem". Journal of Global Optimization. 13 (1): 1–24. doi:10.1023/A:1008215702611. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. pp. 162–169. ISBN 9783642183508. <a href="9783642183508" target="_blank">9783642183508</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. pp. 162–169. ISBN 9783642183508. <a href="9783642183508" target="_blank">9783642183508</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Ehrgott, Matthias; Löhne, Andreas; Shao, Lizhen (2011). "A dual variant of Benson's "outer approximation algorithm" for multiple objective linear programming". Journal of Global Optimization. 52 (4): 757–778. doi:10.1007/s10898-011-9709-y. ISSN 0925-5001. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Heyde, Frank; Löhne, Andreas (2008). "Geometric Duality in Multiple Objective Linear Programming" (PDF). SIAM Journal on Optimization. 19 (2): 836–845. doi:10.1137/060674831. ISSN 1052-6234. <a href="http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/06-15report.pdf" target="_blank">http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/06-15report.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Benson's algorithm open-in-new

Benson's algorithm