Re: [Help-glpk] non-negativity and structural vars

[Andrew Makhorin]

> This relates to GLPK 4.25 (I did not want to upgrade
> past 4.25 while the database functionality was being
> resolved, for the record 4.28 is current).

> I have been trying to find out how deep the
> non-negativity condition on structural variables is.

> So I took the tutorial problem from the manual -- a
> maximization exercise -- and ran it:

>     *     0:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
>     *     2:   objval =   7.333333333e+02   infeas =   0.000000000e+00 (0)
>     OPTIMAL SOLUTION FOUND

>     Z = 733.333; x1 = 33.3333; x2 = 66.6667; x3 = 0

> So far so good!  I then commented out statements s13,
> s16, s19 which prevent the x's from being negative
> definite (meaning zero is okay).  And reran the
> problem:

>     !     0:   objval =   0.000000000e+00   infeas =   0.000000000e+00
>     OPTIMAL SOLUTION FOUND

>     Z = 0; x1 = 0; x2 = 0; x3 = 0

> Oops!  Given that the three removed statements are
> mathematically redundant in this case, this result
> looks puzzling.

All columns (structural variables) being just created are fixed at zero
as if there were a call glp_set_col_bnds(lp, j, GLP_FX, 0, 0).

The mark '!' means that the solver performed no iteration, i.e. the
starting basis passed to the solver was found optimal.

> Commenting out just one of the three statements gave
> different results in some cases but never a negative
> definite x.  For instance, disabling s16 for x2
> yielded:

>     *     0:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
>     *     1:   objval =   6.000000000e+02   infeas =   0.000000000e+00 (0)
>     OPTIMAL SOLUTION FOUND

>     Z = 600; x1 = 60; x2 = 0; x3 = 0

> Changing the three statements in question from 'GLP_LO'
> to 'GLP_FR' (free) resulted in this:

>     *     0:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
>     *     2:   objval =   7.333333333e+02   infeas =   0.000000000e+00 (0)
>     PROBLEM HAS UNBOUNDED SOLUTION

>     Z = 733.333; x1 = 33.3333; x2 = 66.6667; x3 = 0

> The solver call returned zero in all cases.  Note that
> the column one '!' in the second case is not documented
> (at least not on page 44).

> In addition, the manual does not indicate what the
> default on unspecified col bounds is (or at least I
> could not find it).

The manual says that "Being added each new column is initially fixed
at zero and has empty list list of the constraint coefficients."

> Does this mean that the non-negativity conditions are
> required by the solver but not necessarily by the
> problem statement?  Or am I missing something
> important?

> Ultimately I would like to know if I need to continue
> to make non-negativity a mandatory condition in my
> application program or not -- thus far it would seem
> so.

You have to set bounds for each structural variable (column) added.