sci.op-research

On Mar 8, 2:50 am, Paul Rubin wrote:
> vijay patil wrote:
> > As my understanding improves, now I fill that I should have considered
> > possible issue of degeneracy. Specifically, before adding any new
> > (generated) pattern/column, I should check if one or more variables
> > current basis are at level 0.0. In other words, basis is degenerate.
> > As I understand, in such case dual values of rows are only
> > *theoretical* and actual improvement in obj. func. cannot be realized,
> > as one or more basic variable is already at 0 level.
>
> I'm not sure what you mean by "theoretical". If the primal solution is
> degenerate, the dual solution is valid optimal solution for the dual
> problem. It's just that the dual problem has multiple optima, and you
> are only getting one of them.

Consider following lp, example with two constraints passing through
same point.
------------
Maximize Z: 3x1 + x2
Subject To
c1: x1 + x2 <= 2.0
c2: 2x1 + x2 <= 4.0
End
------------

If I solve this using GLPK solver, and print solution and dual values
I get.

lpx_read_cpxlp: reading problem data from `test2.lp'...
lpx_read_cpxlp: 2 rows, 2 columns, 4 non-zeros
lpx_read_cpxlp: 7 lines were read
* 0: objval = 0.000000000e+00 infeas = 0.000000000e+00 (0)
* 1: objval = 6.000000000e+00 infeas = 0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
optimal value of col 1 = 2.00
optimal value of col 2 = 0.00
dual of row 1 = 0.00
dual of row 2 = 1.50

Note optimal solution is degenerate (col 2 i.e x2) is 0.0.
Importantly, note that dual value of row 2 is 1.5. If I increase RHS
of row 2 by one unit, I will not get obj. func. improvement (increase)
of 1.5.
Similarly if I add new column/variable x3 with its coefficient -1.0 in
row 2, then also I will NOT get obj. fun. improvement (increase) of
1.5, per unit value of x3.
This is what I meant by row dual costs are "theoretical" in case of
degeneracy and therefore should not be considered while calculating
reduced cost of generated new columns. This will avoid adding useless
columns to the model.

> That seems inappropriate to me. First, it makes no sense, unless you
> are assuming that Xi is basic in the i-th row. Second, if we assume
> that Xi is basic in row i, that does not "implicate" the i-th constraint
> in any meaningful way. Bear in mind that the i-th row of the _final_
> tableau has a zero right-hand side, but that row is the result of a
> number of pivots and thus represents a linear combination of the
> original constraints, not just the i-th original constraint (whereas the
> i-th shadow price does correspond to the i-th original constraint).
>
> Are you observing any substantial number of iterations where you add a
> column and the primal solution does not change?

Yes primal obj fun value remains constant for few iterations while
columns are being added.
After a while obj fun value starts to improve but bu this time lot of
columns are added to the model,
possibly causing increase in overall runtime. I am planning to write
the code to reproduce the
behavior (no more have access to project mentioned).

I will have to put some more thought, thanks for your reply.