Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*******************************************************
- * MC658 - Projeto e Analise de Algoritmo III - 1s2017
- * Prof: Flavio Keidi Miyazawa
- * PED: Edson Ticona Zegarra
- ******************************************************/
- #include "prizecollectingpath.h"
- #include <lemon/dijkstra.h>
- #include <lemon/path.h>
- #include <lemon/adaptors.h>
- #include <set>
- #include <list>
- //1.749409000000e+06
- using namespace lemon;
- ///Preencher aqui para facilitar a correcao.
- // Nome1:
- // RA1:
- // Nome2:
- // RA2:
- // This cutting plane routine inserts finds violated cuts between the root and the other terminals.
- // Any cut separating the root from the other terminals must have capacity at least 1
- // This is a user cut. That is, it is called when the variables x are still fractionary
- class CutToS: public GRBCallback
- {
- ListDigraph &g;
- ListDigraph::ArcMap<GRBVar>& arcos;
- ListDigraph::NodeMap<GRBVar>& nodes;
- ListDigraph::Node s;
- double (GRBCallback::*solution_value)(GRBVar);
- public:
- CutToS(ListDigraph &g,ListDigraph::ArcMap<GRBVar>& arcos, ListDigraph::NodeMap<GRBVar>& nodes, ListDigraph::Node s) :
- g(g),arcos(arcos),nodes(nodes),s(s)
- { }
- protected:
- void callback()
- {
- if (where==GRB_CB_MIPSOL){ solution_value = &CutToS::getSolution;}
- else if (where==GRB_CB_MIPNODE && getIntInfo(GRB_CB_MIPNODE_STATUS)==GRB_OPTIMAL) {
- solution_value = &CutToS::getNodeRel;
- } else return;
- try {
- ArcValueMap capacity(g);
- DCutMap cut(g);
- double vcut;
- for (ArcIt a(g); a!=INVALID; ++a)
- capacity[a] = (this->*solution_value)(arcos[a]); // or getSolution(x[a]);
- for (ListDigraph::NodeIt n(g); n!=INVALID; ++n) {
- GRBLinExpr expr;
- // find a mincut between root V[0] and other terminal
- vcut = DiMinCut(g,capacity, s , n, cut);
- if (vcut >= 1.0-MY_EPS) continue;
- // found violated cut
- for (ArcIt a(g); a!=INVALID; ++a) {
- if ((cut[g.source(a)]==cut[s]) && (cut[g.target(a)]!=cut[s])){
- expr += arcos[a];
- addLazy( getSolution(nodes[n]) >= arcos[a] );
- }
- }
- addLazy( expr == getSolution(nodes[n])); // or addLazy(expr,GRB_GREATER_EQUAL,1.0);
- }
- } catch (GRBException e) {
- cout << "Error number: " << e.getErrorCode() << endl;
- cout << e.getMessage() << endl;
- } catch (...) {
- cout << "Error during callback**" << endl;
- }
- }
- };
- ///
- // PLI function
- ///
- 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){
- int verbose = 0;
- GRBEnv env = GRBEnv();
- GRBModel model = GRBModel(env);
- GRBLinExpr expr1, expr2, expr3, expr4, expr5, expr6;
- model.set(GRB_IntAttr_ModelSense, GRB_MAXIMIZE);
- env.set(GRB_DoubleParam_TimeLimit, tMax);
- int cntNode = 0, cntArc = 0, constantContraint;
- // Variaveis para os nos (0 nao ta na soluçao, 1 ta)
- ListDigraph::NodeMap<GRBVar> nodes(g);
- // Variaveis para os arcos (0 nao ta na soluçao, 1 ta)
- ListDigraph::ArcMap<GRBVar> arcos(g);
- // nodes[s] = model.addVar(0.0, 1.0, 0,GRB_BINARY ,"");
- // nodes[t] = model.addVar(0.0, 1.0, 0, GRB_BINARY ,"");
- for (ListDigraph::NodeIt n(g); n != INVALID; ++n){
- // if(n != s and n != t)
- nodes[n] = model.addVar(0.0, 1.0, prize[n],GRB_BINARY ,"");
- // com fator prize na funçao objetive se nao for s o t
- cntNode++;
- }
- // Restriçoes sobre as variaveis de arcos
- for (ListDigraph::ArcIt a(g); a != INVALID; ++a){
- // Fator -cost na funcao objetive
- arcos[a] = model.addVar(0.0, 1.0, -cost[a],GRB_BINARY ,"");
- cntArc++;
- }
- model.update();
- // if(withHeurisic){
- // model.getEnv().set(GRB_DoubleParam_Cutoff, LB);
- // model.update();
- // }
- // Restriçoes sobre os arcos para achar um caminho - conexo
- // 0 in s, 1 out s
- // 1 in t, 0 out t
- expr1 = 0;
- expr2 = 0;
- expr3 = 0;
- expr4 = 0;
- expr5 = 0;
- expr6 = 0;
- for ( ListDigraph::OutArcIt a(g,s); a!=INVALID; ++a ) {
- expr1 += arcos[a];
- }
- model.addConstr(expr1 == 1);
- for ( ListDigraph::InArcIt a(g,s); a!=INVALID; ++a ) {
- expr2 += arcos[a];
- }
- model.addConstr(expr2 == 0);
- for ( ListDigraph::OutArcIt a(g,t); a!=INVALID; ++a ) {
- expr3 += arcos[a];
- }
- model.addConstr(expr3 == 0);
- for ( ListDigraph::InArcIt a(g,t); a!=INVALID; ++a ) {
- expr4 += arcos[a];
- }
- model.addConstr(expr4 == 1);
- //expr5 sao as arestas entrando
- //expr6 as arestas saindo
- for(ListDigraph::NodeIt n(g); n!= INVALID ; ++n){
- if((n!=s) && (n!=t)){
- for ( ListDigraph::InArcIt a(g,n); a!=INVALID; ++a ) {
- expr5 += arcos[a];
- model.addConstr(arcos[a] <= nodes[n]);
- }
- for ( ListDigraph::OutArcIt a(g,n); a!=INVALID; ++a ) {
- expr6 += arcos[a];
- }
- model.addConstr(expr5 == expr6);
- model.addConstr(expr5 <= 1);
- model.addConstr(expr6 <= 1);
- model.addConstr(expr5 >= nodes[n]);
- model.addConstr(expr6 >= nodes[n]);
- }
- model.update();
- }
- expr1 = 0;
- expr2 = 0;
- for(ListDigraph::OutArcIt a(g,s); a!= INVALID ; ++a){
- expr1 +=arcos[a];
- }
- for(ListDigraph::InArcIt a(g,s); a!= INVALID ; ++a){
- expr2 +=arcos[a];
- }
- model.addConstr(expr1 == 1);
- model.addConstr(expr2 == 0);
- model.update();
- expr3 = 0;
- expr4 = 0;
- for(ListDigraph::OutArcIt a(g,t); a!= INVALID ; ++a){
- expr3 +=arcos[a];
- }
- for(ListDigraph::InArcIt a(g,t); a!= INVALID ; ++a){
- expr4 +=arcos[a];
- }
- model.addConstr(expr3 == 0);
- model.addConstr(expr4 == 1);
- model.update();
- // Precisao no cout
- // (TEM QUE POR TAMBEM NO MAIN CHAMANDO PARA QUE TUDO FICA BEM LIMPO)
- cout.precision(2);
- cout<<fixed;
- // std::cout<<"Node : "<<cntNode<<std::endl;
- // std::cout<<"Arc : "<<cntArc<<std::endl;
- //model.getEnv().set(GRB_DoubleParam_TimeLimit, tMax);
- CutToS cb = CutToS(g,arcos,nodes,s);
- model.setCallback(&cb);
- model.update();
- model.optimize();
- //double runtime = model.get(GRB_DoubleAttr_Runtime);
- if(verbose){
- std::cout<<"Solution : "<<std::endl;
- for(ListDigraph::ArcIt a(g); a!=INVALID ; ++a){
- if((int)arcos[a].get(GRB_DoubleAttr_X) == 1){
- //std::cout<< std::to_string(g.id(a))<<" : ";
- //std::cout<<cost[a]<<std::endl;
- }
- }
- }
- // Construi a soluçao
- ListDigraph::Node last = s;
- double countPath = 0;
- // while(last!=t){
- for(ListDigraph::NodeIt n(g); n != INVALID ;++n){
- if(nodes[n].get(GRB_DoubleAttr_X)){
- countPath++;
- //last = g.target(a);
- path.push_back(n);
- }
- }
- for(ListDigraph::ArcIt a(g); a != INVALID ;++a){
- if(arcos[a].get(GRB_DoubleAttr_X)){
- std::cout<<"from "<<std::to_string(g.id(g.source(a)))<<" to "<<std::to_string(g.id(g.target(a)))<<endl;
- }
- }
- // for(OutArcIt a(g, last); a != INVALID ;++a){
- // if(arcos[a].get(GRB_DoubleAttr_X)){
- // countPath++;
- // last = g.target(a);
- // path.push_back(last);
- // }
- // }
- // }
- std::cout<<"TAILLE SOL "<<countPath<<endl;
- std::cout<<path.size()<<std::endl;
- // Set with s,
- // for (ListDigraph::NodeIt n(g); n != INVALID; ++n){
- // std::cout<< std::to_string(g.id(n))<<" : ";
- // std::cout<<prize[n]<<std::endl;//*0/
- // if((int)nodes[n].get(GRB_DoubleAttr_X) == 1)
- // path.push_back(n);
- // }
- // return true;
- // }
- }
- 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){
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement