jbmr.c

Lin-Kernighan heuristic for the TSP and minimum weight perfect matching

#if !LENGTH_TYPE_IS_EXACT
best_gain_with_slop= best_gain+instance_epsilon;
#endif

best_two_i= two_i;
best_exit_a= t2ip1;
best_exit_b= t2ip2;
best_scheme_id= e[BL][enbl].scheme_id;
/*148:*/
#line 3587 "./jbmr.w"

#if JBMR_MAX_VERBOSE >= 200
if(verbose>=200){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3590 "./jbmr.w"

printf("best_gain = "length_t_spec" %d %d s%d\n",
length_t_pcast(best_gain),best_exit_a,best_exit_b,best_scheme_id);
fflush(stdout);
}
#endif

/*:148*/
#line 1894 "./jbmr.w"

}
}

/*:67*/
#line 2947 "./jbmr.w"

#endif

/*:100*/
#line 1794 "./jbmr.w"

e[BL][enbl].t2ip1= t2ip1;
e[BL][enbl].t2ip2= t2ip2;

#if !SPLIT_GAIN_VAR
e[BL][enbl].gain_for_comparison= e[BL][enbl].gain= cum_2;
#else
e[BL][enbl].gain_for_comparison= cum_2_pos-cum_2_neg;
e[BL][enbl].gain_pos= cum_2_pos;
e[BL][enbl].gain_neg= cum_2_neg;
#endif

#if JBMR_DECLUSTER_IN_GREEDY
e[BL][enbl].gain_for_comparison-= cluster_dist;
#endif
#if JBMR_DECLUSTER_IN_ELIGIBILITY_TEST
e[BL][enbl].cluster_dist= cluster_dist;
#endif

/*158:*/
#line 3739 "./jbmr.w"

#if JBMR_MAX_VERBOSE >= 500
if(verbose>=500){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3742 "./jbmr.w"

#if !SPLIT_GAIN_VAR
printf("%d: %d %d "length_t_spec" s%d\n",
enbl,t2ip1,t2ip2,
length_t_pcast(cum_2),
#else
printf("%d: %d %d "length_t_spec"-"length_t_spec"="length_t_spec" s%d\n",
enbl,t2ip1,t2ip2,
length_t_pcast(cum_2_pos),
length_t_pcast(cum_2_neg),
length_t_pcast(cum_2_pos-cum_2_neg),
#endif
e[BL][enbl].scheme_id);
fflush(stdout);
}
#endif

/*:158*/
#line 1813 "./jbmr.w"

enbl++;
}
}

/*:64*/
#line 2659 "./jbmr.w"

}
}
}
#endif

/*:87*//*99:*/
#line 2929 "./jbmr.w"

#if BL==3
if(t2ip2!=t[1]&&t2ip2!=t[two_i]){
int is_tabu= 0;
/*110:*/
#line 3154 "./jbmr.w"

#if defined(TABU_LINEAR)
#if defined(TABU_JBMR)
{
int i;
for(i= 2,is_tabu= 0;i<two_i;i+= 2){
if((t2ip1==t[i]&&t2ip2==t[i+1])
||(t2ip1==t[i+1]&&t2ip2==t[i])){
is_tabu= 1;
break;
}
}
}
#elif defined(TABU_Papadimitriou)
{errorif(1,"TABU_Papadimitriou is not implemented yet");}
#else
#error "Need one of TABU_JBMR or TABU_Papadimitriou defined"
#endif
#endif 

/*:110*//*119:*/
#line 3252 "./jbmr.w"

#if defined(TABU_SPLAY) && defined(TABU_JBMR)
{int edge[2];
if(t2ip1<t2ip2){edge[0]= t2ip2;edge[1]= t2ip1;}
else{edge[0]= t2ip1;edge[1]= t2ip2;}
is_tabu= dict_find(tabu,edge)!=NULL;
}
#endif

/*:119*//*129:*/
#line 3421 "./jbmr.w"

#if defined(TABU_HASH) && defined(TABU_JBMR)
{is_tabu= tabu_hash_includes(tabu_hash,t2ip1,t2ip2);}
#endif

/*:129*/
#line 2933 "./jbmr.w"

if(!is_tabu){
/*64:*/
#line 1773 "./jbmr.w"

{
#if JBMR_DECLUSTER_IN_ELIGIBILITY_TEST || JBMR_DECLUSTER_IN_GREEDY
const length_t cluster_dist= decluster_d(t[1],t2ip2);
/*159:*/
#line 3760 "./jbmr.w"

#if JBMR_MAX_VERBOSE >= 501 && (JBMR_DECLUSTER_IN_ELIGIBILITY_TEST||JBMR_DECLUSTER_IN_GREEDY)
if(verbose>=501){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3763 "./jbmr.w"

printf(" v---- next clust_dist==%f\n",(double)cluster_dist);
}
#endif

/*:159*/
#line 1777 "./jbmr.w"

#endif

#if !SPLIT_GAIN_VAR
cum_2= cum_1+cost(t2ip1,t2ip2);
#else 
cum_2_pos= cum_1_pos+cost(t2ip1,t2ip2);
cum_2_neg= cum_1_neg;
#endif 

#if JBMR_DECLUSTER_IN_ELIGIBILITY_TEST
if(CAREFUL_OP(cum_2,<=,cluster_dist+best_gain)){
/*160:*/
#line 3769 "./jbmr.w"

#if JBMR_MAX_VERBOSE
num_reject_by_decluster++;
#if JBMR_MAX_VERBOSE >= 500
if(verbose>=500){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3774 "./jbmr.w"

printf("%d: %d %d "length_t_spec" s%d rejected (#%d), clust_dist==%f\n",
enbl,t2ip1,t2ip2,
#if !SPLIT_GAIN_VAR
length_t_pcast(cum_2),
#else
length_t_pcast(cum_2_pos-cum_2_neg),
#endif
e[BL][enbl].scheme_id,
num_reject_by_decluster,
(double)cluster_dist);
fflush(stdout);
}
#endif
#endif

/*:160*/
#line 1789 "./jbmr.w"

}else
#endif

{
/*66:*/
#line 1842 "./jbmr.w"

#if BL==0
if(tour_inorder(t[1],t[2],t2ip2,t2ip1)){
e[BL][enbl].scheme_id= 4;
if(t[1]!=t[4]){
/*67:*/
#line 1864 "./jbmr.w"

{const length_t cost_phantom= cost(t[1],t2ip2);
#if !SPLIT_GAIN_VAR
const length_t cum_exit_now= cum_2-cost_phantom;
#endif

if(
#if LENGTH_TYPE_IS_EXACT
cum_exit_now> best_gain
#elif SPLIT_GAIN_VAR
cum_2_pos> best_gain_with_slop+cum_2_neg+cost_phantom
#else
cum_exit_now> best_gain_with_slop
#endif
)
{

#if SPLIT_GAIN_VAR
best_gain= cum_2_pos-cum_2_neg-cost_phantom;
#else
best_gain= cum_exit_now;
#endif
#if !LENGTH_TYPE_IS_EXACT
best_gain_with_slop= best_gain+instance_epsilon;
#endif

best_two_i= two_i;
best_exit_a= t2ip1;
best_exit_b= t2ip2;
best_scheme_id= e[BL][enbl].scheme_id;
/*148:*/
#line 3587 "./jbmr.w"

#if JBMR_MAX_VERBOSE >= 200
if(verbose>=200){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3590 "./jbmr.w"

printf("best_gain = "length_t_spec" %d %d s%d\n",
length_t_pcast(best_gain),best_exit_a,best_exit_b,best_scheme_id);
fflush(stdout);
}
#endif

/*:148*/
#line 1894 "./jbmr.w"

}
}

/*:67*/
#line 1847 "./jbmr.w"

}
}else{
e[BL][enbl].scheme_id= 0;
}
#endif



/*:66*//*81:*/
#line 2371 "./jbmr.w"

#if BL==1
if(scheme_num_cities[e[BL][enbl].scheme_id= base_scheme[6]]==6){
/*67:*/
#line 1864 "./jbmr.w"

{const length_t cost_phantom= cost(t[1],t2ip2);
#if !SPLIT_GAIN_VAR
const length_t cum_exit_now= cum_2-cost_phantom;
#endif

if(
#if LENGTH_TYPE_IS_EXACT
cum_exit_now> best_gain
#elif SPLIT_GAIN_VAR
cum_2_pos> best_gain_with_slop+cum_2_neg+cost_phantom
#else
cum_exit_now> best_gain_with_slop
#endif
)
{

#if SPLIT_GAIN_VAR
best_gain= cum_2_pos-cum_2_neg-cost_phantom;
#else
best_gain= cum_exit_now;
#endif
#if !LENGTH_TYPE_IS_EXACT
best_gain_with_slop= best_gain+instance_epsilon;
#endif

best_two_i= two_i;
best_exit_a= t2ip1;
best_exit_b= t2ip2;
best_scheme_id= e[BL][enbl].scheme_id;
/*148:*/
#line 3587 "./jbmr.w"

#if JBMR_MAX_VERBOSE >= 200
if(verbose>=200){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3590 "./jbmr.w"

printf("best_gain = "length_t_spec" %d %d s%d\n",
length_t_pcast(best_gain),best_exit_a,best_exit_b,best_scheme_id);
fflush(stdout);
}
#endif

/*:148*/
#line 1894 "./jbmr.w"

}
}

/*:67*/
#line 2374 "./jbmr.w"

}
#endif

/*:81*//*90:*/
#line 2709 "./jbmr.w"

#if BL==2
e[BL][enbl].scheme_id= base_scheme[8];
/*67:*/
#line 1864 "./jbmr.w"

{const length_t cost_phantom= cost(t[1],t2ip2);
#if !SPLIT_GAIN_VAR
const length_t cum_exit_now= cum_2-cost_phantom;
#endif

if(
#if LENGTH_TYPE_IS_EXACT
cum_exit_now> best_gain
#elif SPLIT_GAIN_VAR
cum_2_pos> best_gain_with_slop+cum_2_neg+cost_phantom
#else
cum_exit_now> best_gain_with_slop
#endif
)
{

#if SPLIT_GAIN_VAR
best_gain= cum_2_pos-cum_2_neg-cost_phantom;
#else
best_gain= cum_exit_now;
#endif
#if !LENGTH_TYPE_IS_EXACT
best_gain_with_slop= best_gain+instance_epsilon;
#endif

best_two_i= two_i;
best_exit_a= t2ip1;
best_exit_b= t2ip2;
best_scheme_id= e[BL][enbl].scheme_id;
/*148:*/
#line 3587 "./jbmr.w"

#if JBMR_MAX_VERBOSE >= 200
if(verbose>=200){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3590 "./jbmr.w"

printf("best_gain = "length_t_spec" %d %d s%d\n",
length_t_pcast(best_gain),best_exit_a,best_exit_b,best_scheme_id);
fflush(stdout);
}
#endif

/*:148*/
#line 1894 "./jbmr.w"

}
}

/*:67*/
#line 2712 "./jbmr.w"

#endif

/*:90*//*100:*/
#line 2944 "./jbmr.w"

#if BL==3
e[BL][enbl].scheme_id= 13;
/*67:*/
#line 1864 "./jbmr.w"

{const length_t cost_phantom= cost(t[1],t2ip2);
#if !SPLIT_GAIN_VAR
const length_t cum_exit_now= cum_2-cost_phantom;
#endif

if(
#if LENGTH_TYPE_IS_EXACT
cum_exit_now> best_gain
#elif SPLIT_GAIN_VAR
cum_2_pos> best_gain_with_slop+cum_2_neg+cost_phantom
#else
cum_exit_now> best_gain_with_slop
#endif
)
{

#if SPLIT_GAIN_VAR
best_gain= cum_2_pos-cum_2_neg-cost_phantom;
#else
best_gain= cum_exit_now;
#endif
#if !LENGTH_TYPE_IS_EXACT
best_gain_with_slop= best_gain+instance_epsilon;
#endif

best_two_i= two_i;
best_exit_a= t2ip1;
best_exit_b= t2ip2;
best_scheme_id= e[BL][enbl].scheme_id;
/*148:*/
#line 3587 "./jbmr.w"

#if JBMR_MAX_VERBOSE >= 200
if(verbose>=200){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3590 "./jbmr.w"

printf("best_gain = "length_t_spec" %d %d s%d\n",
length_t_pcast(best_gain),best_exit_a,best_exit_b,best_scheme_id);
fflush(stdout);
}
#endif

/*:148*/
#line 1894 "./jbmr.w"

}
}

/*:67*/
#line 2947 "./jbmr.w"

#endif

/*:100*/
#line 1794 "./jbmr.w"

e[BL][enbl].t2ip1= t2ip1;
e[BL][enbl].t2ip2= t2ip2;

#if !SPLIT_GAIN_VAR
e[BL][enbl].gain_for_comparison= e[BL][enbl].gain= cum_2;
#else
e[BL][enbl].gain_for_comparison= cum_2_pos-cum_2_neg;
e[BL][enbl].gain_pos= cum_2_pos;
e[BL][enbl].gain_neg= cum_2_neg;
#endif

#if JBMR_DECLUSTER_IN_GREEDY
e[BL][enbl].gain_for_comparison-= cluster_dist;
#endif
#if JBMR_DECLUSTER_IN_ELIGIBILITY_TEST
e[BL][enbl].cluster_dist= cluster_dist;
#endif

/*158:*/
#line 3739 "./jbmr.w"

#if JBMR_MAX_VERBOSE >= 500
if(verbose>=500){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3742 "./jbmr.w"

#if !SPLIT_GAIN_VAR
printf("%d: %d %d "length_t_spec" s%d\n",
enbl,t2ip1,t2ip2,
length_t_pcast(cum_2),
#else
printf("%d: %d %d "length_t_spec"-"length_t_spec"="length_t_spec" s%d\n",
enbl,t2ip1,t2ip2,
length_t_pcast(cum_2_pos),
length_t_pcast(cum_2_neg),
length_t_pcast(cum_2_pos-cum_2_neg),
#endif
e[BL][enbl].scheme_id);
fflush(stdout);
}
#endif

/*:158*/
#line 1813 "./jbmr.w"

enbl++;
}
}

/*:64*/
#line 2935 "./jbmr.w"

}
}
#endif


/*:99*/
#line 1732 "./jbmr.w"

if(BL==2&&no_extra_backtrack&&enbl)break;
}
}
#endif

/*:60*/
#line 1695 "./jbmr.w"

#endif

/*:59*//*79:*/
#line 2145 "./jbmr.w"

#if BL==1
if(t2ip1!=t[3]){
switch(e[0][ec[0]].scheme_id){
case 0:base_scheme[5]= tour_inorder(t[1],t[2],t2ip1,t[3])?0:2;break;
case 4:base_scheme[5]= tour_inorder(t[1],t[2],t2ip1,t[4])?5:8;break;
default:errorif(1,"Non exhaustive switch: %d",e[0][ec[0]].scheme_id);
}
/*165:*/
#line 3847 "./jbmr.w"

#if JBMR_MAX_VERBOSE >= 1000
if(verbose>=1000){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3850 "./jbmr.w"
printf("base_scheme5 == %d\n",base_scheme[5]);
fflush(stdout);
}
#endif

/*:165*/
#line 2153 "./jbmr.w"

/*60:*/
#line 1725 "./jbmr.w"

#if defined(JBMR_UNROLL_PREV_NEXT_LOOP)
#error "JBMR_UNROLL_PREV_NEXT_LOOP is not implemented"
#else
{int which_neighbour;
for(which_neighbour= 0;which_neighbour<2;which_neighbour++){
t2ip2= (tour_neighbour[which_neighbour])(t2ip1);
/*63:*/
#line 1757 "./jbmr.w"

#if BL==0
if(t[2]!=t2ip2){
/*64:*/
#line 1773 "./jbmr.w"

{
#if JBMR_DECLUSTER_IN_ELIGIBILITY_TEST || JBMR_DECLUSTER_IN_GREEDY
const length_t cluster_dist= decluster_d(t[1],t2ip2);
/*159:*/
#line 3760 "./jbmr.w"

#if JBMR_MAX_VERBOSE >= 501 && (JBMR_DECLUSTER_IN_ELIGIBILITY_TEST||JBMR_DECLUSTER_IN_GREEDY)
if(verbose>=501){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3763 "./jbmr.w"

printf(" v---- next clust_dist==%f\n",(double)cluster_dist);
}
#endif

/*:159*/
#line 1777 "./jbmr.w"

#endif

#if !SPLIT_GAIN_VAR
cum_2= cum_1+cost(t2ip1,t2ip2);
#else 
cum_2_pos= cum_1_pos+cost(t2ip1,t2ip2);
cum_2_neg= cum_1_neg;
#endif 

#if JBMR_DECLUSTER_IN_ELIGIBILITY_TEST
if(CAREFUL_OP(cum_2,<=,cluster_dist+best_gain)){
/*160:*/
#line 3769 "./jbmr.w"

#if JBMR_MAX_VERBOSE
num_reject_by_decluster++;
#if JBMR_MAX_VERBOSE >= 500
if(verbose>=500){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3774 "./jbmr.w"

printf("%d: %d %d "length_t_spec" s%d rejected (#%d), clust_dist==%f\n",
enbl,t2ip1,t2ip2,
#if !SPLIT_GAIN_VAR
length_t_pcast(cum_2),
#else
length_t_pcast(cum_2_pos-cum_2_neg),
#endif
e[BL][enbl].scheme_id,
num_reject_by_decluster,
(double)cluster_dist);
fflush(stdout);
}
#endif
#endif

/*:160*/
#line 1789 "./jbmr.w"

}else
#endif

{
/*66:*/
#line 1842 "./jbmr.w"

#if BL==0
if(tour_inorder(t[1],t[2],t2ip2,t2ip1)){
e[BL][enbl].scheme_id= 4;
if(t[1]!=t[4]){
/*67:*/
#line 1864 "./jbmr.w"

{const length_t cost_phantom= cost(t[1],t2ip2);
#if !SPLIT_GAIN_VAR
const length_t cum_exit_now= cum_2-cost_phantom;
#endif

if(
#if LENGTH_TYPE_IS_EXACT
cum_exit_now> best_gain
#elif SPLIT_GAIN_VAR
cum_2_pos> best_gain_with_slop+cum_2_neg+cost_phantom
#else
cum_exit_now> best_gain_with_slop
#endif
)
{

#if SPLIT_GAIN_VAR
best_gain= cum_2_pos-cum_2_neg-cost_phantom;
#else
best_gain= cum_exit_now;
#endif
#if !LENGTH_TYPE_IS_EXACT
best_gain_with_slop= best_gain+instance_epsilon;
#endif

best_two_i= two_i;
best_exit_a= t2ip1;
best_exit_b= t2ip2;
best_scheme_id= e[BL][enbl].scheme_id;
/*148:*/
#line 3587 "./jbmr.w"

#if JBMR_MAX_VERBOSE >= 200
if(verbose>=200){
/*167:*/
#line 3866 "./jbmr.w"

#if JBMR_MAX_VERBOSE
{int i;for(i= 0;i<two_i;i++)printf(" ");}
#endif

/*:167*/
#line 3590 "./jbmr.w"

printf("best_gain = "length_t_spec" %d %d s%d\n",
length_t_pcast(best_gain),best_exit_a,best_exit_b,best_scheme_id);
fflush(stdout);
}
#endif

/*:148*/
#line 1894 "./jbmr.w"

}
}

/*:67*/
#line 1847 "./jbmr.w"

}
}else{
e[BL][enbl].scheme_id= 0;
}
#endif



/*:66*//*81:*/
#line 2371 "./jbmr.w"

#if BL==1
if(scheme_num_cities[e[BL][enbl].scheme_id= base_scheme[6]]==6){
/*67:*/
#line 1864 "./jbmr.w"