AAP_tm.cpp

// $Id: AAP_tm.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 "BCP_tm.hpp"
#include "CoinHelperFunctions.hpp"
#include "AAP_tm.hpp"
#include "AAP_var.hpp"
#include "AAP_init.hpp"
#include "AAP_user_data.hpp"

/*--------------------------------------------------------------------------*/
void AAP_tm::pack_module_data(BCP_buffer & buf, BCP_process_t ptype){
  //Pack information to be passed to the LP process
  lp_par.pack(buf);  //the list of parameters read in
  aap->pack(buf);    //the AAP instance
}

/*--------------------------------------------------------------------------*/
void AAP_tm::pack_var_algo(const BCP_var_algo* var, BCP_buffer& buf){
  //Pack an algorithmic variable (AAP_var is derived from BCP_var_algo)
  {
    const AAP_var * mvar = dynamic_cast<const AAP_var*>(var);
    if(mvar){
      mvar->pack(buf);
      return;
    }
  }
  throw BCP_fatal_error("AAP_tm::pack_var_algo() : unknown cut type!\n");
}

/*--------------------------------------------------------------------------*/
BCP_var_algo* AAP_tm::unpack_var_algo(BCP_buffer& buf){
  //Unpack an algorithmic variable (AAP_var is derived from BCP_var_algo)
  return new AAP_var(buf);
}

/*--------------------------------------------------------------------------*/
void AAP_tm::pack_user_data(const BCP_user_data* ud, BCP_buffer& buf){
  //Pack user data
  {
    const AAP_user_data * data = dynamic_cast<const AAP_user_data*>(ud);
    if(data){
      data->pack(buf);
      return;
    }
  }
  throw BCP_fatal_error("AAP_tm::pack_user_data() : cast failed!\n");
}

/*--------------------------------------------------------------------------*/
BCP_user_data * AAP_tm::unpack_user_data(BCP_buffer& buf){
  return new AAP_user_data(buf);
}

/*--------------------------------------------------------------------------*/
void AAP_tm::display_feasible_solution(const BCP_solution * sol){

  //Display the current feasible solution
#ifdef DBG_PRINT
  const BCP_solution_generic* gsol =
    dynamic_cast<const BCP_solution_generic*>(sol);
  if(gsol){
    const int varnum = gsol->_vars.size();
    for (int c = 0; c < varnum; ++c) {   
      const AAP_var* mvar = dynamic_cast<const AAP_var*>(gsol->_vars[c]);
      if(mvar){
        cout << "Column " << gsol->_vars[c]->bcpind() << " : " 
             << gsol->_values[c] << endl; 
        mvar->print(aap->getDimension());
      }
    }
  }
#else
  BCP_tm_user::display_feasible_solution(sol);
#endif
}

/*--------------------------------------------------------------------------*/
void AAP_tm::initialize_core(BCP_vec<BCP_var_core*>& vars,
                             BCP_vec<BCP_cut_core*>& cuts,
                             BCP_lp_relax*& matrix) {
  /*
    Axial Assignment Problem:
    min {ijk in I x J x K} c_ijk x_ijk
    sum {jk in J x K}            x_ijk = 1, forall i in I (1)
    sum {ik in I x K}            x_ijk = 1, forall j in J (2)
    sum {ij in I x J}            x_ijk = 1, forall k in K (3)
    x_ijk in {0,1}, for all ijk in I x J x K              (4)

    Dantizg-Wolfe LP Formulation:
    min {s in F'}                c_s lambda_s             
    sum {s in F', jk in J x K} s_ijk lambda_s = 1, forall i in I (5) DUAL:uhat
    sum {s in F'}                    lambda_s = 1                (6) DUAL:alpha

    Note: 
    F'    = {s in Z_n : (2)(3)(4)} - an AP point (the J x K assignment)
    x_ijk = sum{s in F'} s_ijk lambda_s
    c_s   = sum{ijk in I x J x K} s_ijk c_ijk
  */

  // Here we define which variables and which constraints are core, i.e., 
  // those which can never be removed from the base model. We have no core 
  // variables. The core constraints are (5) and (6).
  const int n_cuts = aap->getDimension() + 1;
  cuts.reserve(n_cuts);

  // Define a core cut for each constraint in (5) and (6) with lb = ub = 1.0
  for(int r = 0; r < n_cuts; r++)
    cuts.unchecked_push_back(new BCP_cut_core(1.0, 1.0));
}

/*--------------------------------------------------------------------------*/
void AAP_tm::create_root(BCP_vec<BCP_var*>& added_vars,
                         BCP_vec<BCP_cut*>& added_cuts,
                         BCP_user_data * & user_data,
                         BCP_pricing_status& pricing_status){

  // Here we define the root node of the search tree.

  // The pricing status says which type of variables need to be priced out
  // to find a solution. In our case we are generating algorithmic variables.
  // Algorithmic variables are used when there are too many to count (index).
  pricing_status = BCP_PriceAlgoVars;

  // Initialize the root node's user data
  user_data = new AAP_user_data();
  
  // AP Points (fix i and find an assignment for J x K)
  // sum {ik in I x K}            x_ijk = 1, forall j in J (2)
  // sum {ij in I x J}            x_ijk = 1, forall k in K (3)
  
  // Seed the root with random AP points such that we have at least one
  // feasible AAP point. Keep it simple for now, just use AP point: x_iii.
  int i, index;
  
  const double * assigncost = aap->getAssignCost();
  const int n = aap->getDimension();

  vector<int> ap;
  ap.reserve(n);

  double cost = 0.0;
  for(i = 0; i < n; i++){
    index = index3(i,i,i,n);
    ap.push_back(index);
    cost += assigncost[index];
  }

  added_vars.push_back(new AAP_var(ap, cost));
}

/*--------------------------------------------------------------------------*/
void AAP_tm::init_new_phase(int phase, BCP_column_generation & colgen) {
  // Initialize the column generation phase
  colgen = BCP_GenerateColumns;
}

---