Re: [Help-glpk] Problem : basis

[Andrew Makhorin]

> I understand the column status.
> For row, if I understood well, the row is active if Ax=b
> for the problem Ax<=b with x auxiliary variables. So, structural
> variables = 0

In general case the lp constraint system is the following:

   L <= Ax <= U
   l <=  x <= u

where L and U are row bounds, l and u are column bounds. In glpk
each row is automatically provided with corresponding auxiliary
variable:

   y[i] = a[i,1]x[1] + ... + a[i,n]x[n]

that leads to the following equivalent constraint system:

(1)   y = Ax
(2)   L <= y <= U
(3)   l <= x <= u

Note that there are m auxiliary variables y[1], ..., y[m] and
n structural variables x[1], ..., x[n].

Geometrically, the basic solution is a point in the space of all
m+n variables, which (point) is an intersection of m+n hyperplanes
defined by *active* constraints. m constraints (1) being linearly
independent equalities are always active, so other n active
constraints can be chosen only from bound constraints (2) and (3).

If the lower or upper bound of variable y[i] or x[j] is active
constraint, the variable is said non-basic, otherwise basic; this
property of a variable is called the status of the variable. Thus,
to define some basic solution, you need to specify statuses of all
(auxiliary and structural) variables, i.e. define which variables
have active bounds and which ones have inactive bounds. As was said
above, there must be exactly n active bound constraints, so exactly
n (auxiliary and/or structural) variables can be non-basic while
other m variables are basic, i.e. in any valid basic solution the
number of basic variables is the same as the number of rows (m) and the
number of non-basic variables is the same as the number of columns (n).

If you delete some active row, i.e. the row, whose auxiliary variable
is non-basic, the number of rows is decreased by one while the number
of variables marked as basic remains the same, and the basis becomes
invalid. Similarly, if you delete some basic structural variable, the
number of rows remains the same while the number of basic variables
is decreased by one, so the basis again becomes invalid.

> my algorithm is:

->solve problem
->delete columns and rows
->add columns
->resolve problem

If a row is active, deleting it invalidates the basis as was explained
above. However, you can attain the same effect by *freeing* the row,
i.e. by changing its bounds to -inf and +inf, resp., in which case the
basis remains valid. Analogously, if a column is basic, you can change
both its bounds to 0, i.e. *fix* the structural variable at zero, rather
than delete it, in which case the basis again remains valid.


Andrew Makhorin