yarrg/rsvalue.c

   1 /**/
   2
   3 #include "rscommon.h"
   4
   5 DEBUG_DEFINE_DEBUGF(value);
   6
   7 typedef struct {
   8   int commodid, src_price, src_qty, dst_price, dst_qty;
   9 } Trade;
  10
  11 #define TRADES_PER_BLOCK 10
  12
  13 typedef struct TradesBlock{
  14   struct TradesBlock *next;
  15   Trade t[TRADES_PER_BLOCK];
  16 } TradesBlock;
  17
  18 typedef struct {
  19   int ntrades;
  20   TradesBlock *trades;
  21 } IslandPair;
  22
  23 int nislands;
  24 IslandPair ***ipairs; /* ipairs[sislandid][dislandid] */
  25
  26 static IslandPair *ipair_get(int si, int di) {
  27   IslandPair *ip, **ipa;
  28
  29   assert(si < nislands);
  30   assert(di < nislands);
  31
  32   if (!(ipa= ipairs[si])) {
  33     ipa= ipairs[si]= mcalloc(sizeof(*ipa) * nislands);
  34   }
  35   if ((ip= ipa[di]))
  36     return ip;
  37
  38   ipa[di]= ip= mmalloc(sizeof(*ip));
  39   ip->ntrades= 0;
  40   ip->trades= 0;
  41   int inblock= TRADES_PER_BLOCK;
  42   TradesBlock *block= 0;
  43
  44   debugf("VALUE ipair_get(%d,%d) running...\n", si,di);
  45   SQL_MUST( sqlite3_bind_int(ss_ipair, 1, si) );
  46   SQL_MUST( sqlite3_bind_int(ss_ipair, 2, di) );
  47
  48   while (SQL_STEP(ss_ipair)) {
  49     if (inblock == TRADES_PER_BLOCK) {
  50       block= mmalloc(sizeof(*block));
  51       block->next= ip->trades;
  52       ip->trades= block;
  53       inblock= 0;
  54     }
  55     int *irp, i;
  56     for (i=0, irp=&block->t[inblock].commodid; i<5; i++, irp++)
  57       *irp= sqlite3_column_int(ss_ipair, i);
  58     ip->ntrades++;
  59     inblock++;
  60   }
  61   if (inblock < TRADES_PER_BLOCK)
  62     block->t[inblock].commodid= -1;
  63
  64   sqlite3_reset(ss_ipair);
  65
  66   return ip;
  67 }
  68
  69 void value_route(int nislands, const int *islands) {
  70   int s,d;
  71
  72   /* We need to construct the LP problem.  GLPK talks
  73    * about rows and columns, which are numbered from 1.
  74    *
  75    * Each column is a `structural variable' ie one of the entries in
  76    * the objective function.  In our case the set of structural
  77    * variable is, for each visit, the set of Trades which collect at
  78    * that island.  (We use `visit' to mean `specific visit to an
  79    * island' so if an island appears more than once so do its trades.)
  80    * We don't need to worry about crossing with all the possible
  81    * delivery locations as we always deliver on the first visit.
  82    * We will call such a structural variable a Flow, for brevity.
  83    *
  84    * We iterate over the possible Flows adding them as columns as we
  85    * go, and also adding their entries to the various constraints.
  86    *
  87    * Each row is an `auxiliary variable' ie one of the constraints.
  88    * We have two kinds of constraint:
  89    *   - mass/volume/capital: one constraint for each sailed leg
  90    *       (unless relevant constraint is not satisfied)
  91    *   - quantity of commodity available for collection
  92    *       or delivery at particular price and island
  93    * The former are numbered predictably: we have first all the mass
  94    * limits, then all the volume limits, then all the capital limits
  95    * (as applicable) - one for each leg, ie one for each entry
  96    * in islands except the first.
  97    *
  98    * The latter are added as needed and the row numbers are stored in
  99    * a data structure for later reuse.
 100    */
 101
 102   for (s=0; s<nislands; s++) {
 103     int si= islands[s];
 104     for (d=s; d<nislands; d++) {
 105       int di= islands[d];
 106       int already_d;
 107       for (already_d=s+1; already_d<d; already_d++)
 108         if (islands[already_d] == di)
 109           /* visited this island already since we left s */
 110           goto next_d;
 111       if (d>s && di==si)
 112         /* route has returned to s, no need to think more about this */
 113         goto next_d;
 114
 115       IslandPair *ip= ipair_get(islands[s], islands[d]);
 116       TradesBlock *block= ip->trades;
 117       int ntrades= ip->ntrades;
 118       int inblock= 0;
 119       while (ntrades-- >0) {
 120         if (inblock >= TRADES_PER_BLOCK) {
 121           block= block->next;
 122           inblock= 0;
 123         }
 124         Trade *t= &block->t[inblock++];
 125
 126         debugf("  TRADE %d#%d..%d#%d %d %d-%d\n",
 127                si,s, di,d, t->commodid, t->src_price, t->dst_price);
 128
 129       }
 130     }
 131     next_d:;
 132   }
 133 }
 134
 135 void setup_value(void) {
 136   sqlite3_stmt *sst;
 137
 138   SQL_MUST( sqlite3_prepare(db, "SELECT max(islandid) FROM islands",
 139                             -1,&sst,0) );
 140   assert( SQL_STEP(sst) );
 141   nislands= sqlite3_column_int(sst,0);
 142   nislands++;
 143   sqlite3_finalize(sst);
 144   debugf("VALUE nislands=%d\n",nislands);
 145
 146   SQL_MUST( sqlite3_prepare(db,
 147      "SELECT\n"
 148      " sell.commodid            commodid,\n"
 149      " sell.price               src_price,\n"
 150      " sum(sell.qty)            src_qty,\n"
 151      " buy.price                dst_price,\n"
 152      " sum(buy.qty)             dst_qty\n"
 153      " FROM sell JOIN buy\n"
 154      "   ON sell.commodid = buy.commodid\n"
 155      "  AND buy.price > sell.price\n"
 156      " WHERE sell.islandid=?\n"
 157      "   AND buy.islandid=?\n"
 158      " GROUP BY sell.commodid, sell.price, buy.price",
 159                             -1, &ss_ipair, 0) );
 160
 161   ipairs= mcalloc(sizeof(*ipairs) * nislands);
 162 }