Changeset 31 for branches


Ignore:
Timestamp:
Oct 8, 2002 4:16:43 PM (17 years ago)
Author:
forrest
Message:

Presolve nearly ready

Location:
branches/devel-1
Files:
10 edited

Legend:

Unmodified
Added
Removed
  • branches/devel-1/ClpSimplex.cpp

    r29 r31  
    16771677{
    16781678  bool goodMatrix=true;
     1679  int i;
    16791680  if ((what&16)!=0) {
    16801681    // move information to work arrays
     1682    if (optimizationDirection_<0.0) {
     1683      // reverse all dual signs
     1684      for (i=0;i<numberColumns_;i++)
     1685        reducedCost_[i] = -reducedCost_[i];
     1686      for (i=0;i<numberRows_;i++)
     1687        dual_[i] = -dual_[i];
     1688    }
    16811689    // row reduced costs
    16821690    if (!dj_) {
     
    17071715    }
    17081716  }
    1709   int i;
    17101717  if ((what&4)!=0) {
    17111718    delete [] cost_;
     
    18741881  }
    18751882  // direction may have been modified by scaling - clean up
    1876   if (optimizationDirection_>0.0)
     1883  if (optimizationDirection_>0.0) {
    18771884    optimizationDirection_ = 1.0;
    1878   else if (optimizationDirection_<0.0)
     1885  }  else if (optimizationDirection_<0.0) {
    18791886    optimizationDirection_ = -1.0;
     1887    // and reverse all dual signs
     1888    for (i=0;i<numberColumns_;i++)
     1889      reducedCost_[i] = -reducedCost_[i];
     1890    for (i=0;i<numberRows_;i++)
     1891      dual_[i] = -dual_[i];
     1892  }
    18801893  // scaling may have been turned off
    18811894  scalingFlag_ = abs(scalingFlag_);
     
    30953108  checkPrimalSolution( rowActivityWork_, columnActivityWork_);
    30963109  checkDualSolution();
     3110#ifdef CLP_DEBUG
     3111  int i;
     3112  double value=0.0;
     3113  for (i=0;i<numberRows_+numberColumns_;i++)
     3114    value += dj_[i]*solution_[i];
     3115  printf("dual value %g, primal %g\n",value,objectiveValue_);
     3116#endif
    30973117  // release extra memory
    30983118  deleteRim(false);
  • branches/devel-1/Presolve.cpp

    r29 r31  
    595595{
    596596  const PresolveAction *paction = paction_;
    597  
     597
    598598  if (prob.colstat_)
    599599    prob.check_nbasic();
     
    678678  memcpy(originalModel_->dualRowSolution(),prob.rowduals_,
    679679         nrows_*sizeof(double));
     680  double maxmin = originalModel_->getObjSense();
     681  if (maxmin<0.0) {
     682    // swap signs
     683    int i;
     684    double * pi = originalModel_->dualRowSolution();
     685    for (i=0;i<nrows_;i++)
     686      pi[i] = -pi[i];
     687  }
    680688  // Now check solution
    681   double maxmin = originalModel_->getObjSense();
    682689  memcpy(originalModel_->dualColumnSolution(),
    683690         originalModel_->objective(),ncols_*sizeof(double));
    684   originalModel_->transposeTimes(-maxmin,
     691  originalModel_->transposeTimes(-1.0,
    685692                                 originalModel_->dualRowSolution(),
    686693                                 originalModel_->dualColumnSolution());
  • branches/devel-1/PresolveEmpty.cpp

    r29 r31  
    182182  double *rcosts        = prob->rcosts_;
    183183  unsigned char *colstat        = prob->colstat_;
     184  const double maxmin = prob->maxmin_;
    184185
    185186  int ncols2 = ncols+nactions;
     
    232233    cost[jcol] = e->cost;
    233234
    234     rcosts[jcol] = cost[jcol];
     235    rcosts[jcol] = maxmin*cost[jcol];
    235236
    236237    hincol[jcol] = 0;
  • branches/devel-1/PresolveForcing.cpp

    r29 r31  
    222222
    223223  const double tol      = ZTOLDP;
    224 #if     TOLEXP
    225   const double inftol   = prob->ztolzb_;
    226 #else
    227   const double inftol   = ZTOLDP;
    228 #endif
     224  const double inftol   = prob->feasibilityTolerance_;
    229225  const int ncols       = prob->ncols_;
    230226
  • branches/devel-1/PresolveImpliedFree.cpp

    r29 r31  
    292292               costj, rhs, coeffj);
    293293#endif
    294 
     294        prob->change_bias(costj * rhs / coeffj);
    295295        // ??
    296296        cost[j] = 0.0;
     
    449449           
    450450      PRESOLVEASSERT(fabs(coeff) > ZTOLDP);
    451       if (rlo[irow] < rup[irow] && dcost[icol] * maxmin < 0.0) {
     451      // choose rowdual to make this col basic
     452      rowduals[irow] = maxmin*dcost[icol] / coeff;
     453      rcosts[icol] = 0.0;
     454      if ((rlo[irow] < rup[irow] && rowduals[irow] < 0.0)
     455          || rlo[irow]< -1.0e20) {
     456        if (rlo[irow]<-1.0e20&&rowduals[irow]>=0.0)
     457          printf("IMP %g %g %g\n",rlo[irow],rup[irow],rowduals[irow]);
    452458        sol[icol] = (rup[irow] - act) / coeff;
    453459        acts[irow] = rup[irow];
     
    457463      }
    458464
    459       // choose rowdual to make this col basic
    460       rowduals[irow] = dcost[icol] / coeff;
    461       rcosts[icol] = 0.0;
    462465
    463466      prob->setRowStatus(irow,PrePostsolveMatrix::atLowerBound);
  • branches/devel-1/PresolveMatrix.cpp

    r29 r31  
    724724  rcosts_ = new double[ncols0_];
    725725  CoinDisjointCopyN(si.getReducedCost(), ncols1, rcosts_);
     726  if (maxmin_<0.0) {
     727    // change so will look as if minimize
     728    int i;
     729    for (i=0;i<nrows1;i++)
     730      rowduals_[i] = - rowduals_[i];
     731    for (i=0;i<ncols1;i++) {
     732      rcosts_[i] = - rcosts_[i];
     733    }
     734  }
    726735
    727736  //CoinDisjointCopyN(si.getRowUpper(), nrows1, rup_);
  • branches/devel-1/PresolveSingleton.cpp

    r29 r31  
    6363  notFinished = false;
    6464
    65   int fixed_cols[ncols];
     65  int * fixed_cols = new int [ncols];
    6666  int nfixed_cols       = 0;
    6767
     
    215215                                         next);
    216216  }
     217  delete [] fixed_cols;
    217218  return (next);
    218219}
  • branches/devel-1/PresolveSubst.cpp

    r29 r31  
    833833            }
    834834
    835         // substitute away jcoly in the other rows
    836         for (int k=kcs; k<kce; ++k)
    837           if (hrow[k] != rowy) {
    838             int rowx = hrow[k];
    839             double coeffx = colels[k];
    840             double coeff_factor = -coeffx / coeffy;     // backwards from doubleton
     835            // substitute away jcoly in the other rows
     836            // Use ap as mcstrt etc may move if compacted
     837            kce = hincol[jcoly];
     838            int k;
     839            action *ap = &actions[nactions-1];
     840            for (k=0; k<kce; ++k) {
     841              int rowx = ap->rows[k];
     842              //assert(rowx==hrow[k+kcs]);
     843              //assert(ap->coeffxs[k]==colels[k+kcs]);
     844              if (rowx != rowy) {
     845                double coeffx = ap->coeffxs[k];
     846                double coeff_factor = -coeffx / coeffy; // backwards from doubleton
    841847
    842848#if     DEBUG_PRESOLVE
    843             {
    844               int krs = mrstrt[rowx];
    845               int kre = krs + hinrow[rowx];
    846               printf("HROW (%d %d %d):  ", rowx, hinrow[rowx], jcoly);
    847               for (int k=krs; k<kre; ++k) {
    848                 int jcol = hcol[k];
    849                 double coeff = rowels[k];
    850                 printf("%d ", jcol);
     849                {
     850                  int krs = mrstrt[rowx];
     851                  int kre = krs + hinrow[rowx];
     852                  printf("HROW (%d %d %d):  ", rowx, hinrow[rowx], jcoly);
     853                  for (int k=krs; k<kre; ++k) {
     854                    int jcol = hcol[k];
     855                    double coeff = rowels[k];
     856                    printf("%d ", jcol);
     857                  }
     858                  printf("\n");
     859#if 0
     860                  for (int k=krs; k<kre; ++k) {
     861                    int jcol = hcol[k];
     862                    prob->addCol(jcol);
     863                    double coeff = rowels[k];
     864                    printf("%g ", coeff);
     865                  }
     866                  printf("\n");
     867#endif
     868                }
     869#endif
     870                {
     871                  int krsx = mrstrt[rowx];
     872                  int krex = krsx + hinrow[rowx];
     873                  int i;
     874                  for (i=krsx;i<krex;i++)
     875                    prob->addCol(hcol[i]);
     876                  if (hincol[jcoly] != 2)
     877                    CoinSort_2(hcol+krsx,hcol+krsx+hinrow[rowx],rowels+krsx);
     878                  //ekk_sort2(hcol+krsx, rowels+krsx, hinrow[rowx]);
     879                }
     880               
     881                // add (coeff_factor * <rowy>) to rowx
     882                // does not affect rowy
     883                // may introduce (or cancel) elements in rowx
     884                add_row(mrstrt,
     885                        rlo, rup,
     886                        rowels, hcol,
     887                        hinrow,
     888                        rlink, nrows,
     889                        coeff_factor,
     890                        rowx, rowy,
     891                        x_to_y);
     892               
     893                // update col rep of rowx from row rep:
     894                // for every col in rowy, copy the elem for that col in rowx
     895                // from the row rep to the col rep
     896                {
     897                  int krs = mrstrt[rowy];
     898                  int kre = krs + hinrow[rowy];
     899                  int niny = hinrow[rowy];
     900                 
     901                  int krsx = mrstrt[rowx];
     902                  int krex = krsx + hinrow[rowx];
     903                  for (int ki=0; ki<niny; ++ki) {
     904                    int k = krs + ki;
     905                    int jcol = hcol[k];
     906                    prob->addCol(jcol);
     907                    int kcs = mcstrt[jcol];
     908                    int kce = kcs + hincol[jcol];
     909                   
     910                    //double coeff = rowels[presolve_find_row(jcol, krsx, krex, hcol)];
     911                    if (hcol[krsx + x_to_y[ki]] != jcol)
     912                      abort();
     913                    double coeff = rowels[krsx + x_to_y[ki]];
     914                   
     915                    // see if rowx appeared in jcol in the col rep
     916                    int k2 = presolve_find_row1(rowx, kcs, kce, hrow);
     917                   
     918                    //PRESOLVEASSERT(fabs(coeff) > ZTOLDP);
     919                   
     920                    if (k2 < kce) {
     921                      // yes - just update the entry
     922                      colels[k2] = coeff;
     923                    } else {
     924                      // no - make room, then append
     925                      expand_row(mcstrt, colels, hrow, hincol, clink, ncols, jcol);
     926                      kcs = mcstrt[jcol];
     927                      kce = kcs + hincol[jcol];
     928                     
     929                      hrow[kce] = rowx;
     930                      colels[kce] = coeff;
     931                      hincol[jcol]++;
     932                    }
     933                  }
     934                }
     935                // now colels[k] == 0.0
     936
     937#if 1
     938                // now remove jcoly from rowx in the row rep
     939                // better if this were first
     940                presolve_delete_from_row(rowx, jcoly, mrstrt, hinrow, hcol, rowels);
     941#endif
     942#if     DEBUG_PRESOLVE
     943                {
     944                  int krs = mrstrt[rowx];
     945                  int kre = krs + hinrow[rowx];
     946                  printf("HROW (%d %d %d):  ", rowx, hinrow[rowx], jcoly);
     947                  for (int k=krs; k<kre; ++k) {
     948                    int jcol = hcol[k];
     949                    double coeff = rowels[k];
     950                    printf("%d ", jcol);
     951                  }
     952                  printf("\n");
     953#if 0
     954                  for (int k=krs; k<kre; ++k) {
     955                    int jcol = hcol[k];
     956                    double coeff = rowels[k];
     957                    printf("%g ", coeff);
     958                  }
     959                  printf("\n");
     960#endif
     961                }
     962#endif
     963               
     964                // don't have to update col rep, since entire col deleted later
    851965              }
    852               printf("\n");
    853 #if 0
    854               for (int k=krs; k<kre; ++k) {
    855                 int jcol = hcol[k];
    856                 prob->addCol(jcol);
    857                 double coeff = rowels[k];
    858                 printf("%g ", coeff);
    859               }
    860               printf("\n");
    861 #endif
    862966            }
    863 #endif
    864             {
    865                 int krsx = mrstrt[rowx];
    866                 int krex = krsx + hinrow[rowx];
    867                 int i;
    868                 for (i=krsx;i<krex;i++)
    869                   prob->addCol(hcol[i]);
    870                 if (hincol[jcoly] != 2)
    871                   CoinSort_2(hcol+krsx,hcol+krsx+hinrow[rowx],rowels+krsx);
    872                 //ekk_sort2(hcol+krsx, rowels+krsx, hinrow[rowx]);
    873             }
    874 
    875             // add (coeff_factor * <rowy>) to rowx
    876             // does not affect rowy
    877             // may introduce (or cancel) elements in rowx
    878             add_row(mrstrt,
    879                     rlo, rup,
    880                     rowels, hcol,
    881                     hinrow,
    882                     rlink, nrows,
    883                     coeff_factor,
    884                     rowx, rowy,
    885                     x_to_y);
    886 
    887             // update col rep of rowx from row rep:
    888             // for every col in rowy, copy the elem for that col in rowx
    889             // from the row rep to the col rep
     967
     968#if     DEBUG_PRESOLVE
     969            printf("\n");
     970#endif
     971
     972            // the addition of rows may have created zero coefficients
     973            bcopy(&hcol[mrstrt[rowy]], &zerocols[nzerocols], hinrow[rowy]*sizeof(int));
     974            nzerocols += hinrow[rowy];
     975           
     976            // delete rowy in col rep
    890977            {
    891978              int krs = mrstrt[rowy];
    892979              int kre = krs + hinrow[rowy];
    893               int niny = hinrow[rowy];
    894 
    895               int krsx = mrstrt[rowx];
    896               int krex = krsx + hinrow[rowx];
    897               for (int ki=0; ki<niny; ++ki) {
    898                 int k = krs + ki;
     980              for (int k=krs; k<kre; ++k) {
    899981                int jcol = hcol[k];
    900                 prob->addCol(jcol);
    901                 int kcs = mcstrt[jcol];
    902                 int kce = kcs + hincol[jcol];
    903 
    904                 //double coeff = rowels[presolve_find_row(jcol, krsx, krex, hcol)];
    905                 if (hcol[krsx + x_to_y[ki]] != jcol)
    906                   abort();
    907                 double coeff = rowels[krsx + x_to_y[ki]];
    908 
    909                 // see if rowx appeared in jcol in the col rep
    910                 int k2 = presolve_find_row1(rowx, kcs, kce, hrow);
    911 
    912                 //PRESOLVEASSERT(fabs(coeff) > ZTOLDP);
    913 
    914                 if (k2 < kce) {
    915                   // yes - just update the entry
    916                   colels[k2] = coeff;
    917                 } else {
    918                   // no - make room, then append
    919                   expand_row(mcstrt, colels, hrow, hincol, clink, ncols, jcol);
    920                   kcs = mcstrt[jcol];
    921                   kce = kcs + hincol[jcol];
    922 
    923                   hrow[kce] = rowx;
    924                   colels[kce] = coeff;
    925                   hincol[jcol]++;
    926                 }
     982               
     983                // delete rowy from the jcol
     984                presolve_delete_from_row(jcol, rowy, mcstrt, hincol, hrow, colels);
    927985              }
    928986            }
    929             // now colels[k] == 0.0
    930 
    931 #if 1
    932             // now remove jcoly from rowx in the row rep
    933             // better if this were first
    934             presolve_delete_from_row(rowx, jcoly, mrstrt, hinrow, hcol, rowels);
    935 #endif
    936 #if     DEBUG_PRESOLVE
    937 {
    938               int krs = mrstrt[rowx];
    939               int kre = krs + hinrow[rowx];
    940               printf("HROW (%d %d %d):  ", rowx, hinrow[rowx], jcoly);
    941               for (int k=krs; k<kre; ++k) {
    942                 int jcol = hcol[k];
    943                 double coeff = rowels[k];
    944                 printf("%d ", jcol);
     987            // delete rowy in row rep
     988            hinrow[rowy] = 0;
     989           
     990            // This last is entirely dual to doubleton, but for the cost adjustment
     991           
     992            // eliminate col entirely from the col rep
     993            PRESOLVE_REMOVE_LINK(clink, jcoly);
     994            hincol[jcoly] = 0;
     995           
     996            // eliminate rowy entirely from the row rep
     997            PRESOLVE_REMOVE_LINK(rlink, rowy);
     998            //cost[irowy] = 0.0;
     999           
     1000            rlo[rowy] = 0.0;
     1001            rup[rowy] = 0.0;
     1002           
     1003#if     0 && DEBUG_PRESOLVE
     1004            printf("ROWY COLS:  ");
     1005            for (int k=0; k<save_ninrowy; ++k)
     1006              if (rowycols[k] != col) {
     1007                printf("%d ", rowycols[k]);
     1008                (void)presolve_find_row(rowycols[k], mrstrt[rowx], mrstrt[rowx]+hinrow[rowx],
     1009                                        hcol);
    9451010              }
    946               printf("\n");
    947 #if 0
    948               for (int k=krs; k<kre; ++k) {
    949                 int jcol = hcol[k];
    950                 double coeff = rowels[k];
    951                 printf("%g ", coeff);
    952               }
    953               printf("\n");
    954 #endif
    955             }
    956 #endif
    957 
    958             // don't have to update col rep, since entire col deleted later
    959           }
    960 
    961 #if     DEBUG_PRESOLVE
    962         printf("\n");
    963 #endif
    964 
    965         // the addition of rows may have created zero coefficients
    966         bcopy(&hcol[mrstrt[rowy]], &zerocols[nzerocols], hinrow[rowy]*sizeof(int));
    967         nzerocols += hinrow[rowy];
    968 
    969         // delete rowy in col rep
    970         {
    971           int krs = mrstrt[rowy];
    972           int kre = krs + hinrow[rowy];
    973           for (int k=krs; k<kre; ++k) {
    974             int jcol = hcol[k];
    975 
    976             // delete rowy from the jcol
    977             presolve_delete_from_row(jcol, rowy, mcstrt, hincol, hrow, colels);
    978           }
    979         }
    980         // delete rowy in row rep
    981         hinrow[rowy] = 0;
    982    
    983         // This last is entirely dual to doubleton, but for the cost adjustment
    984 
    985         // eliminate col entirely from the col rep
    986         PRESOLVE_REMOVE_LINK(clink, jcoly);
    987         hincol[jcoly] = 0;
    988 
    989         // eliminate rowy entirely from the row rep
    990         PRESOLVE_REMOVE_LINK(rlink, rowy);
    991         //cost[irowy] = 0.0;
    992 
    993         rlo[rowy] = 0.0;
    994         rup[rowy] = 0.0;
    995 
    996 #if     0 && DEBUG_PRESOLVE
    997         printf("ROWY COLS:  ");
    998         for (int k=0; k<save_ninrowy; ++k)
    999           if (rowycols[k] != col) {
    1000             printf("%d ", rowycols[k]);
    1001             (void)presolve_find_row(rowycols[k], mrstrt[rowx], mrstrt[rowx]+hinrow[rowx],
    1002                            hcol);
    1003           }
    1004         printf("\n");
    1005 #endif
    1006 
     1011            printf("\n");
     1012#endif
    10071013#if 0
    10081014        presolve_links_ok(clink, mcstrt, hincol, ncols);
     
    10691075  const double ztolzb   = prob->ztolzb_;
    10701076  const double ztoldj   = prob->ztoldj_;
     1077  const double maxmin = prob->maxmin_;
    10711078
    10721079  for (const action *f = &actions[nactions-1]; actions<=f; f--) {
     
    12551262    {
    12561263      int k;
    1257       double dj = dcost[icol];
     1264      double dj = maxmin*dcost[icol];
    12581265      double bounds_factor = rhsy/coeffy;
    12591266      for (int i=0; i<nincoly; ++i)
  • branches/devel-1/Test/unitTest.cpp

    r30 r31  
    143143
    144144#if 1
     145    mpsName.push_back("80bau3b");min.push_back(true);nRows.push_back(2263);nCols.push_back(9799);objValueTol.push_back(1.e-10);objValue.push_back(9.8722419241E+05);
    145146    mpsName.push_back("blend");min.push_back(true);nRows.push_back(75);nCols.push_back(83);objValueTol.push_back(1.e-10);objValue.push_back(-3.0812149846e+01);
    146147    mpsName.push_back("pilotnov");min.push_back(true);nRows.push_back(976);nCols.push_back(2172);objValueTol.push_back(1.e-10);objValue.push_back(-4.4972761882e+03);
     
    150151    mpsName.push_back("pilot4");min.push_back(true);nRows.push_back(411);nCols.push_back(1000);objValueTol.push_back(1.e-8);objValue.push_back(-2.5811392641e+03);
    151152    mpsName.push_back("pilot87");min.push_back(true);nRows.push_back(2031);nCols.push_back(4883);objValueTol.push_back(1.e-4);objValue.push_back(3.0171072827e+02);
    152     mpsName.push_back("80bau3b");min.push_back(true);nRows.push_back(2263);nCols.push_back(9799);objValueTol.push_back(1.e-10);objValue.push_back(9.8722419241E+05);
    153153    mpsName.push_back("adlittle");min.push_back(true);nRows.push_back(57);nCols.push_back(97);objValueTol.push_back(1.e-10);objValue.push_back(2.2549496316e+05);
    154154    mpsName.push_back("afiro");min.push_back(true);nRows.push_back(28);nCols.push_back(32);objValueTol.push_back(1.e-10);objValue.push_back(-4.6475314286e+02);
     
    255255
    256256      solution.setDblParam(ClpObjOffset,mps.objectiveOffset());
     257#if 0
     258      solution.setOptimizationDirection(-1);
     259      {
     260        int j;
     261        double * obj = solution.objective();
     262        int n=solution.numberColumns();
     263        for (j=0;j<n;j++)
     264          obj[j] *= -1.0;
     265      }
     266#endif
    257267      if (doPresolve) {
    258268#ifdef USE_PRESOLVE
  • branches/devel-1/include/PresolveMatrix.hpp

    r29 r31  
    163163  const double ztoldj_;
    164164
    165   const double maxmin_;
     165  double maxmin_;
    166166
    167167  int whichpass_;       // mostly for debugging
Note: See TracChangeset for help on using the changeset viewer.