/home/coin/SVN-release/OS-2.4.0/Bcp/examples/MaxCut/Member/MC_mst_heur.cpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 
00004 #include "CoinHelperFunctions.hpp"
00005 #include "CoinSort.hpp"
00006 
00007 #include "BCP_vector.hpp"
00008 #include "MC.hpp"
00009 #include "MC_cut.hpp"
00010 #include "MC_solution.hpp"
00011 
00012 MC_solution*
00013 MC_mst_heur(const MC_problem & mc, const double * x, const double * w,
00014             const double alpha, const double beta,
00015             const MC_EdgeOrdering edge_ordering,
00016             const int heurswitchround,
00017             const bool do_edge_switch_heur, const int struct_switch_heur)
00018 {
00019   MC_solution* sol;
00020   
00021   const int m = mc.num_edges;
00022   const int n = mc.num_nodes;
00023 
00024   BCP_vec<int> nodesign(n, 1);
00025   int * edgeorder = new int[m];
00026   int * edges_in_tree = new int[n-1];
00027   double * composite_weight = new double[m];
00028 
00029   int j;
00030   switch (edge_ordering) {
00031   case MC_MstEdgeOrderingPreferZero:
00032     if (w == NULL || beta == 0.0) {
00033       for (j = 0; j < m; ++j)
00034         composite_weight[j] = alpha * x[j];
00035     } else {
00036       for (j = 0; j < m; ++j)
00037         composite_weight[j] = alpha * x[j] - beta * w[j];
00038     }
00039     break;
00040   case MC_MstEdgeOrderingPreferOne:
00041     if (w == NULL || beta == 0.0) {
00042       for (j = 0; j < m; ++j)
00043         composite_weight[j] = alpha * (1.0-x[j]);
00044     } else {
00045       for (j = 0; j < m; ++j)
00046         composite_weight[j] = alpha * (1.0-x[j]) - beta * w[j];
00047     }
00048     break;
00049   case MC_MstEdgeOrderingPreferExtreme:
00050     if (w == NULL || beta == 0.0) {
00051       for (j = 0; j < m; ++j)
00052         composite_weight[j] = alpha * CoinMin(x[j], 1.0-x[j]);
00053     } else {
00054       for (j = 0; j < m; ++j)
00055         composite_weight[j] = alpha*CoinMin(x[j], 1.0-x[j]) - beta*w[j];
00056     }
00057     break;
00058   }
00059   CoinIotaN(edgeorder, m, 0);
00060 
00061   CoinSort_2(composite_weight, composite_weight + m, edgeorder);
00062 
00063   MC_kruskal(mc, edgeorder, x, nodesign.begin(), edges_in_tree);
00064 
00065   delete[] composite_weight;
00066   delete[] edges_in_tree;
00067   delete[] edgeorder;
00068 
00069   sol = new MC_solution(nodesign, mc, heurswitchround,
00070                         do_edge_switch_heur, struct_switch_heur);
00071   return sol;
00072 }
00073 

Generated on Thu Sep 22 03:05:51 2011 by  doxygen 1.4.7