[Clp] Clp-1.7 Dual Simplex Algorithm

[Bo Jensen]

I think you should try to solve these subproblems with the primal simplex
algorithm. It would most likely do minimizing sum of infeasibility and will
likely be less degenerated. Actually this is equal to a old strategy by the
great GDB himself, where he suggest minimizing primal sum of infeasibility
on the subset of dual degenerated variables (in this case all of them).
You are right that all the duals in theory are zero in dual simplex in this
case, but in practice they contain small perturbations to avoid the
degeneracy issue, so depending on the solver it may or may not exploit this.


On Mon, Jun 29, 2009 at 7:55 PM, Bulutoglu Dursun A Civ AFIT/ENC <
Dursun.Bulutoglu at afit.edu> wrote:

>  Dear Clp forum,
>
> I am using an IP solver that uses Clp-1.7. My IP problems are all feasibility
> problems.
>
> I am trying to find all feasible solutions to an IP. I am using the zero
> function  as my objective (i.e. all of my objective function'scoefficientsare equal to zero). Then
> in the dual simplex algorithm all the calculations involving reduced costs
> are unnecessary. Skipping these calculations will undoubtedly speed up the
> dual simplex calculations in solving an LP relaxation within an IP.
>
> I was wondering if there is a version of Clp whose dual simplex componentskips calculations
> involving reduced costs when the objective function is the zero function.
>
> Dursun Bulutoglu
>
>
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/clp
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090630/d0c2dc73/attachment.html>