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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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." $\endgroup$ – dwstu Oct 28 '12 at 7:51
0
$\begingroup$

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 <=

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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