8
$\begingroup$

According to Bertsimas' text, the standard form of a LP problem is:

Bertsimas

According to Vanderbei's text, the standard form of a LP problem is:

Vanderbei

So, what is the standard form of a linear programming (LP) problem? Thanks.

  • 0
    Every author has his/her own convention. Some prefer the minimization formulation; some prefer the maximization form, and... you get the idea. Go with what you're comfortable with.2012-10-28

2 Answers 2

6

I have seen both the $\min$ and $\max$ forms of an LP frequently, it seems to be an author preference sort of thing. The only difference is a minus sign in the objective ($-c^Tx$ instead of $c^Tx$).

Regarding the constraints, I have more often seen the first form (your Bertsimas reference) referred to as standard or canonical. The two forms are equivalent in some sense.

Since $Ax=b$ can be written as the pair of inequality constraints $Ax \leq b$ and $(-A)x \leq (-b)$, it is clear that the first form can be expressed directly as a problem of the second form.

The inequality $Ax\leq b$ can be written as a combination of an equality $Ax+ \sigma = b$ and an inequality $\sigma \geq 0$. Hence by increasing the number of variables (ie, using the variables $x$ and $\sigma$), we can express the second form as a problem of the first form, ie, $\begin{bmatrix} A & I \end{bmatrix} \pmatrix{x \\ \sigma} = b$, $\pmatrix{x \\ \sigma} \geq 0$.

The problem $\min \{ c^T x | A x \leq b \}$ is sometimes referred to as an inequality form LP. Again, it is equivalent to the other two forms.

  • 0
    Thanks @copper.hat. Perhaps it is indeed a matter of preference. In Bertsimas' own words "we will often use the general form $ \mathbf{Ax} \geq b $ to develop the theory of linear programming. However, when it comes to algorithms, and especially the simplex and interior point methods, we will be focusing on the standard form $ \mathbf{Ax} = b, \mathbf{x} \geq 0 $, which is computationally more convenient."2012-10-28
0

Both are standard form. The Objective Function (first line) can be aimed to either minimize OR maximize, the constraints (everything after "subject to") can be many or few, and the constraints can be in any of the following forms: >=, =, or <=