Changeset 4


Ignore:
Timestamp:
09/18/19 10:00:22 (5 years ago)
Author:
bart
Message:

Faster example parties

Files:
13 added
25 edited

Legend:

Unmodified
Added
Removed

  • bidspace/pom.xml

    r2 r4  
    140140                                        <target>1.8</target>
    141141                                </configuration>
     142                        </plugin>
     143                        <plugin>
     144                                <groupId>org.apache.maven.plugins</groupId>
     145                                <artifactId>maven-source-plugin</artifactId>
     146                                <executions>
     147                                        <execution>
     148                                                <id>attach-sources</id>
     149                                                <goals>
     150                                                        <goal>jar</goal>
     151                                                </goals>
     152                                        </execution>
     153                                </executions>
    142154                        </plugin>
    143155

  • bidspace/src/main/java/geniusweb/bidspace/BidsWithUtility.java

    r2 r4  
    33import java.math.BigDecimal;
    44import java.math.BigInteger;
    5 import java.util.ArrayList;
    6 import java.util.LinkedList;
     5import java.util.Collections;
     6import java.util.HashMap;
    77import java.util.List;
     8import java.util.Map;
     9import java.util.stream.Collectors;
    810
    911import geniusweb.issuevalue.Bid;
     12import geniusweb.issuevalue.Domain;
     13import geniusweb.issuevalue.Value;
    1014import geniusweb.profile.utilityspace.LinearAdditiveUtilitySpace;
    1115import tudelft.utilities.immutablelist.AbstractImmutableList;
     16import tudelft.utilities.immutablelist.FixedList;
     17import tudelft.utilities.immutablelist.ImmutableList;
     18import tudelft.utilities.immutablelist.JoinedList;
     19import tudelft.utilities.immutablelist.MapList;
     20import tudelft.utilities.immutablelist.Tuple;
    1221
    1322/**
    14  * Object containing a subset of all bids, that have utility within given range.
     23 * Tool class containing functions dealing with utilities of all bids in a given
     24 * {@link LinearAdditiveUtilitySpace}. This class caches previously computed
     25 * values to accelerate the calls and subsequent calls. Re-use the object to
     26 * keep/reuse the cache.
    1527 */
    16 public class BidsWithUtility extends AbstractImmutableList<Bid> {
    17 
    18         private final List<Bid> collectedbids;
    19 
    20         /**
    21          * Create Bids with utility within given bounds.
    22          *
    23          * @param space the {@link LinearAdditiveUtilitySpace} to search
    24          * @param min   the minimum required utility
    25          * @param max   the maximum required utility
    26          */
    27         public BidsWithUtility(LinearAdditiveUtilitySpace space, BigDecimal min, BigDecimal max) {
    28                 this.collectedbids = new ArrayList<Bid>(getBids(space, min, max));
    29         }
    30 
    31         /**
    32          * Brute force hack for this time. Maybe we can construct this in a lazy way.
    33          *
    34          * @param space
    35          * @param min
    36          * @param max
    37          * @return
    38          */
    39         private List<Bid> getBids(LinearAdditiveUtilitySpace space, BigDecimal min, BigDecimal max) {
    40                 List<Bid> goodbids = new LinkedList<Bid>();
    41                 for (Bid bid : new AllBidsList(space.getDomain())) {
    42                         BigDecimal util = space.getUtility(bid);
    43                         if (util.compareTo(min) >= 0 && util.compareTo(max) <= 0) {
    44                                 goodbids.add(bid);
    45                         }
    46                 }
    47                 return goodbids;
     28public class BidsWithUtility {
     29
     30        private final List<IssueInfo> issueInfo;
     31        private final int precision; // #digits used for Intervals
     32
     33        /**
     34         * cache. Key = call arguments for {@link #get(int, Interval)}. Value=return
     35         * value of that call.
     36         */
     37        private final Map<Tuple<Integer, Interval>, ImmutableList<Bid>> cache = new HashMap<>();
     38
     39        /**
     40         * Default constructor, uses default precision 6. This value seems practical
     41         * for the common range of issues, utilities and weights. See
     42         * {@link #BidsWithUtil(LinearAdditiveUtilitySpace, int)} for more details
     43         * on the precision.
     44         *
     45         * @param space the {@link LinearAdditiveUtilitySpace} to analyze
     46         */
     47        public BidsWithUtility(LinearAdditiveUtilitySpace space) {
     48                this(space, 6);
     49        }
     50
     51        /**
     52         *
     53         * @param space     the {@link LinearAdditiveUtilitySpace} to analyze
     54         * @param precision the number of digits to use for computations. This value
     55         *                  should match the max number of (digits used in the
     56         *                  weight of an issue + number of digits used in the issue
     57         *                  utility). Usually you also look at the step size, and
     58         *                  the range of interest. For instance if your utility
     59         *                  function has values 1/3 and 2/3, then these have an
     60         *                  'infinite' number of relevant digits. But if we want to
     61         *                  search bids between utility 0.1 and 0.2, then computing
     62         *                  in 2 digits might already be sufficient. This algorithm
     63         *                  has memory and space complexity O( |nissues|
     64         *                  10^precision ). For spaces up to 7 issues, 7 digits
     65         *                  should be feasible; for 9 issues, 6 digits may be the
     66         *                  maximum.
     67         */
     68        public BidsWithUtility(LinearAdditiveUtilitySpace space, int precision) {
     69                this(getInfo(space, precision), precision);
     70        }
     71
     72        /**
     73         *
     74         * @param issuesInfo List of the relevant issues (in order of relevance) and
     75         *                   all info of each issue.
     76         * @param precision  the number of digits used in Intervals.
     77         */
     78        public BidsWithUtility(List<IssueInfo> issuesInfo, int precision) {
     79                if (issuesInfo == null || issuesInfo.isEmpty()) {
     80                        throw new IllegalArgumentException(
     81                                        "sortedissues list must contain at least 1 element");
     82                }
     83
     84                this.issueInfo = issuesInfo;
     85                this.precision = precision;
     86
     87        }
     88
     89        /**
     90         * @return the utility {@link Interval} of this space: minimum and maximum
     91         *         achievable utility.
     92         */
     93        public Interval getRange() {
     94                return getRange(issueInfo.size() - 1);
     95        }
     96
     97        /**
     98         *
     99         * @param range the minimum and maximum utility required of the bids. to be
     100         *              included (both ends inclusive).
     101         * @return a list with bids that have utility inside range. possibly empty.
     102         *         With decreasing precision, more bids may drop out due to rounding
     103         *         errors.
     104         */
     105        public ImmutableList<Bid> getBids(Interval range) {
     106                return get(issueInfo.size() - 1, range.round(precision));
     107        }
     108
     109        public List<IssueInfo> getInfo() {
     110                return Collections.unmodifiableList(issueInfo);
     111        }
     112
     113        /**
     114         * Create partial BidsWithUtil list considering only issues 0..n, with
     115         * utilities in given range.
     116         *
     117         * @param n    the number of {@link #issueRanges} to consider, we consider
     118         *             0..n here. The recursion decreases n until n=0
     119         * @param goal the minimum and maximum utility required of the bids. to be
     120         *             included (both ends inclusive)
     121         * @return BidsWithUtil list, possibly empty.
     122         */
     123        protected ImmutableList<Bid> get(int n, Interval goal) {
     124                if (goal == null) {
     125                        throw new NullPointerException("Interval=null");
     126                }
     127
     128                // clamp goal into what is reachable. Avoid caching empty
     129                goal = goal.intersect(getRange(n));
     130                if (goal.isEmpty()) {
     131                        return new FixedList<>();
     132                }
     133
     134                Tuple<Integer, Interval> cachetuple = new Tuple<>(n, goal);
     135                ImmutableList<Bid> cached = cache.get(cachetuple);
     136                if (cached != null) {
     137                        // hits++;
     138                        return cached;
     139                }
     140
     141                ImmutableList<Bid> result = checkedGet(n, goal);
     142                cache.put(cachetuple, result);
     143                return result;
     144        }
     145
     146        private static List<IssueInfo> getInfo(LinearAdditiveUtilitySpace space2,
     147                        int precision) {
     148                Domain dom = space2.getDomain();
     149                return space2.getDomain().getIssues().stream()
     150                                .map(issue -> new IssueInfo(issue, dom.getValues(issue),
     151                                                space2.getUtilities().get(issue),
     152                                                space2.getWeight(issue), precision))
     153                                .collect(Collectors.toList());
     154        }
     155
     156        private ImmutableList<Bid> checkedGet(int n, Interval goal) {
     157                IssueInfo info = issueInfo.get(n);
     158                // issue is the first issuesWithRange.
     159                String issue = issueInfo.get(n).getName();
     160
     161                if (n == 0)
     162                        return new OneIssueSubset(info, goal);
     163
     164                // make new list, joining all sub-lists
     165                ImmutableList<Bid> fulllist = new FixedList<>();
     166                for (Value val : info.getValues()) {
     167                        BigDecimal weightedutil = info.getWeightedUtil(val);
     168                        Interval subgoal = goal.subtract(weightedutil);
     169                        // recurse: get list of bids for the subspace
     170                        ImmutableList<Bid> partialbids = get(n - 1, subgoal);
     171
     172                        Bid bid = new Bid(issue, val);
     173                        ImmutableList<Bid> fullbids = new MapList<Bid, Bid>(
     174                                        pbid -> pbid.merge(bid), partialbids);
     175                        if (!fullbids.size().equals(BigInteger.ZERO))
     176                                fulllist = new JoinedList<Bid>(fullbids, fulllist);
     177                }
     178                return fulllist;
     179        }
     180
     181        /**
     182         * @param n the maximum issuevalue utility to include. Use n=index of last
     183         *          issue s= (#issues in the domain - 1) for the full range of this
     184         *          domain.
     185         * @return Interval (min, max) of the total weighted utility Interval of
     186         *         issues 0..n. All weighted utilities have been rounded to the set
     187         *         {@link #precision}
     188         */
     189        private Interval getRange(int n) {
     190                Interval value = Interval.ZERO;
     191                for (int i = 0; i <= n; i++) {
     192                        value = value.add(issueInfo.get(i).getInterval());
     193                }
     194                return value;
     195        }
     196
     197}
     198
     199/**
     200 * List of all one-issue bids that have utility inside given interval.
     201 */
     202class OneIssueSubset extends AbstractImmutableList<Bid> {
     203        private final IssueInfo info;
     204        private final Interval interval;
     205        private BigInteger size;
     206
     207        /**
     208         *
     209         * @param info     the {@link IssueInfo}
     210         * @param interval a utility interval (weighted)
     211         */
     212        OneIssueSubset(IssueInfo info, Interval interval) {
     213                this.info = info;
     214                this.interval = interval;
     215                this.size = BigInteger.valueOf(info.subsetSize(interval));
    48216        }
    49217
    50218        @Override
    51219        public Bid get(BigInteger index) {
    52                 return collectedbids.get(index.intValue());
     220                return new Bid(info.getName(),
     221                                info.subset(interval).get(index.intValue()));
    53222        }
    54223
    55224        @Override
    56225        public BigInteger size() {
    57                 return BigInteger.valueOf(collectedbids.size());
     226                return size;
    58227        }
    59228

  • bidspace/src/test/java/geniusweb/bidspace/BidsWithUtilityTest.java

    r2 r4  
    11package geniusweb.bidspace;
    22
    3 import static org.junit.Assert.assertEquals;
    4 import static org.mockito.Matchers.any;
    5 import static org.mockito.Mockito.mock;
    6 import static org.mockito.Mockito.when;
     3import static org.junit.Assert.assertTrue;
    74
    85import java.io.IOException;
    96import java.math.BigDecimal;
    107import java.math.BigInteger;
     8import java.math.RoundingMode;
    119import java.nio.file.Files;
    1210import java.nio.file.Paths;
     11import java.util.Arrays;
    1312import java.util.Collection;
    14 import java.util.HashMap;
    15 import java.util.LinkedList;
    16 import java.util.Map;
     13import java.util.Random;
    1714
    18 import org.junit.Before;
    1915import org.junit.Test;
     16import org.junit.runner.RunWith;
     17import org.junit.runners.Parameterized;
     18import org.junit.runners.Parameterized.Parameters;
    2019
    2120import com.fasterxml.jackson.databind.ObjectMapper;
    2221
    2322import geniusweb.issuevalue.Bid;
    24 import geniusweb.issuevalue.DiscreteValue;
    25 import geniusweb.issuevalue.DiscreteValueSet;
    26 import geniusweb.issuevalue.Domain;
    27 import geniusweb.issuevalue.NumberValue;
    28 import geniusweb.issuevalue.NumberValueSet;
    29 import geniusweb.issuevalue.ValueSet;
    3023import geniusweb.profile.Profile;
    3124import geniusweb.profile.utilityspace.LinearAdditiveUtilitySpace;
     25import tudelft.utilities.immutablelist.ImmutableList;
    3226
     27@RunWith(Parameterized.class)
    3328public class BidsWithUtilityTest {
    34         private static final DiscreteValue I1V2 = new DiscreteValue("i1v2");
    35         private static final DiscreteValue I1V1 = new DiscreteValue("i1v1");
    36         private static final NumberValue I2V1 = new NumberValue("2.00");
    37         private static final NumberValue I2V2 = new NumberValue("2.45");
    38         private static final NumberValue I2V3 = new NumberValue("2.90");
    39         private static final String DOMAINNAME = "testdomain";
    40         private static final String ISSUE1 = "issue1";
    41         private static final String ISSUE2 = "issue2";
    42         private static final Map<String, ValueSet> issues = new HashMap<>();
     29        private final static ObjectMapper jackson = new ObjectMapper();
     30        private final Interval utilityGoal = new Interval(new BigDecimal("0.50"),
     31                        new BigDecimal("0.51"));
     32        private LinearAdditiveUtilitySpace profile;
     33        private long expectedSize;
     34        private int accuracy = 5;
    4335
    44         private static ValueSet values1;
    45         private static ValueSet values2;
    46         private static final BigDecimal TWO = new BigDecimal("2");
    47         private static final BigDecimal THREE = new BigDecimal("3");
    48         private final static BigDecimal ZERO_1 = new BigDecimal("0.1"), ZERO_2 = new BigDecimal("0.2"),
    49                         ZERO_3 = new BigDecimal("0.3");
     36        @Parameters
     37        public static Collection<Object[]> data() {
     38                return Arrays.asList(new Object[][] {
     39                                { "src/test/resources/jobs/jobs1.json", 11 },
     40                                { "src/test/resources/7issues/7issues1.json", 260000 },
     41                                { "src/test/resources/9issues/9issues1.json", 25000000 } });
     42        }
    5043
    51         private static Domain domain;
    52         private final static ObjectMapper jackson = new ObjectMapper();
     44        public BidsWithUtilityTest(String filename, long expectedsize)
     45                        throws IOException {
     46                String file = new String(Files.readAllBytes(Paths.get(filename)));
     47                profile = (LinearAdditiveUtilitySpace) jackson.readValue(file,
     48                                Profile.class);
     49                this.expectedSize = expectedsize;
     50        }
    5351
    54         @Before
    55         public void before() {
    56                 Collection<DiscreteValue> discretevalues1 = new LinkedList<>();
    57                 discretevalues1.add(I1V1);
    58                 discretevalues1.add(I1V2);
    59                 values1 = new DiscreteValueSet(discretevalues1);
    60                 issues.put(ISSUE1, values1);
    61 
    62                 values2 = new NumberValueSet(TWO, THREE, new BigDecimal("0.45"));
    63                 issues.put(ISSUE2, values2);
    64 
    65                 domain = new Domain(DOMAINNAME, issues);
     52        /**
     53         * Test if the values are within acceptable range from the goal.
     54         */
     55        @Test
     56        public void test() {
     57                ImmutableList<Bid> list = new BidsWithUtility(profile, accuracy)
     58                                .getBids(utilityGoal);
     59                Random rand = new Random();
     60                // check not all but only 10000 random bids as list may be way too large
     61                // to test them all. Testing 1 billion bids may take 15 minutes or so on
     62                // quad core i7 @2.4GHz.....
     63                // also notice that we may be checking only part of the list if
     64                // the size of the list would become bigger than maxint.
     65                for (int n = 0; n < 10000; n++) {
     66                        Bid bid = list.get(rand.nextInt(list.size().intValue()));
     67                        assertTrue(utilityGoal.contains(profile.getUtility(bid)
     68                                        .setScale(accuracy - 1, RoundingMode.HALF_UP)));
     69                }
     70                assertTrue(
     71                                list.size().compareTo(BigInteger.valueOf(expectedSize)) >= 0);
    6672
    6773        }
    6874
    6975        @Test
    70         public void smokeTest() {
    71                 LinearAdditiveUtilitySpace space = mock(LinearAdditiveUtilitySpace.class);
    72                 when(space.getDomain()).thenReturn(domain);
    73                 when(space.getUtility(any(Bid.class))).thenReturn(ZERO_2);
    74                 new BidsWithUtility(space, new BigDecimal("0.1"), new BigDecimal("0.3"));
     76        public void testMaxUtil() {
     77                BidsWithUtility bidswithutil = new BidsWithUtility(profile);
     78                // notice, this is the *rounded* max util
     79                BigDecimal maxutil = bidswithutil.getRange().getMax();
     80                Interval goal = new Interval(
     81                                maxutil.subtract(new BigDecimal("0.00001")), maxutil);
     82
     83                ImmutableList<Bid> bidsnearmax = bidswithutil.getBids(goal);
     84                assertTrue(bidsnearmax.size() != BigInteger.ZERO);
     85
     86                BigDecimal foundmax = BigDecimal.ZERO;
     87                for (Bid bid : bidsnearmax) {
     88                        BigDecimal util = profile.getUtility(bid);
     89                        if (util.compareTo(foundmax) > 0) {
     90                                foundmax = util;
     91                        }
     92                }
     93                // found maximum may be slightly lower or higher because we rounded
     94                // all weighted utilities.
     95                assertTrue(Math
     96                                .abs(foundmax.doubleValue() - maxutil.doubleValue()) < 0.0001);
    7597        }
    7698
    7799        @Test
    78         public void testSelection() {
    79                 LinearAdditiveUtilitySpace space = mock(LinearAdditiveUtilitySpace.class);
     100        public void benchmark() {
     101                System.out.println("\nBenchmarking " + profile.getName());
     102                BigInteger domainsize = new AllBidsList(profile.getDomain()).size();
    80103
    81                 when(space.getDomain()).thenReturn(domain);
    82                 when(space.getUtility(any(Bid.class))).thenReturn(ZERO_2);
    83                 BidsWithUtility selected = new BidsWithUtility(space, new BigDecimal("0.1"), new BigDecimal("0.3"));
    84                 assertEquals(new BigInteger("6"), selected.size());
    85         }
    86 
    87         @Test
    88         public void testRealSpace() throws IOException {
    89                 String file1 = new String(Files.readAllBytes(Paths.get("src/test/resources/jobs/jobs1.json")));
    90                 LinearAdditiveUtilitySpace profile = (LinearAdditiveUtilitySpace) jackson.readValue(file1, Profile.class);
    91                 BidsWithUtility selected = new BidsWithUtility(profile, ZERO_1, ZERO_3);
    92 
    93                 assertEquals(new BigInteger("56"), selected.size());
    94                 for (Bid bid : selected) {
    95                         assertEquals(1, profile.getUtility(bid).compareTo(ZERO_1));
    96                         assertEquals(-1, profile.getUtility(bid).compareTo(ZERO_3));
    97                 }
     104                long start = System.currentTimeMillis();
     105                BidsWithUtility body = new BidsWithUtility(profile, accuracy);
     106                ImmutableList<Bid> list = body.getBids(utilityGoal);
     107                long end = System.currentTimeMillis();
     108                System.out.println("run time: " + (end - start) / 1000. + "s");
     109                System.out.println("Total size of bidspace:" + domainsize);
     110                System.out.println("Result size: " + list.size());
    98111        }
    99112

  • events/pom.xml

    r1 r4  
    134134                                        <target>1.8</target>
    135135                                </configuration>
     136                        </plugin>
     137                        <plugin>
     138                                <groupId>org.apache.maven.plugins</groupId>
     139                                <artifactId>maven-source-plugin</artifactId>
     140                                <executions>
     141                                        <execution>
     142                                                <id>attach-sources</id>
     143                                                <goals>
     144                                                        <goal>jar</goal>
     145                                                </goals>
     146                                        </execution>
     147                                </executions>
    136148                        </plugin>
    137149

  • exampleparties/boulware/pom.xml

    r2 r4  
    7474                                        <target>1.8</target>
    7575                                </configuration>
     76                        </plugin>
     77                        <plugin>
     78                                <groupId>org.apache.maven.plugins</groupId>
     79                                <artifactId>maven-source-plugin</artifactId>
     80                                <executions>
     81                                        <execution>
     82                                                <id>attach-sources</id>
     83                                                <goals>
     84                                                        <goal>jar</goal>
     85                                                </goals>
     86                                        </execution>
     87                                </executions>
    7688                        </plugin>
    7789

  • exampleparties/conceder/pom.xml

    r2 r4  
    7474                                        <target>1.8</target>
    7575                                </configuration>
     76                        </plugin>
     77                        <plugin>
     78                                <groupId>org.apache.maven.plugins</groupId>
     79                                <artifactId>maven-source-plugin</artifactId>
     80                                <executions>
     81                                        <execution>
     82                                                <id>attach-sources</id>
     83                                                <goals>
     84                                                        <goal>jar</goal>
     85                                                </goals>
     86                                        </execution>
     87                                </executions>
    7688                        </plugin>
    7789

  • exampleparties/hardliner/pom.xml

    r2 r4  
    7474                                        <target>1.8</target>
    7575                                </configuration>
     76                        </plugin>
     77                        <plugin>
     78                                <groupId>org.apache.maven.plugins</groupId>
     79                                <artifactId>maven-source-plugin</artifactId>
     80                                <executions>
     81                                        <execution>
     82                                                <id>attach-sources</id>
     83                                                <goals>
     84                                                        <goal>jar</goal>
     85                                                </goals>
     86                                        </execution>
     87                                </executions>
    7688                        </plugin>
    7789

  • exampleparties/linear/pom.xml

    r2 r4  
    7474                                        <target>1.8</target>
    7575                                </configuration>
     76                        </plugin>
     77                        <plugin>
     78                                <groupId>org.apache.maven.plugins</groupId>
     79                                <artifactId>maven-source-plugin</artifactId>
     80                                <executions>
     81                                        <execution>
     82                                                <id>attach-sources</id>
     83                                                <goals>
     84                                                        <goal>jar</goal>
     85                                                </goals>
     86                                        </execution>
     87                                </executions>
    7688                        </plugin>
    7789

  • exampleparties/randomparty/pom.xml

    r2 r4  
    156156                                        <target>1.8</target>
    157157                                </configuration>
     158                        </plugin>
     159                        <plugin>
     160                                <groupId>org.apache.maven.plugins</groupId>
     161                                <artifactId>maven-source-plugin</artifactId>
     162                                <executions>
     163                                        <execution>
     164                                                <id>attach-sources</id>
     165                                                <goals>
     166                                                        <goal>jar</goal>
     167                                                </goals>
     168                                        </execution>
     169                                </executions>
    158170                        </plugin>
    159171

  • exampleparties/randompartypy/pom.xml

    r2 r4  
    147147                                        <target>1.8</target>
    148148                                </configuration>
     149                        </plugin>
     150                        <plugin>
     151                                <groupId>org.apache.maven.plugins</groupId>
     152                                <artifactId>maven-source-plugin</artifactId>
     153                                <executions>
     154                                        <execution>
     155                                                <id>attach-sources</id>
     156                                                <goals>
     157                                                        <goal>jar</goal>
     158                                                </goals>
     159                                        </execution>
     160                                </executions>
    149161                        </plugin>
    150162

  • exampleparties/timedependentparty/pom.xml

    r2 r4  
    158158                        </plugin>
    159159
     160                        <plugin>
     161                                <groupId>org.apache.maven.plugins</groupId>
     162                                <artifactId>maven-source-plugin</artifactId>
     163                                <executions>
     164                                        <execution>
     165                                                <id>attach-sources</id>
     166                                                <goals>
     167                                                        <goal>jar</goal>
     168                                                </goals>
     169                                        </execution>
     170                                </executions>
     171                        </plugin>
    160172
    161173                        <plugin>

  • exampleparties/timedependentparty/src/main/java/geniusweb/exampleparties/timedependentparty/TimeDependentParty.java

    r3 r4  
    33import java.io.IOException;
    44import java.math.BigDecimal;
     5import java.math.BigInteger;
    56import java.net.URI;
    67import java.net.URISyntaxException;
    … …  
    1415import geniusweb.actions.Offer;
    1516import geniusweb.actions.PartyId;
    16 import geniusweb.bidspace.AllBidsList;
    17 import geniusweb.bidspace.BidsWithUtility;
    1817import geniusweb.issuevalue.Bid;
    1918import geniusweb.party.Capabilities;
    … …  
    2423import geniusweb.party.inform.Settings;
    2524import geniusweb.party.inform.YourTurn;
     25import geniusweb.profile.Profile;
    2626import geniusweb.profile.utilityspace.LinearAdditiveUtilitySpace;
    27 import geniusweb.profile.utilityspace.UtilitySpace;
    2827import geniusweb.profileconnection.ProfileConnectionFactory;
    2928import geniusweb.profileconnection.ProfileInterface;
    … …  
    3130import geniusweb.progress.ProgressRounds;
    3231import geniusweb.references.ProtocolRef;
     32import tudelft.utilities.immutablelist.ImmutableList;
    3333import tudelft.utilities.logging.Reporter;
    3434
    … …  
    4141public abstract class TimeDependentParty extends DefaultParty {
    4242
     43        private static final BigDecimal DEC0001 = new BigDecimal("0.0001");
     44        private static final BigDecimal DEC100 = new BigDecimal("100");
    4345        private ProfileInterface profileint;
     46        private LinearAdditiveUtilitySpace utilspace = null; // last received space
    4447        private PartyId me;
    4548        private Progress progress;
    46         private Double minUtil = null, maxUtil = null;
    4749        private Bid lastReceivedBid = null;
    48         private double tolerance;
     50        private ExtendedUtilSpace extendedspace;
    4951
    5052        public TimeDependentParty() {
    … …  
    7779                                this.me = settings.getID();
    7880                                this.progress = settings.getProgress();
    79                                 computeMinMax();
    8081                        } else if (info instanceof ActionDone) {
    8182                                Action otheract = ((ActionDone) info).getAction();
    … …  
    117118
    118119        private void myTurn() throws IOException {
    119                 Action myAction = null;
     120                updateUtilSpace();
    120121                Bid bid = makeBid();
    121                 UtilitySpace utilspace = getUtilSpace();
    122122
    123                 if (lastReceivedBid != null && utilspace.getUtility(lastReceivedBid)
    124                                 .compareTo(utilspace.getUtility(bid)) >= 0) {
     123                Action myAction;
     124                if (bid == null || lastReceivedBid != null
     125                                && utilspace.getUtility(lastReceivedBid)
     126                                                .compareTo(utilspace.getUtility(bid)) >= 0) {
     127                        // if bid==null we failed to suggest next bid.
    125128                        myAction = new Accept(me, lastReceivedBid);
    126129                } else {
    127                         myAction = new Offer(me, makeBid());
     130                        myAction = new Offer(me, bid);
    128131                }
    129132                getConnection().send(myAction);
    … …  
    131134        }
    132135
    133         private UtilitySpace getUtilSpace() {
    134                 return (LinearAdditiveUtilitySpace) profileint.getProfile();
     136        private LinearAdditiveUtilitySpace updateUtilSpace() {
     137                Profile newutilspace = profileint.getProfile();
     138                if (!newutilspace.equals(utilspace)) {
     139                        utilspace = (LinearAdditiveUtilitySpace) newutilspace;
     140                        extendedspace = new ExtendedUtilSpace(utilspace);
     141                }
     142                return utilspace;
    135143        }
    136144
    137145        /**
    138          * Computes the fields minutil and maxUtil if not yet computed. minutil is
    139          * the minimum utility of any bid, but at least the utility of the
    140          * reservation bid. maxUtil is the maximum util of any bid.
    141          * <p>
    142          * TODO this is simplistic, very expensive method and may cause us to run
    143          * out of time on large domains.
    144          * <p>
    145          * Can be called only after profileint has been set.
     146         * @return next possible bid with current target utility, or null if no such
     147         *         bid.
    146148         */
    147         private void computeMinMax() {
    148                 if (this.maxUtil != null && this.minUtil != null)
    149                         return;
    150                 this.minUtil = 1d;
    151                 this.maxUtil = 0d;
    152                 UtilitySpace utilspace = getUtilSpace();
    153                 AllBidsList allbidslist = new AllBidsList(
    154                                 profileint.getProfile().getDomain());
    155                 for (Bid bid : allbidslist) {
    156                         double util = utilspace.getUtility(bid).doubleValue();
    157                         if (util < minUtil)
    158                                 minUtil = util;
    159                         if (util > maxUtil)
    160                                 maxUtil = util;
    161                 }
    162 
    163                 Bid rvbid = utilspace.getReservationBid();
    164                 if (rvbid != null) {
    165                         double rv = utilspace.getUtility(rvbid).doubleValue();
    166                         if (rv > minUtil)
    167                                 minUtil = rv;
    168                 }
    169                 tolerance = 100 / allbidslist.size().longValue();
    170                 tolerance = Math.max(tolerance, 0.1);
    171         }
    172 
    173149        private Bid makeBid() {
    174150                double time = progress.get(System.currentTimeMillis());
    175                 double utilityGoal = utilityGoal(time, getE());
    176                 BidsWithUtility options = new BidsWithUtility(
    177                                 (LinearAdditiveUtilitySpace) profileint.getProfile(),
    178                                 BigDecimal.valueOf(utilityGoal),
    179                                 BigDecimal.valueOf(utilityGoal + tolerance));
     151                BigDecimal utilityGoal = utilityGoal(time, getE());
     152                ImmutableList<Bid> options = extendedspace.getBids(utilityGoal);
     153                if (options.size() == BigInteger.ZERO)
     154                        return null;
    180155                // pick a random one.
    181156                return options.get(new Random().nextInt(options.size().intValue()));
    … …  
    190165         * @return the utility goal for this time and e value
    191166         */
    192         private double utilityGoal(double t, double e) {
     167        private BigDecimal utilityGoal(double t, double e) {
     168                BigDecimal minUtil = extendedspace.getMin();
     169                BigDecimal maxUtil = extendedspace.getMax();
     170
    193171                double ft = 0;
    194172                if (e != 0)
    195173                        ft = Math.pow(t, 1 / e);
    196                 // we subtract 0.000001 to correct possibly small round-up errors
    197                 return minUtil + (maxUtil - minUtil) * (1 - ft) - 0.000001;
     174                // we subtract epsilon to correct possibly small round-up errors
     175                return new BigDecimal(minUtil.doubleValue()
     176                                + (maxUtil.doubleValue() - minUtil.doubleValue()) * (1 - ft))
     177                                                .min(maxUtil).max(minUtil);
    198178        }
    199179}

  • issuevalue/pom.xml

    r2 r4  
    128128                                        <target>1.8</target>
    129129                                </configuration>
     130                        </plugin>
     131                       
     132                        <plugin>
     133                                <groupId>org.apache.maven.plugins</groupId>
     134                                <artifactId>maven-source-plugin</artifactId>
     135                                <executions>
     136                                        <execution>
     137                                                <id>attach-sources</id>
     138                                                <goals>
     139                                                        <goal>jar</goal>
     140                                                </goals>
     141                                        </execution>
     142                                </executions>
    130143                        </plugin>
    131144

  • issuevalue/src/main/java/geniusweb/issuevalue/Bid.java

    r1 r4  
    33import java.util.Collections;
    44import java.util.HashMap;
     5import java.util.HashSet;
    56import java.util.Map;
    67import java.util.Set;
    … …  
    4041
    4142        /**
     43         * Makes partial bid with just 1 issue and value.
     44         *
     45         * @param issue the issue name
     46         * @param value the {@link Value}
     47         */
     48        public Bid(String issue, Value value) {
     49                if (issue == null || value == null) {
     50                        throw new NullPointerException("issue and value must be not =null");
     51                }
     52
     53                issuevalues = new HashMap<>();
     54                issuevalues.put(issue, value);
     55        }
     56
     57        /**
    4258         * @param issue
    4359         * @return the value for the given issue, or null if there is no value for
    … …  
    5975        public Set<String> getIssues() {
    6076                return Collections.unmodifiableSet(issuevalues.keySet());
     77        }
     78
     79        /**
     80         * Merges this partial bid with another partial bid.
     81         *
     82         * @param otherbid another partial bid.
     83         * @return a bid with the combined values of both partial bids.
     84         * @throws IllegalArgumentException if issues overlap.
     85         */
     86        public Bid merge(Bid otherbid) {
     87                Set<String> ourissues = new HashSet<>(issuevalues.keySet());
     88                ourissues.retainAll(otherbid.getIssues());
     89                if (!ourissues.isEmpty()) {
     90                        throw new IllegalArgumentException(
     91                                        "Otherbid contains issues that are already set:"
     92                                                        + ourissues);
     93                }
     94                HashMap<String, Value> newvalues = new HashMap<>(issuevalues);
     95                newvalues.putAll(otherbid.issuevalues);
     96                return new Bid(newvalues);
     97
    6198        }
    6299

  • issuevalue/src/test/java/geniusweb/issuevalue/BidTest.java

    r1 r4  
    1717import com.fasterxml.jackson.databind.ObjectMapper;
    1818
    19 import geniusweb.issuevalue.Bid;
    20 import geniusweb.issuevalue.DiscreteValue;
    21 import geniusweb.issuevalue.NumberValue;
    22 import geniusweb.issuevalue.Value;
    2319import tudelft.utilities.junit.GeneralTests;
    2420
    … …  
    125121        }
    126122
     123        @Test
     124        public void testMerge() {
     125                Map<String, Value> issuevalues = new HashMap<>();
     126                issuevalues.put(ISSUE1, VALUE1);
     127                Bid partial1 = new Bid(issuevalues);
     128
     129                issuevalues = new HashMap<>();
     130                issuevalues.put(ISSUE2, VALUE2);
     131                Bid partial2 = new Bid(issuevalues);
     132
     133                Bid mergedbid = partial1.merge(partial2);
     134                assertEquals(bidc, mergedbid);
     135        }
     136
     137        @Test(expected = IllegalArgumentException.class)
     138        public void testMergeIssuesOverlap() {
     139                Map<String, Value> issuevalues = new HashMap<>();
     140                issuevalues.put(ISSUE1, VALUE1);
     141                Bid partial1 = new Bid(issuevalues);
     142
     143                issuevalues = new HashMap<>();
     144                issuevalues.put(ISSUE1, VALUE2);
     145                Bid partial2 = new Bid(issuevalues);
     146
     147                partial1.merge(partial2);
     148        }
     149
     150        @Test
     151        public void smokeTestConstructor2() {
     152                new Bid("issue", new DiscreteValue("dss"));
     153        }
     154
     155        @Test
     156        public void smokeTestConstructor2b() {
     157                new Bid("issue", new NumberValue("0.5"));
     158        }
     159
     160        @Test(expected = NullPointerException.class)
     161        public void smokeTestConstructor2Null1() {
     162                new Bid(null, new DiscreteValue("dss"));
     163        }
     164
     165        @Test(expected = NullPointerException.class)
     166        public void smokeTestConstructor2Null2() {
     167                new Bid("issue", null);
     168        }
     169
    127170}

  • party/pom.xml

    r1 r4  
    154154                                        <target>1.8</target>
    155155                                </configuration>
     156                        </plugin>
     157                        <plugin>
     158                                <groupId>org.apache.maven.plugins</groupId>
     159                                <artifactId>maven-source-plugin</artifactId>
     160                                <executions>
     161                                        <execution>
     162                                                <id>attach-sources</id>
     163                                                <goals>
     164                                                        <goal>jar</goal>
     165                                                </goals>
     166                                        </execution>
     167                                </executions>
    156168                        </plugin>
    157169

  • profile/pom.xml

    r1 r4  
    134134                                        <target>1.8</target>
    135135                                </configuration>
     136                        </plugin>
     137                        <plugin>
     138                                <groupId>org.apache.maven.plugins</groupId>
     139                                <artifactId>maven-source-plugin</artifactId>
     140                                <executions>
     141                                        <execution>
     142                                                <id>attach-sources</id>
     143                                                <goals>
     144                                                        <goal>jar</goal>
     145                                                </goals>
     146                                        </execution>
     147                                </executions>
    136148                        </plugin>
    137149

  • profile/src/main/java/geniusweb/profile/utilityspace/LinearAdditiveUtilitySpace.java

    r1 r4  
    88import com.fasterxml.jackson.annotation.JsonAutoDetect;
    99import com.fasterxml.jackson.annotation.JsonAutoDetect.Visibility;
     10import com.fasterxml.jackson.annotation.JsonCreator;
     11import com.fasterxml.jackson.annotation.JsonProperty;
    1012
    1113import geniusweb.issuevalue.Bid;
    1214import geniusweb.issuevalue.Domain;
    1315import geniusweb.issuevalue.Value;
    14 
    15 import com.fasterxml.jackson.annotation.JsonCreator;
    16 import com.fasterxml.jackson.annotation.JsonProperty;
    1716
    1817/**
    … …  
    221220
    222221        /**
    223          * @return the map from issue names to valuesetutilities
     222         * @return the map from issue names to valuesetutilities (un-weighted)
    224223         */
    225224        public Map<String, ValueSetUtilities> getUtilities() {

  • profile/src/main/java/geniusweb/profile/utilityspace/NumberValueSetUtilities.java

    r3 r4  
    106106        }
    107107
     108        /**
     109         * @return the lowest value
     110         */
     111        public BigDecimal getLowValue() {
     112                return lowValue;
     113        }
     114
     115        /**
     116         *
     117         * @return the highest value
     118         */
     119        public BigDecimal getHighValue() {
     120                return highValue;
     121        }
     122
     123        /**
     124         *
     125         * @return the utility of the lowest value
     126         */
     127        public BigDecimal getLowUtility() {
     128                return lowUtility;
     129        }
     130
     131        /**
     132         *
     133         * @return the utility of the highest value
     134         */
     135        public BigDecimal getHighUtility() {
     136                return highUtility;
     137        }
     138
    108139        @Override
    109140        public String toString() {

  • profileconnection/pom.xml

    r1 r4  
    143143                                        <target>1.8</target>
    144144                                </configuration>
     145                        </plugin>
     146                        <plugin>
     147                                <groupId>org.apache.maven.plugins</groupId>
     148                                <artifactId>maven-source-plugin</artifactId>
     149                                <executions>
     150                                        <execution>
     151                                                <id>attach-sources</id>
     152                                                <goals>
     153                                                        <goal>jar</goal>
     154                                                </goals>
     155                                        </execution>
     156                                </executions>
    145157                        </plugin>
    146158

  • protocol/src/main/java/geniusweb/protocol/ProtocolException.java

    r1 r4  
    1313
    1414        /**
    15          *
    1615         * @param message the error message
    1716         * @param party   offending party, either the {@link PartyId} or a
    … …  
    1918         */
    2019        public ProtocolException(String message, String party) {
    21                 super(party + ":" + message);
    22                 this.party = party;
     20                this(message, party, null);
    2321        }
    2422
    2523        /**
     24         * ProtocolException is special, in that it does not auto-fill the
     25         * stacktrace. This is needed because usually a ProtocolException is caused
     26         * by a party doing a bad action. Creating a stacktrace pointing to the
     27         * class reporting the protocol exception (usually, the protocol handler)
     28         * makes no sense as the protocol handler is doing the correct job there.
     29         *
    2630         *
    2731         * @param message the error message
    … …  
    3135         */
    3236        public ProtocolException(String message, String party, Throwable e) {
    33                 super(party + ":" + message, e);
     37                super(party + ":" + message, e, true, false);
    3438                this.party = party;
    3539        }

  • protocol/src/main/java/geniusweb/protocol/session/saop/SAOP.java

    r1 r4  
    22
    33import java.io.IOException;
     4import java.sql.Date;
     5import java.text.SimpleDateFormat;
    46import java.util.List;
    57import java.util.Timer;
    … …  
    190192                                                        "BUG. Deadline timer has triggered but state is not final");
    191193                                }
     194                                log.log(Level.WARNING,
     195                                                "SAOP deadline reached. Terminating session.");
    192196                                finish();
    193197                        }
    … …  
    196200                // early
    197201                deadlinetimer.schedule(task, deadline.getDuration() + TIME_MARGIN);
     202                log.log(Level.INFO, "SAOP deadline set to "
     203                                + new SimpleDateFormat("yyyy/MM/dd HH:mm:ss")
     204                                                .format(new Date(System.currentTimeMillis()
     205                                                                + deadline.getDuration() + TIME_MARGIN)));
    198206        }
    199207
    … …  
    251259                        final ConnectionWithParty partyconn, final Action action) {
    252260                if (action == null) {
    253                         handleError("Received null from " + partyconn + ". Closing session",
     261                        handleError(partyconn
     262                                        + " did null action, breaching the protocol. Closing session",
    254263                                        partyconn.getParty().getName(), null);
    255264                        return;
    … …  
    259268                        if (!partyconn.getParty().equals(state.getNextActor())) {
    260269                                // party does not have the turn.
    261                                 throw new ProtocolException(" act without having the turn",
     270                                throw new ProtocolException(
     271                                                "Party acts without having the turn",
    262272                                                partyconn.getParty().getName());
    263273                        }

  • protocol/src/main/java/geniusweb/protocol/session/saop/SAOPState.java

    r1 r4  
    189189                }
    190190                if (!actor.equals(getNextActor())) {
    191                         throw new ProtocolException("actor does not have the turn ",
     191                        throw new ProtocolException("Party does not have the turn ",
    192192                                        actor.getName());
    193193
    … …  
    211211                        if (!bid.equals(((Accept) action).getBid())) {
    212212                                throw new ProtocolException(
    213                                                 "Accepts a bid that was not offered (last offer =" + bid
    214                                                                 + ", action=" + action + ")",
     213                                                "Party accepts a bid differing from the last offer ="
     214                                                                + bid + ", action=" + action + ")",
    215215                                                actor.getName());
    216216                        }

  • protocol/src/test/java/geniusweb/protocol/session/saop/SAOPStateTest.java

    r1 r4  
    284284                assertTrue(state.isFinal(NOW));
    285285                assertEquals(
    286                                 "geniusweb.protocol.ProtocolException: party1:actor does not have the turn ",
     286                                "geniusweb.protocol.ProtocolException: party1:Party does not have the turn ",
    287287                                state.getError().toString());
    288288        }
    … …  
    297297                state = state.with(party2, nullaccept);
    298298                assertTrue(state.isFinal(NOW));
    299                 assertTrue(state.getError().toString()
    300                                 .matches(".*party2.*Accepts a bid that was not offered.*"));
     299                assertTrue(state.getError().toString().matches(
     300                                ".*party2.*Party accepts a bid differing from the last offer.*"));
    301301        }
    302302

  • timeline/pom.xml

    r1 r4  
    121121                                        <target>1.8</target>
    122122                                </configuration>
     123                        </plugin>
     124                        <plugin>
     125                                <groupId>org.apache.maven.plugins</groupId>
     126                                <artifactId>maven-source-plugin</artifactId>
     127                                <executions>
     128                                        <execution>
     129                                                <id>attach-sources</id>
     130                                                <goals>
     131                                                        <goal>jar</goal>
     132                                                </goals>
     133                                        </execution>
     134                                </executions>
    123135                        </plugin>
    124136
Note: See TracChangeset for help on using the changeset viewer.