This blog is going to talk about the general form and standard form, and the transformation between different forms.

General form of Linear Optimization

We given a cost vector ${ \bar{c} = \left[ \begin{smallmatrix} c_1 & c_2 & \cdots & c_n \end{smallmatrix} \right]^\top}$ and we seek to minimize or maximize the linear cost function ${ \bar{x} \in \mathbb{R}^n \mapsto \bar{c}^T \bar{x} \in \mathbb{R}^n}$

Over all vectors ${ \bar{x} = \left[ \begin{smallmatrix} x_1 & x_2 & \cdots & x_n \end{smallmatrix} \right] ^\top \in \mathbb{R}^n }$ satisfying a set of linear equality and inequality constrains, like the following form

$$ \begin{equation} \begin{aligned} &\text{minimize} & \bar{c}^T \bar{x} & \\ &\text{subject to} & \bar{a}_i^T \bar{x} \leq b_i, &i\in L \\ & & \bar{a}_i^T \bar{x} = b_i, &i\in E \\ & & \bar{a}_i^T \bar{x} \geq b_i, &i\in G \\ & &x_j \geq 0, &j \in P \\ & &x_j \leq 0, &j \in N \\ \end{aligned} \end{equation} $$

Here, ${ L,E,G }$ are some finite index sets (they may be empty). ${ P,N }$ are subsets of ${ {1,2,\cdots, n} }$

Important terms

• The variables ${ x_1,x_2,\cdots,x_n }$ are called decision variables .

• A vector ${ \bar{x} }$ satisfying all the contraints is called a feasible solution or a feasible vector.

• The set of all feasible solution is called the feasible set or a feasible region.

• A feasible solution ${ \bar{x}^* }$ that minimizes the cost function or objective function is called an optimal (feasible) solution (i.e. a feasible solution ${ \bar{x}^*}$ such that ${ \forall \bar{x} \in \text{feasible set }, \bar{c}^T\bar{x}^* \leq \bar{c}^T \bar{x}}$)

• The value of ${ \bar{c}^T\bar{x}^* }$ is called the optimal cost

• We say that the cost is unbounded below or that the optimal cost is ${ -\infty }$, if ${ \forall K\in \mathbb{R}, \exists }$ a feasible solution ${ \bar{x} }$ such that ${ \bar{c}^T\bar{x} \leq K }$

E.g. following optimization problem gives an example that the cost function is unbounded below

$$ \begin{equation} \begin{aligned} &\text{minimize} & 5x_1 -3x_2 & \\ &\text{subject to} & x_1 \geq 0& \\ & & x_2 \geq 0& \end{aligned} \end{equation} $$

Unify the General form

• An equality constraint ${ \bar{a_i}^T \bar{x_i} = b_i}$ is equivalent to the pair of inequality contraints ${ \bar{a_i}^T \bar{x_i} \leq b_i, \bar{a_i}^T \bar{x_i} \geq b_i }$

• The constraint ${ \bar{a_i}^T \bar{x_i} \leq b_i}$ is equivalent to ${ - \bar{a_i}^T \bar{x_i} \geq -b_i }$

• A constraint of the form ${ x_j \geq 0 }$ is a special case of the constraint ${ \bar{a_i}^T \bar{x_i} \geq b_i }$, where ${ b_i = 0, \bar{a_i} = \left[\matrix{0\\0\\ \vdots\\0\\1 \\0 \\ \vdots \\0 } \right] \matrix{ \ \ \ \ \leftarrow j^{th} element}}$

The feasible set in a general linear optimization problem can thus be expressed exclusively in terms of constrains of the form ${ \bar{a_i}^T \bar{x_i} \geq b_i }$

Next, we can rewrite the ${ m }$ constains into another form ${ A\bar{x} \geq \bar{b} }$, here

$$ A = \left[ \matrix{\bar{a_1}^T \\ \bar{a_2}^T \\ \vdots \\ \bar{a_m}^T} \right], \bar{b} = \left[ \matrix{b_1 \\b_2 \\ \vdots \\ b_m} \right] $$

PS: the “${ \geq }$” between two vector means all the componets of front vector are equal and greater than corresponding elements of second vector.

• Maximazing ${ \bar{x} \mapsto \bar{c}^T \bar{x} }$ is equivalent to minimazing ${ \bar{x} \mapsto - \bar{c}^T \bar{x}}$. We just need to take the “Opposite number” of cost value for original optimization problem.

In summary, all the Linear Optimization problem can be written as General form:

$$ \begin{equation} \begin{aligned} &\text{minimize} &\bar{c}^T\bar{x} \\ &\text{subject to} &A\bar{x} \geq \bar{b} \end{aligned} \end{equation} $$

Standard form of Linear Optimization

A linear programming problem of the form

$$ \begin{equation} \begin{aligned} & \text{minimize} & \bar{c}^T\bar{x} \\ & \text{subject to} & A\bar{x} = \bar{b} \\ & & \bar{x} \geq \bar{0} \end{aligned} \end{equation} $$

Standard form will be more convenient in solving Linear Optimization problem.

Fact: Any linear optimization problem can be transformed into an equivalent problem in standard form!.

Method for transforming into Standard form

Step 1. Eliminate Unrestricted Variables

If a decision variable ${ x_i }$ is unrestricted in sign, introduce two new decision variables ${ x_i^+ , x_i^- }$ substitute ${ x_i^+ - x_i^- }$ for every ${ x_i }$ in the problem and the restrictions ${ x_i^+ \geq 0 , x_i^- \geq 0}$ to the list of contraints.

Step 2. Eliminate Inequality Constrains of type ${ \sum_{j=1}^n a_{ij} x_j \leq b_i }$

For each contrains like that, introduce a new decision variable ${ s_i }$ and replace the inequality constraint as

$$ \begin{equation} \begin{aligned} & \sum_{j=1}^n a_{ij} x_j + s_i = b_i \\ & s_i \geq 0 \end{aligned} \end{equation} $$

The new decision variable ${ s_i }$ is called a slack variable

Step 3. Eliminate Inequality Constrains of type ${ \sum_{j=1}^n a_{ij} x_j \geq b_i }$

Similar way to treat it like above, replace the constrains as

$$ \begin{equation} \begin{aligned} & \sum_{j=1}^n a_{ij} x_j - s_i = b_i \\ & s_i \geq 0 \end{aligned} \end{equation} $$

The new decision variable ${ s_i }$ is called a surplus variable

An example of transforming

$$ \begin{equation} \begin{aligned} &\text{minimize} && 2x_1 + 4x_2 \\ &\text{subject to} && x_1 + x_2 \geq 3 \\ & && 3x_1 +2x_2 = 14 \\ & && x_1 \geq 0 \end{aligned} \end{equation} $$

1. Replace all the unrestricted variables

$$ \begin{equation} \begin{aligned} &\text{minimize} && 2x_1 + 4 (x_2^+ - x_2^-) \\ &\text{subject to} && x_1 + (x_2^+ - x_2^-) \geq 3 \\ & && 3x_1 +2(x_2^+ - x_2^-) = 14 \\ & && x_1 \geq 0 \\ & && x_2^+ \geq 0 \\ & && x_2^- \geq 0 \end{aligned} \end{equation} $$

1. Add surplus/slack variables

$$ \begin{equation} \begin{aligned} &\text{minimize} && 2x_1 + 4 (x_2^+ - x_2^-) + 0\cdot s \\ &\text{subject to} && x_1 + (x_2^+ - x_2^-) -s = 3 \\ & && 3x_1 +2(x_2^+ - x_2^-) = 14 \\ & && x_1 \geq 0 \\ & && x_2^+ \geq 0 \\ & && x_2^- \geq 0 \\ & && s\geq 0 \end{aligned} \end{equation} $$

Note!

In Linear Optimization problem, when we say two LO problems are equivalent, it means givena solution of one, we can transform it into a feasible solution of another one with same cost.

Here are two pairs of solutions of above problem

$$ \begin{equation} \begin{aligned} x_1 = 6 , x_2 = -2 \Rightarrow x_1 = 6, x_2^+ = 0, x_2^- =2 , s = x_1 + x_2 -3 = 1 \\ x_1 = 8 , x_2 = -5 \Rightarrow x_1 = 8, x_2^+ = 2, x_2^- =7 , s = x_1 + x_2 -3 = 0 \\ \end{aligned} \end{equation} $$

Second Example

$$ \begin{equation} \begin{aligned} &\text{minimize} && 3x_1 - 2x_2 + 7x_3 \\ &\text{subject to} && 3x_1 - 2x_2 \leq 13 \\ & && 4x_1 - 6x_2 + 5x_3 \geq 8 \\ & && x_2 \geq 0 \\ & && x_3 \geq 0 \end{aligned} \end{equation} $$ $$ \begin{equation} \begin{aligned} &\text{minimize} && 3(x_1^+-x_1^-) - 2x_2 + 7x_3 \\ &\text{subject to} && 3(x_1^+-x_1^-) - 2x_2 \leq 13 \\ & && 4(x_1^+-x_1^-) - 6x_2 + 5x_3 \geq 8 \\ & && x_2 \geq 0 \\ & && x_3 \geq 0 \\ & && x_1^+ \geq 0 \\ & && x_1^- \geq 0 \end{aligned} \end{equation} $$ $$ \begin{equation} \begin{aligned} &\text{minimize} && 3(x_1^+-x_1^-) - 2x_2 + 7x_3 + 0 \cdot s_1 + 0 \cdot s_2\\ &\text{subject to} && 3(x_1^+-x_1^-) - 2x_2 + s_1 = 13 \\ & && 4(x_1^+-x_1^-) - 6x_2 + 5x_3 -s_2 = 8 \\ & && x_2 \geq 0 \\ & && x_3 \geq 0 \\ & && x_1^+ \geq 0 \\ & && x_1^- \geq 0 \\ & && s_1 \geq 0 \\ & && s_2 \geq 0 \\ \end{aligned} \end{equation} $$

Special cases

• If ${ 0\leq x_1 \leq 2 }$, we can treat it as ${ x_1 \geq 0, x_1 \leq 2 }$. Then add slack variable ${ x_1 + s = 2, s\geq 0 }$

• If ${ x_1 \geq -2 }$

${\Rightarrow x_1^+ - x_1^- \geq -2, x_1^+ , x_1^- \geq 0 }$

${\Rightarrow x_1^+ - x_1^- - s = -2, x_1^+ , x_1^-,s \geq 0 }$