source: geniuswebcore/geniusweb/bidspace/BidsWithUtility.py@ 97

Last change on this file since 97 was 96, checked in by Bart Vastenhouw, 2 years ago

Fixed small issues in domaineditor.

File size: 7.5 KB
Line 
1
2
3from decimal import Decimal
4from typing import List, Dict
5
6from tudelft.utilities.immutablelist.AbstractImmutableList import AbstractImmutableList
7from tudelft.utilities.immutablelist.FixedList import FixedList
8from tudelft.utilities.immutablelist.ImmutableList import ImmutableList
9from tudelft.utilities.immutablelist.JoinedList import JoinedList
10from tudelft.utilities.immutablelist.MapList import MapList
11from tudelft.utilities.immutablelist.Tuple import Tuple
12
13from geniusweb.bidspace.Interval import Interval
14from geniusweb.bidspace.IssueInfo import IssueInfo
15from geniusweb.issuevalue.Bid import Bid
16from geniusweb.issuevalue.Domain import Domain
17from geniusweb.issuevalue.Value import Value
18from geniusweb.profile.utilityspace.LinearAdditive import LinearAdditive
19from geniusweb.utils import val
20
21
22class BidsWithUtility:
23 '''
24 Tool class containing functions dealing with utilities of all bids in a given
25 {@link LinearAdditive}. This class caches previously computed values to
26 accelerate the calls and subsequent calls. Re-use the object to keep/reuse
27 the cache.
28 <h2>Rounding</h2> Internally, utilities of bids are rounded to the given
29 precision. This may cause inclusion/exclusion of some bids in the results.
30 See {@link #BidsWithUtility(LinearAdditive, int)} for more details
31 Immutable.
32 '''
33
34 def __init__(self, issuesInfo:List[IssueInfo] , precision:int):
35 '''
36 @param issuesInfo List of the relevant issues (in order of relevance) and
37 all info of each issue.
38 @param precision the number of digits to use for computations. In
39 practice, 6 seems a good default value.
40 <p>
41 All utilities * weight are rounded to this number of
42 digits. This value should match the max number of
43 (digits used in the weight of an issue + number of
44 digits used in the issue utility). To determine the
45 optimal value, one may consider the step size of the
46 issues, and the range of interest. For instance if the
47 utility function has values 1/3 and 2/3, then these have
48 an 'infinite' number of relevant digits. But if the goal
49 is to search bids between utility 0.1 and 0.2, then
50 computing in 2 digits might already be sufficient.
51 <p>
52 This algorithm has memory and space complexity O(
53 |nissues| 10^precision ). For spaces up to 7 issues, 7
54 digits should be feasible; for 9 issues, 6 digits may be
55 the maximum.
56 '''
57 if issuesInfo == None or len(issuesInfo) == 0:
58 raise ValueError("sortedissues list must contain at least 1 element")
59 self._issueInfo = issuesInfo;
60 self._precision = precision;
61 # cache. Key = call arguments for {@link #get(int, Interval)}. Value=return
62 # value of that call.
63
64 self._cache:Dict[Tuple[int, Interval], ImmutableList[Bid]] = {}
65
66 @staticmethod
67 def create(space:LinearAdditive, precision:int=6) -> "BidsWithUtility":
68 '''
69 Support constructor, uses default precision 6. This value seems practical
70 for the common range of issues, utilities and weights. See
71 {@link #BidsWithUtility(LinearAdditive, int)} for more details on the
72 precision.
73
74 @param space the {@link LinearAdditive} to analyze
75 @param space the {@link LinearAdditive} to analyze. Optional, defaults to 6
76 '''
77 return BidsWithUtility(BidsWithUtility._getInfo(space, precision), precision);
78
79 def getRange(self) -> Interval:
80 '''
81 @return the (rounded) utility {@link Interval} of this space: minimum and
82 maximum achievable utility.
83 '''
84 return self._getRange(len(self._issueInfo) - 1)
85
86 def getBids(self, range: Interval) -> ImmutableList[Bid]:
87 '''
88 @param range the minimum and maximum utility required of the bids. to be
89 included (both ends inclusive).
90 @return a list with bids that have a (rounded) utility inside range.
91 possibly empty.
92 '''
93 return self._get(len(self._issueInfo) - 1, range.round(self._precision));
94
95 def getInfo(self) -> List[IssueInfo]:
96 return self._issueInfo.copy()
97
98 def getExtremeBid(self, isMax:bool) -> Bid:
99 '''
100 @param isMax the extreme bid required
101 @return the extreme bid, either the minimum if isMax=false or maximum if
102 isMax=true
103 '''
104 map:Dict[str, Value] = {}
105 for info in self._issueInfo:
106 map[info.getName()] = info.getExtreme(isMax)
107 return Bid(map)
108
109 def _get(self, n:int , goal:Interval) -> ImmutableList[Bid]:
110 '''
111 Create partial BidsWithUtil list considering only issues 0..n, with
112 utilities in given range.
113
114 @param n the number of issueRanges to consider, we consider 0..n here.
115 The recursion decreases n until n=0
116 @param goal the minimum and maximum utility required of the bids. to be
117 included (both ends inclusive)
118 @return BidsWithUtil list, possibly empty.
119 '''
120 if goal == None:
121 raise ValueError("Interval=null")
122
123 # clamp goal into what is reachable. Avoid caching empty
124 goal = goal.intersect(self._getRange(n))
125 if (goal.isEmpty()):
126 return FixedList([])
127
128 cachetuple = Tuple(n, goal)
129 if (cachetuple in self._cache):
130 return self._cache[cachetuple]
131
132 result = self._checkedGet(n, goal)
133 self._cache[cachetuple] = result
134 return result
135
136 @staticmethod
137 def _getInfo(space2:LinearAdditive , precision:int) -> List[IssueInfo]:
138 dom = space2.getDomain()
139 return [IssueInfo(issue, dom.getValues(issue), \
140 val(space2.getUtilities().get(issue)), \
141 space2.getWeight(issue), precision) \
142 for issue in dom.getIssues()]
143
144 def _checkedGet(self, n:int, goal:Interval) -> ImmutableList[Bid]:
145 info = self._issueInfo[n]
146 # issue is the first issuesWithRange.
147 issue = info.getName()
148
149 if n == 0:
150 return OneIssueSubset(info, goal)
151
152 # make new list, joining all sub-lists
153 fulllist:ImmutableList[Bid] = FixedList([])
154 for val in info.getValues():
155 weightedutil = info.getWeightedUtil(val)
156 subgoal = goal.subtract(weightedutil)
157 # recurse: get list of bids for the subspace
158 partialbids = self._get(n - 1, subgoal)
159
160 bid = Bid({issue: val})
161 fullbids = BidsWithUtility.maplist(bid, partialbids)
162 if fullbids.size() != 0:
163 fulllist = JoinedList[Bid]([fullbids, fulllist])
164 return fulllist
165
166 @staticmethod
167 def maplist(bid: Bid, partialbids: ImmutableList[Bid]) -> ImmutableList[Bid]:
168 '''
169 this is just to force a scope onto bid
170 '''
171 return MapList[Bid, Bid](lambda pbid: pbid.merge(bid), partialbids)
172
173 def _getRange(self, n:int) -> Interval:
174 '''
175 @param n the maximum issuevalue utility to include. Use n=index of last
176 issue s= (#issues in the domain - 1) for the full range of this
177 domain.
178 @return Interval (min, max) of the total weighted utility Interval of
179 issues 0..n. All weighted utilities have been rounded to the set
180 {@link #precision}
181 '''
182 value = Interval(Decimal(0), Decimal(0))
183 for i in range(0, n + 1): # include end point
184 value = value.add(self._issueInfo[i].getInterval())
185 return value
186
187
188class OneIssueSubset (AbstractImmutableList[Bid]):
189 '''
190 List of all one-issue bids that have utility inside given interval.
191 '''
192
193 def __init__(self, info:IssueInfo , interval:Interval):
194 '''
195 @param info the {@link IssueInfo}
196 @param interval a utility interval (weighted)
197 '''
198 self._info = info;
199 self._interval = interval;
200 self._size = info._subsetSize(interval)
201
202 # Override
203 def get(self, index:int) -> Bid:
204 return Bid({self._info.getName():
205 self._info._subset(self._interval)[index]})
206
207 # Override
208 def size(self) -> int:
209 return self._size
Note: See TracBrowser for help on using the repository browser.