chiark / gitweb /
WIP routesearch; Cache relevant bits of database in memory
[ypp-sc-tools.db-live.git] / yarrg / rsvalue.c
1 /**/
2
3 #include <glpk.h>
4
5 #include "rscommon.h"
6
7 DEBUG_DEFINE_DEBUGF(value);
8
9 typedef struct { int mass, volu; } CommodInfo;
10 static int commodstabsz;
11 static CommodInfo *commodstab;
12
13 static sqlite3_stmt *ss_ipair_dist;
14 static sqlite3_stmt *ss_ite_buy, *ss_ite_sell;
15
16 #define MAX_LEGS (MAX_ROUTELEN-1)
17
18 typedef struct {
19   int commodid, src_price, dst_price;
20 } Trade;
21
22 #define TRADES_PER_BLOCK 10
23
24 typedef struct TradesBlock {
25   struct TradesBlock *next;
26   int ntrades;
27   Trade t[TRADES_PER_BLOCK];
28 } TradesBlock;
29
30 static IslandPair ***ipairs; /* ipairs[sislandid][dislandid] */
31
32 typedef struct IslandTradeEnd {
33   struct IslandTradeEnd *next;
34   /* key: */
35   int commodid, price;
36   /* values: */
37   int qty;
38   unsigned long generation;
39   int rownum;
40 } IslandTradeEnd;
41
42 typedef struct {
43   IslandTradeEnd *src, *dst;
44 } IslandTradeEndHeads;
45
46 IslandTradeEndHeads *itradeends;
47   /* itradeends[islandid].{src,dst}->commodid etc. */
48
49 static LPX *lp;
50 static unsigned long generation;
51
52 static int nconstraint_rows;
53 static int constraint_rows[1+2+3*MAX_LEGS];
54 static double constraint_coeffs[1+2+3*MAX_LEGS];
55       /* dummy0, src, dst, for_each_leg( [mass], [volume], [capital] ) */
56
57 static void add_constraint(int row, double coefficient) {
58   nconstraint_rows++; /* glpk indices start from 1 !!! */
59   constraint_rows  [nconstraint_rows]= row;
60   constraint_coeffs[nconstraint_rows]= coefficient;
61 }
62
63 static void avail_c(const Trade *t, IslandTradeEnd **trades,
64                     int price, const char *srcdst,
65                     int islandid, sqlite3_stmt *ss_ite) {
66   /* find row number of trade availability constraint */
67   IslandTradeEnd *search;
68
69   for (search= *trades; search; search=search->next)
70     if (search->commodid==t->commodid && search->price==price)
71       goto found;
72   abort();
73   
74  found:;
75   if (search->generation != generation) {
76     search->rownum= lpx_add_rows(lp, 1);
77     lpx_set_row_bnds(lp, search->rownum, LPX_UP, 0, search->qty);
78
79     if (DEBUGP(value) || DEBUGP(check)) {
80       char *name= masprintf("%s_i%d_c%d_%d_all",
81                             srcdst, islandid, t->commodid, price);
82       lpx_set_row_name(lp,search->rownum,name);
83
84       if (DEBUGP(check)) {
85         int nrows= lpx_get_num_rows(lp);
86         assert(search->rownum == nrows);
87         int i;
88         for (i=1; i<nrows; i++)
89           assert(strcmp(name, lpx_get_row_name(lp,i)));
90       }
91       free(name);
92     }
93     search->generation= generation;
94   }
95
96   add_constraint(search->rownum, 1.0);
97 }
98
99 static int setup_leg_constraints(double max_thing, int legs, const char *wh) {
100   int leg, startrow;
101   if (max_thing < 0 || !legs) return -1;
102   startrow= lpx_add_rows(lp, legs);
103   for (leg=0; leg<legs; leg++) {
104     int row= leg+startrow;
105     lpx_set_row_bnds(lp, row, LPX_UP, 0, max_thing);
106     if (DEBUGP(value)) {
107       char *name= masprintf("%s_%d",wh,leg);
108       lpx_set_row_name(lp,row,name);
109       free(name);
110     }
111   }
112   return startrow;
113 }
114
115 static void add_leg_c(int startrow, int leg, double value) {
116   if (startrow<=0) return;
117   assert(value > 0);
118   add_constraint(startrow+leg, value);
119 }
120
121 IslandPair *ipair_get(int si, int di) {
122   IslandPair *ip, **ipa;
123
124   assert(si < islandtablesz);
125   assert(di < islandtablesz);
126
127   if (!(ipa= ipairs[si])) {
128     ipa= ipairs[si]= mcalloc(sizeof(*ipa) * islandtablesz);
129   }
130   if ((ip= ipa[di]))
131     return ip;
132
133   ipa[di]= ip= mmalloc(sizeof(*ip));
134   ip->trades= 0;
135   ip->route_tail_value= -1;
136
137   debugf("VALUE ipair_get(i%d,i%d) running...\n", si,di);
138   SQL_MUST( sqlite3_bind_int(ss_ipair_dist, 1, si) );
139   SQL_MUST( sqlite3_bind_int(ss_ipair_dist, 2, di) );
140   assert(SQL_STEP(ss_ipair_dist));
141   int dist= sqlite3_column_int(ss_ipair_dist, 0);
142   ip->distance_loss_factor= pow(distance_loss_factor_per_league, dist);
143   sqlite3_reset(ss_ipair_dist);
144   
145   return ip;
146 }
147
148 double value_route(int nislands, const int *islands, int exclude_arbitrage) {
149   int s,d;
150
151   /* We need to construct the LP problem.  GLPK talks
152    * about rows and columns, which are numbered from 1.
153    *
154    * Each column is a `structural variable' ie one of the entries in
155    * the objective function.  In our case the set of structural
156    * variable is, for each port, the set of Trades which collect at
157    * that island.  (We use `port' to mean `specific visit to an
158    * island' so if an island appears more than once so do its trades.)
159    * We don't need to worry about crossing with all the possible
160    * delivery locations as we always deliver on the first port.
161    * We will call such a structural variable a Flow, for brevity.
162    *
163    * We iterate over the possible Flows adding them as columns as we
164    * go, and also adding their entries to the various constraints.
165    *
166    * Each row is an `auxiliary variable' ie one of the constraints.
167    * We have two kinds of constraint:
168    *   - mass/volume/capital: one constraint for each sailed leg
169    *       (unless relevant constraint is not satisfied)
170    *   - quantity of commodity available for collection
171    *       or delivery at particular price and island
172    * The former are numbered predictably: we have first all the mass
173    * limits, then all the volume limits, then all the capital limits
174    * (as applicable) - one for each leg, ie one for each entry
175    * in islands except the first.
176    *
177    * The latter are added as needed and the row numbers are stored in
178    * a data structure for later reuse.
179    */
180
181   assert(nislands >= 1);
182   assert(++generation);
183
184   assert(!lp);
185   lp= lpx_create_prob();
186   lpx_set_obj_dir(lp, LPX_MAX);
187   lpx_set_int_parm(lp, LPX_K_MSGLEV, DEBUGP(lp) ? 3 : 1);
188
189   if (DEBUGP(value)) {
190     lpx_set_prob_name(lp,(char*)"value_route");
191     lpx_set_obj_name(lp,(char*)"profit");
192   }
193
194   int legs= nislands-1;
195   int mass_constraints= setup_leg_constraints(max_mass, legs, "mass");
196   int volu_constraints= setup_leg_constraints(max_volu, legs, "volu");
197   int capi_constraints= setup_leg_constraints(max_capi, legs, "capi");
198
199   double delay_slot_loss_factor= 1.0;
200   for (s=0;
201        s<nislands;
202        s++, delay_slot_loss_factor *= LOSS_FACTOR_PER_DELAY_SLOT) {
203     int si= islands[s];
204     
205     for (d= s + exclude_arbitrage;
206          d < nislands;
207          d++) {
208       int di= islands[d];
209       int already_d;
210       for (already_d=s+1; already_d<d; already_d++)
211         if (islands[already_d] == di)
212           /* visited this island already since we left s, uninteresting */
213           goto next_d;
214
215       if (d>s && di==si)
216         /* route has returned to si, no need to think more about s */
217         goto next_s;
218
219       /*----- actually add these trades to the LP problem -----*/
220       
221       IslandPair *ip= ipair_get(islands[s], islands[d]);
222
223       if (!ip->trades)
224         goto next_d;
225
226       double loss_factor= delay_slot_loss_factor * ip->distance_loss_factor;
227       debugf(" SOME   i%d#%d..i%d#%d  dslf=%g dlf=%g  lf=%g\n",
228              si,s, di,d,
229              delay_slot_loss_factor, ip->distance_loss_factor, loss_factor);
230
231       TradesBlock *block;
232       for (block=ip->trades; block; block=block->next) {
233         int inblock;
234         for (inblock=0; inblock<block->ntrades; inblock++) {
235           Trade *t= &block->t[inblock];
236
237           debugf("  TRADE i%d#%d..i%d#%d c%d %d-%d  ",
238                  si,s, di,d, t->commodid, t->src_price, t->dst_price);
239
240           nconstraint_rows=0;
241
242           avail_c(t, &itradeends[si].src, t->src_price, "src", si,ss_ite_sell);
243           avail_c(t, &itradeends[di].dst, t->dst_price, "dst", di,ss_ite_buy);
244
245           int leg;
246           for (leg=s; leg<d; leg++) {
247             add_leg_c(mass_constraints,leg, commodstab[t->commodid].mass*1e-3);
248             add_leg_c(volu_constraints,leg, commodstab[t->commodid].volu*1e-3);
249             add_leg_c(capi_constraints,leg, t->src_price);
250           }
251
252           double unit_profit= t->dst_price * loss_factor - t->src_price;
253           debugf("    unit profit %f\n", unit_profit);
254           if (unit_profit <= 0) continue;
255
256           int col= lpx_add_cols(lp,1);
257           lpx_set_col_bnds(lp, col, LPX_LO, 0, 0);
258           lpx_set_obj_coef(lp, col, unit_profit);
259           lpx_set_mat_col(lp, col, nconstraint_rows,
260                           constraint_rows, constraint_coeffs);
261
262           if (DEBUGP(value)) {
263             char *name= masprintf("c%d_p%d_%d_p%d_%d", t->commodid,
264                                   s, t->src_price, d, t->dst_price);
265             lpx_set_col_name(lp, col, name);
266             free(name);
267           }
268         } /* inblock */
269       } /* block */
270       
271       /*----- that's done adding these trades to the LP problem -----*/
272       
273     next_d:;
274     } /* for (d) */
275   next_s:;
276   } /* for (s) */
277
278   double profit= 0;
279
280   if (lpx_get_num_cols(lp)) {
281     if (DEBUGP(lp))
282       lpx_write_cpxlp(lp, (char*)DEBUG_DEV);
283
284     int ipr= lpx_simplex(lp);
285     assert(ipr==LPX_E_OK);
286
287     if (DEBUGP(lp))
288       lpx_print_sol(lp, (char*)DEBUG_DEV);
289
290     int lpst= lpx_get_status(lp);
291     assert(lpst == LPX_OPT);
292     profit= lpx_get_obj_val(lp);
293   }
294
295   lpx_delete_prob(lp);
296   lp= 0;
297
298   return profit;
299 }
300
301 #define TRADE_FROM                                                      \
302     "  FROM sell, buy\n"                                                \
303     "  WHERE sell.commodid=buy.commodid AND sell.price < buy.price\n"
304               
305 static void read_trades(void) {
306   /* We would like to use DISTINCT but sqlite3 is too stupid
307    * to notice that it could use the index to do the DISTINCT
308    * which makes it rather slow. */
309   sqlite3_stmt *ss_trades;
310
311 #define TRADE_COLS \
312     "sell.commodid, sell.islandid, sell.price, buy.islandid, buy.price"
313   SQL_PREPARE(ss_trades,
314               " SELECT " TRADE_COLS "\n"
315               TRADE_FROM
316               "  ORDER BY " TRADE_COLS);
317
318   SQL_DISTINCT_DECL(cols,5);
319   while (SQL_DISTINCT_STEP(ss_trades,cols,5)) {    
320     IslandPair *ip= ipair_get(cols[1], cols[3]);
321     TradesBlock *block= ip->trades;
322     if (!block || ip->trades->ntrades >= TRADES_PER_BLOCK) {
323       block= mmalloc(sizeof(*block));
324       block->next= ip->trades;
325       ip->trades= block;
326       block->ntrades= 0;
327     }
328     Trade *trade= &block->t[block->ntrades];
329     trade->commodid=  cols[0];
330     trade->src_price= cols[2];
331     trade->dst_price= cols[4];
332     block->ntrades++;
333   }
334   sqlite3_finalize(ss_trades);
335 }
336
337 static void read_islandtradeends(const char *bs, int srcdstoff) {
338
339 #define TRADEEND_KEYCOLS "%s.commodid, %s.islandid, %s.stallid"
340   char *stmt= masprintf(" SELECT " TRADEEND_KEYCOLS ", %s.price, %s.qty\n"
341                         TRADE_FROM
342                         "  ORDER BY "  TRADEEND_KEYCOLS,
343                         bs,bs,bs,bs,bs, bs,bs,bs);
344   char *stmt_id= masprintf("qtys (%s)",bs);
345   sqlite3_stmt *ss= sql_prepare(stmt, stmt_id);
346   free(stmt); free(stmt_id);
347
348   SQL_DISTINCT_DECL(cols,5);
349   while (SQL_DISTINCT_STEP(ss,cols,3)) {
350     IslandTradeEnd *search;
351
352     int commodid= cols[0];
353     int islandid= cols[1];
354     int price= cols[3];
355     int qty= cols[4];
356
357     IslandTradeEnd **trades= (void*)((char*)&itradeends[islandid] + srcdstoff);
358
359     for (search= *trades; search; search=search->next)
360       if (search->commodid==commodid && search->price==price)
361         goto found;
362     /* not found, add new end */
363
364     search= mmalloc(sizeof(*search));
365     search->commodid= commodid;
366     search->price= price;
367     search->next= *trades;
368     search->generation= 0;
369     search->qty= 0;
370     *trades= search;
371
372   found:
373     search->qty += qty;
374   }
375   sqlite3_finalize(ss);
376 }
377
378 void setup_value(void) {
379   sqlite3_stmt *sst;
380   int i;
381
382   commodstabsz= sql_single_int("SELECT max(commodid) FROM commods") + 1;
383   commodstab= mmalloc(sizeof(*commodstab)*commodstabsz);
384   for (i=0; i<commodstabsz; i++)
385     commodstab[i].mass= commodstab[i].volu= -1;
386
387   SQL_PREPARE(sst,
388               "SELECT commodid,unitmass,unitvolume FROM commods");
389   while (SQL_STEP(sst)) {
390     int id= sqlite3_column_int(sst,0);
391     assert(id>=0 && id<commodstabsz);
392     commodstab[id].mass= sqlite3_column_int(sst,1);
393     commodstab[id].volu= sqlite3_column_int(sst,2);
394   }
395   sqlite3_finalize(sst);
396
397   ipairs= mcalloc(sizeof(*ipairs) * islandtablesz);
398   itradeends= mcalloc(sizeof(*itradeends) * islandtablesz);
399
400   SQL_PREPARE(ss_ipair_dist,
401               " SELECT dist FROM dists\n"
402               "  WHERE aiid=? and biid=?");
403
404   read_trades();
405   read_islandtradeends("sell", offsetof(IslandTradeEndHeads, src));
406   read_islandtradeends("buy",  offsetof(IslandTradeEndHeads, dst));
407 }