sci.op-research

vijay patil wrote:
> On Mar 8, 2:50 am, Paul Rubin wrote:
>> 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.

Ok, I see what you are saying. The dual solution you get is a valid
(and optimal) solution to the dual; it's just not helpful to you. Dual
solutions in general are *bounds* on the marginal rate of change to the
primal objective as one changes a single RHS; they're exact in the
absence of degeneracy, but as you've observed not necessarily exact when
the primal solution is degenerate.

In the small example above, the second constraint is redundant, in that
removing it does not affect the primal feasible region. Your idea of
replacing a shadow price with zero if the basic variable in the
corresponding row is zero in essence amounts to ignoring that
constraint. There are still one if not two problems with this:

(a) it is easy to create examples where the primal solution is
degenerate but none of the constraints are redundant, in which case
implicitly ignoring a constraint seems risky to me; and

(b) although I don't have an example at hand, I suspect it is possible
to construct an example like the one above in which a constraint is
redundant but the zero basic variable occurs in a different row, in
which case you would be zeroing out the wrong shadow price.
>
>> 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).

An approach sometimes used to get past degenerate corners in the primal
problem is to temporarily perturb the corner randomly. The random
perturbation temporarily breaks the degeneracy. Perhaps that would work
for you. Proceed as normal but check for degeneracy before invoking the
column generation routine. If the primal solution is degenerate, make a
small perturbation to the right side and use the shadow prices you get
from that in the column generation problem.

/Paul