1. /**************************************************************************

  2. IMPLICIT.C of ZIB optimizer MCF, SPEC version

  3. 

  4. This software was developed at ZIB Berlin. Maintenance and revisions 

  5. solely on responsibility of Andreas Loebel

  6. 

  7. Dr. Andreas Loebel

  8. Ortlerweg 29b, 12207 Berlin

  9. 

  10. Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)

  11. Scientific Computing - Optimization

  12. Takustr. 7, 14195 Berlin-Dahlem

  13. 

  14. Copyright (c) 1998-2000 ZIB.           

  15. Copyright (c) 2000-2002 ZIB & Loebel.  

  16. Copyright (c) 2003-2005 Andreas Loebel.

  17. **************************************************************************/

  18. /*  LAST EDIT: Thu Feb 17 21:45:45 2005 by Andreas Loebel (boss.local.de)  */

  19. /*  $Id: implicit.c,v 1.20 2005/02/17 21:43:12 bzfloebe Exp $  */

  20. 

  21. 

  22. 

  23. #include "implicit.h"

  24. 

  25. 

  26. 

  27. #ifdef _PROTO_

  28. long resize_prob( network_t *net )

  29. #else

  30. long resize_prob( net )

  31.      network_t *net;

  32. #endif

  33. {

  34.     arc_t *arc;

  35.     node_t *node, *stop, *root;

  36.     size_t off;

  37.             

  38.     

  39.     assert( net->max_new_m >= 3 );

  40. 

  41. 

  42.     net->max_m += net->max_new_m;

  43.     net->max_residual_new_m += net->max_new_m;

  44.     

  45. 

  46. #if defined AT_HOME

  47.     printf( "\nresize arcs to %4ld MB (%ld elements a %d B)\n\n",

  48.             net->max_m * sizeof(arc_t) / 0x100000,

  49.             net->max_m,

  50.             sizeof(arc_t) );

  51.     fflush( stdout );

  52. #endif

  53. 

  54. 

  55.     arc = (arc_t *) realloc( net->arcs, net->max_m * sizeof(arc_t) );

  56.     if( !arc )

  57.     {

  58.         printf( "network %s: not enough memory\n", net->inputfile );

  59.         fflush( stdout );

  60.         return -1;

  61.     }

  62.     

  63.     off = (size_t)arc - (size_t)net->arcs;

  64.         

  65.     net->arcs = arc;

  66.     net->stop_arcs = arc + net->m;

  67. 

  68.     root = node = net->nodes;

  69.     for( node++, stop = (void *)net->stop_nodes; node < stop; node++ )

  70.         if( node->pred != root )

  71.             node->basic_arc = (arc_t *)((size_t)node->basic_arc + off);

  72.         

  73.     return 0;

  74. }

  75. 

  76. 

  77. 

  78. 

  79. 

  80. 

  81. 

  82. #ifdef _PROTO_

  83. void insert_new_arc( arc_t *new, long newpos, node_t *tail, node_t *head,

  84.                      cost_t cost, cost_t red_cost )

  85. #else

  86. void insert_new_arc( new, newpos, tail, head, cost, red_cost )

  87.      arc_t *new;

  88.      long newpos;

  89.      node_t *tail;

  90.      node_t *head;

  91.      cost_t cost;

  92.      cost_t red_cost;

  93. #endif

  94. {

  95.     long pos;

  96. 

  97.     new[newpos].tail      = tail;

  98.     new[newpos].head      = head;

  99.     new[newpos].org_cost  = cost;

  100.     new[newpos].cost      = cost;

  101.     new[newpos].flow      = (flow_t)red_cost; 

  102.     

  103.     pos = newpos+1;

  104.     while( pos-1 && red_cost > (cost_t)new[pos/2-1].flow )

  105.     {

  106.         new[pos-1].tail     = new[pos/2-1].tail;

  107.         new[pos-1].head     = new[pos/2-1].head;

  108.         new[pos-1].cost     = new[pos/2-1].cost;

  109.         new[pos-1].org_cost = new[pos/2-1].cost;

  110.         new[pos-1].flow     = new[pos/2-1].flow;

  111.         

  112.         pos = pos/2;

  113.         new[pos-1].tail     = tail;

  114.         new[pos-1].head     = head;

  115.         new[pos-1].cost     = cost;

  116.         new[pos-1].org_cost = cost;

  117.         new[pos-1].flow     = (flow_t)red_cost; 

  118.     }

  119.     

  120.     return;

  121. }   

  122. 

  123. 

  124. 

  125. 

  126. 

  127. 

  128. #ifdef _PROTO_

  129. void replace_weaker_arc( network_t *net, arc_t *new, node_t *tail, node_t *head,

  130.                          cost_t cost, cost_t red_cost )

  131. #else

  132. void replace_weaker_arc( net, new, tail, head, cost, red_cost )

  133.      network *net;

  134.      arc_t *new;

  135.      node_t *tail;

  136.      node_t *head;

  137.      cost_t cost;

  138.      cost_t red_cost;

  139. #endif

  140. {

  141.     long pos;

  142.     long cmp;

  143. 

  144.     new[0].tail     = tail;

  145.     new[0].head     = head;

  146.     new[0].org_cost = cost;

  147.     new[0].cost     = cost;

  148.     new[0].flow     = (flow_t)red_cost; 

  149.                     

  150.     pos = 1;

  151.     cmp = (new[1].flow > new[2].flow) ? 2 : 3;

  152.     while( cmp <= net->max_residual_new_m && red_cost < new[cmp-1].flow )

  153.     {

  154.         new[pos-1].tail = new[cmp-1].tail;

  155.         new[pos-1].head = new[cmp-1].head;

  156.         new[pos-1].cost = new[cmp-1].cost;

  157.         new[pos-1].org_cost = new[cmp-1].cost;

  158.         new[pos-1].flow = new[cmp-1].flow;

  159.         

  160.         new[cmp-1].tail = tail;

  161.         new[cmp-1].head = head;

  162.         new[cmp-1].cost = cost;

  163.         new[cmp-1].org_cost = cost;

  164.         new[cmp-1].flow = (flow_t)red_cost; 

  165.         pos = cmp;

  166.         cmp *= 2;

  167.         if( cmp + 1 <= net->max_residual_new_m )

  168.             if( new[cmp-1].flow < new[cmp].flow )

  169.                 cmp++;

  170.     }

  171.     

  172.     return;

  173. }   

  174. 

  175. 

  176. 

  177. 

  178. #if defined AT_HOME

  179. #include 

  180. double Get_Time( void  ) 

  181. {

  182.     struct timeval tp;

  183.     struct timezone tzp;

  184.     if( gettimeofday( &tp, &tzp ) == 0 )

  185.         return (double)(tp.tv_sec) + (double)(tp.tv_usec)/1.0e6;

  186.     else

  187.         return 0.0;

  188. }

  189. static double wall_time = 0; 

  190. #endif

  191. 

  192. 

  193. #ifdef _PROTO_

  194. long price_out_impl( network_t *net )

  195. #else

  196. long price_out_impl( net )

  197.      network_t *net;

  198. #endif

  199. {

  200.     long i;

  201.     long trips;

  202.     long new_arcs = 0;

  203.     long resized = 0;

  204.     long latest;

  205.     long min_impl_duration = 15;

  206. 

  207.     register cost_t bigM = net->bigM;

  208.     register cost_t head_potential;

  209.     register cost_t arc_cost = 30;

  210.     register cost_t red_cost;

  211.     register cost_t bigM_minus_min_impl_duration;

  212.         

  213.     register arc_t *arcout, *arcin, *arcnew, *stop;

  214.     register arc_t *first_of_sparse_list;

  215.     register node_t *tail, *head;

  216. 

  217. 

  218. #if defined AT_HOME

  219.     wall_time -= Get_Time();

  220. #endif

  221. 

  222.     

  223.     bigM_minus_min_impl_duration = (cost_t)bigM - min_impl_duration;

  224.     

  225. 

  226.     

  227.     if( net->n_trips <= MAX_NB_TRIPS_FOR_SMALL_NET )

  228.     {

  229.       if( net->m + net->max_new_m > net->max_m 

  230.           &&

  231.           (net->n_trips*net->n_trips)/2 + net->m > net->max_m

  232.           )

  233.       {

  234.         resized = 1;

  235.         if( resize_prob( net ) )

  236.           return -1;

  237.         

  238.         refresh_neighbour_lists( net );

  239.       }

  240.     }

  241. #if !defined SPEC_STATIC

  242.     else

  243.     {

  244.       if( net->m + net->max_new_m > net->max_m 

  245.           &&

  246.           (net->n_trips*net->n_trips)/2 + net->m > net->max_m

  247.           )

  248.       {

  249.         resized = 1;

  250.         if( resize_prob( net ) )

  251.           return -1;

  252.         

  253.         refresh_neighbour_lists( net );

  254.       }

  255.     }

  256. #endif

  257. 

  258.         

  259.     arcnew = net->stop_arcs;

  260.     trips = net->n_trips;

  261. 

  262.     arcout = net->arcs;

  263.     for( i = 0; i < trips && arcout[1].ident == FIXED; i++, arcout += 3 );

  264.     first_of_sparse_list = (arc_t *)NULL;

  265.     for( ; i < trips; i++, arcout += 3 )

  266.     {

  267.         if( arcout[1].ident != FIXED )

  268.         {

  269.             arcout->head->firstout->head->arc_tmp = first_of_sparse_list;

  270.             first_of_sparse_list = arcout + 1;

  271.         }

  272.         

  273.         if( arcout->ident == FIXED )

  274.             continue;

  275.         

  276.         head = arcout->head;

  277.         latest = head->time - arcout->org_cost 

  278.             + (long)bigM_minus_min_impl_duration;

  279.                 

  280.         head_potential = head->potential;

  281.         

  282.         arcin = first_of_sparse_list->tail->arc_tmp;

  283.         while( arcin )

  284.         {

  285.             tail = arcin->tail;

  286. 

  287.             if( tail->time + arcin->org_cost > latest )

  288.             {

  289.                 arcin = tail->arc_tmp;

  290.                 continue;

  291.             }

  292.             

  293.             red_cost = arc_cost - tail->potential + head->potential;

  294.             

  295.             if( red_cost < 0 )

  296.             {

  297.                 if( new_arcs < net->max_residual_new_m )

  298.                 {

  299.                     insert_new_arc( arcnew, new_arcs, tail, head, 

  300.                                     arc_cost, red_cost );

  301.                     new_arcs++;                 

  302.                 }

  303.                 else if( (cost_t)arcnew[0].flow > red_cost )

  304.                     replace_weaker_arc( net, arcnew, tail, head, 

  305.                                         arc_cost, red_cost );

  306.             }

  307. 

  308.             arcin = tail->arc_tmp;

  309.         }

  310.     }

  311.     

  312.     if( new_arcs )

  313.     {

  314.         arcnew = net->stop_arcs;

  315.         net->stop_arcs += new_arcs;

  316.         stop = (void *)net->stop_arcs;

  317.         if( resized )

  318.         {

  319.             for( ; arcnew != stop; arcnew++ )

  320.             {

  321.                 arcnew->flow = (flow_t)0;

  322.                 arcnew->ident = AT_LOWER;

  323.             }

  324.         }

  325.         else

  326.         {

  327.             for( ; arcnew != stop; arcnew++ )

  328.             {

  329.                 arcnew->flow = (flow_t)0;

  330.                 arcnew->ident = AT_LOWER;

  331.                 arcnew->nextout = arcnew->tail->firstout;

  332.                 arcnew->tail->firstout = arcnew;

  333.                 arcnew->nextin = arcnew->head->firstin;

  334.                 arcnew->head->firstin = arcnew;

  335.             }

  336.         }

  337.         

  338.         net->m += new_arcs;

  339.         net->m_impl += new_arcs;

  340.         net->max_residual_new_m -= new_arcs;

  341.     }

  342.     

  343. 

  344. #if defined AT_HOME

  345.     wall_time += Get_Time();

  346.     printf( "total time price_out_impl(): %0.0f\n", wall_time );

  347. #endif

  348. 

  349. 

  350.     return new_arcs;

  351. }   

  352. 

  353. 

  354. 

  355. 

  356. 

  357. 

  358. #ifdef _PROTO_

  359. long suspend_impl( network_t *net, cost_t threshold, long all )

  360. #else

  361. long suspend_impl( net, threshold, all )

  362.      network_t *net;

  363.      cost_t threshold;

  364.      long all;

  365. #endif

  366. {

  367.     long susp;

  368.     

  369.     cost_t red_cost;

  370.     arc_t *new_arc, *arc;

  371.     void *stop;

  372. 

  373.     

  374. 

  375.     if( all )

  376.         susp = net->m_impl;

  377.     else

  378.     {

  379.         stop = (void *)net->stop_arcs;

  380.         new_arc = &(net->arcs[net->m - net->m_impl]);

  381.         for( susp = 0, arc = new_arc; arc < (arc_t *)stop; arc++ )

  382.         {

  383.             if( arc->ident == AT_LOWER )

  384.                 red_cost = arc->cost - arc->tail->potential 

  385.                         + arc->head->potential;

  386.             else

  387.             {

  388.                 red_cost = (cost_t)-2;

  389.                 

  390.                 if( arc->ident == BASIC )

  391.                 {

  392.                     if( arc->tail->basic_arc == arc )

  393.                         arc->tail->basic_arc = new_arc;

  394.                     else

  395.                         arc->head->basic_arc = new_arc;

  396.                 }

  397.             }

  398.             

  399.             if( red_cost > threshold )

  400.                 susp++;

  401.             else

  402.             {

  403.                 *new_arc = *arc;

  404.                 new_arc++;

  405.             }

  406.         }

  407.     }

  408.     

  409.         

  410. #if defined AT_HOME

  411.     printf( "\nremove %ld arcs\n\n", susp );

  412.     fflush( stdout );

  413. #endif

  414. 

  415.     if( susp )

  416.     {

  417.         net->m -= susp;

  418.         net->m_impl -= susp;

  419.         net->stop_arcs -= susp;

  420.         net->max_residual_new_m += susp;

  421.         

  422.         refresh_neighbour_lists( net );

  423.     }

  424. 

  425.     return susp;

  426. }

  427. 

  428. 

  429.