Main Page | Class Hierarchy | Alphabetical List | Class List | File List | Class Members

Idiot Class Reference

#include <Idiot.hpp>

List of all members.

Public Member Functions

Constructors and destructor
Just a pointer to model is kept

 Idiot ()
 Default constructor.

 Idiot (OsiSolverInterface &model)
 Constructor with model.

 Idiot (const Idiot &)
 Copy constructor.

Idiot & operator= (const Idiot &rhs)
 Assignment operator. This copies the data.

 ~Idiot ()
 Destructor.

Algorithmic calls
void solve ()
 Get an approximate solution with the idiot code.

void crash (int numberPass, CoinMessageHandler *handler,const CoinMessages *messages)
 Lightweight "crash".

void crossOver (int mode)
Gets and sets of most useful data
double getStartingWeight () const
void setStartingWeight (double value)
double getWeightFactor () const
void setWeightFactor (double value)
double getFeasibilityTolerance () const
void setFeasibilityTolerance (double value)
double getReasonablyFeasible () const
void setReasonablyFeasible (double value)
double getExitInfeasibility () const
void setExitInfeasibility (double value)
int getMajorIterations () const
void setMajorIterations (int value)
int getMinorIterations () const
void setMinorIterations (int value)
int getReduceIterations () const
void setReduceIterations (int value)
int getLogLevel () const
 Amount of information - default of 1 should be okay.

void setLogLevel (int value)
int getLightweight () const
 How lightweight - 0 not, 1 yes, 2 very lightweight.

void setLightweight (int value)
int getStrategy () const
 strategy

void setStrategy (int value)
double getDropEnoughFeasibility () const
 Fine tuning - okay if feasibility drop this factor.

void setDropEnoughFeasibility (double value)
double getDropEnoughWeighted () const
 Fine tuning - okay if weighted obj drop this factor.

void setDropEnoughWeighted (double value)

Private Member Functions

void solve2 (CoinMessageHandler *handler, const CoinMessages *messages)
 Does actual work.

IdiotResult IdiSolve (int nrows, int ncols, double *rowsol, double *colsol, double *pi, double *djs, const double *origcost, const double *rowlower, double *rowupper, const double *lower, const double *upper, const double *element, const int *row, const CoinBigIndex *colcc, const int *length, double *lambda, int maxIts, double mu, double drop, double maxmin, double offset, int strategy, double djTol, double djExit, double djFlag)
int dropping (IdiotResult result, double tolerance, double small, int *nbad)
IdiotResult objval (int nrows, int ncols, double *rowsol, double *colsol, double *pi, double *djs, const double *cost, const double *rowlower, const double *rowupper, const double *lower, const double *upper, const double *elemnt, const int *row, const CoinBigIndex *columnStart, const int *length, int extraBlock, int *rowExtra, double *solExtra, double *elemExtra, double *upperExtra, double *costExtra, double weight)

Private Attributes

OsiSolverInterface * model_
 Underlying model.

double djTolerance_
double mu_
double drop_
double muFactor_
double stopMu_
double smallInfeas_
double reasonableInfeas_
double exitDrop_
double muAtExit_
double exitFeasibility_
double dropEnoughFeasibility_
double dropEnoughWeighted_
int * whenUsed_
int maxBigIts_
int maxIts_
int majorIterations_
int logLevel_
int logFreq_
int checkFrequency_
int lambdaIterations_
int maxIts2_
int strategy_
int lightWeight_

Detailed Description

This class implements a very silly algorithm. It has no merit apart from the fact that it gets an approximate solution to some classes of problems. Better if vaguely homogeneous. It works on problems where volume algorithm works and often gets a better primal solution but it has no dual solution.

It can also be used as a "crash" to get a problem started. This is probably its most useful function.

It is based on the idea that algorithms with terrible convergence properties may be okay at first. Throw in some random dubious tricks and the resulting code may be worth keeping as long as you don't look at it.

Definition at line 45 of file Idiot.hpp.

Member Function Documentation

void Idiot::crossOver (  int  mode  ) 
 

Use simplex to get an optimal solution mode is how many steps the simplex crossover should take to arrive to an extreme point: 0 - chosen,all ever used, all 1 - chosen, all 2 - all 3 - do not do anything - maybe basis + 16 do presolves

Definition at line 781 of file Idiot.cpp.

References ClpMatrixBase::getElements(), ClpMatrixBase::getIndices(), ClpMatrixBase::getVectorLengths(), ClpMatrixBase::getVectorStarts(), and model_.

Referenced by crash(). 

00782 {
00783   double fixTolerance=IDIOT_FIX_TOLERANCE;
00784   double startTime = CoinCpuTime();
00785   ClpSimplex * saveModel=NULL;
00786   ClpMatrixBase * matrix = model_->clpMatrix();
00787   const int * row = matrix->getIndices();
00788   const CoinBigIndex * columnStart = matrix->getVectorStarts();
00789   const int * columnLength = matrix->getVectorLengths(); 
00790   const double * element = matrix->getElements();
00791   const double * rowupper = model_->getRowUpper();
00792   int nrows=model_->getNumRows();
00793   int ncols=model_->getNumCols();
00794   double * rowsol, * colsol;
00795   // different for Osi
00796   double * lower = model_->columnLower();
00797   double * upper = model_->columnUpper();
00798   const double * rowlower= model_->getRowLower();
00799   int * whenUsed=whenUsed_;
00800   rowsol= model_->primalRowSolution();
00801   colsol= model_->primalColumnSolution();;
00802   double * cost=model_->objective();
00803 
00804   int slackEnd,ordStart,ordEnd;
00805   int slackStart = countCostedSlacks(model_);
00806 
00807   int addAll = mode&7;
00808   int presolve=0;
00809 
00810   double djTolerance = djTolerance_;
00811   if (djTolerance>0.0&&djTolerance<1.0)
00812     djTolerance=1.0;
00813   int iteration;
00814   int i, n=0;
00815   double ratio=1.0;
00816   double objValue=0.0;
00817   if ((strategy_&128)!=0) {
00818     fixTolerance=SMALL_IDIOT_FIX_TOLERANCE;
00819   }
00820   if ((mode&16)!=0&&addAll<3) presolve=1;
00821   double * saveUpper = NULL;
00822   double * saveLower = NULL;
00823   if (addAll<3) {
00824     saveUpper = new double [ncols];
00825     saveLower = new double [ncols];
00826     memcpy(saveUpper,upper,ncols*sizeof(double));
00827     memcpy(saveLower,lower,ncols*sizeof(double));
00828   }
00829   if (slackStart>=0) {
00830     slackEnd=slackStart+nrows;
00831     if (slackStart) {
00832       ordStart=0;
00833       ordEnd=slackStart;
00834     } else {
00835       ordStart=nrows;
00836       ordEnd=ncols;
00837     }
00838   } else {
00839     slackEnd=slackStart;
00840     ordStart=0;
00841     ordEnd=ncols;
00842   }
00843   /* get correct rowsol (without known slacks) */
00844   memset(rowsol,0,nrows*sizeof(double));
00845   for (i=ordStart;i<ordEnd;i++) {
00846     CoinBigIndex j;
00847     double value=colsol[i];
00848     if (value<lower[i]+fixTolerance) {
00849       value=lower[i];
00850       colsol[i]=value;
00851     }
00852     for (j=columnStart[i];j<columnStart[i]+columnLength[i];j++) {
00853       int irow=row[j];
00854       rowsol[irow]+=value*element[j];
00855     }
00856   }
00857   if (slackStart>=0) {
00858     for (i=0;i<nrows;i++) {
00859       if (ratio*rowsol[i]>rowlower[i]&&rowsol[i]>1.0e-8) {
00860         ratio=rowlower[i]/rowsol[i];
00861       }
00862     }
00863     for (i=0;i<nrows;i++) {
00864       rowsol[i]*=ratio;
00865     }
00866     for (i=ordStart;i<ordEnd;i++) {
00867       double value=colsol[i]*ratio;
00868       colsol[i]=value;
00869       objValue+=value*cost[i];
00870     }
00871     for (i=0;i<nrows;i++) {
00872       double value=rowlower[i]-rowsol[i];
00873       colsol[i+slackStart]=value;
00874       objValue+=value*cost[i+slackStart];
00875     }
00876     printf("New objective after scaling %g\n",objValue);
00877   }
00878 #if 0
00879    maybe put back - but just get feasible ?
00880   // If not many fixed then just exit
00881   int numberFixed=0;
00882   for (i=ordStart;i<ordEnd;i++) {
00883     if (colsol[i]<lower[i]+fixTolerance) 
00884       numberFixed++;
00885     else if (colsol[i]>upper[i]-fixTolerance) 
00886       numberFixed++;
00887   }
00888   if (numberFixed<ncols/2) {
00889     addAll=3;
00890     presolve=0;
00891   }
00892 #endif
00893   model_->createStatus();
00894   /* addAll
00895      0 - chosen,all used, all 
00896      1 - chosen, all
00897      2 - all
00898      3 - do not do anything  - maybe basis
00899   */
00900   for (i=ordStart;i<ordEnd;i++) {
00901     if (addAll<2) {
00902       if (colsol[i]<lower[i]+fixTolerance) {
00903         upper[i]=lower[i];
00904         colsol[i]=lower[i];
00905       } else if (colsol[i]>upper[i]-fixTolerance) {
00906         lower[i]=upper[i];
00907         colsol[i]=upper[i];
00908       }
00909     }
00910     model_->setColumnStatus(i,ClpSimplex::superBasic);
00911   }
00912   double maxmin;
00913   if (model_->getObjSense()==-1.0) {
00914     maxmin=-1.0;
00915   } else {
00916     maxmin=1.0;
00917   }
00918   if (slackStart>=0) {
00919     for (i=0;i<nrows;i++) {
00920       model_->setRowStatus(i,ClpSimplex::superBasic);
00921     }
00922     for (i=slackStart;i<slackEnd;i++) {
00923       model_->setColumnStatus(i,ClpSimplex::basic);
00924     }
00925   } else {
00926     /* still try and put singletons rather than artificials in basis */
00927     int ninbas=0;
00928     for (i=0;i<nrows;i++) {
00929       model_->setRowStatus(i,ClpSimplex::basic);
00930     }
00931     for (i=0;i<ncols;i++) {
00932       if (columnLength[i]==1&&upper[i]>lower[i]+1.0e-5) {
00933         CoinBigIndex j =columnStart[i];
00934         double value=element[j];
00935         int irow=row[j];
00936         double rlo=rowlower[irow];
00937         double rup=rowupper[irow];
00938         double clo=lower[i];
00939         double cup=upper[i];
00940         double csol=colsol[i];
00941         /* adjust towards feasibility */
00942         double move=0.0;
00943         if (rowsol[irow]>rup) {
00944           move=(rup-rowsol[irow])/value;
00945           if (value>0.0) {
00946             /* reduce */
00947             if (csol+move<clo) move=min(0.0,clo-csol);
00948           } else {
00949             /* increase */
00950             if (csol+move>cup) move=max(0.0,cup-csol);
00951           }
00952         } else if (rowsol[irow]<rlo) {
00953           move=(rlo-rowsol[irow])/value;
00954           if (value>0.0) {
00955             /* increase */
00956             if (csol+move>cup) move=max(0.0,cup-csol);
00957           } else {
00958             /* reduce */
00959             if (csol+move<clo) move=min(0.0,clo-csol);
00960           }
00961         } else {
00962           /* move to improve objective */
00963           if (cost[i]*maxmin>0.0) {
00964             if (value>0.0) {
00965               move=(rlo-rowsol[irow])/value;
00966               /* reduce */
00967               if (csol+move<clo) move=min(0.0,clo-csol);
00968             } else {
00969               move=(rup-rowsol[irow])/value;
00970               /* increase */
00971               if (csol+move>cup) move=max(0.0,cup-csol);
00972             }
00973           } else if (cost[i]*maxmin<0.0) {
00974             if (value>0.0) {
00975               move=(rup-rowsol[irow])/value;
00976               /* increase */
00977               if (csol+move>cup) move=max(0.0,cup-csol);
00978             } else {
00979               move=(rlo-rowsol[irow])/value;
00980               /* reduce */
00981               if (csol+move<clo) move=min(0.0,clo-csol);
00982             }
00983           }
00984         }
00985         rowsol[irow] +=move*value;
00986         colsol[i]+=move;
00987         /* put in basis if row was artificial */
00988         if (rup-rlo<1.0e-7&&model_->getRowStatus(irow)==ClpSimplex::basic) {
00989           model_->setRowStatus(irow,ClpSimplex::superBasic);
00990           model_->setColumnStatus(i,ClpSimplex::basic);
00991           ninbas++;
00992         }
00993       }
00994     }
00995     /*printf("%d in basis\n",ninbas);*/
00996   }
00997   if (addAll<3) {
00998     ClpPresolve pinfo;
00999     if (presolve) {
01000       saveModel = model_;
01001       model_ = pinfo.presolvedModel(*model_,1.0e-8,false,5);
01002     }
01003     if (model_) {
01004       model_->primal(1);
01005       if (presolve) {
01006         pinfo.postsolve(true);
01007         delete model_;
01008         model_ = saveModel;
01009         saveModel=NULL;
01010       }
01011     } else {
01012       // not feasible
01013       addAll=1;
01014       presolve=0;
01015       model_ = saveModel;
01016       saveModel=NULL;
01017     }
01018     if (addAll<2) {
01019       n=0;
01020       if (!addAll ) {
01021         /* could do scans to get a good number */
01022         iteration=1;
01023         for (i=ordStart;i<ordEnd;i++) {
01024           if (whenUsed[i]>=iteration) {
01025             if (upper[i]-lower[i]<1.0e-5&&saveUpper[i]-saveLower[i]>1.0e-5) {
01026               n++;
01027               upper[i]=saveUpper[i];
01028               lower[i]=saveLower[i];
01029             }
01030           }
01031         }
01032       } else {
01033         for (i=ordStart;i<ordEnd;i++) {
01034           if (upper[i]-lower[i]<1.0e-5&&saveUpper[i]-saveLower[i]>1.0e-5) {
01035             n++;
01036             upper[i]=saveUpper[i];
01037             lower[i]=saveLower[i];
01038           }
01039         }
01040       }
01041       printf("Time so far %g, %d now added from previous iterations\n",
01042              CoinCpuTime()-startTime,n);
01043       if (addAll)
01044         presolve=0;
01045       if (presolve) {
01046         saveModel = model_;
01047         model_ = pinfo.presolvedModel(*model_,1.0e-8,false,5);
01048       } else {
01049         presolve=0;
01050       }
01051       model_->primal(1);
01052       if (presolve) {
01053         pinfo.postsolve(true);
01054         delete model_;
01055         model_ = saveModel;
01056         saveModel=NULL;
01057       }
01058       if (!addAll) {
01059         n=0;
01060         for (i=ordStart;i<ordEnd;i++) {
01061           if (upper[i]-lower[i]<1.0e-5&&saveUpper[i]-saveLower[i]>1.0e-5) {
01062             n++;
01063             upper[i]=saveUpper[i];
01064             lower[i]=saveLower[i];
01065           }
01066         }
01067         printf("Time so far %g, %d now added from previous iterations\n",
01068                CoinCpuTime()-startTime,n);
01069       }
01070       if (presolve) {
01071         saveModel = model_;
01072         model_ = pinfo.presolvedModel(*model_,1.0e-8,false,5);
01073       } else {
01074         presolve=0;
01075       }
01076       model_->primal(1);
01077       if (presolve) {
01078         pinfo.postsolve(true);
01079         delete model_;
01080         model_ = saveModel;
01081         saveModel=NULL;
01082       }
01083     }
01084     printf("Total time in crossover %g\n", CoinCpuTime()-startTime);
01085     delete [] saveUpper;
01086     delete [] saveLower;
01087   }
01088   return ;
01089 }

double Idiot::getExitInfeasibility (   )  const [inline]
 

Exit infeasibility - exit if sum of infeasibilities less than this. Default -1.0 (i.e. switched off)

Definition at line 118 of file Idiot.hpp. 

00119   { return exitFeasibility_;};

double Idiot::getFeasibilityTolerance (   )  const [inline]
 

Feasibility tolerance - problem essentially feasible if individual infeasibilities less than this. default 0.1

Definition at line 105 of file Idiot.hpp. 

00106   { return smallInfeas_;};

int Idiot::getMajorIterations (   )  const [inline]
 

Major iterations. stop after this number. Default 30. Use 2-5 for "crash" 50-100 for serious crunching

Definition at line 124 of file Idiot.hpp. 

00125   { return majorIterations_;};

int Idiot::getMinorIterations (   )  const [inline]
 

Minor iterations. Do this number of tiny steps before deciding whether to change weights etc. Default - dubious sqrt(Number of Rows). Good numbers 105 to 405 say (5 is dubious method of making sure idiot is not trying to be clever which it may do every 10 minor iterations)

Definition at line 134 of file Idiot.hpp. 

00135   { return maxIts2_;};

double Idiot::getReasonablyFeasible (   )  const [inline]
 

Reasonably feasible. Dubious method concentrates more on objective when sum of infeasibilities less than this. Very dubious default value of (Number of rows)/20

Definition at line 112 of file Idiot.hpp. 

00113   { return reasonableInfeas_;};

int Idiot::getReduceIterations (   )  const [inline]
 

Reduce weight after this many major iterations. It may get reduced before this but this is a maximum. Default 3. 3-10 plausible.

Definition at line 141 of file Idiot.hpp. 

00142   { return maxBigIts_;};

double Idiot::getStartingWeight (   )  const [inline]
 

Starting weight - small emphasizes feasibility, default 1.0e-4

Definition at line 92 of file Idiot.hpp. 

00093   { return mu_;};

double Idiot::getWeightFactor (   )  const [inline]
 

Weight factor - weight multiplied by this when changes, default 0.333

Definition at line 98 of file Idiot.hpp. 

00099   { return muFactor_;};

The documentation for this class was generated from the following files:
Generated on Wed Dec 3 14:37:50 2003 for CLP by doxygen 1.3.5