Changeset 216


Ignore:
Timestamp:
Nov 24, 2005 6:55:32 AM (14 years ago)
Author:
forrest
Message:

add branching stuff

Location:
trunk
Files:
10 edited

Legend:

Unmodified
Added
Removed
  • trunk/CbcBranchActual.cpp

    r201 r216  
    25872587  printf("\n");
    25882588}
     2589// Default Constructor
     2590CbcNWay::CbcNWay ()
     2591  : CbcObject(),
     2592    numberMembers_(0),
     2593    members_(NULL),
     2594    consequence_(NULL)
     2595{
     2596}
     2597
     2598// Useful constructor (which are integer indices)
     2599CbcNWay::CbcNWay (CbcModel * model, int numberMembers,
     2600                  const int * which, int identifier)
     2601  : CbcObject(model)
     2602{
     2603  id_=identifier;
     2604  numberMembers_=numberMembers;
     2605  if (numberMembers_) {
     2606    members_ = new int[numberMembers_];
     2607    memcpy(members_,which,numberMembers_*sizeof(int));
     2608  } else {
     2609    members_ = NULL;
     2610  }
     2611  consequence_ = NULL;
     2612}
     2613
     2614// Copy constructor
     2615CbcNWay::CbcNWay ( const CbcNWay & rhs)
     2616  :CbcObject(rhs)
     2617{
     2618  numberMembers_ = rhs.numberMembers_;
     2619  consequence_ = NULL;
     2620  if (numberMembers_) {
     2621    members_ = new int[numberMembers_];
     2622    memcpy(members_,rhs.members_,numberMembers_*sizeof(int));
     2623    if (rhs.consequence_) {
     2624      consequence_ = new CbcConsequence * [numberMembers_];
     2625      for (int i=0;i<numberMembers_;i++) {
     2626        if (rhs.consequence_[i])
     2627          consequence_[i]= rhs.consequence_[i]->clone();
     2628        else
     2629          consequence_[i]=NULL;
     2630      }
     2631    }
     2632  } else {
     2633    members_ = NULL;
     2634  }
     2635}
     2636
     2637// Clone
     2638CbcObject *
     2639CbcNWay::clone() const
     2640{
     2641  return new CbcNWay(*this);
     2642}
     2643
     2644// Assignment operator
     2645CbcNWay &
     2646CbcNWay::operator=( const CbcNWay& rhs)
     2647{
     2648  if (this!=&rhs) {
     2649    CbcObject::operator=(rhs);
     2650    delete [] members_;
     2651    numberMembers_ = rhs.numberMembers_;
     2652    if (consequence_) {
     2653      for (int i=0;i<numberMembers_;i++)
     2654        delete consequence_[i];
     2655      delete [] consequence_;
     2656      consequence_=NULL;
     2657    }
     2658    if (numberMembers_) {
     2659      members_ = new int[numberMembers_];
     2660      memcpy(members_,rhs.members_,numberMembers_*sizeof(int));
     2661    } else {
     2662      members_ = NULL;
     2663    }
     2664    if (rhs.consequence_) {
     2665      consequence_ = new CbcConsequence * [numberMembers_];
     2666      for (int i=0;i<numberMembers_;i++) {
     2667        if (rhs.consequence_[i])
     2668          consequence_[i]= rhs.consequence_[i]->clone();
     2669        else
     2670          consequence_[i]=NULL;
     2671      }
     2672    }
     2673  }
     2674  return *this;
     2675}
     2676
     2677// Destructor
     2678CbcNWay::~CbcNWay ()
     2679{
     2680  delete [] members_;
     2681  if (consequence_) {
     2682    for (int i=0;i<numberMembers_;i++)
     2683      delete consequence_[i];
     2684    delete [] consequence_;
     2685  }
     2686}
     2687// Set up a consequence for a single member
     2688void
     2689CbcNWay::setConsequence(int iColumn, const CbcConsequence & consequence)
     2690{
     2691  if (!consequence_) {
     2692    consequence_ = new CbcConsequence * [numberMembers_];
     2693    for (int i=0;i<numberMembers_;i++)
     2694      consequence_[i]=NULL;
     2695  }
     2696  for (int i=0;i<numberMembers_;i++) {
     2697    if (members_[i]==iColumn) {
     2698      consequence_[i]=consequence.clone();
     2699      break;
     2700    }
     2701  }
     2702}
     2703
     2704// Applies a consequence for a single member
     2705void
     2706CbcNWay::applyConsequence(int iSequence, int state) const
     2707{
     2708  assert (state==-9999||state==9999);
     2709  if (consequence_) {
     2710    CbcConsequence * consequence = consequence_[iSequence];
     2711    if (consequence)
     2712      consequence->applyToSolver(model_->solver(),state);
     2713  }
     2714}
     2715 
     2716// Infeasibility - large is 0.5
     2717double
     2718CbcNWay::infeasibility(int & preferredWay) const
     2719{
     2720  int numberUnsatis=0;
     2721  int j;
     2722  OsiSolverInterface * solver = model_->solver();
     2723  const double * solution = model_->testSolution();
     2724  const double * lower = solver->getColLower();
     2725  const double * upper = solver->getColUpper();
     2726  double largestValue=0.0;
     2727 
     2728  double integerTolerance =
     2729    model_->getDblParam(CbcModel::CbcIntegerTolerance);
     2730
     2731  for (j=0;j<numberMembers_;j++) {
     2732    int iColumn = members_[j];
     2733    double value = solution[iColumn];
     2734    value = CoinMax(value, lower[iColumn]);
     2735    value = CoinMin(value, upper[iColumn]);
     2736    double distance = CoinMin(value-lower[iColumn],upper[iColumn]-value);
     2737    if (distance>integerTolerance) {
     2738      numberUnsatis++;
     2739      largestValue = CoinMax(distance,largestValue);
     2740    }
     2741  }
     2742  preferredWay=1;
     2743  if (numberUnsatis) {
     2744    return largestValue;
     2745  } else {
     2746    return 0.0; // satisfied
     2747  }
     2748}
     2749
     2750// This looks at solution and sets bounds to contain solution
     2751void
     2752CbcNWay::feasibleRegion()
     2753{
     2754  int j;
     2755  OsiSolverInterface * solver = model_->solver();
     2756  const double * solution = model_->testSolution();
     2757  const double * lower = solver->getColLower();
     2758  const double * upper = solver->getColUpper();
     2759  double integerTolerance =
     2760    model_->getDblParam(CbcModel::CbcIntegerTolerance);
     2761  for (j=0;j<numberMembers_;j++) {
     2762    int iColumn = members_[j];
     2763    double value = solution[iColumn];
     2764    value = CoinMax(value, lower[iColumn]);
     2765    value = CoinMin(value, upper[iColumn]);
     2766    if (value>=upper[iColumn]-integerTolerance) {
     2767      solver->setColLower(iColumn,upper[iColumn]);
     2768    } else {
     2769      assert (value<=lower[iColumn]+integerTolerance);
     2770      solver->setColUpper(iColumn,lower[iColumn]);
     2771    }
     2772  }
     2773}
     2774
     2775
     2776// Creates a branching object
     2777CbcBranchingObject *
     2778CbcNWay::createBranch(int way)
     2779{
     2780  int numberFree=0;
     2781  int j;
     2782
     2783  OsiSolverInterface * solver = model_->solver();
     2784  const double * solution = model_->testSolution();
     2785  const double * lower = solver->getColLower();
     2786  const double * upper = solver->getColUpper();
     2787  int * list = new int[numberMembers_];
     2788  double * sort = new double[numberMembers_];
     2789
     2790  for (j=0;j<numberMembers_;j++) {
     2791    int iColumn = members_[j];
     2792    double value = solution[iColumn];
     2793    value = CoinMax(value, lower[iColumn]);
     2794    value = CoinMin(value, upper[iColumn]);
     2795    if (upper[iColumn]>lower[iColumn]) {
     2796      double distance = CoinMin(value-lower[iColumn],upper[iColumn]-value);
     2797      list[numberFree]=j;
     2798      sort[numberFree++]=distance;
     2799    }
     2800  }
     2801  assert (numberFree);
     2802  // sort
     2803  CoinSort_2(sort,sort+numberFree,list);
     2804  // create object
     2805  CbcBranchingObject * branch;
     2806  branch = new CbcNWayBranchingObject(model_,this,numberFree,list);
     2807  delete [] list;
     2808  delete [] sort;
     2809  return branch;
     2810}
     2811 
     2812// Default Constructor
     2813CbcNWayBranchingObject::CbcNWayBranchingObject()
     2814  :CbcBranchingObject()
     2815{
     2816  order_=NULL;
     2817  object_=NULL;
     2818  numberInSet_=0;
     2819  way_=0;
     2820}
     2821
     2822// Useful constructor
     2823CbcNWayBranchingObject::CbcNWayBranchingObject (CbcModel * model,
     2824                                                const CbcNWay * nway,
     2825                                                int number, const int * order)
     2826  :CbcBranchingObject(model,nway->id(),-1,0.5)
     2827{
     2828  order_ = new int [number];
     2829  object_=nway;
     2830  numberInSet_=number;
     2831  memcpy(order_,order,number*sizeof(int));
     2832  numberBranchesLeft_=number;
     2833}
     2834
     2835// Copy constructor
     2836CbcNWayBranchingObject::CbcNWayBranchingObject ( const CbcNWayBranchingObject & rhs) :CbcBranchingObject(rhs)
     2837{
     2838  numberInSet_=rhs.numberInSet_;
     2839  object_=rhs.object_;
     2840  if (numberInSet_) {
     2841    order_ = new int [numberInSet_];
     2842    memcpy(order_,rhs.order_,numberInSet_*sizeof(int));
     2843  } else {
     2844    order_=NULL;
     2845  }   
     2846}
     2847
     2848// Assignment operator
     2849CbcNWayBranchingObject &
     2850CbcNWayBranchingObject::operator=( const CbcNWayBranchingObject& rhs)
     2851{
     2852  if (this != &rhs) {
     2853    CbcBranchingObject::operator=(rhs);
     2854    object_=rhs.object_;
     2855    delete [] order_;
     2856    numberInSet_=rhs.numberInSet_;
     2857    if (numberInSet_) {
     2858      order_ = new int [numberInSet_];
     2859      memcpy(order_,rhs.order_,numberInSet_*sizeof(int));
     2860    } else {
     2861      order_=NULL;
     2862    }   
     2863  }
     2864  return *this;
     2865}
     2866CbcBranchingObject *
     2867CbcNWayBranchingObject::clone() const
     2868{
     2869  return (new CbcNWayBranchingObject(*this));
     2870}
     2871
     2872
     2873// Destructor
     2874CbcNWayBranchingObject::~CbcNWayBranchingObject ()
     2875{
     2876  delete [] order_;
     2877}
     2878double
     2879CbcNWayBranchingObject::branch(bool normalBranch)
     2880{
     2881  if (model_->messageHandler()->logLevel()>2&&normalBranch)
     2882    print(normalBranch);
     2883  numberBranchesLeft_--;
     2884  assert (numberBranchesLeft_>=0);
     2885  int which = numberBranchesLeft_;
     2886  if (numberBranchesLeft_==numberInSet_) {
     2887    // first branch so way_ may mean something
     2888    assert (way_==-1||way_==1);
     2889    if (way_==1)
     2890      which--;
     2891  } else if (numberBranchesLeft_+1==numberInSet_) {
     2892    // second branch so way_ may mean something
     2893    assert (way_==-1||way_==1);
     2894    if (way_==-1)
     2895      which++;
     2896    // switch way off
     2897    way_=0;
     2898  }
     2899  const double * lower = model_->solver()->getColLower();
     2900  const double * upper = model_->solver()->getColUpper();
     2901  const int * members = object_->members();
     2902  for (int j=0;j<numberInSet_;j++) {
     2903    int iSequence = order_[j];
     2904    int iColumn = members[iSequence];
     2905    if (j!=numberBranchesLeft_) {
     2906      model_->solver()->setColUpper(iColumn,lower[iColumn]);
     2907      //model_->solver()->setColLower(iColumn,lower[iColumn]);
     2908      assert (lower[iColumn]>-1.0e20);
     2909      // apply any consequences
     2910      object_->applyConsequence(iSequence,-9999);
     2911    } else {
     2912      model_->solver()->setColLower(iColumn,upper[iColumn]);
     2913      //model_->solver()->setColUpper(iColumn,upper[iColumn]);
     2914#ifdef FULL_PRINT
     2915      printf("Up Fix %d to %g\n",iColumn,upper[iColumn]);
     2916#endif
     2917      assert (upper[iColumn]<1.0e20);
     2918      // apply any consequences
     2919      object_->applyConsequence(iSequence,9999);
     2920    }
     2921  }
     2922  return 0.0;
     2923}
     2924void
     2925CbcNWayBranchingObject::print(bool normalBranch)
     2926{
     2927  printf("NWay - Up Fix ");
     2928  const int * members = object_->members();
     2929  for (int j=0;j<way_;j++) {
     2930    int iColumn = members[order_[j]];
     2931    printf("%d ",iColumn);
     2932  }
     2933  printf("\n");
     2934}
     2935
     2936// Default Constructor
     2937CbcFixVariable::CbcFixVariable ()
     2938  : CbcConsequence(),
     2939    numberStates_(0),
     2940    states_(NULL),
     2941    startLower_(NULL),
     2942    startUpper_(NULL),
     2943    newBound_(NULL),
     2944    variable_(NULL)
     2945{
     2946}
     2947
     2948// One useful Constructor
     2949CbcFixVariable::CbcFixVariable (int numberStates,const int * states, const int * numberNewLower,
     2950                                const int ** newLowerValue,
     2951                                const int ** lowerColumn,
     2952                                const int * numberNewUpper, const int ** newUpperValue,
     2953                                const int ** upperColumn)
     2954  : CbcConsequence(),
     2955    states_(NULL),
     2956    startLower_(NULL),
     2957    startUpper_(NULL),
     2958    newBound_(NULL),
     2959    variable_(NULL)
     2960{
     2961  // How much space
     2962  numberStates_ = numberStates;
     2963  if (numberStates_) {
     2964    states_ = new int[numberStates_];
     2965    memcpy(states_,states,numberStates_*sizeof(int));
     2966    int i;
     2967    int n=0;
     2968    startLower_ = new int[numberStates_+1];
     2969    startUpper_ = new int[numberStates_+1];
     2970    startLower_[0]=0;
     2971    //count
     2972    for (i=0;i<numberStates_;i++) {
     2973      n += numberNewLower[i];
     2974      startUpper_[i]=n;
     2975      n += numberNewUpper[i];
     2976      startLower_[i+1]=n;
     2977    }
     2978    newBound_ = new double [n];
     2979    variable_ = new int [n];
     2980    n=0;
     2981    for (i=0;i<numberStates_;i++) {
     2982      int j;
     2983      int k;
     2984      const int * bound;
     2985      const int * variable;
     2986      k=numberNewLower[i];
     2987      bound = newLowerValue[i];
     2988      variable = lowerColumn[i];
     2989      for (j=0;j<k;j++) {
     2990        newBound_[n]=bound[j];
     2991        variable_[n++]=variable[j];
     2992      }
     2993      k=numberNewUpper[i];
     2994      bound = newUpperValue[i];
     2995      variable = upperColumn[i];
     2996      for (j=0;j<k;j++) {
     2997        newBound_[n]=bound[j];
     2998        variable_[n++]=variable[j];
     2999      }
     3000    }
     3001  }
     3002}
     3003
     3004// Copy constructor
     3005CbcFixVariable::CbcFixVariable ( const CbcFixVariable & rhs)
     3006  :CbcConsequence(rhs)
     3007{
     3008  numberStates_ = rhs.numberStates_;
     3009  states_ = NULL;
     3010  startLower_ = NULL;
     3011  startUpper_ = NULL;
     3012  newBound_ = NULL;
     3013  variable_ = NULL;
     3014  if (numberStates_) {
     3015    states_ = CoinCopyOfArray(rhs.states_,numberStates_);
     3016    startLower_ = CoinCopyOfArray(rhs.startLower_,numberStates_+1);
     3017    startUpper_ = CoinCopyOfArray(rhs.startUpper_,numberStates_+1);
     3018    int n=startLower_[numberStates_];
     3019    newBound_ = CoinCopyOfArray(rhs.newBound_,n);
     3020    variable_ = CoinCopyOfArray(rhs.variable_,n);
     3021  }
     3022}
     3023
     3024// Clone
     3025CbcConsequence *
     3026CbcFixVariable::clone() const
     3027{
     3028  return new CbcFixVariable(*this);
     3029}
     3030
     3031// Assignment operator
     3032CbcFixVariable &
     3033CbcFixVariable::operator=( const CbcFixVariable& rhs)
     3034{
     3035  if (this!=&rhs) {
     3036    CbcConsequence::operator=(rhs);
     3037    delete [] states_;
     3038    delete [] startLower_;
     3039    delete [] startUpper_;
     3040    delete [] newBound_;
     3041    delete [] variable_;
     3042    states_ = NULL;
     3043    startLower_ = NULL;
     3044    startUpper_ = NULL;
     3045    newBound_ = NULL;
     3046    variable_ = NULL;
     3047    numberStates_ = rhs.numberStates_;
     3048    if (numberStates_) {
     3049      states_ = CoinCopyOfArray(rhs.states_,numberStates_);
     3050      startLower_ = CoinCopyOfArray(rhs.startLower_,numberStates_+1);
     3051      startUpper_ = CoinCopyOfArray(rhs.startUpper_,numberStates_+1);
     3052      int n=startLower_[numberStates_];
     3053      newBound_ = CoinCopyOfArray(rhs.newBound_,n);
     3054      variable_ = CoinCopyOfArray(rhs.variable_,n);
     3055    }
     3056  }
     3057  return *this;
     3058}
     3059
     3060// Destructor
     3061CbcFixVariable::~CbcFixVariable ()
     3062{
     3063  delete [] states_;
     3064  delete [] startLower_;
     3065  delete [] startUpper_;
     3066  delete [] newBound_;
     3067  delete [] variable_;
     3068}
     3069// Set up a startLower for a single member
     3070void
     3071CbcFixVariable::applyToSolver(OsiSolverInterface * solver, int state) const
     3072{
     3073  assert (state==-9999||state==9999);
     3074  // Find state
     3075  int find;
     3076  for (find=0;find<numberStates_;find++)
     3077    if (states_[find]==state)
     3078      break;
     3079  if (find==numberStates_)
     3080    return;
     3081  int i;
     3082  // Set new lower bounds
     3083  for (i=startLower_[find];i<startUpper_[find];i++) {
     3084    int iColumn = variable_[i];
     3085    double value = newBound_[i];
     3086    double oldValue = solver->getColLower()[iColumn];
     3087    //printf("for %d old lower bound %g, new %g",iColumn,oldValue,value);
     3088    solver->setColLower(iColumn,CoinMax(value,oldValue));
     3089    //printf(" => %g\n",solver->getColLower()[iColumn]);
     3090  }
     3091  // Set new upper bounds
     3092  for (i=startUpper_[find];i<startLower_[find+1];i++) {
     3093    int iColumn = variable_[i];
     3094    double value = newBound_[i];
     3095    double oldValue = solver->getColUpper()[iColumn];
     3096    //printf("for %d old upper bound %g, new %g",iColumn,oldValue,value);
     3097    solver->setColUpper(iColumn,CoinMin(value,oldValue));
     3098    //printf(" => %g\n",solver->getColUpper()[iColumn]);
     3099  }
     3100}
  • trunk/CbcBranchBase.cpp

    r129 r216  
    9797  way_=0;
    9898  value_=0.0;
    99   numberBranchesLeft_=0;
     99  numberBranchesLeft_=2;
    100100}
    101101
     
    189189}
    190190
     191// Default constructor
     192CbcConsequence::CbcConsequence()
     193{
     194}
     195
     196
     197// Destructor
     198CbcConsequence::~CbcConsequence ()
     199{
     200}
     201
     202// Copy constructor
     203CbcConsequence::CbcConsequence ( const CbcConsequence & rhs)
     204{
     205}
     206
     207// Assignment operator
     208CbcConsequence &
     209CbcConsequence::operator=( const CbcConsequence& rhs)
     210{
     211  if (this!=&rhs) {
     212  }
     213  return *this;
     214}
     215
    191216 
  • trunk/CbcBranchCut.cpp

    r149 r216  
    131131  down_=OsiRowCut();
    132132  up_=OsiRowCut();
     133  canFix_=false;
    133134}
    134135
     
    136137CbcCutBranchingObject::CbcCutBranchingObject (CbcModel * model,
    137138                                              OsiRowCut & down,
    138                                               OsiRowCut &up)
     139                                              OsiRowCut &up,
     140                                              bool canFix)
    139141  :CbcBranchingObject(model,0,-1,0.0)
    140142{
    141143  down_ = down;
    142144  up_ = up;
     145  canFix_ = canFix;
    143146}
    144147
     
    148151  down_ = rhs.down_;
    149152  up_ = rhs.up_;
     153  canFix_ = rhs.canFix_;
    150154}
    151155
     
    158162    down_ = rhs.down_;
    159163    up_ = rhs.up_;
     164    canFix_ = rhs.canFix_;
    160165  }
    161166  return *this;
     
    217222  }
    218223  // assume cut was cunningly constructed so we need not worry too much about tolerances
    219   if (low+1.0e-8>=ub) {
     224  if (low+1.0e-8>=ub&&canFix_) {
    220225    // fix
    221226    for (int i=0;i<n;i++) {
     
    228233      }
    229234    }
    230   } else if (high-1.0e-8<=lb) {
     235  } else if (high-1.0e-8<=lb&&canFix_) {
    231236    // fix
    232237    for (int i=0;i<n;i++) {
     
    253258    cut = &down_;
    254259    printf("CbcCut would branch down");
    255     way_=1;
    256260  } else {
    257261    cut = &up_;
    258262    printf("CbcCut would branch up");
    259     way_=-1;      // Swap direction
    260263  }
    261264  double lb = cut->lb();
     
    355358    fractionFixed_ = rhs.fractionFixed_;
    356359    int numberColumns = model_->getNumCols();
     360    delete [] mark_;
    357361    mark_ = CoinCopyOfArray(rhs.mark_,numberColumns);
    358362    matrixByRow_=rhs.matrixByRow_;
     
    503507  up.setLb(rhs +1.0);
    504508  up.setUb(COIN_DBL_MAX);
     509  // Say can fix one way
    505510  CbcCutBranchingObject * newObject =
    506     new CbcCutBranchingObject(model_,down,up);
     511    new CbcCutBranchingObject(model_,down,up,true);
    507512  if (model_->messageHandler()->logLevel()>1)
    508513    printf("creating cut in CbcBranchCut\n");
     
    658663    return 1.0e20;
    659664}
     665
     666/** Default Constructor
     667*/
     668CbcBranchAllDifferent::CbcBranchAllDifferent ()
     669  : CbcBranchCut(),
     670    numberInSet_(0),
     671    which_(NULL)
     672{
     673}
     674
     675/* Useful constructor - passed set of variables
     676*/
     677CbcBranchAllDifferent::CbcBranchAllDifferent (CbcModel * model, int numberInSet,
     678                                              const int * members)
     679  : CbcBranchCut(model)
     680{
     681  numberInSet_=numberInSet;
     682  which_ = CoinCopyOfArray(members,numberInSet_);
     683}
     684// Copy constructor
     685CbcBranchAllDifferent::CbcBranchAllDifferent ( const CbcBranchAllDifferent & rhs)
     686  :CbcBranchCut(rhs)
     687{
     688  numberInSet_=rhs.numberInSet_;
     689  which_ = CoinCopyOfArray(rhs.which_,numberInSet_);
     690}
     691
     692// Clone
     693CbcObject *
     694CbcBranchAllDifferent::clone() const
     695{
     696  return new CbcBranchAllDifferent(*this);
     697}
     698
     699// Assignment operator
     700CbcBranchAllDifferent &
     701CbcBranchAllDifferent::operator=( const CbcBranchAllDifferent& rhs)
     702{
     703  if (this!=&rhs) {
     704    CbcBranchCut::operator=(rhs);
     705    delete [] which_;
     706    numberInSet_=rhs.numberInSet_;
     707    which_ = CoinCopyOfArray(rhs.which_,numberInSet_);
     708  }
     709  return *this;
     710}
     711
     712// Destructor
     713CbcBranchAllDifferent::~CbcBranchAllDifferent ()
     714{
     715  delete [] which_;
     716}
     717// Creates a branching object
     718CbcBranchingObject *
     719CbcBranchAllDifferent::createBranch(int way)
     720{
     721  // by default way must be -1
     722  assert (way==-1);
     723  const double * solution = model_->testSolution();
     724  double * values = new double[numberInSet_];
     725  int * which = new int[numberInSet_];
     726  int i;
     727  for (i=0;i<numberInSet_;i++) {
     728    int iColumn = which_[i];
     729    values[i]=solution[iColumn];
     730    which[i]=iColumn;
     731  }
     732  CoinSort_2(values,values+numberInSet_,which);
     733  double last = -1.0;
     734  double closest=1.0;
     735  int worst=-1;
     736  for (i=0;i<numberInSet_;i++) {
     737    if (values[i]-last<closest) {
     738      closest=values[i]-last;
     739      worst=i-1;
     740    }
     741    last=values[i];
     742  }
     743  assert (closest<=0.99999);
     744  OsiRowCut down;
     745  down.setLb(-COIN_DBL_MAX);
     746  down.setUb(-1.0);
     747  int pair[2];
     748  double elements[]={1.0,-1.0};
     749  pair[0]=which[worst];
     750  pair[1]=which[worst+1];
     751  delete [] values;
     752  delete [] which;
     753  down.setRow(2,pair,elements);
     754  // up is same - just with rhs changed
     755  OsiRowCut up = down;
     756  up.setLb(1.0);
     757  up.setUb(COIN_DBL_MAX);
     758  // Say is not a fix type branch
     759  CbcCutBranchingObject * newObject =
     760    new CbcCutBranchingObject(model_,down,up,false);
     761  if (model_->messageHandler()->logLevel()>1)
     762    printf("creating cut in CbcBranchCut\n");
     763  return newObject;
     764}
     765// Infeasibility - large is 0.5
     766double
     767CbcBranchAllDifferent::infeasibility(int & preferredWay) const
     768{
     769  preferredWay=-1;
     770  //OsiSolverInterface * solver = model_->solver();
     771  const double * solution = model_->testSolution();
     772  //const double * lower = solver->getColLower();
     773  //const double * upper = solver->getColUpper();
     774  double * values = new double[numberInSet_];
     775  int i;
     776  for (i=0;i<numberInSet_;i++) {
     777    int iColumn = which_[i];
     778    values[i]=solution[iColumn];
     779  }
     780  std::sort(values,values+numberInSet_);
     781  double last = -1.0;
     782  double closest=1.0;
     783  for (i=0;i<numberInSet_;i++) {
     784    if (values[i]-last<closest) {
     785      closest=values[i]-last;
     786    }
     787    last=values[i];
     788  }
     789  delete [] values;
     790  if (closest>0.99999)
     791    return 0.0;
     792  else
     793    return 0.5*(1.0-closest);
     794}
  • trunk/CbcModel.cpp

    r210 r216  
    932932                             CoinMax(fabs(bestObjective_),fabs(bestPossibleObjective_))
    933933                             *dblParam_[CbcAllowableFractionGap]);
    934     if (bestObjective_-bestPossibleObjective_ < testGap) {
     934    if (bestObjective_-bestPossibleObjective_ < testGap && getCutoffIncrement()>=0.0) {
    935935      stoppedOnGap = true ;
    936936    }
     
    11591159            newNode->createInfo(this,node,lastws,lowerBefore,upperBefore,
    11601160                                numberOldActiveCuts,numberNewCuts) ;
    1161             if (newNode->numberUnsatisfied())
     1161            if (newNode->numberUnsatisfied()) {
     1162              newNode->initializeInfo() ;
    11621163              newNode->nodeInfo()->addCuts(cuts,newNode->numberBranches(),
    1163                                            whichGenerator) ; } }
     1164                                           whichGenerator) ; } } }
    11641165        else
    11651166        { anyAction = -2 ; }
     
    12941295            lastHeuristic_ = NULL;
    12951296            incrementUsed(solver_->getColSolution());
    1296             assert(nodeInfo->numberPointingToThis() <= 2) ;
     1297            //assert(nodeInfo->numberPointingToThis() <= 2) ;
    12971298            // avoid accidental pruning, if newNode was final branch arm
    12981299            nodeInfo->increment();
     
    27852786      CoinWarmStartBasis::Status status =
    27862787        lastws->getArtifStatus(i+numberRowsAtContinuous_);
    2787       if (status != CoinWarmStartBasis::basic&&addedCuts_[i]) {
     2788      if (addedCuts_[i]&&(status != CoinWarmStartBasis::basic||addedCuts_[i]->effectiveness()==COIN_DBL_MAX)) {
    27882789#       ifdef CHECK_CUT_COUNTS
    27892790        printf("Using cut %d %x as row %d\n",i,addedCuts_[i],
     
    29612962  int violated = 0 ;
    29622963  int numberRowsAtStart = solver_->getNumRows() ;
     2964  //printf("solver had %d rows\n",numberRowsAtStart);
    29632965  int numberColumns = solver_->getNumCols() ;
    29642966  CoinBigIndex numberElementsAtStart = solver_->getNumElements();
     
    31483150      // branch was a cut - add it
    31493151      theseCuts.insert(*nextRowCut_);
    3150       //nextRowCut_->print();
     3152      if (handler_->logLevel()>1)
     3153        nextRowCut_->print();
    31513154      const OsiRowCut * cut=nextRowCut_;
    31523155      const double * solution = solver_->getColSolution();
     
    45854588      // replace
    45864589      int iColumn = obj1->columnNumber();
     4590      int priority = obj1->priority();
    45874591      delete object_[iObject];
    45884592      CbcSimpleIntegerDynamicPseudoCost * newObject =
    45894593        new CbcSimpleIntegerDynamicPseudoCost(this,iObject,iColumn,0.3);
    45904594      newObject->setNumberBeforeTrust(numberBeforeTrust_);
     4595      newObject->setPriority(priority);
    45914596      object_[iObject] = newObject;
    45924597    }
  • trunk/CbcNode.cpp

    r211 r216  
    611611    }
    612612  }
    613   for (i=0;i<numberCuts_;i++)
     613  for (i=0;i<numberCuts_;i++) {
    614614    addCuts[currentNumberCuts+i]= cuts_[i];
     615    if (model->messageHandler()->logLevel()>1) {
     616      printf("from papply ");
     617      cuts_[i]->print();
     618    }
     619  }
     620   
    615621  currentNumberCuts += numberCuts_;
    616622  return ;
     
    10941100      if ( !model->object(choice[i].objectNumber)->boundBranch())
    10951101        numberStrong=0; // switch off
     1102      if ( choice[i].possibleBranch->numberBranches()>2)
     1103        numberStrong=0; // switch off
    10961104      // Do best choice in case switched off
    10971105      if (choice[i].upMovement>worstInfeasibility) {
     
    13981406        // repeat the whole exercise, forcing the variable up
    13991407        if (!clp) {
    1400           choice[i].possibleBranch->branch();
    14011408          bool feasible=true;
    1402           if (checkFeasibility) {
    1403             // check branching did not make infeasible
    1404             int iColumn;
    1405             int numberColumns = solver->getNumCols();
    1406             const double * columnLower = solver->getColLower();
    1407             const double * columnUpper = solver->getColUpper();
    1408             for (iColumn= 0;iColumn<numberColumns;iColumn++) {
    1409               if (columnLower[iColumn]>columnUpper[iColumn]+1.0e-5)
    1410                 feasible=false;
     1409          // If odd branching then maybe just one possibility
     1410          if(choice[i].possibleBranch->numberBranchesLeft()>0) {
     1411            choice[i].possibleBranch->branch();
     1412            if (checkFeasibility) {
     1413              // check branching did not make infeasible
     1414              int iColumn;
     1415              int numberColumns = solver->getNumCols();
     1416              const double * columnLower = solver->getColLower();
     1417              const double * columnUpper = solver->getColUpper();
     1418              for (iColumn= 0;iColumn<numberColumns;iColumn++) {
     1419                if (columnLower[iColumn]>columnUpper[iColumn]+1.0e-5)
     1420                  feasible=false;
     1421              }
    14111422            }
     1423          } else {
     1424            // second branch infeasible
     1425            feasible=false;
    14121426          }
    14131427          if (feasible) {
     
    14931507          caller.
    14941508        */
     1509        // reset
     1510        choice[i].possibleBranch->resetNumberBranchesLeft();
    14951511        if (choice[i].upMovement<1.0e100) {
    14961512          if(choice[i].downMovement<1.0e100) {
     
    24372453          caller.
    24382454        */
     2455        // reset
     2456        choice.possibleBranch->resetNumberBranchesLeft();
    24392457        if (choice.upMovement<1.0e100) {
    24402458          if(choice.downMovement<1.0e100) {
  • trunk/Test/CoinSolve.cpp

    r212 r216  
    1515#include "CoinHelperFunctions.hpp"
    1616// Same version as CBC
    17 #define CBCVERSION "1.00.00"
     17#define CBCVERSION "1.00.01"
    1818
    1919#include "CoinMpsIO.hpp"
     
    7171#include "CbcTreeLocal.hpp"
    7272#include "CbcCompareActual.hpp"
     73#include "CbcBranchActual.hpp"
    7374#include  "CbcOrClpParam.hpp"
    7475#include  "CbcCutGenerator.hpp"
     
    421422    // set reasonable defaults
    422423    int preSolve=5;
    423     int preProcess=1;
     424    int preProcess=4;
    424425    bool preSolveFile=false;
    425426   
     
    484485    parameters[whichParam(INCREMENT,numberParameters,parameters)].setDoubleValue(model.getDblParam(CbcModel::CbcCutoffIncrement));
    485486    // Set up likely cut generators and defaults
    486     parameters[whichParam(PREPROCESS,numberParameters,parameters)].setCurrentOption("on");
     487    parameters[whichParam(PREPROCESS,numberParameters,parameters)].setCurrentOption("sos");
    487488
    488489    CglGomory gomoryGen;
     
    12641265                /* Do not try and produce equality cliques and
    12651266                   do up to 10 passes */
    1266                 OsiSolverInterface * solver2 = process.preProcess(*saveSolver,preProcess==3,10);
     1267                OsiSolverInterface * solver2;
     1268                {
     1269                  // Tell solver we are in Branch and Cut
     1270                  saveSolver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo) ;
     1271                  // Default set of cut generators
     1272                  CglProbing generator1;
     1273                  generator1.setUsingObjective(true);
     1274                  generator1.setMaxPass(3);
     1275                  generator1.setMaxProbeRoot(saveSolver->getNumCols());
     1276                  generator1.setMaxElements(100);
     1277                  generator1.setMaxLookRoot(50);
     1278                  generator1.setRowCuts(3);
     1279                  // Add in generators
     1280                  process.addCutGenerator(&generator1);
     1281                  int translate[]={9999,0,0,-1,2};
     1282                  solver2 = process.preProcessNonDefault(*saveSolver,translate[preProcess],10);
     1283                  // Tell solver we are not in Branch and Cut
     1284                  saveSolver->setHintParam(OsiDoInBranchAndCut,false,OsiHintDo) ;
     1285                  if (solver2)
     1286                    solver2->setHintParam(OsiDoInBranchAndCut,false,OsiHintDo) ;
     1287                }
    12671288                if (!solver2) {
    12681289                  printf("Pre-processing says infeasible\n");
     
    14951516              OsiSolverInterface * strengthenedModel=NULL;
    14961517              if (type==BAB) {
     1518                if (preProcess&&process.numberSOS()) {
     1519                  int numberSOS = process.numberSOS();
     1520                  int numberIntegers = babModel->numberIntegers();
     1521                  /* model may not have created objects
     1522                     If none then create
     1523                  */
     1524                  if (!numberIntegers||!babModel->numberObjects()) {
     1525                    babModel->findIntegers(true);
     1526                    numberIntegers = babModel->numberIntegers();
     1527                  }
     1528                  CbcObject ** oldObjects = babModel->objects();
     1529                  // Do sets and priorities
     1530                  CbcObject ** objects = new CbcObject * [numberSOS];
     1531                  // set old objects to have low priority
     1532                  int numberOldObjects = babModel->numberObjects();
     1533                  int numberColumns = babModel->getNumCols();
     1534                  for (int iObj = 0;iObj<numberOldObjects;iObj++)
     1535                    oldObjects[iObj]->setPriority(numberColumns+1);
     1536                  const int * starts = process.startSOS();
     1537                  const int * which = process.whichSOS();
     1538                  const int * type = process.typeSOS();
     1539                  const double * weight = process.weightSOS();
     1540                  int iSOS;
     1541                  for (iSOS =0;iSOS<numberSOS;iSOS++) {
     1542                    int iStart = starts[iSOS];
     1543                    int n=starts[iSOS+1]-iStart;
     1544                    objects[iSOS] = new CbcSOS(babModel,n,which+iStart,weight+iStart,
     1545                                               iSOS,type[iSOS]);
     1546                    // branch on long sets first
     1547                    objects[iSOS]->setPriority(numberColumns-n);
     1548                  }
     1549                  babModel->addObjects(numberSOS,objects);
     1550                  for (iSOS=0;iSOS<numberSOS;iSOS++)
     1551                    delete objects[iSOS];
     1552                  delete [] objects;
     1553                }
    14971554                babModel->branchAndBound();
    14981555              } else {
     
    25192576  The testing next version may be activated by CBC_NEXT_VERSION
    25202577  This applies to OsiClp, Clp etc
     2578  Version 1.00.01 November 24 2005
     2579  Added several classes for advanced users.  This can't affect code (if you don't use it)
     2580  Made some tiny changes (for N way branching) which should not change anything.
     2581  CbcNWay object class - for N way branching this also allows use of CbcConsequence class.
     2582  CbcBranchAllDifferent object class - for branching on general integer variables
     2583  to stop them having same value so branches are x >= y+1 and x <= y-1.
     2584  Added two new Cgl classes - CglAllDifferent which does column fixing (too slowly)
     2585  and CglStored which just has a list of cuts which can be activated.
     2586  Modified preprocess option to SOS
    25212587*/
  • trunk/include/CbcBranchActual.hpp

    r129 r216  
    275275};
    276276
     277/** Define an n-way class for variables.
     278    Only valid value is one at UB others at LB
     279    Normally 0-1
     280*/
     281
     282
     283class CbcNWay : public CbcObject {
     284
     285public:
     286
     287  // Default Constructor
     288  CbcNWay ();
     289
     290  /** Useful constructor (which are matrix indices)
     291  */
     292  CbcNWay (CbcModel * model, int numberMembers,
     293             const int * which, int identifier);
     294 
     295  // Copy constructor
     296  CbcNWay ( const CbcNWay &);
     297   
     298  /// Clone
     299  virtual CbcObject * clone() const;
     300
     301  /// Assignment operator
     302  CbcNWay & operator=( const CbcNWay& rhs);
     303
     304  /// Destructor
     305  ~CbcNWay ();
     306
     307  /// Set up a consequence for a single member
     308  void setConsequence(int iColumn, const CbcConsequence & consequence);
     309 
     310  /// Applies a consequence for a single member
     311  void applyConsequence(int iSequence, int state) const;
     312 
     313  /// Infeasibility - large is 0.5 (and 0.5 will give this)
     314  virtual double infeasibility(int & preferredWay) const;
     315
     316  /// This looks at solution and sets bounds to contain solution
     317  virtual void feasibleRegion();
     318  /// Creates a branching object
     319  virtual CbcBranchingObject * createBranch(int way) ;
     320  /// Number of members
     321  inline int numberMembers() const
     322  {return numberMembers_;};
     323
     324  /// Members (indices in range 0 ... numberColumns-1)
     325  inline const int * members() const
     326  {return members_;};
     327
     328protected:
     329  /// data
     330  /// Number of members
     331  int numberMembers_;
     332
     333  /// Members (indices in range 0 ... numberColumns-1)
     334  int * members_;
     335  /// Consequences (normally NULL)
     336  CbcConsequence ** consequence_;
     337};
    277338
    278339/** Simple branching object for an integer variable
     
    623684};
    624685
     686/** N way branching Object class.
     687    Variable is number of set.
     688 */
     689class CbcNWayBranchingObject : public CbcBranchingObject {
     690
     691public:
     692
     693  // Default Constructor
     694  CbcNWayBranchingObject ();
     695
     696  /** Useful constructor - order had matrix indices
     697      way_ -1 corresponds to setting first, +1 to second, +3 etc.
     698      this is so -1 and +1 have similarity to normal
     699  */
     700  CbcNWayBranchingObject (CbcModel * model,  const CbcNWay * nway,
     701                          int numberBranches, const int * order);
     702 
     703  // Copy constructor
     704  CbcNWayBranchingObject ( const CbcNWayBranchingObject &);
     705   
     706  // Assignment operator
     707  CbcNWayBranchingObject & operator=( const CbcNWayBranchingObject& rhs);
     708
     709  /// Clone
     710  virtual CbcBranchingObject * clone() const;
     711
     712  // Destructor
     713  virtual ~CbcNWayBranchingObject ();
     714 
     715  /// Does next branch and updates state
     716  virtual double branch(bool normalBranch=false);
     717
     718  /** \brief Print something about branch - only if log level high
     719  */
     720  virtual void print(bool normalBranch);
     721  /** The number of branch arms created for this branching object
     722  */
     723  virtual int numberBranches() const
     724  {return numberInSet_;};
     725  /// Is this a two way object (-1 down, +1 up)
     726  virtual bool twoWay() const
     727  { return false;};
     728private:
     729  /// order of branching - points back to CbcNWay
     730  int * order_;
     731  /// Points back to object
     732  const CbcNWay * object_;
     733  /// Number in set
     734  int numberInSet_;
     735};
     736
    625737/** Branching decision default class
    626738
     
    805917  int * upList_;
    806918};
     919/** Class for consequent bounds.
     920    When a variable is branched on it normally interacts with other variables by
     921    means of equations.  There are cases where we want to step outside LP and do something
     922    more directly e.g. fix bounds.  This class is for that.
     923
     924    A state of -9999 means at LB, +9999 means at UB,
     925    others mean if fixed to that value.
     926
     927 */
     928
     929class CbcFixVariable : public CbcConsequence {
     930
     931public:
     932
     933  // Default Constructor
     934  CbcFixVariable ();
     935
     936  // One useful Constructor
     937  CbcFixVariable (int numberStates,const int * states, const int * numberNewLower, const int ** newLowerValue,
     938                  const int ** lowerColumn,
     939                  const int * numberNewUpper, const int ** newUpperValue,
     940                  const int ** upperColumn);
     941
     942  // Copy constructor
     943  CbcFixVariable ( const CbcFixVariable & rhs);
     944   
     945  // Assignment operator
     946  CbcFixVariable & operator=( const CbcFixVariable & rhs);
     947
     948  /// Clone
     949  virtual CbcConsequence * clone() const;
     950
     951  /// Destructor
     952  virtual ~CbcFixVariable ();
     953
     954  /** Apply to an LP solver.  Action depends on state
     955   */
     956  virtual void applyToSolver(OsiSolverInterface * solver, int state) const;
     957 
     958protected:
     959  /// Number of states
     960  int numberStates_;
     961  /// Values of integers for various states
     962  int * states_;
     963  /// Start of information for each state (setting new lower)
     964  int * startLower_;
     965  /// Start of information for each state (setting new upper)
     966  int * startUpper_;
     967  /// For each variable new bounds
     968  double * newBound_;
     969  /// Variable
     970  int * variable_;
     971};
     972
    807973#endif
  • trunk/include/CbcBranchBase.hpp

    r135 r216  
    157157  /// Column number if single column object -1 otherwise
    158158  virtual int columnNumber() const;
     159
    159160 
    160161   /// update model
     
    238239  virtual int numberBranchesLeft() const
    239240  {return numberBranchesLeft_;};
     241  /// Reset number of branches left to original
     242  inline void resetNumberBranchesLeft()
     243  { numberBranchesLeft_ = numberBranches();};
    240244
    241245  /** \brief Execute the actions required to branch, as specified by the
     
    399403 
    400404};
     405/** Abstract base class for consequent bounds.
     406    When a variable is branched on it normally interacts with other variables by
     407    means of equations.  There are cases where we want to step outside LP and do something
     408    more directly e.g. fix bounds.  This class is for that.
     409
     410    At present it need not be virtual as only instance is CbcFixVariable, but ...
     411
     412 */
     413
     414class CbcConsequence {
     415
     416public:
     417
     418  // Default Constructor
     419  CbcConsequence ();
     420
     421  // Copy constructor
     422  CbcConsequence ( const CbcConsequence & rhs);
     423   
     424  // Assignment operator
     425  CbcConsequence & operator=( const CbcConsequence & rhs);
     426
     427  /// Clone
     428  virtual CbcConsequence * clone() const=0;
     429
     430  /// Destructor
     431  virtual ~CbcConsequence ();
     432
     433  /** Apply to an LP solver.  Action depends on state
     434   */
     435  virtual void applyToSolver(OsiSolverInterface * solver, int state) const=0;
     436 
     437protected:
     438};
    401439
    402440#endif
  • trunk/include/CbcBranchCut.hpp

    r149 r216  
    113113      Assumed down will be first so way_ set to -1
    114114  */
    115   CbcCutBranchingObject (CbcModel * model, OsiRowCut & down, OsiRowCut &up);
     115  CbcCutBranchingObject (CbcModel * model, OsiRowCut & down, OsiRowCut &up, bool canFix);
    116116 
    117117  /// Copy constructor
     
    146146  /// Cut for the up arm (way_ = 1)
    147147  OsiRowCut up_;
     148  /// True if one way can fix variables
     149  bool canFix_;
    148150};
    149151
     
    216218  bool alwaysCreate_;
    217219};
     220
     221/** Define a branch class that branches so that it is only satsified if all
     222    members have different values
     223    So cut is x <= y-1 or x >= y+1
     224*/
     225
     226
     227class CbcBranchAllDifferent : public CbcBranchCut {
     228
     229public:
     230
     231  // Default Constructor
     232  CbcBranchAllDifferent ();
     233
     234  /** Useful constructor - passed set of integer variables which must all be different
     235  */
     236  CbcBranchAllDifferent (CbcModel * model, int number,const int * which);
     237 
     238  // Copy constructor
     239  CbcBranchAllDifferent ( const CbcBranchAllDifferent &);
     240   
     241  /// Clone
     242  virtual CbcObject * clone() const;
     243
     244  // Assignment operator
     245  CbcBranchAllDifferent & operator=( const CbcBranchAllDifferent& rhs);
     246
     247  // Destructor
     248  ~CbcBranchAllDifferent ();
     249
     250  /// Infeasibility - large is 0.5
     251  virtual double infeasibility(int & preferredWay) const;
     252
     253  /// Creates a branching object
     254  virtual CbcBranchingObject * createBranch(int way);
     255
     256
     257protected:
     258  /// data
     259
     260  /// Number of entries
     261  int numberInSet_;
     262  /// Which variables
     263  int * which_;
     264};
    218265#endif
  • trunk/include/CbcModel.hpp

    r208 r216  
    13171317      1 bit (2) - use current basis to check integer solution (rather than all slack)
    13181318      2 bit (4) - don't check integer solution
     1319      3 bit (8) - fast analyze
    13191320  */
    13201321  /// Set special options
     
    15471548      1 bit (2) - use current basis to check integer solution (rather than all slack)
    15481549      2 bit (4) - don't check integer solution
     1550      3 bit (8) - Strong is doing well - keep on
    15491551  */
    15501552  int specialOptions_;
Note: See TracChangeset for help on using the changeset viewer.