[Coin-lpsolver] What is the best way of getting out N feasible extreme points?

[Yiming Yao]

I've tried to trap message 102 (CLP_SIMPLEX_HOUSE2) since my algorithm 
needs to find all feasible extreme points (FEPs) with an objective value 
within a limit. However, for a minimization problem,  the FEPs produced an 
increasing objective value stream like:
0.125
10.4
....
415.8
521.15 (optimal solution)

Since this was minimization, I expected the FEPs would produce a decrease 
objective value stream like (100012.3, 2569.2, ..., 652.0, 521.15). Have I 
done something wrong? (please see the description below.)

Thanks,

Yiming

----------------------------------------------------------

Here's what I've done:

1. in ClpMessage.cpp, changed
{CLP_SIMPLEX_HOUSE2,102,4,"%d %g In: %c%d Out: %c%d%? dj ratio %g distance 
%g%? dj %g distance %g"},
to
{CLP_SIMPLEX_HOUSE2,102,4,"%d %g In: %c%d Out: %c%d%? dj ratio %g distance 
%g%? dj %g distance %g"},

2. Created MlpMessageHandler class by inheriting CoinMessageHandler in a 
similar way as the MyMessageHandler class.  The main method of this class 
looks like the following (I also asked some questions as comments):

int
MlpMessageHandler::print()
{
   if (currentSource()=="Clp") {
     if (currentMessage().externalNumber()==102) {

       // feasible?
       // Is this better way to check feasibility?
       // if (model_->numberPrimalInfeasibilities()== intValue(1));
       if (model_->numberPrimalInfeasibilities()==0) {

         // this seems to give wrong value: double objValue = 
model_->getObjValue();

          // compute objective value = solution{[]*objCoef[].
           int numberColumns = model_->numberColumns();
           double * solutionRaw = model_->solutionRegion(1);
           const double * columnScale = model_->columnScale();
           bool scaleFlag = model_->columnScale();
           double *solution = new double[numberColumns];
           for (int i=0;i<numberColumns;i++) {
             if(scaleFlag) {
               solution[i] = solutionRaw[i] * columnScale[i];
           } else {
             solution[i] = solutionRaw[i];
           }
         }
         const double *objCoefs = model_->getObjCoefficients();
         double objValue1 = 0;
         for (int i=0;i<numberColumns;i++) {
           objValue1 += solution[i]*objCoefs[i];
         }

           //Observe objective value. Strange that objValue1 increases 
iteration after iteration for minimization.
         cout << objValue1 << endl;

         // Is the objective value within limit?
         if( objValue1 > 0 && objValue1 <= artificialBound) { // 
artificialBound is an input parameter
         //twoLevelPtr points to my algorithm object.
           twoLevelPtr->addCut(solution);

         }
         delete [] solution;
       }
     }
   }
   return CoinMessageHandler::print();
}







At 05:31 PM 7/24/2003 -0400, you wrote:

>Yiming,
>
>If anything I found a slight bug/feature so that it would save even when 
>infeasible.
>
>It should be okay, although message 5 is only printed every 
>re-factorization so on small problems you may not get enough 
>solutions.  One way round that would be to set  the factorization 
>frequency to small for small problems.  At present I am busy with a 
>development branch and don't have code to hand but there is an example in 
>Samples/driver.cpp.    In the development branch "pre" you would say
>
>if (model2->numberRows()<100)
>    model2->setFactorizationFrequency(10)
>
>I think in the default it would be
>if ()
>   model2->factorization()->maximumPivots(10);
>
>and you would have to include ClpFactorization.hpp
>
>If that does not help, then one of the beauties of open source is that you 
>can debug it for me :-)
>
>If it is easy, send me enough to debug it.  If not then just put a few 
>printf or std::cout statements - it should be easy to see what is happening.
>
>If you want every iteration then trap message 102
>
>John Forrest

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20030806/957189c4/attachment.html>