Benson's algorithm

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

Benson's algorithm, named after Harold Benson, is a method for solving multi-objective linear programming problems and vector linear programs. This works by finding the "efficient extreme points in the outcome set". The primary concept in Benson's algorithm is to evaluate the upper image of the vector optimization problem by cutting planes.

Consider a vector linear program

min

        C
      
    
    P
    x
    
    
       subject to 
    
    A
    x
    ≥
    b
  

{\displaystyle \min _{C}Px\;{\text{ subject to }}Ax\geq b}

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 extreme points of the set

    P
    [
    S
    ]
    +
    C
  

{\displaystyle P[S]+C}

, which is called upper image.

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 (multiobjective optimization).

There is a dual variant of Benson's algorithm, which is based on geometric duality for multi-objective linear programs.

Bensolve - a free VLP solver

• www.bensolve.org

Inner

• Link to github

.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}body.skin-vector-2022 .mw-parser-output .reflist-columns-2{column-width:27em}body.skin-vector-2022 .mw-parser-output .reflist-columns-3{column-width:22.5em}.mw-parser-output .references[data-mw-group=upper-alpha]{list-style-type:upper-alpha}.mw-parser-output .references[data-mw-group=upper-roman]{list-style-type:upper-roman}.mw-parser-output .references[data-mw-group=lower-alpha]{list-style-type:lower-alpha}.mw-parser-output .references[data-mw-group=lower-greek]{list-style-type:lower-greek}.mw-parser-output .references[data-mw-group=lower-roman]{list-style-type:lower-roman}.mw-parser-output div.reflist-liststyle-upper-alpha .references{list-style-type:upper-alpha}.mw-parser-output div.reflist-liststyle-upper-roman .references{list-style-type:upper-roman}.mw-parser-output div.reflist-liststyle-lower-alpha .references{list-style-type:lower-alpha}.mw-parser-output div.reflist-liststyle-lower-greek .references{list-style-type:lower-greek}.mw-parser-output div.reflist-liststyle-lower-roman .references{list-style-type:lower-roman}

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}