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