#define mark_dirty(CITY) (dirty_add(dirty_set,(CITY) ) )  \ \#define write_log(a) (change_log[change_log_next++]= a)  \#define DEPTHS_BOUND (n+20) #define swap_bridge(a,b) {int temp= a[0];a[0]= b[0];b[0]= temp;temp= a[1];a[1]= b[1];b[1]= temp;}#define bridge_less(a,b) (tour_inorder(edge[0][0],edge[0][1],a[0],b[0]) )  \ \#define bridge_t(X) (edge[(X-1) >>1][(X-1) &1]) #define bridge_move(a,b,c,d) (tour_flip_arb(bridge_t(a) ,bridge_t(b) ,bridge_t(c) ,bridge_t(d) ) )  \#define mutate(a) (mutation[mutation_next++]= bridge_t(a) )  \/*4:*/#line 595 "./jbmr.w"#include <config.h> #include "lkconfig.h"/*5:*/#line 612 "./jbmr.w"#include <stdio.h> #if !defined(__USE_MISC)#define __USE_MISC  #endif#include <stdlib.h> #include <stddef.h> #include <limits.h> #include "fixincludes.h"/*:5*/#line 598 "./jbmr.w"/*8:*/#line 645 "./jbmr.w"#include "error.h"#include "memory.h"#include "length.h"#include "read.h"#include "nn.h"#include "lk.h"/*:8*/#line 599 "./jbmr.w"/*7:*/#line 631 "./jbmr.w"#include "prng.h"#include "jbmr.h"/*:7*//*16:*/#line 716 "./jbmr.w"#include "dirty.h"/*:16*//*65:*/#line 1819 "./jbmr.w"#include "decluster.h"#include "declevel.h"/*:65*//*117:*/#line 3218 "./jbmr.w"#include "pool.h"#include "dict.h"/*:117*//*127:*/#line 3376 "./jbmr.w"#include "tabuhash.h"/*:127*//*134:*/#line 3458 "./jbmr.w"#include "milestone.h"/*:134*//*142:*/#line 3528 "./jbmr.w"#include "resource.h"/*:142*/#line 600 "./jbmr.w"/*30:*/#line 964 "./jbmr.w"#if LENGTH_TYPE_IS_EXACT || defined(JBMR_REQUIRE_JOINED_GAIN_VAR)#define SPLIT_GAIN_VAR 0#else#define SPLIT_GAIN_VAR 1#endif/*:30*//*55:*/#line 1578 "./jbmr.w"#if LENGTH_TYPE_IS_EXACT#define CAREFUL_OP(LHS,OP,RHS) ((LHS) OP (RHS))#elif SPLIT_GAIN_VAR#define CAREFUL_OP(LHS,OP,RHS) ((LHS##_pos) OP ((RHS##_with_slop)+(LHS##_neg)))#else#define CAREFUL_OP(LHS,OP,RHS) ((LHS) OP (RHS##_with_slop))#endif/*:55*//*169:*/#line 3888 "./jbmr.w"#if JBMR_MAX_VERBOSE||JBMR_REPORT_DEPTHS#define TRACK_DEPTHS 1#else#define TRACK_DEPTHS 0#endif/*:169*/#line 602 "./jbmr.w"/*46:*/#line 1434 "./jbmr.w"typedef struct{length_t gain_for_comparison;#if JBMR_DECLUSTER_IN_ELIGIBILITY_TEST || JBMR_DECLUSTER_IN_GREEDYlength_t cluster_dist;#endif#if !SPLIT_GAIN_VARlength_t gain;#else length_t gain_pos,gain_neg;#endif int t2ip1,t2ip2,scheme_id;}eligible_t;/*:46*/#line 603 "./jbmr.w"/*11:*/#line 670 "./jbmr.w"static int n;/*:11*//*40:*/#line 1184 "./jbmr.w"static int scheme[14][16]= {{1,2,5,6,4,3,2,5},{1,2,6,5,2,6,4,3,1,5,4,6},{5,6,3,4,1,2,6,3,6,2,8,7,1,3,2,8},{5,6,3,4,8,7,6,3,1,2,3,8},{1,2,3,4},{1,2,3,4,1,4,6,5,6,4,8,7,1,5,4,8},{1,2,3,4,6,5,8,7,1,4,5,8},{1,2,3,4,1,4,5,6},{1,2,5,6,5,2,3,4},{6,5,8,7,4,3,8,5,1,2,3,8},{1,2,8,7,1,7,6,5,1,5,2,8,4,3,2,5},{6,5,4,3,6,3,8,7,1,2,3,8},{6,5,8,7,1,2,5,8,5,2,3,4},{-1}};static int scheme_max[14]= {8,12,16,12,4,16,12,8,8,12,16,12,12,0};static int scheme_num_cities[14]= {6,6,8,8,4,8,8,6,6,8,8,8,8,0};/*:40*//*89:*/#line 2685 "./jbmr.w"static int scheme_feas_check[14][10]= {{-1},{-1},{1,3,3,6,2,6,1,8,2,8},{3,8,1,8,3,6},{-1},{1,4,4,6,1,5,4,8},{1,4,5,8,1,8},{-1},{-1},{1,8,3,8,5,8},{1,7,1,5,2,8,2,5,1,8},{1,8,3,6,3,8},{5,8,2,5,1,8},{-1}};static int scheme_feas_n[14]= {0,0,10,6,0,8,6,0,0,6,10,6,6,0};/*:89*//*144:*/#line 3551 "./jbmr.w"#if JBMR_MAX_VERBOSE >= 100 && defined(JBMR_WATCH_THIS_CITY)static int old_verbose,old_verbose_is_set= 0;#endif/*:144*//*182:*/#line 3989 "./jbmr.w"#if TRACK_DEPTHSstatic int*p_depths= NULL,*m_depths= NULL;#endif/*:182*/#line 604 "./jbmr.w"/*27:*/#line 871 "./jbmr.w"static int tour_inorder(int a,int b,int c,int d);static inttour_inorder(int a,int b,int c,int d){if(tour_next(a)==b)return tour_between(b,c,d);else if(tour_prev(a)==b)return tour_between(d,c,b);else{/*168:*/#line 3872 "./jbmr.w"{int i,c,cn;printf("Tour: 0");for(i= 0,c= 0;i<n;i++){errorif(c==0&&i> 0,"Not a tour");cn= tour_next(c);printf(" %d",cn);c= cn;if(i%20==19)printf("\n");}printf("\n");fflush(stdout);errorif(c!=0,"Not a tour");}/*:168*/#line 878 "./jbmr.w"errorif(1,"Bad tour_inorder(%d,%d,%d,%d)\n");return-1;}}/*:27*//*69:*/#line 1923 "./jbmr.w"static intcmp_eligible(const void*a,const void*b){length_t diff= ((const eligible_t*)a)->gain_for_comparison-((const eligible_t*)b)->gain_for_comparison;return diff> 0?-1:(diff<0?1:#if defined(QSORT_DETERMINATE)(int)(((eligible_t*)a)-((eligible_t*)b))#else0#endif);}/*:69*//*85:*/#line 2477 "./jbmr.w"static void tour_flip_arb(int a,int b,int c,int d);static voidtour_flip_arb(int a,int b,int c,int d){/*152:*/#line 3642 "./jbmr.w"#if JBMR_MAX_VERBOSE >= 350if(verbose>=350){printf("tour_flip_arb(%d,%d,%d,%d)",a,b,c,d);fflush(stdout);}#endif/*:152*/#line 2481 "./jbmr.w"if(b==d||a==c)return;if(a==tour_next(b)&&d==tour_next(c)){tour_flip(a,b,c,d);/*154:*/#line 3660 "./jbmr.w"#if JBMR_MAX_VERBOSE >= 350if(verbose>=350){printf(" case a\n");fflush(stdout);}#endif/*:154*/#line 2485 "./jbmr.w"}else if(a==tour_prev(b)&&d==tour_prev(c)){tour_flip(b,a,d,c);/*155:*/#line 3669 "./jbmr.w"#if JBMR_MAX_VERBOSE >= 350if(verbose>=350){printf(" case b\n");fflush(stdout);}#endif/*:155*/#line 2488 "./jbmr.w"}else{printf("\nNeighbour conditions not met\n");/*168:*/#line 3872 "./jbmr.w"{int i,c,cn;printf("Tour: 0");for(i= 0,c= 0;i<n;i++){errorif(c==0&&i> 0,"Not a tour");cn= tour_next(c);printf(" %d",cn);c= cn;if(i%20==19)printf("\n");}printf("\n");fflush(stdout);errorif(c!=0,"Not a tour");}/*:168*/#line 2491 "./jbmr.w"printf("\t(%d) %d (%d)",tour_prev(a),a,tour_next(a));printf("\t(%d) %d (%d)",tour_prev(b),b,tour_next(b));printf("\t(%d) %d (%d)",tour_prev(c),c,tour_next(c));printf("\t(%d) %d (%d)",tour_prev(d),d,tour_next(d));printf("\n");errorif(1,"Neighbour conditions not met.");}}/*:85*//*118:*/#line 3234 "./jbmr.w"#if defined(TABU_SPLAY)static int cmp_pair(const void*a,const void*b);static intcmp_pair(const void*a,const void*b){int a1= *((const int*)a),a2= *(((const int*)a)+1);int b1= *((const int*)b),b2= *(((const int*)b)+1);if(a1<a2){int t= a1;a1= a2;a2= t;}if(b1<b2){int t= b1;b1= b2;b2= t;}return a1==b1?a2-b2:a1-b1;}#endif/*:118*//*124:*/#line 3339 "./jbmr.w"#if defined(TABU_SPLAY)static void move_t(void*env,void**p);static voidmove_t(void*env,void**p){int*old_t= ((int**)env)[0],*t= ((int**)env)[1];*p= (void*)(t+((int*)(*p)-old_t));}#endif/*:124*//*157:*/#line 3696 "./jbmr.w"#if JBMR_MAX_VERBOSE >= 300#if !SPLIT_GAIN_VAR#define put_city(X) \if ( verbose >= 300 ) { \ int i;\ length_t cg =  cum_gain, bg =  best_gain; \ for ( i= 0;i<(X);i++) {printf(" ");}\ printf("t%d == %d p=%d n=%d",(X),t[(X)],tour_prev(t[(X)]),tour_next(t[(X)]));\ if (X> 1) { \  int c =  cost(t[(X)-1],t[X]); \  printf(" c(t%d,t%d)=%d",(X)-1,(X),c); \  c =  cost(t[(X)],t[1]); \  printf(" c(t%d,t1)=%d",(X),c); \ } \ printf("\tcg "length_t_spec" bg "length_t_spec"\n",length_t_pcast(cg),\  length_t_pcast(bg)); \ fflush(stdout); \}#else#define put_city(X) \if ( verbose >= 300 ) { \ int i;\ length_t cg =  cum_gain_pos-cum_gain_neg, bg =  best_gain; \ for ( i= 0;i<(X);i++) {printf(" ");}\ printf("t%d == %d p=%d n=%d",(X),t[(X)],tour_prev(t[(X)]),tour_next(t[(X)]));\ if (X> 1) { \  int c =  cost(t[(X)-1],t[X]); \  printf(" c(t%d,t%d)=%d",(X)-1,(X),c); \  c =  cost(t[(X)],t[1]); \  printf(" c(t%d,t1)=%d",(X),c); \ } \ printf("\tcg "length_t_spec" bg "length_t_spec"\n",length_t_pcast(cg),\  length_t_pcast(bg)); \ fflush(stdout); \}#endif#else#define put_city(X)#endif/*:157*/#line 605 "./jbmr.w"/*9:*/#line 658 "./jbmr.w"voidjbmr_setup(int the_n){n= the_n;/*180:*/#line 3974 "./jbmr.w"#if TRACK_DEPTHS && defined(TABU_JBMR)p_depths= new_arr_of_zero(int,DEPTHS_BOUND);m_depths= new_arr_of_zero(int,DEPTHS_BOUND);#endif/*:180*/#line 662 "./jbmr.w"}/*:9*//*12:*/#line 674 "./jbmr.w"voidjbmr_cleanup(void){n= 0;/*181:*/#line 3982 "./jbmr.w"#if TRACK_DEPTHSfree_mem(p_depths);mem_deduct(DEPTHS_BOUND*sizeof(int));free_mem(m_depths);mem_deduct(DEPTHS_BOUND*sizeof(int));#endif/*:181*/#line 679 "./jbmr.w"}/*:12*//*21:*/#line 771 "./jbmr.w"voidjbmr_run(const int iterations,prng_t*random_stream){/*15:*/#line 712 "./jbmr.w"dirty_set_t*dirty_set;/*:15*//*23:*/#line 823 "./jbmr.w"int*t,t_max_alloc;/*:23*//*31:*/#line 972 "./jbmr.w"#if SPLIT_GAIN_VARlength_t cum_gain_pos,cum_gain_neg;#endif/*:31*//*32:*/#line 981 "./jbmr.w"length_t best_gain;/*:32*//*33:*/#line 993 "./jbmr.w"#if !SPLIT_GAIN_VARlength_t cum_gain;#endif/*:33*//*34:*/#line 1020 "./jbmr.w"int best_two_i,best_exit_a,best_exit_b,best_scheme_id;/*:34*//*35:*/#line 1053 "./jbmr.w"int more_backtracking;/*:35*//*36:*/#line 1068 "./jbmr.w"int two_i;/*:36*//*41:*/#line 1287 "./jbmr.w"int scheme_id,base_scheme[9];/*:41*//*47:*/#line 1457 "./jbmr.w"eligible_t*(e[4]);/*:47*//*50:*/#line 1484 "./jbmr.w"int en[4];/*:50*//*51:*/#line 1494 "./jbmr.w"int ec[4];/*:51*//*52:*/#line 1527 "./jbmr.w"#if !(LENGTH_TYPE_IS_EXACT)length_t instance_epsilon= incumbent_len*LENGTH_MACHINE_EPSILON;length_t best_gain_with_slop;#endif/*:52*//*57:*/#line 1678 "./jbmr.w"int num_reject_by_cum_1,num_reject_pre_e_build;const int no_extra_backtrack= !extra_backtrack;/*:57*//*61:*/#line 1741 "./jbmr.w"#if !defined(JBMR_UNROLL_PREV_NEXT_LOOP)int(*tour_neighbour[2])(int);#endif/*:61*//*78:*/#line 2109 "./jbmr.w"int*change_log= NULL,change_log_max_alloc,change_log_next= 0;/*:78*//*95:*/#line 2859 "./jbmr.w"int last_special_two_i;int generic_flips_made;/*:95*//*115:*/#line 3204 "./jbmr.w"#if defined(TABU_SPLAY)dict_t*tabu= dict_create(cmp_pair,NULL);#endif/*:115*//*126:*/#line 3365 "./jbmr.w"#if defined(TABU_HASH)tabu_hash_t*tabu_hash= NULL;tabu_hash_t*(*tabu_hash_create)(int vertex_bound,int max_size)= NULL;void(*tabu_hash_destroy)(tabu_hash_t*th)= NULL;int(*tabu_hash_includes)(tabu_hash_t*th,int u,int v)= NULL;void(*tabu_hash_add)(tabu_hash_t*th,int u,int v)= NULL;void(*tabu_hash_make_empty)(tabu_hash_t*th)= NULL;#endif/*:126*//*135:*/#line 3464 "./jbmr.w"milestone_state_t ms_lower_bound;milestone_state_t ms_upper_bound;/*:135*//*161:*/#line 3791 "./jbmr.w"int num_reject_by_decluster;/*:161*//*177:*/#line 3944 "./jbmr.w"#if TRACK_DEPTHSint probe_depth,move_depth;#endif/*:177*//*179:*/#line 3967 "./jbmr.w"#if JBMR_MAX_VERBOSE >= 125int probes= 0;#endif/*:179*//*186:*/#line 4033 "./jbmr.w"#if TRACK_DEPTHSint last_probe_depth= 0;#endif/*:186*//*189:*/#line 4073 "./jbmr.w"length_t previous_incumbent_len= 0;/*:189*//*199:*/#line 4254 "./jbmr.w"int mutation[12];/*:199*/#line 775 "./jbmr.w"int iteration;/*58:*/#line 1683 "./jbmr.w"num_reject_by_cum_1= num_reject_pre_e_build= 0;/*:58*//*62:*/#line 1747 "./jbmr.w"#if !defined(JBMR_UNROLL_PREV_NEXT_LOOP)tour_neighbour[0]= tour_prev;tour_neighbour[1]= tour_next;#endif/*:62*//*128:*/#line 3397 "./jbmr.w"#if defined(TABU_HASH){const int max_tabu_size= max_generic_flips<(INT_MAX-4)?max_generic_flips+4:n;if(max_tabu_size<=n){tabu_hash_create= tabu_hash_bd_create;tabu_hash_destroy= tabu_hash_bd_destroy;tabu_hash_includes= tabu_hash_bd_includes;tabu_hash_add= tabu_hash_bd_add;tabu_hash_make_empty= tabu_hash_bd_make_empty;}else{tabu_hash_create= tabu_hash_unbd_create;tabu_hash_destroy= tabu_hash_unbd_destroy;tabu_hash_includes= tabu_hash_unbd_includes;tabu_hash_add= tabu_hash_unbd_add;tabu_hash_make_empty= tabu_hash_unbd_make_empty;}tabu_hash= tabu_hash_create(n,max_tabu_size);}#endif/*:128*//*136:*/#line 3469 "./jbmr.w"milestone_initialize(&ms_lower_bound,lower_bound_name,(length_t)lower_bound_value,begin_data_structures_mark);milestone_initialize(&ms_upper_bound,upper_bound_name,(length_t)upper_bound_value,begin_data_structures_mark);milestone_show_initial(&ms_lower_bound,incumbent_len);milestone_show_initial(&ms_upper_bound,incumbent_len);/*:136*//*162:*/#line 3796 "./jbmr.w"num_reject_by_decluster= 0;/*:162*/#line 778 "./jbmr.w"/*24:*/#line 834 "./jbmr.w"t_max_alloc= 128;t= new_arr_of(int,t_max_alloc);/*:24*//*48:*/#line 1464 "./jbmr.w"e[0]= new_arr_of(eligible_t,nn_max_bound*2);e[1]= new_arr_of(eligible_t,nn_max_bound*2);e[2]= new_arr_of(eligible_t,nn_max_bound*2);e[3]= new_arr_of(eligible_t,nn_max_bound*2);/*:48*//*76:*/#line 2097 "./jbmr.w"change_log_max_alloc= 10000;change_log= new_arr_of(int,change_log_max_alloc);/*:76*/#line 779 "./jbmr.w"/*18:*/#line 730 "./jbmr.w"dirty_set= dirty_create(n,1,prng_unif_int(random_stream,n),__FILE__,__LINE__);/*:18*/#line 780 "./jbmr.w"for(iteration= 0;iteration<iterations;iteration++){int dirty;/*96:*/#line 2864 "./jbmr.w"last_special_two_i= INT_MAX;generic_flips_made= 0;/*:96*/#line 784 "./jbmr.w"while((dirty= dirty_remove(dirty_set))>=0){/*42:*/#line 1300 "./jbmr.w"{int t1_n[2],t1_i;length_t t1_l[2];