X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~yarrgweb/git?a=blobdiff_plain;f=yarrg%2Fweb%2Froutetrade;h=b198b9b3867ab7cff6ca4fb2150f2b33d037c921;hb=7cc77cd4ea67381979c41f74927a40d28225d618;hp=0da1fd80a81929454605e46df2064d56d26d3083;hpb=555b3391b3cd9967a29b219fff242b583137d2b8;p=ypp-sc-tools.db-live.git diff --git a/yarrg/web/routetrade b/yarrg/web/routetrade index 0da1fd8..b198b9b 100644 --- a/yarrg/web/routetrade +++ b/yarrg/web/routetrade @@ -38,23 +38,22 @@ $dbh @islandids @archipelagoes $qa -$max_mass -$max_volume -$lossperleaguepct +$routeparams %args> -<&| script &> - da_pageload= Date.now(); -&script> +<& query_age:pageload &> <%perl> -my $loss_per_league= defined $lossperleaguepct ? $lossperleaguepct*0.01 : 1e-7; +my $loss_per_league= defined $routeparams->{LossPerLeaguePct} + ? $routeparams->{LossPerLeaguePct}*0.01 : 1e-7; +my $loss_per_delay_slot= 1e-8; my $now= time; my @flow_conds; my @query_params; my %dists; +my $expected_total_profit; my $sd_condition= sub { my ($bs, $ix) = @_; @@ -67,42 +66,43 @@ my $sd_condition= sub { } }; -my %islandpair; -# $islandpair{$a,$b}= [ $start_island_ix, $end_island_ix ] - my $specific= !grep { !defined $_ } @islandids; -my $confusing= 0; -foreach my $src_i (0..$#islandids) { - my $src_isle= $islandids[$src_i]; - my $src_cond= $sd_condition->('sell',$src_i); +my %ipair2subflowinfs; +# $ipair2subflowinfs{$orgi,$dsti}= [ [$orgix,$distix], ... ] + +my @subflows; +# $subflows[0]{Flow} = { ... } +# $subflows[0]{Org} = $orgix +# $subflows[0]{Dst} = $dstix + +foreach my $org_i (0..$#islandids) { + my $org_isle= $islandids[$org_i]; + my $org_cond= $sd_condition->('sell',$org_i); my @dst_conds; - foreach my $dst_i ($src_i..$#islandids) { + foreach my $dst_i ($org_i..$#islandids) { my $dst_isle= $islandids[$dst_i]; - my $dst_cond= $sd_condition->('buy',$dst_i); - if ($dst_i==$src_i and !defined $src_isle) { + # Don't ever consider sailing things round the houses: + next if defined $dst_isle and + grep { $dst_isle == $_ } @islandids[$org_i..$dst_i-1]; + next if defined $org_isle and + grep { $org_isle == $_ } @islandids[$org_i+1..$dst_i]; + my $dst_cond; + if ($dst_i==$org_i and !defined $org_isle) { # we always want arbitrage, but mentioning an arch # once shouldn't produce intra-arch trades - $dst_cond= - "($dst_cond AND sell.islandid = buy.islandid)"; + $dst_cond= "sell.islandid = buy.islandid"; + } else { + $dst_cond= $sd_condition->('buy',$dst_i); } push @dst_conds, $dst_cond; - if ($specific && !$confusing && - # With a circular route, do not carry goods round the loop - !(($src_i==0 || $src_i==$#islandids) && - $dst_i==$#islandids && - $src_isle == $islandids[$dst_i])) { - if ($islandpair{$src_isle,$dst_isle}) { - $confusing= 1; -print "confusing $src_i $src_isle $dst_i $dst_isle\n"; - } else { - $islandpair{$src_isle,$dst_isle}= - [ $src_i, $dst_i ]; - } + if ($specific) { + push @{ $ipair2subflowinfs{$org_isle,$dst_isle} }, + [ $org_i, $dst_i ]; } } - push @flow_conds, "$src_cond AND ( + push @flow_conds, "$org_cond AND ( ".join(" OR ",@dst_conds)." )"; @@ -241,7 +241,6 @@ foreach my $v (qw(MaxMass MaxVolume)) { $f= { Ix => scalar(@flows), - Var => "f".@flows, %$got }; $f->{"org_stallid"}= $f->{"dst_stallid"}= 'all' @@ -262,9 +261,18 @@ foreach my $v (qw(MaxMass MaxVolume)) { <& dumptable:end, qa => $qa &> % } +% if (@islandids==1) { +% if (defined $islandids[0]) { +Searched for arbitrage trades only. +% } else { +Searched for arbitrage trades only, in <% $archipelagoes[0] |h %> +[?]. +% } +% } + <%perl> -my @total_massvol; +my @sail_total; if (!@flows) { print 'No profitable trading opportunities were found.'; @@ -313,7 +321,7 @@ foreach my $f (@flows) { my $first= $base; do { my $this= $uue % $base; -print STDERR "uue=$uue this=$this "; +#print STDERR "uue=$uue this=$this "; $uue -= $this; $uue /= $base; $this += $first; @@ -321,8 +329,8 @@ print STDERR "uue=$uue this=$this "; $cmpu .= chr($this + ($this < 26 ? ord('a') : $this < 52 ? ord('A')-26 : ord('0')-52)); -print STDERR " uue=$uue this=$this cmpu=$cmpu\n"; -die "$cmpu $uue ?" if length $cmpu > 20; +#print STDERR " uue=$uue this=$this cmpu=$cmpu\n"; + die "$cmpu $uue ?" if length $cmpu > 20; } while ($uue); $cmpu; } @uid; @@ -361,25 +369,33 @@ die "$cmpu $uue ?" if length $cmpu > 20; if (defined $qa->{"R$f->{UidShort}"} && !defined $qa->{"T$f->{UidShort}"}) { $f->{Suppress}= 1; + } else { + my $sfis= $ipair2subflowinfs{$f->{'org_id'},$f->{'dst_id'}}; + foreach my $sfi (@$sfis) { + my $subflow= { + Flow => $f, + Org => $sfi->[0], + Dst => $sfi->[1], + Var => sprintf "f%ss%s_c%d_p%d_%d_p%d_%d", + $f->{Ix}, $sfi->[0], + $f->{'commodid'}, + $sfi->[0], $f->{'org_price'}, + $sfi->[1], $f->{'dst_price'} + }; + push @{ $f->{Subflows} }, $subflow; + push @subflows, $subflow; + } } - } %perl> -% my $optimise= $specific && !$confusing && @islandids>1; +% my $optimise= $specific; % if (!$optimise) {
-% if (@islandids<=1) { -Route contains only one location. -% } % if (!$specific) { Route contains archipelago(es), not just specific islands. % } -% if ($confusing) { -Route is complex - it visits the same island several times -and isn't a simple loop. -% } Therefore, optimal voyage trade plan not calculated. % } else { # ========== OPTMISATION ========== @@ -389,82 +405,97 @@ my $cplex= " Maximize totalprofit: - ".(join " - ", map { - sprintf "%+.20f %s", $_->{ExpectedUnitProfit}, $_->{Var} - } @flows)." +"; + +foreach my $sf (@subflows) { + my $eup= $sf->{Flow}{ExpectedUnitProfit}; + $eup *= (1.0-$loss_per_delay_slot) ** $sf->{Org}; + $cplex .= sprintf " + %+.20f %s", $eup, $sf->{Var}; +} +$cplex .= " Subject To "; -my %avail_csts; +my %avail_lims; foreach my $flow (@flows) { - if ($flow->{Suppress}) { - $cplex .= " - $flow->{Var} = 0 -"; - next; - } + next if $flow->{Suppress}; foreach my $od (qw(org dst)) { - my $cstname= join '_', ( - 'avail', - $flow->{'commodid'}, + my $limname= join '_', ( $od, - $flow->{"${od}_id"}, + 'i'.$flow->{"${od}_id"}, + 'c'.$flow->{'commodid'}, $flow->{"${od}_price"}, $flow->{"${od}_stallid"}, ); - - push @{ $avail_csts{$cstname}{Flows} }, $flow->{Var}; - $avail_csts{$cstname}{Qty}= $flow->{"${od}_qty_agg"}; + + push @{ $avail_lims{$limname}{SubflowVars} }, + map { $_->{Var} } @{ $flow->{Subflows} }; + $avail_lims{$limname}{Qty}= $flow->{"${od}_qty_agg"}; } } -foreach my $cstname (sort keys %avail_csts) { - my $c= $avail_csts{$cstname}; - $cplex .= " - ". sprintf("%-30s","$cstname:")." ". - join("+", @{ $c->{Flows} }). - " <= ".$c->{Qty}."\n"; +foreach my $limname (sort keys %avail_lims) { + my $c= $avail_lims{$limname}; + $cplex .= + sprintf(" %-30s","$limname:")." ". + join("+", @{ $c->{SubflowVars} }). + " <= ".$c->{Qty}."\n"; } foreach my $ci (0..($#islandids-1)) { - my @rel_flows; + my @rel_subflows; + foreach my $f (@flows) { next if $f->{Suppress}; - next if $f->{'org_id'} == $f->{'dst_id'}; - next unless grep { $f->{'org_id'} == $_ } - @islandids[0..$ci]; - next unless grep { $f->{'dst_id'} == $_ } - @islandids[$ci+1..@islandids-1]; - push @rel_flows, $f; -#print " RELEVANT $ci $f->{Ix} "; + my @relsubflow= grep { + $_->{Org} <= $ci && + $_->{Dst} > $ci; + } @{ $f->{Subflows} }; + next unless @relsubflow; + die unless @relsubflow == 1; + push @rel_subflows, @relsubflow; +#print " RELEVANT $ci $relsubflow[0]->{Var} "; } -#print " RELEVANT $ci COUNT ".scalar(@rel_flows)." "; - next unless @rel_flows; - foreach my $mv (qw(mass volume)) { - my $max_vn= "max_$mv"; - my $max= $mv eq 'mass' ? $max_mass : $max_volume; +#print " RELEVANT $ci COUNT ".scalar(@rel_subflows)." "; + if (!@rel_subflows) { + foreach my $mv (qw(mass volume)) { + $sail_total[$ci]{$mv}= 0; + } + next; + } + + my $applylimit= sub { + my ($mv, $f2val) = @_; + my $max= $routeparams->{"Max".ucfirst $mv}; $max= 1e9 unless defined $max; #print " DEFINED MAX $mv $max "; $cplex .= " ". sprintf("%-10s","${mv}_$ci:")." ". - join(" + ", map { ($_->{"unit$mv"}*1e-3).' f'.$_->{Ix} } @rel_flows). - " <= $max"; - } + join(" + ", map { +#print " PART MAX $_->{Var} $_->{Flow}{Ix} "; + $f2val->($_->{Flow}) .' '. $_->{Var}; + } @rel_subflows). + " <= $max"; + }; + + $applylimit->('mass', sub { $_[0]{'unitmass'} *1e-3 }); + $applylimit->('volume', sub { $_[0]{'unitvolume'}*1e-3 }); + $applylimit->('capital', sub { $_[0]{'org_price'} }); $cplex.= "\n"; } $cplex.= " Bounds ".(join " - ", map { "$_->{Var} >= 0" } @flows)." + ", map { "$_->{Var} >= 0" } @subflows)." "; $cplex.= " Integer ".(join " - ", map { "f$_" } (0..$#flows))." + ", map { $_->{Var} } @subflows)." End "; @@ -481,7 +512,8 @@ if ($qa->{'debug'}) { my $input= pipethrough_prep(); print $input $cplex or die $!; my $output= pipethrough_run_along($input, undef, 'glpsol', - qw(glpsol --cpxlp /dev/stdin -o /dev/stdout)); + qw(glpsol --tmlim 2 --memlim 5 --intopt --cuts --bfs + --cpxlp /dev/stdin -o /dev/stdout)); print "
\n" if $qa->{'debug'}; my $found_section= 0; my $glpsol_out= ''; @@ -494,6 +526,9 @@ if ($qa->{'debug'}) { $found_section= 1; next; } + if (m/^Objective:\s+totalprofit = (\d+(?:\.\d*)?) /) { + $expected_total_profit= $1; + } next unless $found_section==1; if (!length $continuation) { next if !$continuation && m/^[- ]+$/; @@ -511,31 +546,31 @@ if ($qa->{'debug'}) { my ($varname, $qty) = m/^ \s* \d+ \s+ (\w+) \s+ (?: [A-Z*]+ \s+ )? - ([0-9.]+) \s - /x or die "$_ ?"; - if ($varname =~ m/^f(\d+)$/) { - my ($ix) = $1; + ([+-e0-9.]+) \s + /x or die "$cplex \n==\n $glpsol_out $_ ?"; + if ($varname =~ m/^f(\d+)s(\d+)_/) { + my ($ix,$orgix) = ($1,$2); my $flow= $flows[$ix] or die; - $flow->{OptQty}= $qty; - $flow->{OptProfit}= $flow->{'unitprofit'} * $qty; - $flow->{OptCapital}= $flow->{OptQty} * - $flow->{'org_price'}; + my @relsubflow= grep { $_->{Org} == $orgix } + @{ $flow->{Subflows} }; + die "$ix $orgix @relsubflow" unless @relsubflow == 1; + my $sf= $relsubflow[0]; + $sf->{OptQty}= $qty; + $sf->{OptProfit}= $qty * $flow->{'unitprofit'}; + $sf->{OptCapital}= $qty * $flow->{'org_price'}; } elsif ($varname =~ m/^(mass|volume)_(\d+)$/) { my ($mv,$ix) = ($1,$2); - $total_massvol[$ix]{$mv}= $qty; + $sail_total[$ix]{$mv}= $qty; } } print "\n" if $qa->{'debug'}; my $prerr= "\n=====\n$cplex\n=====\n$glpsol_out\n=====\n "; pipethrough_run_finish($output,$prerr); - map { defined $_->{OptQty} or die "$prerr $_->{Ix}" } @flows; -# map { defined -# die $prerr if grep { ! } @flows; -# map { die -# die $prerr if map { + map { defined $_->{OptQty} or die "$prerr $_->{Flow}{Ix}" } @subflows; + defined $expected_total_profit or die "$prerr ?"; }; -$addcols->({ DoReverse => 1, Special => sub { +$addcols->({ DoReverse => 1, TotalSubflows => 1, Special => sub { my ($flow,$col,$v,$spec) = @_; if ($flow->{ExpectedUnitProfit} < 0) { $spec->{Span}= 3; @@ -545,7 +580,7 @@ $addcols->({ DoReverse => 1, Special => sub { } }, qw( OptQty )); -$addcols->({ Total => 0, DoReverse => 1 }, qw( +$addcols->({ Total => 0, DoReverse => 1, TotalSubflows => 1 }, qw( OptCapital OptProfit )); @@ -553,113 +588,32 @@ $addcols->({ Total => 0, DoReverse => 1 }, qw( % } # ========== OPTIMISATION ========== -% my %ts_sortkeys; -% { -% my $cdspan= $qa->{ShowStalls} ? ' colspan=2' : ''; -% my $cdstall= $qa->{ShowStalls} ? '
- | >Collect - | >Deliver - | - | Collect - | Deliver - | Profit - | Max - | - | Max -% if ($optimise) { - | Planned -% } - - | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
- | Island <% $cdstall %> - | Island <% $cdstall %> - | Commodity - | Price - | Qty - | Price - | Qty - | Margin - | Unit - | Qty - | Capital - | Profit - | Dist - | Mass - | Vol -% if ($optimise) { - | Qty - | Capital - | Profit
-% }
+% if (!printable($m)) {
+Contents+
|
Stall | ' : ''; +
---|
+ | >Collect + | >Deliver + | + | Collect + | Deliver + | Profit + | Max + | + | Max +% if ($optimise) { + | Planned +% } + + | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
+ | Island <% $cdstall %> + | Island <% $cdstall %> + | Commodity + | Price + | Qty + | Price + | Qty + | Margin + | Unit + | Qty + | Capital + | Profit + | Dist + | Mass + | Vol +% if ($optimise) { + | Qty + | Capital + | Profit +% } +% } + + |
+% } + +% foreach my $flowix (0..$#flows) { +% my $flow= $flows[$flowix]; +% my $rowid= "id_row_$flow->{UidShort}"; + | ||||||||||||||||||
{UidShort} %> value=""> + {UidShort} %> value="" + <% $flow->{Suppress} ? '' : 'checked' %> > +% my $ci= 1; +% while ($ci < @cols) { +% my $col= $cols[$ci]; +% my $spec= { +% Span => 1, +% Align => ($col->{Text} ? '' : 'align=right') +% }; +% my $cn= $col->{Name}; +% my $v; +% if (!$col->{TotalSubflows}) { +% $v= $flow->{$cn}; +% } else { +% $v= 0; +% $v += $_->{$cn} foreach @{ $flow->{Subflows} }; +% } +% if ($col->{Special}) { $col->{Special}($flow,$col,$v,$spec); } +% $col->{Total} += $v +% if defined $col->{Total} and not $flow->{Suppress}; +% $v='' if !$col->{Text} && !$v; +% my $sortkey= $col->{SortColKey} ? +% $flow->{$col->{SortColKey}} : $v; +% $ts_sortkeys{$ci}{$rowid}= $sortkey; + | {Span} ? "colspan=$spec->{Span}" : '' + %> <% $spec->{Align} + %>><% exists $spec->{String} ? $spec->{String} : $v |h %> +% $ci += $spec->{Span}; +% } +% } + | |||||||||||||||||
+ | Total +% foreach my $ci (3..$#cols) { +% my $col= $cols[$ci]; + | +% if (defined $col->{Total}) { +<% $col->{Total} |h %> +% } +% } + |
+ + +% } # !printable + <%init> use CommodsWeb; use Commods;