[Coin-discuss] Quick checking, if the problem is primal feasible

[John J Forrest]

Daniel,

I can not see any way of getting rid of the initialSolve.  You could
improve the time somewhat by -
a) using the presolved problem rather than the initial (and giving hint to
initialSolve not to presolve).
b) making sure you have a zero objective function (probably - but if dual
quicker then very small and random)
c) doing tests to see if primal or dual solves faster (see point b))

Depending on the structure of the problem you could also try aggregating
rows to give a smaller problem.  This would increase worst running time but
might improve average.

John Forrest


                                                                           
             Daniel Stoinski                                               
             <Daniel.Stoinski@                                             
             nagler-company.co                                          To 
             m>                        coin-discuss at list.coin-or.org       
             Sent by:                                                   cc 
             coin-discuss-boun                                             
             ces at list.coin-or.                                     Subject 
             org                       [Coin-discuss] Quick checking, if   
                                       the problem is primal feasible      
                                                                           
             07/10/06 05:13 AM                                             
                                                                           
                                                                           
             Please respond to                                             
             Discussions about                                             
                open source                                                
               software for                                                
                Operations                                                 
                 Research                                                  
             <coin-discuss at lis                                             
              t.coin-or.org>                                               
                                                                           
                                                                           




Hi,

we only want to check, if the problem is primal feasible, without solving
the problem. And we want to be really quick, becuase the operation will be
performed for quite big problems in a loop.

At the moment we're using the following non performant code:

short isPrimalInfeasible(OsiClpSolverInterface &aSolver)
{
  OsiSolverInterface    *solver2;
  OsiPresolve           pinfo;
  bool                  isPrimalInfeasible;

  solver2 = pinfo.presolvedModel(aSolver, 0.0);
  if (solver2 != NULL)
  {
    delete solver2;
    aSolver.initialSolve();
    return aSolver.isProvenPrimalInfeasible();
  }
  return 1;
}

If the problem is "really" infeasible, both primal and dual, we get
solver2 = NULL very quickly and this is fine. For "partially" feasible
problems we call initialSolve(), which takes a lot of time until it
states, that the problem is only dual feasible.

Is there any possibility to get rid of this initialSolve()?

Probably we could become a little bid faster, if we use ClpPresolve and
ClpSimplex instead of the Osi interface.

But my impression is, that the most time gets lost for the unnecessary
solving the problem, while only the information about the
primal feasibility is needed.

Really best thanks for any hint. Best regards
Daniel Stoinski

_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss