Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Bertsimas' text refers to Introduction to Linear Optimization. Vanderbei's text refers to Linear Programming: Foundations and Extensions. –  dwstu Oct 28 '12 at 4:11
    
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. –  J. M. Oct 28 '12 at 4:49
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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." –  dwstu Oct 28 '12 at 7:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.