Ignore:
Timestamp:
Mar 11, 2006 4:45:45 PM (14 years ago)
Author:
forrest
Message:

makes some problems faster

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/ClpSimplexDual.cpp

    r736 r740  
    10151015        rowArray_[0]->createPacked(1,&pivotRow_,&direction);
    10161016        factorization_->updateColumnTranspose(rowArray_[1],rowArray_[0]);
     1017        // Allow to do dualColumn0
     1018        if (numberThreads_<-1)
     1019          spareIntArray_[0]=1;
     1020        spareDoubleArray_[0]=acceptablePivot;
     1021        rowArray_[3]->clear();
     1022        sequenceIn_=-1;
    10171023        // put row of tableau in rowArray[0] and columnArray[0]
    10181024        matrix_->transposeTimes(this,-1.0,
    10191025                              rowArray_[0],rowArray_[3],columnArray_[0]);
    10201026        // do ratio test for normal iteration
    1021         bestPossiblePivot = dualColumn(rowArray_[0],columnArray_[0],columnArray_[1],
    1022                  rowArray_[3],acceptablePivot,dubiousWeights);
     1027        bestPossiblePivot = dualColumn(rowArray_[0],columnArray_[0],rowArray_[3],
     1028                 columnArray_[1],acceptablePivot,dubiousWeights);
    10231029      } else {
    10241030        // Make sure direction plausible
     
    23882394  }
    23892395}
    2390 /*
    2391    Row array has row part of pivot row (as duals so sign may be switched)
    2392    Column array has column part.
    2393    This chooses pivot column.
    2394    Spare array will be needed when we start getting clever.
    2395    We will check for basic so spare array will never overflow.
    2396    If necessary will modify costs
    2397 */
    2398 double
    2399 ClpSimplexDual::dualColumn(CoinIndexedVector * rowArray,
    2400                            CoinIndexedVector * columnArray,
     2396int
     2397ClpSimplexDual::dualColumn0(const CoinIndexedVector * rowArray,
     2398                           const CoinIndexedVector * columnArray,
    24012399                           CoinIndexedVector * spareArray,
    2402                            CoinIndexedVector * spareArray2,
    24032400                           double acceptablePivot,
    2404                            CoinBigIndex * dubiousWeights)
     2401                           double & upperReturn, double &bestReturn)
    24052402{
    2406   double * work;
     2403  // do first pass to get possibles
     2404  double * spare = spareArray->denseVector();
     2405  int * index = spareArray->getIndices();
     2406  const double * work;
    24072407  int number;
    2408   int * which;
    2409   double * reducedCost;
    2410   int iSection;
    2411 
    2412   sequenceIn_=-1;
    2413   int numberPossiblySwapped=0;
    2414   int numberRemaining=0;
    2415  
    2416   double totalThru=0.0; // for when variables flip
    2417   //double saveAcceptable=acceptablePivot;
    2418   //acceptablePivot=1.0e-9;
    2419 
    2420   double bestEverPivot=acceptablePivot;
    2421   int lastSequence = -1;
    2422   double lastPivot=0.0;
    2423   double upperTheta;
    2424   double newTolerance = dualTolerance_;
    2425   //newTolerance = dualTolerance_+1.0e-6*dblParam_[ClpDualTolerance];
    2426   // will we need to increase tolerance
    2427   bool thisIncrease=false;
    2428   // If we think we need to modify costs (not if something from broad sweep)
    2429   bool modifyCosts=false;
    2430   // Increase in objective due to swapping bounds (may be negative)
    2431   double increaseInObjective=0.0;
    2432 
    2433   // use spareArrays to put ones looked at in
    2434   // we are going to flip flop between
    2435   int iFlip = 0;
    2436   // Possible list of pivots
    2437   int interesting[2];
    2438   // where possible swapped ones are
    2439   int swapped[2];
    2440   // for zeroing out arrays after
    2441   int marker[2][2];
    2442   // pivot elements
    2443   double * array[2], * spare, * spare2;
    2444   // indices
    2445   int * indices[2], * index, * index2;
    2446   spareArray->clear();
    2447   spareArray2->clear();
    2448   array[0] = spareArray->denseVector();
    2449   indices[0] = spareArray->getIndices();
    2450   spare = array[0];
    2451   index = indices[0];
    2452   array[1] = spareArray2->denseVector();
    2453   indices[1] = spareArray2->getIndices();
    2454   int i;
    2455   const double * lower;
    2456   const double * upper;
    2457 
    2458   // initialize lists
    2459   for (i=0;i<2;i++) {
    2460     interesting[i]=0;
    2461     swapped[i]=numberColumns_;
    2462     marker[i][0]=0;
    2463     marker[i][1]=numberColumns_;
    2464   }
    2465 
    2466   /*
    2467     First we get a list of possible pivots.  We can also see if the
    2468     problem looks infeasible or whether we want to pivot in free variable.
    2469     This may make objective go backwards but can only happen a finite
    2470     number of times and I do want free variables basic.
    2471 
    2472     Then we flip back and forth.  At the start of each iteration
    2473     interesting[iFlip] should have possible candidates and swapped[iFlip]
    2474     will have pivots if we decide to take a previous pivot.
    2475     At end of each iteration interesting[1-iFlip] should have
    2476     candidates if we go through this theta and swapped[1-iFlip]
    2477     pivots if we don't go through.
    2478 
    2479     At first we increase theta and see what happens.  We start
    2480     theta at a reasonable guess.  If in right area then we do bit by bit.
    2481 
    2482    */
    2483 
    2484   // do first pass to get possibles
     2408  const int * which;
     2409  const double * reducedCost;
    24852410  // We can also see if infeasible or pivoting on free
    24862411  double tentativeTheta = 1.0e25;
    2487   upperTheta = 1.0e31;
     2412  double upperTheta = 1.0e31;
    24882413  double freePivot = acceptablePivot;
    24892414  double bestPossible=0.0;
    2490 
    2491   for (iSection=0;iSection<2;iSection++) {
     2415  int numberRemaining=0;
     2416  int i;
     2417  for (int iSection=0;iSection<2;iSection++) {
    24922418
    24932419    int addSequence;
    24942420
    24952421    if (!iSection) {
    2496       lower = rowLowerWork_;
    2497       upper = rowUpperWork_;
    24982422      work = rowArray->denseVector();
    24992423      number = rowArray->getNumElements();
     
    25022426      addSequence = numberColumns_;
    25032427    } else {
    2504       lower = columnLowerWork_;
    2505       upper = columnUpperWork_;
    25062428      work = columnArray->denseVector();
    25072429      number = columnArray->getNumElements();
     
    25562478        value = oldValue-tentativeTheta*alpha;
    25572479        //assert (oldValue<=dualTolerance_*1.0001);
    2558         if (value>newTolerance) {
     2480        if (value>dualTolerance_) {
    25592481          bestPossible = CoinMax(bestPossible,-alpha);
    25602482          value = oldValue-upperTheta*alpha;
    2561           if (value>newTolerance && -alpha>=acceptablePivot)
    2562             upperTheta = (oldValue-newTolerance)/alpha;
     2483          if (value>dualTolerance_ && -alpha>=acceptablePivot)
     2484            upperTheta = (oldValue-dualTolerance_)/alpha;
    25632485          // add to list
    25642486          spare[numberRemaining]=alpha;
     
    25712493        value = oldValue-tentativeTheta*alpha;
    25722494        //assert (oldValue>=-dualTolerance_*1.0001);
    2573         if (value<-newTolerance) {
     2495        if (value<-dualTolerance_) {
    25742496          bestPossible = CoinMax(bestPossible,alpha);
    25752497          value = oldValue-upperTheta*alpha;
    2576           if (value<-newTolerance && alpha>=acceptablePivot)
    2577             upperTheta = (oldValue+newTolerance)/alpha;
     2498          if (value<-dualTolerance_ && alpha>=acceptablePivot)
     2499            upperTheta = (oldValue+dualTolerance_)/alpha;
    25782500          // add to list
    25792501          spare[numberRemaining]=alpha;
     
    25842506    }
    25852507  }
     2508  upperReturn = upperTheta;
     2509  bestReturn = bestPossible;
     2510  return numberRemaining;
     2511}
     2512/*
     2513   Row array has row part of pivot row (as duals so sign may be switched)
     2514   Column array has column part.
     2515   This chooses pivot column.
     2516   Spare array will be needed when we start getting clever.
     2517   We will check for basic so spare array will never overflow.
     2518   If necessary will modify costs
     2519*/
     2520double
     2521ClpSimplexDual::dualColumn(CoinIndexedVector * rowArray,
     2522                           CoinIndexedVector * columnArray,
     2523                           CoinIndexedVector * spareArray,
     2524                           CoinIndexedVector * spareArray2,
     2525                           double acceptablePivot,
     2526                           CoinBigIndex * dubiousWeights)
     2527{
     2528  int numberPossiblySwapped=0;
     2529  int numberRemaining=0;
     2530 
     2531  double totalThru=0.0; // for when variables flip
     2532  //double saveAcceptable=acceptablePivot;
     2533  //acceptablePivot=1.0e-9;
     2534
     2535  double bestEverPivot=acceptablePivot;
     2536  int lastSequence = -1;
     2537  double lastPivot=0.0;
     2538  double upperTheta;
     2539  double newTolerance = dualTolerance_;
     2540  //newTolerance = dualTolerance_+1.0e-6*dblParam_[ClpDualTolerance];
     2541  // will we need to increase tolerance
     2542  bool thisIncrease=false;
     2543  // If we think we need to modify costs (not if something from broad sweep)
     2544  bool modifyCosts=false;
     2545  // Increase in objective due to swapping bounds (may be negative)
     2546  double increaseInObjective=0.0;
     2547
     2548  // use spareArrays to put ones looked at in
     2549  // we are going to flip flop between
     2550  int iFlip = 0;
     2551  // Possible list of pivots
     2552  int interesting[2];
     2553  // where possible swapped ones are
     2554  int swapped[2];
     2555  // for zeroing out arrays after
     2556  int marker[2][2];
     2557  // pivot elements
     2558  double * array[2], * spare, * spare2;
     2559  // indices
     2560  int * indices[2], * index, * index2;
     2561  spareArray2->clear();
     2562  array[0] = spareArray->denseVector();
     2563  indices[0] = spareArray->getIndices();
     2564  spare = array[0];
     2565  index = indices[0];
     2566  array[1] = spareArray2->denseVector();
     2567  indices[1] = spareArray2->getIndices();
     2568  int i;
     2569
     2570  // initialize lists
     2571  for (i=0;i<2;i++) {
     2572    interesting[i]=0;
     2573    swapped[i]=numberColumns_;
     2574    marker[i][0]=0;
     2575    marker[i][1]=numberColumns_;
     2576  }
     2577  /*
     2578    First we get a list of possible pivots.  We can also see if the
     2579    problem looks infeasible or whether we want to pivot in free variable.
     2580    This may make objective go backwards but can only happen a finite
     2581    number of times and I do want free variables basic.
     2582
     2583    Then we flip back and forth.  At the start of each iteration
     2584    interesting[iFlip] should have possible candidates and swapped[iFlip]
     2585    will have pivots if we decide to take a previous pivot.
     2586    At end of each iteration interesting[1-iFlip] should have
     2587    candidates if we go through this theta and swapped[1-iFlip]
     2588    pivots if we don't go through.
     2589
     2590    At first we increase theta and see what happens.  We start
     2591    theta at a reasonable guess.  If in right area then we do bit by bit.
     2592
     2593   */
     2594
     2595  // do first pass to get possibles
     2596  upperTheta = 1.0e31;
     2597  double bestPossible=0.0;
     2598  if (spareIntArray_[0]!=-1) {
     2599    numberRemaining = dualColumn0(rowArray,columnArray,spareArray,
     2600                                  acceptablePivot,upperTheta,bestPossible);
     2601  } else {
     2602    // already done
     2603    numberRemaining = spareArray->getNumElements();
     2604    spareArray->setNumElements(0);
     2605    upperTheta = spareDoubleArray_[0];
     2606    bestPossible = spareDoubleArray_[1];
     2607    theta_ = spareDoubleArray_[2];
     2608    alpha_ = spareDoubleArray_[3];
     2609    sequenceIn_ = spareIntArray_[1];
     2610  }
     2611  // switch off
     2612  spareIntArray_[0]=0;
     2613  // We can also see if infeasible or pivoting on free
     2614  double tentativeTheta = 1.0e25;
    25862615  interesting[0]=numberRemaining;
    25872616  marker[0][0] = numberRemaining;
     
    26242653      // 1 bias increase by ones with slightly wrong djs
    26252654      // 2 bias by all
    2626       // 3 bias by all - tolerance
     2655      // 3 bias by all - tolerance 
    26272656#define TRYBIAS 3
    26282657
Note: See TracChangeset for help on using the changeset viewer.