Encyclopedia

Multi-objective linear programming

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated October 16, 2025

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

01Problem formulation

In mathematical terms, a MOLP can be written as:

$\min _{x}Px\quad {\text{s.t.}}\quad a\leq Bx\leq b,\;\ell \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 \}$ , $b$ is an $m$ -dimensional vector with components in $\mathbb {R} \cup \{+\infty \}$ , $\ell$ is an $n$ -dimensional vector with components in $\mathbb {R} \cup \{-\infty \}$ , $u$ is an $n$ -dimensional vector with components in $\mathbb {R} \cup \{+\infty \}$

02Solution concepts

A feasible point $x$ is called efficient if there is no feasible point $y$ with $Px\leq Py$ , $Px\neq Py$ , where $\leq$ denotes the component-wise ordering.

Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points..... There are also algorithms to determine the set of all maximal efficient faces. Based on these goals, the set of all efficient (extreme) points can be seen to be the solution of MOLP. This type of solution concept is called decision set based. It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).

Efficient points are frequently called efficient solutions. This term is misleading because a single efficient point can be already obtained by solving one linear program, such as the linear program with the same feasible set and the objective function being the sum of the objectives of MOLP.

More recent references consider outcome set based solution concepts and corresponding algorithms. Assume MOLP is bounded, i.e. there is some $y\in \mathbb {R} ^{q}$ such that $y\leq Px$ for all feasible $x$ . A solution of MOLP is defined to be a finite subset ${\bar {S}}$ of efficient points that carries a sufficient amount of information in order to describe the upper image of MOLP. Denoting by $S$ the feasible set of MOLP, the upper image of MOLP is the set ${\mathcal {P}}:=P[S]+\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:\;\exists x\in S:y\geq Px\}$ . A formal definition of a solution is as follows:

A finite set ${\bar {S}}$ of efficient points is called solution to MOLP if $\operatorname {conv} P[{\bar {S}}]+\mathbb {R} _{+}^{q}={\mathcal {P}}$ ("conv" denotes the convex hull).

If MOLP is not bounded, a solution consists not only of points but of points and directions

03Solution methods

Multiobjective variants of the simplex algorithm are used to compute decision set based solutions and objective set based solutions.

Objective set based solutions can be obtained by Benson's algorithm.

Watch videos about Multi-objective linear programmingExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Multi-objective linear programming”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Multi-objective linear programming

01Problem formulation

02Solution concepts

03Solution methods

04Related problem classes

Sources and credits