[Dip] Achieving master problem feasibility

[Matthew Galati]

Yes - this is correct. It is like the standard two-phase revised-simplex
method.



Is the method for achieving master problem feasibility described
> anywhere? From what I can tell, looking at the code and the master
> problems being generated, there's a two phase approach where:
> - during the first phase DIP minimizes infeasibility until enough
> columns have been generated to ensure feasibility.
> - this is done by adding positive and negative slack to all constraints.
>

For 'E' it uses 2 slacks. For 'L' or 'G' it only needs one.





> - once feasibility is achieved the algorithm switches to the real
> restricted master problem without the "soft" constraints.
>


Yes, once the Phase 1 objective is 0 (minimizing the slacks), it fixes all
the slacks to 0 (essentially removing them) and sets the real (Phase 2)
objective. Since we do full branch-price-and-cut, we might fall back into
Phase1 after cuts or branching - so we keep the slacks around and unfix them
when needed.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/dip/attachments/20110204/47457a91/attachment.html