Advertisement
Guest User

Untitled

a guest
Jun 28th, 2017
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.42 KB | None | 0 0
  1. /*******************************************************
  2.  * MC658 - Projeto e Analise de Algoritmo III - 1s2017
  3.  * Prof: Flavio Keidi Miyazawa
  4.  * PED: Edson Ticona Zegarra
  5.  ******************************************************/
  6. #include "prizecollectingpath.h"
  7. #include <lemon/dijkstra.h>
  8. #include <lemon/path.h>
  9. #include <lemon/adaptors.h>
  10. #include <set>
  11. #include <list>
  12. //1.749409000000e+06
  13. using namespace lemon;
  14. ///Preencher aqui para facilitar a correcao.
  15. // Nome1:
  16. // RA1:
  17. // Nome2:
  18. // RA2:
  19.  
  20.  
  21. // This cutting plane routine inserts finds violated cuts between the root and the other terminals.
  22. // Any cut separating the root from the other terminals must have capacity at least 1
  23. // This is a user cut. That is, it is called when the variables x are still fractionary
  24.  
  25. class CutToS: public GRBCallback
  26. {
  27.     ListDigraph &g;
  28.     ListDigraph::ArcMap<GRBVar>& arcos;
  29.     ListDigraph::NodeMap<GRBVar>& nodes;
  30.     ListDigraph::Node s;
  31.     double (GRBCallback::*solution_value)(GRBVar);
  32. public:
  33.     CutToS(ListDigraph &g,ListDigraph::ArcMap<GRBVar>& arcos, ListDigraph::NodeMap<GRBVar>& nodes, ListDigraph::Node s) :
  34.     g(g),arcos(arcos),nodes(nodes),s(s)
  35.     {    }
  36. protected:
  37.     void callback()
  38.     {
  39.         if (where==GRB_CB_MIPSOL){ solution_value = &CutToS::getSolution;}
  40.         else if (where==GRB_CB_MIPNODE && getIntInfo(GRB_CB_MIPNODE_STATUS)==GRB_OPTIMAL) {
  41.             solution_value = &CutToS::getNodeRel;
  42.         } else return;
  43.         try {
  44.             ArcValueMap capacity(g);
  45.             DCutMap cut(g);
  46.             double vcut;
  47.             for (ArcIt a(g); a!=INVALID; ++a)
  48.                 capacity[a] = (this->*solution_value)(arcos[a]);  // or getSolution(x[a]);
  49.  
  50.             for (ListDigraph::NodeIt n(g); n!=INVALID; ++n) {
  51.                 GRBLinExpr expr;
  52.     // find a mincut between root V[0] and other terminal
  53.                 vcut = DiMinCut(g,capacity, s , n, cut);
  54.                 if (vcut >= 1.0-MY_EPS) continue;
  55.  
  56.     // found violated cut
  57.                 for (ArcIt a(g); a!=INVALID; ++a) {
  58.                     if ((cut[g.source(a)]==cut[s]) && (cut[g.target(a)]!=cut[s])){
  59.                         expr += arcos[a];
  60.                         addLazy( getSolution(nodes[n])  >= arcos[a] );
  61.                     }
  62.                 }
  63.         addLazy( expr == getSolution(nodes[n])); // or addLazy(expr,GRB_GREATER_EQUAL,1.0);
  64.     }
  65. } catch (GRBException e) {
  66.     cout << "Error number: " << e.getErrorCode() << endl;
  67.     cout << e.getMessage() << endl;
  68. } catch (...) {
  69.     cout << "Error during callback**" << endl;
  70. }
  71. }
  72. };
  73.  
  74. ///
  75. // PLI function
  76. ///
  77. int prize_collecting_st_path_pli(ListDigraph& g, ListDigraph::NodeMap<double>& prize, ListDigraph::ArcMap<double>& cost, ListDigraph::Node t, ListDigraph::Node s, std::vector<ListDigraph::Node> &path, double &LB, double &UB, int tMax){
  78.     int verbose = 0;
  79.    
  80.     GRBEnv env = GRBEnv();
  81.     GRBModel model = GRBModel(env);
  82.     GRBLinExpr expr1, expr2, expr3, expr4, expr5, expr6;
  83.     model.set(GRB_IntAttr_ModelSense, GRB_MAXIMIZE);
  84.     env.set(GRB_DoubleParam_TimeLimit, tMax);
  85.     int cntNode = 0, cntArc = 0, constantContraint;
  86.     // Variaveis para os nos (0 nao ta na soluçao, 1 ta)
  87.     ListDigraph::NodeMap<GRBVar> nodes(g);
  88.     // Variaveis para os arcos (0 nao ta na soluçao, 1 ta)
  89.     ListDigraph::ArcMap<GRBVar> arcos(g);
  90.     // nodes[s] = model.addVar(0.0, 1.0, 0,GRB_BINARY ,"");
  91.     // nodes[t] = model.addVar(0.0, 1.0, 0, GRB_BINARY ,"");
  92.     for (ListDigraph::NodeIt n(g); n != INVALID; ++n){
  93.         // if(n != s and n != t)
  94.             nodes[n] = model.addVar(0.0, 1.0, prize[n],GRB_BINARY ,"");
  95.         // com fator prize na funçao objetive se nao for s o t
  96.         cntNode++;
  97.     }
  98.     // Restriçoes sobre as variaveis de arcos
  99.     for (ListDigraph::ArcIt a(g); a != INVALID; ++a){
  100.         // Fator -cost na funcao objetive
  101.         arcos[a] = model.addVar(0.0, 1.0, -cost[a],GRB_BINARY ,"");
  102.         cntArc++;
  103.     }
  104.     model.update();
  105.     // if(withHeurisic){
  106.     //  model.getEnv().set(GRB_DoubleParam_Cutoff, LB);
  107.     //  model.update();
  108.     // }
  109.     // Restriçoes sobre os arcos para achar um caminho - conexo
  110.     // 0 in s, 1 out s
  111.     // 1 in t, 0 out t
  112.     expr1 = 0;
  113.     expr2 = 0;
  114.     expr3 = 0;
  115.     expr4 = 0;
  116.     expr5 = 0;
  117.     expr6 = 0;
  118.     for ( ListDigraph::OutArcIt a(g,s); a!=INVALID; ++a ) {
  119.         expr1 += arcos[a];
  120.     }
  121.     model.addConstr(expr1 == 1);
  122.     for ( ListDigraph::InArcIt a(g,s); a!=INVALID; ++a ) {
  123.         expr2 += arcos[a];
  124.     }
  125.     model.addConstr(expr2 == 0);
  126.     for ( ListDigraph::OutArcIt a(g,t); a!=INVALID; ++a ) {
  127.         expr3 += arcos[a];
  128.     }
  129.     model.addConstr(expr3 == 0);
  130.     for ( ListDigraph::InArcIt a(g,t); a!=INVALID; ++a ) {
  131.         expr4 += arcos[a];
  132.     }
  133.     model.addConstr(expr4 == 1);
  134.     //expr5 sao as arestas entrando
  135.     //expr6 as arestas saindo
  136.     for(ListDigraph::NodeIt n(g); n!= INVALID ; ++n){
  137.         if((n!=s) && (n!=t)){
  138.             for ( ListDigraph::InArcIt a(g,n); a!=INVALID; ++a ) {
  139.                 expr5 += arcos[a];
  140.                 model.addConstr(arcos[a] <= nodes[n]);
  141.             }
  142.             for ( ListDigraph::OutArcIt a(g,n); a!=INVALID; ++a ) {
  143.                 expr6 += arcos[a];
  144.             }
  145.             model.addConstr(expr5 == expr6);
  146.             model.addConstr(expr5 <= 1);
  147.             model.addConstr(expr6 <= 1);
  148.             model.addConstr(expr5 >= nodes[n]);
  149.             model.addConstr(expr6 >= nodes[n]);
  150.            
  151.         }
  152.         model.update();
  153.        
  154.     }
  155.     expr1 = 0;
  156.     expr2 = 0;
  157.     for(ListDigraph::OutArcIt a(g,s); a!= INVALID ; ++a){
  158.         expr1 +=arcos[a];
  159.     }
  160.     for(ListDigraph::InArcIt a(g,s); a!= INVALID ; ++a){
  161.         expr2 +=arcos[a];
  162.     }
  163.     model.addConstr(expr1 == 1);
  164.     model.addConstr(expr2 == 0);
  165.     model.update();
  166.     expr3 = 0;
  167.     expr4 = 0;
  168.     for(ListDigraph::OutArcIt a(g,t); a!= INVALID ; ++a){
  169.         expr3 +=arcos[a];
  170.     }
  171.     for(ListDigraph::InArcIt a(g,t); a!= INVALID ; ++a){
  172.         expr4 +=arcos[a];
  173.     }
  174.    
  175.     model.addConstr(expr3 == 0);
  176.     model.addConstr(expr4 == 1);
  177.     model.update();
  178.  
  179.     // Precisao no cout
  180.     // (TEM QUE POR TAMBEM NO MAIN CHAMANDO PARA QUE TUDO FICA BEM LIMPO)
  181.     cout.precision(2);
  182.     cout<<fixed;
  183.  
  184.     // std::cout<<"Node : "<<cntNode<<std::endl;
  185.     // std::cout<<"Arc : "<<cntArc<<std::endl;
  186.    
  187.     //model.getEnv().set(GRB_DoubleParam_TimeLimit, tMax);
  188.    
  189.     CutToS cb = CutToS(g,arcos,nodes,s);
  190.     model.setCallback(&cb);
  191.     model.update();
  192.  
  193.     model.optimize();
  194.     //double runtime = model.get(GRB_DoubleAttr_Runtime);
  195.     if(verbose){
  196.         std::cout<<"Solution : "<<std::endl;
  197.         for(ListDigraph::ArcIt a(g); a!=INVALID ; ++a){
  198.             if((int)arcos[a].get(GRB_DoubleAttr_X) == 1){
  199.                 //std::cout<< std::to_string(g.id(a))<<" : ";
  200.                 //std::cout<<cost[a]<<std::endl;
  201.             }
  202.         }
  203.     }
  204.     // Construi a soluçao
  205.     ListDigraph::Node last = s;
  206.     double countPath = 0;
  207.     // while(last!=t){
  208.         for(ListDigraph::NodeIt n(g); n != INVALID ;++n){
  209.             if(nodes[n].get(GRB_DoubleAttr_X)){
  210.                 countPath++;
  211.                 //last = g.target(a);
  212.                 path.push_back(n);
  213.             }
  214.         }
  215.         for(ListDigraph::ArcIt a(g); a != INVALID ;++a){
  216.             if(arcos[a].get(GRB_DoubleAttr_X)){
  217.                 std::cout<<"from "<<std::to_string(g.id(g.source(a)))<<" to "<<std::to_string(g.id(g.target(a)))<<endl;
  218.             }
  219.         }
  220.         // for(OutArcIt a(g, last); a != INVALID ;++a){
  221.         //  if(arcos[a].get(GRB_DoubleAttr_X)){
  222.         //      countPath++;
  223.         //      last = g.target(a);
  224.         //      path.push_back(last);
  225.         //  }
  226.         // }
  227.     // }
  228.     std::cout<<"TAILLE SOL "<<countPath<<endl;
  229.     std::cout<<path.size()<<std::endl;
  230.     // Set with s,
  231.     // for (ListDigraph::NodeIt n(g); n != INVALID; ++n){
  232.     //  std::cout<< std::to_string(g.id(n))<<" : ";
  233.     //      std::cout<<prize[n]<<std::endl;//*0/
  234.     //      if((int)nodes[n].get(GRB_DoubleAttr_X) == 1)
  235.     //          path.push_back(n);
  236.     //  }  
  237.     //  return true;
  238.     // }
  239. }
  240.  
  241.     int prize_collecting_st_path_heuristic(ListDigraph& g, ListDigraph::NodeMap<double>& prize, ListDigraph::ArcMap<double> &cost, ListDigraph::Node s, ListDigraph::Node t, std::vector<ListDigraph::Node> &path, double &LB, double &UB, int tMax){
  242.  
  243.         return 0;
  244.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement