atour.cc

#ifndef ATOUR_CONSTRAINT_CC
#define ATOUR_CONSTRAINT_CC

#include<scil/scil.h>
#include<scil/var_map.h>
#include<LEDA/graph.h>
#include<LEDA/graph_alg.h>
#include<LEDA/set.h>
#include<scil/constraints/atour.h>

using namespace SCIL;
using namespace LEDA;

#define VALONE 1000000

class ATOUR::dir_degree_equality : public cons_obj {
private:
  const graph& G;
  node v;
  double deg;
  scil_map<edge>& VM;
  bool in;
  
public:

  dir_degree_equality(subproblem& S_,
                  const graph& G_, node v_, scil_map<edge>& VM_,
                  double d, bool i_)
    /*{create The constraint $\sum_{e \in \delta(v)} x_e = d$, where $\delta(v)$ are the 
      edges which are adjacent to v and for which a variable was defined.}*/
    : cons_obj(Equal, d), G(G_), VM(VM_) { 
    v=v_; deg=d, in=i_; 
  };

  virtual
  ~dir_degree_equality()
  {};
  
  node gnode() { return v; };
  
  virtual void non_zero_entries(row& r) {
    edge e;
    if(in) {
      forall_out_edges(e, v) {
        r+=VM(e);
      }
    } else {
      forall_in_edges(e, v) {
        r+=VM(e);
      }
    };
  };
};

class ATOUR::dir_cutset_inequality : public cons_obj {
private:
  graph& G;
  scil_map<edge>& VM;
  node_array<bool> cut;
  double rhs;
  
public:
  
  dir_cutset_inequality(graph& Gt, scil_map<edge>& VM_, list<node>& L) 
    : cons_obj(Less, L.size()-1), G(Gt), VM(VM_) {
    node v;
    cut.init(G, false);
    forall(v,L) cut[v]=true;
  }

  void non_zero_entries(row& r) { 
    edge e;
    forall_edges(e,G) {
      if(coeff(e)==1) r+=VM(e);
    }
  }

  virtual
  ~dir_cutset_inequality() {};

  double coeff(edge e) { 
    if(e==nil) return 0;
    if((cut[G.source(e)]) && (cut[G.target(e)])) return 1;
    return(0);
  };
};


ATOUR::ATOUR(graph& G_, scil_map<edge>& VM_)
  : G(G_), VM(VM_)
{ };

void ATOUR::init(subproblem& S) {
  node v;
  forall_nodes(v, G) {
    S.add_basic_constraint(new dir_degree_equality(S,G,v,VM,1, true));
    S.add_basic_constraint(new dir_degree_equality(S,G,v,VM,1, false));
  }
}
  
ATOUR::status ATOUR::separate(subproblem& S) {
  // Preperation
  int i=0;
  edge_array<int> val(G);
  edge e;
  forall_edges(e, G) val[e]=leda::max((int) (VALONE*S.value(VM(e))),0);
  
  // Heutistic
  graph H;
  node u;
  node_array<node> HtoG(H, G.number_of_nodes(), u);
  node_array<node> GtoH(G);
  
  forall_nodes(u, G) { GtoH[u]=H.new_node(); HtoG[GtoH[u]]=u; }
  
  forall_edges(e, G) if(val[e]>=VALONE-5)
    H.new_edge(GtoH[source(e)], GtoH[target(e)]);

  node_array<int> CC(H);
  int k=COMPONENTS(H,CC);
  list<node> CCL[k];
  forall_nodes(u,H) CCL[CC[u]].append(HtoG[u]);
  cout<<k<<" Connected Components\n";

  if(k>1) {
    for(int j=0;j<k;j++) {
      cons_obj* c=new dir_cutset_inequality(G,VM,CCL[j]);
      if (c->violated(S)) { 
        i++;
        S.add_basic_constraint(c, Dynamic); 
      } else delete c;
    }
  }

  // Heuristic succeeded?
  if(i>0) { 
    cout<<i<<" Heuristic\n"; return constraint_found; 
  }
  //return no_constraint_found;

  // exact separation
  list<node> mc=MIN_CUT(G, val);
  cons_obj* c=new dir_cutset_inequality(G,VM,mc);
  if (c->violated(S)) {
    i++; S.add_basic_constraint(c, Dynamic);
  } else delete c;
  if(i>0) {
    cout<<"Exact CUT fount inequality\n";
    return constraint_found;
  }
/*
  H.del_all_edges();

  // Copy the edges with fractional value
  forall_edges(e, G) if((val[e]>=5) && (val[e]<=VALONE-5))
    H.new_edge(GtoH[source(e)], GtoH[target(e)]);
  
  // Compute the connected components
  {
    node_array<int> CC(H);
    int k=COMPONENTS(H,CC);
    list<node> CCL[k];
    forall_nodes(u,H) CCL[CC[u]].append(HtoG[u]);

    // Create the corresponding comb constraints and check for
    // violation
    node v;
    node_array<bool> R(G, false);
    node_array<bool> T(G, false);
    list<node> TL;
    if(k>1) {
      for(int j=0;j<k;j++) {
        row r;
        forall(v, CCL[j]) R[v]=true;
        double d=0;
        int t=0;
        forall_edges(e,G) {
          if((R[source(e)]) && (R[target(e)])) { 
            d+=S.value(VM(e));
            r+=VM(e);
          }
          if((R[source(e)]!=R[target(e)]) && (val[e]>VALONE-10)) {
            d+=S.value(VM(e));
            r+=VM(e);
            if(R[source(e)]) u=target(e); else u=source(e);
            if(T[u]==false) {
              t++;
              T[u]=true;
              TL.append(u);
            };
          };
        };
        if((t % 2==1) && (d>CCL[j].size()+(t-1)/2+0.01)) {
          i++;
          S.add_basic_constraint(r<=CCL[j].size()+(t-1)/2);
          cout<<"comb\n";
        };
        forall(v, CCL[j]) R[v]=false;
        forall(v,TL) T[v]=false;
        TL.clear();
      }
    }
  }
*/
  if(i>0) {
    return constraint_found;
  }

  return no_constraint_found;
}

ATOUR::status ATOUR::feasible(solution& S) {
  node_array<node> GtoH(G);
  graph H;
  node u;
  forall_nodes(u, G)
    GtoH[u]=H.new_node();
  edge e;
  forall_edges(e,G) {
    if(S.value(VM(e))>0.5) H.new_edge(GtoH[source(e)], GtoH[target(e)]);
  }
  if (Is_Connected(H)) return feasible_solution;
  return infeasible_solution;
}
#undef VALONE

#endif

---