[519] | 1 | package geniusweb.bidspace;
|
---|
| 2 |
|
---|
| 3 | import java.math.BigDecimal;
|
---|
| 4 | import java.math.BigInteger;
|
---|
| 5 | import java.util.Collections;
|
---|
| 6 | import java.util.HashMap;
|
---|
| 7 | import java.util.List;
|
---|
| 8 | import java.util.Map;
|
---|
[579] | 9 | import java.util.function.Function;
|
---|
[519] | 10 | import java.util.stream.Collectors;
|
---|
| 11 |
|
---|
[804] | 12 | import org.eclipse.jdt.annotation.NonNull;
|
---|
| 13 |
|
---|
[519] | 14 | import geniusweb.issuevalue.Bid;
|
---|
| 15 | import geniusweb.issuevalue.Domain;
|
---|
| 16 | import geniusweb.issuevalue.Value;
|
---|
| 17 | import geniusweb.profile.utilityspace.LinearAdditive;
|
---|
| 18 | import tudelft.utilities.immutablelist.AbstractImmutableList;
|
---|
| 19 | import tudelft.utilities.immutablelist.FixedList;
|
---|
| 20 | import tudelft.utilities.immutablelist.ImmutableList;
|
---|
| 21 | import tudelft.utilities.immutablelist.JoinedList;
|
---|
| 22 | import tudelft.utilities.immutablelist.MapList;
|
---|
| 23 | import tudelft.utilities.immutablelist.Tuple;
|
---|
| 24 |
|
---|
| 25 | /**
|
---|
| 26 | * Tool class containing functions dealing with utilities of all bids in a given
|
---|
| 27 | * {@link LinearAdditive}. This class caches previously computed values to
|
---|
| 28 | * accelerate the calls and subsequent calls. Re-use the object to keep/reuse
|
---|
| 29 | * the cache.
|
---|
| 30 | * <h2>Rounding</h2> Internally, utilities of bids are rounded to the given
|
---|
| 31 | * precision. This may cause inclusion/exclusion of some bids in the results.
|
---|
| 32 | * See {@link #BidsWithUtility(LinearAdditive, int)} for more details
|
---|
| 33 | */
|
---|
| 34 | public class BidsWithUtility {
|
---|
| 35 |
|
---|
[814] | 36 | private final @NonNull List<@NonNull IssueInfo> issueInfo;
|
---|
[519] | 37 | private final int precision; // #digits used for Intervals
|
---|
| 38 |
|
---|
| 39 | /**
|
---|
| 40 | * cache. Key = call arguments for {@link #get(int, Interval)}. Value=return
|
---|
| 41 | * value of that call.
|
---|
| 42 | */
|
---|
[814] | 43 | private final @NonNull Map<@NonNull Tuple<@NonNull Integer, @NonNull Interval>, @NonNull ImmutableList<@NonNull Bid>> cache = new HashMap<>();
|
---|
| 44 | private final @NonNull ImmutableList<@NonNull Bid> emptylist = new FixedList<>();
|
---|
[519] | 45 |
|
---|
| 46 | /**
|
---|
| 47 | * Default constructor, uses default precision 6. This value seems practical
|
---|
| 48 | * for the common range of issues, utilities and weights. See
|
---|
| 49 | * {@link #BidsWithUtility(LinearAdditive, int)} for more details on the
|
---|
| 50 | * precision.
|
---|
| 51 | *
|
---|
| 52 | * @param space the {@link LinearAdditive} to analyze
|
---|
| 53 | */
|
---|
[810] | 54 | public BidsWithUtility(@NonNull LinearAdditive space) {
|
---|
[519] | 55 | this(space, 6);
|
---|
| 56 | }
|
---|
| 57 |
|
---|
| 58 | /**
|
---|
| 59 | *
|
---|
| 60 | * @param space the {@link LinearAdditive} to analyze
|
---|
| 61 | * @param precision the number of digits to use for computations. In
|
---|
| 62 | * practice, 6 seems a good default value.
|
---|
| 63 | * <p>
|
---|
| 64 | * All utilities * weight are rounded to this number of
|
---|
| 65 | * digits. This value should match the max number of
|
---|
| 66 | * (digits used in the weight of an issue + number of
|
---|
| 67 | * digits used in the issue utility). To determine the
|
---|
| 68 | * optimal value, one may consider the step size of the
|
---|
| 69 | * issues, and the range of interest. For instance if the
|
---|
| 70 | * utility function has values 1/3 and 2/3, then these have
|
---|
| 71 | * an 'infinite' number of relevant digits. But if the goal
|
---|
| 72 | * is to search bids between utility 0.1 and 0.2, then
|
---|
| 73 | * computing in 2 digits might already be sufficient.
|
---|
| 74 | * <p>
|
---|
| 75 | * This algorithm has memory and space complexity O(
|
---|
| 76 | * |nissues| 10^precision ). For spaces up to 7 issues, 7
|
---|
| 77 | * digits should be feasible; for 9 issues, 6 digits may be
|
---|
| 78 | * the maximum.
|
---|
| 79 | */
|
---|
[810] | 80 | public BidsWithUtility(@NonNull LinearAdditive space, int precision) {
|
---|
[519] | 81 | this(getInfo(space, precision), precision);
|
---|
| 82 | }
|
---|
| 83 |
|
---|
| 84 | /**
|
---|
| 85 | *
|
---|
| 86 | * @param issuesInfo List of the relevant issues (in order of relevance) and
|
---|
[814] | 87 | * all info of each issue. Must not be empty.
|
---|
[519] | 88 | * @param precision the number of digits used in Intervals.
|
---|
| 89 | */
|
---|
[814] | 90 | public BidsWithUtility(@NonNull List<@NonNull IssueInfo> issuesInfo,
|
---|
| 91 | int precision) {
|
---|
[519] | 92 | if (issuesInfo == null || issuesInfo.isEmpty()) {
|
---|
| 93 | throw new IllegalArgumentException(
|
---|
| 94 | "sortedissues list must contain at least 1 element");
|
---|
| 95 | }
|
---|
| 96 |
|
---|
| 97 | this.issueInfo = issuesInfo;
|
---|
| 98 | this.precision = precision;
|
---|
| 99 |
|
---|
| 100 | }
|
---|
| 101 |
|
---|
[825] | 102 | @NonNull
|
---|
[519] | 103 | /**
|
---|
| 104 | * @return the (rounded) utility {@link Interval} of this space: minimum and
|
---|
| 105 | * maximum achievable utility.
|
---|
| 106 | */
|
---|
[825] | 107 | public Interval getRange() {
|
---|
[519] | 108 | return getRange(issueInfo.size() - 1);
|
---|
| 109 | }
|
---|
| 110 |
|
---|
[825] | 111 | @NonNull
|
---|
[519] | 112 | /**
|
---|
| 113 | *
|
---|
| 114 | * @param range the minimum and maximum utility required of the bids. to be
|
---|
| 115 | * included (both ends inclusive).
|
---|
| 116 | * @return a list with bids that have a (rounded) utility inside range.
|
---|
| 117 | * possibly empty.
|
---|
| 118 | */
|
---|
[825] | 119 | public ImmutableList<@NonNull Bid> getBids(@NonNull Interval range) {
|
---|
[519] | 120 | return get(issueInfo.size() - 1, range.round(precision));
|
---|
| 121 | }
|
---|
| 122 |
|
---|
[814] | 123 | public @NonNull List<@NonNull IssueInfo> getInfo() {
|
---|
[519] | 124 | return Collections.unmodifiableList(issueInfo);
|
---|
| 125 | }
|
---|
| 126 |
|
---|
[825] | 127 | @NonNull
|
---|
[519] | 128 | /**
|
---|
| 129 | *
|
---|
| 130 | * @param isMax the extreme bid required
|
---|
| 131 | * @return the extreme bid, either the minimum if isMax=false or maximum if
|
---|
| 132 | * isMax=true
|
---|
| 133 | */
|
---|
[825] | 134 | public Bid getExtremeBid(boolean isMax) {
|
---|
[814] | 135 | final @NonNull Map<@NonNull String, @NonNull Value> map = new HashMap<>();
|
---|
| 136 | for (final @NonNull IssueInfo info : issueInfo) {
|
---|
[519] | 137 | map.put(info.getName(), info.getExtreme(isMax));
|
---|
| 138 | }
|
---|
| 139 | return new Bid(map);
|
---|
| 140 | }
|
---|
| 141 |
|
---|
[825] | 142 | @SuppressWarnings("unused")
|
---|
| 143 | @NonNull
|
---|
[519] | 144 | /**
|
---|
| 145 | * Create partial BidsWithUtil list considering only issues 0..n, with
|
---|
| 146 | * utilities in given range.
|
---|
| 147 | * <h2>Memory use</h2> Memory use of the return value can be large, if large
|
---|
| 148 | * domains are given and the requested interval contains large numbers of
|
---|
| 149 | * bids. To give some idea, here are some typical memory uses:
|
---|
| 150 | * <table border="1">
|
---|
| 151 | * <tr>
|
---|
| 152 | * <td>domain</td>
|
---|
| 153 | * <td>mem use (MB) of returned object</td>
|
---|
| 154 | * <td>nr. of selected bids</td>
|
---|
| 155 | * </tr>
|
---|
| 156 | * <tr>
|
---|
| 157 | * <td>jobs1</td>
|
---|
| 158 | * <td>0.028</td>
|
---|
| 159 | * <td>23</td>
|
---|
| 160 | * </tr>
|
---|
| 161 | * <tr>
|
---|
| 162 | * <td>7issues1</td>
|
---|
| 163 | * <td>34</td>
|
---|
| 164 | * <td>346327</td>
|
---|
| 165 | * </tr>
|
---|
| 166 | * <tr>
|
---|
| 167 | * <td>9issues1</td>
|
---|
| 168 | * <td>98</td>
|
---|
| 169 | * <td>37160666</td>
|
---|
| 170 | * </tr>
|
---|
| 171 | * </table>
|
---|
| 172 | *
|
---|
| 173 | * @param n the number of issueRanges to consider, we consider 0..n here.
|
---|
| 174 | * The recursion decreases n until n=0
|
---|
| 175 | * @param goal the minimum and maximum utility required of the bids. to be
|
---|
| 176 | * included (both ends inclusive)
|
---|
| 177 | * @return BidsWithUtil list, possibly empty.
|
---|
| 178 | */
|
---|
[825] | 179 | protected ImmutableList<@NonNull Bid> get(int n, @NonNull Interval goal) {
|
---|
[519] | 180 | if (goal == null) {
|
---|
| 181 | throw new NullPointerException("Interval=null");
|
---|
| 182 | }
|
---|
| 183 |
|
---|
| 184 | // clamp goal into what is reachable. Avoid caching empty
|
---|
| 185 | goal = goal.intersect(getRange(n));
|
---|
| 186 | if (goal.isEmpty()) {
|
---|
| 187 | return new FixedList<>();
|
---|
| 188 | }
|
---|
| 189 |
|
---|
[814] | 190 | final @NonNull Tuple<@NonNull Integer, @NonNull Interval> cachetuple = new Tuple<>(
|
---|
| 191 | n, goal);
|
---|
| 192 | final ImmutableList<@NonNull Bid> cached = cache.get(cachetuple);
|
---|
[519] | 193 | if (cached != null) {
|
---|
| 194 | // hits++;
|
---|
| 195 | return cached;
|
---|
| 196 | }
|
---|
| 197 |
|
---|
[814] | 198 | final @NonNull ImmutableList<@NonNull Bid> result = checkedGet(n, goal);
|
---|
[519] | 199 | cache.put(cachetuple, result);
|
---|
| 200 | return result;
|
---|
| 201 | }
|
---|
| 202 |
|
---|
[814] | 203 | private static @NonNull List<@NonNull IssueInfo> getInfo(
|
---|
| 204 | @NonNull LinearAdditive space2, int precision) {
|
---|
| 205 | final @NonNull Domain dom = space2.getDomain();
|
---|
[579] | 206 | /*#PY
|
---|
[814] | 207 | * return [ IssueInfo(issue, dom.getValues(issue),
|
---|
[579] | 208 | * space2.getUtilities().get(issue),
|
---|
| 209 | * space2.getWeight(issue), precision))
|
---|
| 210 | * for issue in space2.getDomain().getIssues() ]
|
---|
| 211 | */
|
---|
[744] | 212 | return space2.getDomain().getIssuesValues().stream()
|
---|
[519] | 213 | .map(issue -> new IssueInfo(issue, dom.getValues(issue),
|
---|
| 214 | space2.getUtilities().get(issue),
|
---|
| 215 | space2.getWeight(issue), precision))
|
---|
| 216 | .collect(Collectors.toList());
|
---|
| 217 | }
|
---|
| 218 |
|
---|
[810] | 219 | private @NonNull ImmutableList<@NonNull Bid> checkedGet(int n,
|
---|
[814] | 220 | final @NonNull Interval goal) {
|
---|
[810] | 221 | final @NonNull IssueInfo info = issueInfo.get(n);
|
---|
[519] | 222 | // issue is the first issuesWithRange.
|
---|
[810] | 223 | final @NonNull String issue = info.getName();
|
---|
[519] | 224 |
|
---|
| 225 | if (n == 0)
|
---|
| 226 | return new OneIssueSubset(info, goal);
|
---|
| 227 |
|
---|
| 228 | // make new list, joining all sub-lists
|
---|
[810] | 229 | @NonNull
|
---|
| 230 | ImmutableList<@NonNull Bid> fulllist = emptylist;
|
---|
| 231 | for (@NonNull
|
---|
| 232 | Value val : info.getValues()) {
|
---|
[519] | 233 | BigDecimal weightedutil = info.getWeightedUtil(val);
|
---|
[810] | 234 | @NonNull
|
---|
[519] | 235 | Interval subgoal = goal.subtract(weightedutil);
|
---|
| 236 | // recurse: get list of bids for the subspace
|
---|
[810] | 237 | @NonNull
|
---|
| 238 | ImmutableList<@NonNull Bid> partialbids = get(n - 1, subgoal);
|
---|
[519] | 239 |
|
---|
[810] | 240 | ImmutableList<@NonNull Bid> fullbids = new MapList<@NonNull Bid, @NonNull Bid>(
|
---|
[814] | 241 | (Function<@NonNull Bid, @NonNull Bid>) pbid -> pbid
|
---|
[579] | 242 | .merge(new Bid(issue, val)),
|
---|
| 243 | partialbids);
|
---|
[519] | 244 | if (!fullbids.size().equals(BigInteger.ZERO))
|
---|
[810] | 245 | fulllist = new JoinedList<@NonNull Bid>(fullbids, fulllist);
|
---|
[519] | 246 | }
|
---|
| 247 | return fulllist;
|
---|
| 248 | }
|
---|
| 249 |
|
---|
[825] | 250 | @NonNull
|
---|
[519] | 251 | /**
|
---|
| 252 | * @param n the maximum issuevalue utility to include. Use n=index of last
|
---|
| 253 | * issue s= (#issues in the domain - 1) for the full range of this
|
---|
| 254 | * domain.
|
---|
| 255 | * @return Interval (min, max) of the total weighted utility Interval of
|
---|
| 256 | * issues 0..n. All weighted utilities have been rounded to the set
|
---|
| 257 | * {@link #precision}
|
---|
| 258 | */
|
---|
[825] | 259 | private Interval getRange(int n) {
|
---|
[814] | 260 | @NonNull
|
---|
[519] | 261 | Interval value = Interval.ZERO;
|
---|
[579] | 262 | for (int i = 0; i <= n; i = i + 1) {
|
---|
[519] | 263 | value = value.add(issueInfo.get(i).getInterval());
|
---|
| 264 | }
|
---|
| 265 | return value;
|
---|
| 266 | }
|
---|
| 267 |
|
---|
| 268 | }
|
---|
| 269 |
|
---|
| 270 | /**
|
---|
| 271 | * List of all one-issue bids that have utility inside given interval.
|
---|
| 272 | */
|
---|
[810] | 273 | class OneIssueSubset extends AbstractImmutableList<@NonNull Bid> {
|
---|
[814] | 274 | private final @NonNull IssueInfo info;
|
---|
| 275 | private final @NonNull Interval interval;
|
---|
| 276 | private @NonNull BigInteger size;
|
---|
[519] | 277 |
|
---|
| 278 | /**
|
---|
| 279 | *
|
---|
| 280 | * @param info the {@link IssueInfo}
|
---|
| 281 | * @param interval a utility interval (weighted)
|
---|
| 282 | */
|
---|
[814] | 283 | OneIssueSubset(@NonNull IssueInfo info, @NonNull Interval interval) {
|
---|
[519] | 284 | this.info = info;
|
---|
| 285 | this.interval = interval;
|
---|
| 286 | this.size = BigInteger.valueOf(info.subsetSize(interval));
|
---|
| 287 | }
|
---|
| 288 |
|
---|
| 289 | @Override
|
---|
[804] | 290 | public @NonNull Bid get(@NonNull BigInteger index) {
|
---|
[519] | 291 | return new Bid(info.getName(),
|
---|
| 292 | info.subset(interval).get(index.intValue()));
|
---|
| 293 | }
|
---|
| 294 |
|
---|
| 295 | @Override
|
---|
[804] | 296 | public @NonNull BigInteger size() {
|
---|
[519] | 297 | return size;
|
---|
| 298 | }
|
---|
| 299 |
|
---|
| 300 | } |
---|