00001
00002
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