The separation algorithm first tries to find a violated subtour elemination constraint with a simple heuristic. We compute the connected components of the graph there we only consider the edges with value close to one. We check the subtour elimination constraints corresponding the the components for violation. If the heuristic succeeds we terminate with the separation. Otherwise we use the LEDA-mincut algorithm to find the most violated subtour elimination constraint.
TOUR::status TOUR::separate(subproblem& S) {
// Preperation : Read the current LP-values of all edges
// We multiply the value with VALONE and round to the next integer
int i=0;
edge_array<int> val(G);
edge e;
forall_edges(e, G) val[e]=(int) (VALONE*S.value(VM(e)));
// Heuristic : We create a copy H of G, where all edges with LP-value less than
// 1 are deleted from the graph. We compute the connected components
// of this graph and check the subtour elemination constraints
// corresponding to the components for violation
graph H;
node u;
node_array<node> HtoG(H, G.number_of_nodes(), u);
node_array<node> GtoH(G);
// Copy all nodes of G
forall_nodes(u, G) { GtoH[u]=H.new_node(); HtoG[GtoH[u]]=u; }
// Copy the edges with value close to 1
forall_edges(e, G) if(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 subtour elemination constraints and check for
// violation
if(k>1) {
for(int j=0;j<k;j++) {
cons_obj* c=new cutset_inequality(G,VM,CCL[j]);
if (c->violated(S)) {
i++;
S.add_basic_constraint(c, Dynamic);
} else delete c;
}
}
// If the heuristic found a violated constraint, we stop the separation
if(i>0) {
cout<<i<<" Heuristic\n"; return constraint_found;
}
// If only the fast heuristic should be applied, we stop the separation
//if(S.configuration("TOUR_heuristic_only")=="true")
// return no_constraint_found;
// exact separation : We compute the minimal cut in G and check the
// corresponding subtour elimination constraint for
// violation
list<node> mc=MIN_CUT(G, val);
cons_obj* c=new cutset_inequality(G,VM,mc);
if (c->violated(S)) {
i++; S.add_basic_constraint(c, Dynamic);
} else delete c;
// return the correct value
if(i>0) {
return constraint_found;
}
return no_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);
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);
t++;
};
};
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;
}
}
}
if(i>0) {
return constraint_found;
}
return no_constraint_found;
}; // END_OF_SEPARATE
TOUR::status TOUR::feasible(solution& S) {
// We construct a copy H of G, where we delete all edges with value different
// from one. We check all degree equalities. If all degree equalities are
// satisfied, we know that H is a Hamiltonian cycle if H is connected
// Create H
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)]);
}
// check degree equalities
forall_nodes(u,H) if (H.degree(u)!=2) return infeasible_solution;
// check connectedness
if (Is_Connected(H)) return feasible_solution;
return infeasible_solution;
}; // END_OF_FEASIBLE
The degree equality is implemented as follows: The constructor saves the references to the graph and the scil_map<edge>. It furthermore saves the right and side and the node of the degree equality.
To generate the correct entries in the LP-matrix, we iterate over the edges adjacent to the node and add the corresponding variables.
class TOUR::degree_equality : public cons_obj
{
private:
const graph& G;
node v;
double deg;
scil_map<edge>& VM;
public:
// The constructor saves the references to the graph and to the scil_map<edge>
// Furthermore we save the right hand side and the given node of the constraint.
// We initialize the sense and the right hand side with equal and the given
// right hand side.
degree_equality(const graph& G_, node v_, scil_map<edge>& VM_,
double d)
: cons_obj(Equal, d), G(G_), VM(VM_) {
v=v_; deg=d;
};
virtual
~degree_equality()
{};
node gnode() { return v; };
// To generate the row, we can simply iterate over all edges adjacent to
// the node of the degree constraint and add the appropriate variables.
virtual void non_zero_entries(row& r) {
edge e;
forall_inout_edges(e, v) {
r+=VM(e);
}
};
}; // END_OF_CLASS_DEGREE_EQUALITY
1.2.16