AAP_lp_branch.cpp

// $Id: AAP_lp_branch.cpp,v 1.2 2003/12/03 01:52:30 magh Exp $

/* ------------------------------------------------------------------------
 Author: Matthew Galati (magh@lehigh.edu)

 (c) Copyright 2003 Lehigh University. All Rights Reserved.

 This software is licensed under the Common Public License. Please see 
 accompanying file for terms.    
---------------------------------------------------------------------------*/

#include "AAP_lp.hpp"
#include "AAP_user_data.hpp"

/*--------------------------------------------------------------------------*/
BCP_branching_decision AAP_lp ::
select_branching_candidates(const BCP_lp_result& lpres,
                            const BCP_vec<BCP_var*>& vars,
                            const BCP_vec<BCP_cut*>& cuts,
                            const BCP_lp_var_pool& local_var_pool,
                            const BCP_lp_cut_pool& local_cut_pool,
                            BCP_vec<BCP_lp_branching_object*>& cans){
  /*
    Create candidate branching objects using a disjunction on:
    x_ijk = sum{s in F'} s_ijk lambda_s

    For x_ijk = 0, for all s in F' such that s_ijk  = 1, set lambda_s = 0
    For x_ijk = 1, for all s in F' such that s_ijk != 1, set lambda_s = 0
    
    Possible return values are:
    BCP_DoNotBranch_Fathomed : The node should be fathomed without branching
    BCP_DoNotBranch          : BCP should continue to work on this node
    BCP_DoBranch :           : Branching must be done. In this case the 
    method returns the branching object candidates 
  */

  // Do not branch if new variables have been generated
  if(local_var_pool.size() > 0)
    return BCP_DoNotBranch;

  //As candidates select those closest to 0.5
  branch_close_to_half(lpres, vars, cans);

  if (cans.size() == 0) {
    throw BCP_fatal_error("\
 LP : No var/cut in pool but couldn't select branching object.\n");
  }
  return BCP_DoBranch;
}

/*--------------------------------------------------------------------------*/
void AAP_lp::set_user_data_for_children(BCP_presolved_lp_brobj* best,
                                        const int selected){

  // Store the information about which variable was branched on and
  // what it was set to in user_data for use in restricting the column 
  // generation routine in generate_vars.
  
  const AAP_user_data * data 
    = dynamic_cast<const AAP_user_data*>(get_user_data());
  
  AAP_user_data * data0 = new AAP_user_data(*data);
  AAP_user_data * data1 = new AAP_user_data(*data);
  
  data0->zeros.push_back(cand_to_variable[selected]);
  data1->ones.push_back(cand_to_variable[selected]);
  
  best->user_data()[0] = data0;
  best->user_data()[1] = data1;
}

/*--------------------------------------------------------------------------*/
void AAP_lp:: branch_close_to_half(const BCP_lp_result& lpres,
                                   const BCP_vec<BCP_var*>& vars,
                                   BCP_vec<BCP_lp_branching_object*>& cans){

  //Order first by closeness to 0.5, then by cost 
  //increasing order on | x* - 0.5 |, decreasing on cost
  //x*_ijk = sum{s in F'} s_ijk lambda*_s
  
  //var_candidates: ijk -> (x*_ijk, c_ijk)
  vector< pair<int, pair<double, double> > > var_candidates;
  var_candidates.reserve(aap->n_cols());

  for(int i = 0; i < aap->n_cols(); i++)
    var_candidates.push_back(make_pair(i, make_pair(0.0, 
                                                    aap->getAssignCost()[i])));
  
  const int varnum = vars.size();
  for(int c = 0; c < varnum; ++c) {
    if(lpres.x()[c] <= tolerance) continue;
    const AAP_var* mvar = dynamic_cast<const AAP_var*>(vars[c]);
    if(mvar){
      for(unsigned int p = 0; p < mvar->ap.size(); p++)
        var_candidates[mvar->ap[p]].second.first += lpres.x()[c]; 
    }
  }

  for(int i = 0; i < aap->n_cols(); i++){
    var_candidates[i].second.first = 
      fabs(var_candidates[i].second.first - 0.5);
  }

  const int strong_branch_cands 
    = lp_par.entry(AAP_lp_par::AAP_StrongBranch_Can);
  
  partial_sort(var_candidates.begin(), 
               var_candidates.begin() + strong_branch_cands,
               var_candidates.end(), is_less_than());

  cand_to_variable.clear();
  append_branching_vars(lpres, vars, var_candidates, cans);

}

/*--------------------------------------------------------------------------*/
void AAP_lp::append_branching_vars(const BCP_lp_result& lpres,
                                   const BCP_vec<BCP_var*>& vars,
                                   const vector< pair<int, pair<double, 
                                   double> > > & var_candidates,
                                   BCP_vec<BCP_lp_branching_object*>& cans){

  const int strong_branch_cands 
    = lp_par.entry(AAP_lp_par::AAP_StrongBranch_Can);
  const int varnum = vars.size();
  
  int count = 0;
  vector< pair<int, pair<double, double> > >::const_iterator vi;
  for(vi = var_candidates.begin(); vi != var_candidates.end(); vi++){
    if(count >= strong_branch_cands) break;

    cand_to_variable.insert(make_pair(count, (*vi).first));

    /*
      Branching candidates are constructed as a BCP_lp_branching_object 
      with the arguments:

      const int children                 - number of children for this object
      BCP_vec<BCP_var*>* const new_vars  - vars to add
      BCP_vec<BCP_cut*>* const new_cuts  - cuts to add
      const BCP_vec<int>* const fvp      - forced variable position
      const BCP_vec<int>* const fcp      - forced constraint position
      const BCP_vec<double>* const fvb   - forced variable bound
      const BCP_vec<double>* const fcb   - forced constraint bound
      const BCP_vec<int>* const ivp      - implied variable position
      const BCP_vec<int>* const icp      - implied constraint position
      const BCP_vec<double>* const ivb   - implied variable bound
      const BCP_vec<double>* const icb   - implied constraint bound   
    
      length of fvb = number of children * 2 * length of fvp
      
      For 2 children, for each position fvb holds the new bound
      for child 1 (x_ijk = 0) lb and ub and child 2 (x_ijk = 1) lb and ub
    */

    BCP_vec<int> fvp;    
    BCP_vec<double> fvb;
    vector<bool> contains_ijk;

    /*
      For x_ijk = 0, for all s in F' such that s_ijk  = 1, set lambda_s = 0
      For x_ijk = 1, for all s in F' such that s_ijk != 1, set lambda_s = 0
      
      So, essentially, *every* column will have its bounds adjusted in one
      of the  children. If ijk is in this s then we want to reset its bounds 
      in child 1, if not, then we want to reset its bounds in child 2.
    */

    for(int s = 0; s < varnum; ++s) {//loop over lambda

      //if this variable has already been branched on, skip it
      if(vars[s]->is_fixed()) continue;

      vector<int>::iterator pos;
      AAP_var* mvar = dynamic_cast<AAP_var*>(vars[s]);
      if(mvar){
        int ijk_index = (*vi).first;
        pos = find(mvar->ap.begin(), mvar->ap.end(), ijk_index);
        if(pos != mvar->ap.end()) 
          contains_ijk.push_back(true);
        else 
          contains_ijk.push_back(false);
        fvp.push_back(s);        
      }
    }

    //x_ijk = 0 (child 1)
    for(unsigned int i = 0; i < fvp.size(); i++){
      if(contains_ijk[i]){//set to 0
        fvb.push_back(vars[fvp[i]]->lb());   
        fvb.push_back(0.0);
      }
      else{              //do nothing
        fvb.push_back(vars[fvp[i]]->lb());   
        fvb.push_back(vars[fvp[i]]->ub());
      }
    }

    //x_ijk = 1 (child 2)
    for(unsigned int i = 0; i < fvp.size(); i++){
      if(!contains_ijk[i]){//set to 0
        fvb.push_back(vars[fvp[i]]->lb());   
        fvb.push_back(0.0);
      }
      else{                //do nothing
        fvb.push_back(vars[fvp[i]]->lb());   
        fvb.push_back(vars[fvp[i]]->ub());
      }
    }

    cans.push_back(new BCP_lp_branching_object(2, 0, 0, &fvp, 0, &fvb, 0,
                                               0, 0, 0, 0));

#ifdef DBG_PRINT
    cout << "Candidate: " << count << " branch on var " << (*vi).first;
    ijk_print((*vi).first, aap->getDimension());
    cout << endl;
    for(unsigned int i = 0; i < fvp.size(); i++){
      cout << "pos : " << fvp[i];
      cout << " (lb, ub) : (" << fvb[2*i] << ", " << fvb[2*i+1] << ")" 
           << " (lb, ub) : (" << fvb[(2*fvp.size()) + (2*i)] 
           << ", " << fvb[(2*fvp.size()) + (2*i)+1] << ")" << endl;
    }
    for(unsigned int i = 0; i < fvb.size(); i++)
      cout << fvb[i] << " ";
    cout << endl;
#endif

    count++;
  }
}

---