WIP routesearch; route tail guesswork pruning optimisation

[ypp-sc-tools.db-live.git] / yarrg / rsvalue.c

diff --git a/yarrg/rsvalue.c b/yarrg/rsvalue.c
index 70e1f65d96cbd683a08aab16867102a5e54de232..eb4d3f053480f82ef5b04ab710488054d1568c2c 100644 (file)
--- a/yarrg/rsvalue.c
+++ b/yarrg/rsvalue.c
@@ -21,18 +21,12 @@ typedef struct {
 
 #define TRADES_PER_BLOCK 10
 
-typedef struct TradesBlock{
+typedef struct TradesBlock {
   struct TradesBlock *next;
   Trade t[TRADES_PER_BLOCK];
 } TradesBlock;
 
-typedef struct {
-  double distance_loss_factor;
-  int ntrades;
-  TradesBlock *trades;
-} IslandPair;
-
-IslandPair ***ipairs; /* ipairs[sislandid][dislandid] */
+static IslandPair ***ipairs; /* ipairs[sislandid][dislandid] */
 
 typedef struct IslandTradeEnd {
   struct IslandTradeEnd *next;
@@ -94,9 +88,18 @@ static void avail_c(const Trade *t, IslandTradeEnd **trades,
     search->rownum= lpx_add_rows(lp, 1);
     lpx_set_row_bnds(lp, search->rownum, LPX_UP, 0, search->qty);
 
-    if (DEBUGP(value)) {
-      char *name= masprintf("%s_c%d_%d",srcdst,t->commodid,price);
+    if (DEBUGP(value) || DEBUGP(check)) {
+      char *name= masprintf("%s_i%d_c%d_%d_all",
+                           srcdst, islandid, t->commodid, price);
       lpx_set_row_name(lp,search->rownum,name);
+
+      if (DEBUGP(check)) {
+       int nrows= lpx_get_num_rows(lp);
+       assert(search->rownum == nrows);
+       int i;
+       for (i=1; i<nrows; i++)
+         assert(strcmp(name, lpx_get_row_name(lp,i)));
+      }
       free(name);
     }
     search->generation= generation;
@@ -113,7 +116,7 @@ static int setup_leg_constraints(double max_thing, int legs, const char *wh) {
     int row= leg+startrow;
     lpx_set_row_bnds(lp, row, LPX_UP, 0, max_thing);
     if (DEBUGP(value)) {
-      char *name= masprintf("max_leg%d_%s",leg,wh);
+      char *name= masprintf("%s_%d",wh,leg);
       lpx_set_row_name(lp,row,name);
       free(name);
     }
@@ -127,7 +130,7 @@ static void add_leg_c(int startrow, int leg, double value) {
   add_constraint(startrow+leg, value);
 }
 
-static IslandPair *ipair_get(int si, int di) {
+IslandPair *ipair_get(int si, int di) {
   IslandPair *ip, **ipa;
 
   assert(si < islandtablesz);
@@ -142,6 +145,7 @@ static IslandPair *ipair_get(int si, int di) {
   ipa[di]= ip= mmalloc(sizeof(*ip));
   ip->ntrades= 0;
   ip->trades= 0;
+  ip->route_tail_value= -1;
   int inblock= TRADES_PER_BLOCK;
   TradesBlock *block=0, **tail=&ip->trades;
 
@@ -178,7 +182,7 @@ static IslandPair *ipair_get(int si, int di) {
   return ip;
 }
 
-double value_route(int nislands, const int *islands) {
+double value_route(int nislands, const int *islands, int exclude_arbitrage) {
   int s,d;
 
   /* We need to construct the LP problem.  GLPK talks
@@ -235,7 +239,9 @@ double value_route(int nislands, const int *islands) {
        s++, delay_slot_loss_factor *= LOSS_FACTOR_PER_DELAY_SLOT) {
     int si= islands[s];
     
-    for (d=s; d<nislands; d++) {
+    for (d= s + exclude_arbitrage;
+        d < nislands;
+        d++) {
       int di= islands[d];
       int already_d;
       for (already_d=s+1; already_d<d; already_d++)
@@ -259,6 +265,9 @@ double value_route(int nislands, const int *islands) {
       int col= lpx_add_cols(lp,ip->ntrades);
 
       double loss_factor= delay_slot_loss_factor * ip->distance_loss_factor;
+      debugf(" SOME   i%d#%d..i%d#%d  dslf=%g dlf=%g  lf=%g\n",
+            si,s, di,d,
+            delay_slot_loss_factor, ip->distance_loss_factor, loss_factor);
 
       while (tradestodo-- >0) {
        if (inblock >= TRADES_PER_BLOCK) {
@@ -267,22 +276,22 @@ double value_route(int nislands, const int *islands) {
        }
        Trade *t= &block->t[inblock++];
 
-       debugf("  TRADE %d#%d..%d#%d %d %d-%d\n",
+       debugf("  TRADE i%d#%d..i%d#%d c%d %d-%d  ",
               si,s, di,d, t->commodid, t->src_price, t->dst_price);
 
        nconstraint_rows=0;
 
-       avail_c(t, &itradeends[s].src, t->src_price, "src", si, ss_ite_sell);
-       avail_c(t, &itradeends[d].dst, t->dst_price, "dst", di, ss_ite_buy);
+       avail_c(t, &itradeends[si].src, t->src_price, "src", si, ss_ite_sell);
+       avail_c(t, &itradeends[di].dst, t->dst_price, "dst", di, ss_ite_buy);
 
        int leg;
        for (leg=s; leg<d; leg++) {
-         add_leg_c(mass_constraints, leg, commodstable[t->commodid].mass);
-         add_leg_c(volu_constraints, leg, commodstable[t->commodid].volu);
-         add_leg_c(capi_constraints, leg, t->src_price);
+         add_leg_c(mass_constraints,leg, commodstable[t->commodid].mass*1e-3);
+         add_leg_c(volu_constraints,leg, commodstable[t->commodid].volu*1e-3);
+         add_leg_c(capi_constraints,leg, t->src_price);
        }
 
-       double unit_profit= (t->dst_price - t->src_price) * loss_factor;
+       double unit_profit= t->dst_price * loss_factor - t->src_price;
        debugf("    unit profit %f\n", unit_profit);
 
        lpx_set_col_bnds(lp, col, LPX_LO, 0, 0);
@@ -313,14 +322,15 @@ double value_route(int nislands, const int *islands) {
     if (DEBUGP(lp))
       lpx_write_cpxlp(lp, (char*)DEBUG_DEV);
 
-    int ipr= lpx_interior(lp);
+    int ipr= lpx_simplex(lp);
     assert(ipr==LPX_E_OK);
 
     if (DEBUGP(lp))
-      lpx_print_ips(lp, (char*)DEBUG_DEV);
+      lpx_print_sol(lp, (char*)DEBUG_DEV);
 
-    assert(lpx_ipt_status(lp) == LPX_T_OPT);
-    profit= lpx_ipt_obj_val(lp);
+    int lpst= lpx_get_status(lp);
+    assert(lpst == LPX_OPT);
+    profit= lpx_get_obj_val(lp);
   }
 
   lpx_delete_prob(lp);