Multi-objective linear programming

Multi-objection linear programming is a subarea of mathematical optimization. A multiple objective linear program (MOLP) is a linear program with more than one linear objective functions. An MOLP is a special case of a vector linear program. Multi-objection linear programming is also a subarea of Multi-objective optimization.

Problem formulation

In mathematical terms, a MOLP can be written as:

$\min _{x}Px\quad {\text{s.t.}}\quad a\leq Bx\leq b,\;l\leq x\leq u$

where $B$ is an $(m\times n)$ matrix, $P$ is a $(q\times n)$ matrix, a is an $m$-dimensional vector with components in $\mathbb {R} \cup \{-\infty \}$

Solution concepts

There are different minimality notions, among them:

• ${\bar {x}}\in S$ is a weakly efficient point (weak minimizer) if for every $x\in S$ one has $f(x)-f({\bar {x}})\not \in -\operatorname {int} C$.
• ${\bar {x}}\in S$ is an efficient point (minimizer) if for every $x\in S$ one has $f(x)-f({\bar {x}})\not \in -C\backslash \{0\}$.
• ${\bar {x}}\in S$ is a properly efficient point (proper minimizer) if ${\bar {x}}$ is a weakly efficient point with respect to a closed pointed convex cone ${\tilde {C}}$ where $C\backslash \{0\}\subseteq \operatorname {int} {\tilde {C}}$.

Every proper minimizer is a minimizer. And every minimizer is a weak minimizer.

Modern solution concepts not only consists of minimality notions but also take into account infimum attainment.

Solution methods

• Benson's algorithm for linear vector optimization problems

Relation to multi-objective optimization

Any multi-objective optimization problem can be written as

$\mathbb {R} _{+}^{d}\operatorname {-} \min _{x\in M}f(x)$

where $f:X\to \mathbb {R} ^{d}$ and $\mathbb {R} _{+}^{d}$ is the non-negative orthant of $\mathbb {R} ^{d}$. Thus the minimizer of this vector optimization problem are the Pareto efficient points.