1
$\begingroup$

I'm taking a course in linear programming, and most authors define a basic solution as follows: Given an matrix A with m rows and n columns such that rank A=m < n, a basic solution for the system Ax=b is obtained by taking m linearly independent columns and solving for the associated variables (called basic variables), setting the remaining variables (called non-basic variables) to zero.

Could an analogous definition be made in cases where the rank of the matrix is less than m (for instance, in the matrix corresponding to a transportation problem)? Or indeed, in a general setup where we only know that m is less than or equal to n?

$\endgroup$
1
$\begingroup$

Given a problem in standard form \begin{align} \min \ \ & c^{\top}x\\ & Ax = b\\ & x \geq 0 \end{align}

the main assumptions for the LP theory are:

  1. $m<n$
  2. $rank (A) = m$

The first assumption is quite obvious. Solutions of an LP problem are points in $\mathbb{R}^n_{+}$. If $m=n$ and the equations are linearly independent, there is nothing to optimize: the unique feasible point is also the optimal solution. The case $m>n$ does not make sense. Actually either all the equations are satisfied by a unique feasible point, as in the case $m=n$, or the equation system is incompatible. Conversely, the case $m < n$ is the most meaningful. Actually if the equations are not incompatible, the feasible set of the LP problem is a polyhedron of dimension $n-rank(A)$ and this polyhedron has at least a vertex.

As for the second assumption, if $rank(A)=m'<m$ then there are $m-m'$ redundant constraints that can be omitted without changing the feasible set of the problem. This is the case you cite, but it is also the case of all network flow problems, where the constraint matrix is not a full-rank matrix. However basic feasible solutions are always related to the rank of the constraint matrix (see the Rouche-Capelli theorem for that) and this is because the LP theory requires full-rank constraint matrices.

Finally note that if the constraints are given as inequalities, when you put the problem in standard form, adding slack or subtracting surplus variables, the two assumptions are automatically fulfilled, independently of original the number of variables and constraints.

$\endgroup$
2
  • $\begingroup$ Could you elaborate on your second last point? Does an LPP always require full rank constraint matrices? Doesn't that clash with what you just said about network flow problems? $\endgroup$ – Student Nov 7 '16 at 18:30
  • $\begingroup$ No it doesn't clash. In a network flow problem there is a variable for each arc and there are n equality constraints (one for each node) but one of them linearly depends on the remaining (n-1) ones and you can omit it. This means that a basis consists of (n-1) variables and the corresponding arcs are the arcs of a spanning tree. That's all: in any feasible LPP the dimension of a basis equals the rank of the constraint matrix. If the constraint matrix has a rank lower than the number of constraints, there are some constraints that are useless. $\endgroup$ – Marcello Sammarra Nov 7 '16 at 20:04
0
$\begingroup$

Note that practical solvers add a slack to each row, so the matrix $A$ becomes $$ \tilde{A} = [A\quad I] $$ so our new matrix has $n+m$ columns which is always greater than $m$. The $m$ basic columns from $\tilde{A}$ form a matrix $B$ and this matrix should be invertible. If by accident it is not, most solvers will try to repair the basis by removing a column from $B$ and inserting a slack (i.e. a column from $I$). This does not happen very often: usually $B$ stays nicely non-singular. Note that a reasonable choice for a starting basis is to use the $m$ columns from $I$: this unit basis is guaranteed to be non-singular.

$\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.