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

Last change on this file since 88 was 88, checked in by Bart Vastenhouw, 3 years ago

Added python SimpleRunner GUI

File size: 7.6 KB
Line 
1
2
3from geniusweb.issuevalue.Bid import Bid
4from geniusweb.issuevalue.Domain import Domain
5from geniusweb.issuevalue.Value import Value
6from geniusweb.profile.utilityspace.LinearAdditive import LinearAdditive
7from tudelft.utilities.immutablelist.AbstractImmutableList import AbstractImmutableList
8from tudelft.utilities.immutablelist.FixedList import FixedList
9from tudelft.utilities.immutablelist.ImmutableList import ImmutableList
10from tudelft.utilities.immutablelist.JoinedList import JoinedList
11from tudelft.utilities.immutablelist.MapList import MapList
12from tudelft.utilities.immutablelist.Tuple import Tuple
13from typing import List, Dict
14from geniusweb.bidspace.IssueInfo import IssueInfo
15from geniusweb.bidspace.Interval import Interval
16from geniusweb.utils import val
17from decimal import Decimal
18
19class BidsWithUtility :
20 '''
21 WARNING DO NOT USE, NOT YET WORKING CORRECTLY
22
23 Tool class containing functions dealing with utilities of all bids in a given
24 {@link LinearAdditive}. This class caches previously computed values to
25 accelerate the calls and subsequent calls. Re-use the object to keep/reuse
26 the cache.
27 <h2>Rounding</h2> Internally, utilities of bids are rounded to the given
28 precision. This may cause inclusion/exclusion of some bids in the results.
29 See {@link #BidsWithUtility(LinearAdditive, int)} for more details
30 Immutable.
31 '''
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
80 def getRange(self) ->Interval :
81 '''
82 @return the (rounded) utility {@link Interval} of this space: minimum and
83 maximum achievable utility.
84 '''
85 return self._getRange(len(self._issueInfo) - 1)
86
87 def getBids(self, range: Interval) -> ImmutableList[Bid] :
88 '''
89 @param range the minimum and maximum utility required of the bids. to be
90 included (both ends inclusive).
91 @return a list with bids that have a (rounded) utility inside range.
92 possibly empty.
93 '''
94 return self._get(len(self._issueInfo) - 1, range.round(self._precision));
95
96 def getInfo(self) -> List[IssueInfo] :
97 return self._issueInfo.copy()
98
99 def getExtremeBid(self, isMax:bool) ->Bid :
100 '''
101 @param isMax the extreme bid required
102 @return the extreme bid, either the minimum if isMax=false or maximum if
103 isMax=true
104 '''
105 map:Dict[str, Value] = {}
106 for info in self._issueInfo:
107 map[info.getName()] = info.getExtreme(isMax)
108 return Bid(map)
109
110 def _get(self, n:int , goal:Interval) -> ImmutableList[Bid] :
111 '''
112 Create partial BidsWithUtil list considering only issues 0..n, with
113 utilities in given range.
114
115 @param n the number of issueRanges to consider, we consider 0..n here.
116 The recursion decreases n until n=0
117 @param goal the minimum and maximum utility required of the bids. to be
118 included (both ends inclusive)
119 @return BidsWithUtil list, possibly empty.
120 '''
121 if goal == None:
122 raise ValueError("Interval=null")
123
124 # clamp goal into what is reachable. Avoid caching empty
125 goal = goal.intersect(self._getRange(n))
126 if (goal.isEmpty()):
127 return FixedList([])
128
129 cachetuple = Tuple(n, goal)
130 if (cachetuple in self._cache):
131 return self._cache[cachetuple]
132
133 result = self._checkedGet(n, goal)
134 self._cache[cachetuple]=result
135 return result
136
137 @staticmethod
138 def _getInfo(space2:LinearAdditive , precision:int) -> List[IssueInfo] :
139 dom = space2.getDomain()
140 return [IssueInfo(issue, dom.getValues(issue), \
141 val(space2.getUtilities().get(issue)), \
142 space2.getWeight(issue), precision) \
143 for issue in dom.getIssues()]
144
145
146 def _checkedGet(self, n:int, goal:Interval ) -> ImmutableList[Bid] :
147 info = self._issueInfo[n]
148 # issue is the first issuesWithRange.
149 issue = info.getName()
150
151 if n == 0:
152 return OneIssueSubset(info, goal)
153
154 # make new list, joining all sub-lists
155 fulllist:ImmutableList[Bid] = FixedList([])
156 for val in info.getValues():
157 weightedutil = info.getWeightedUtil(val)
158 subgoal = goal.subtract(weightedutil)
159 # recurse: get list of bids for the subspace
160 partialbids = self._get(n - 1, subgoal)
161
162 bid = Bid({issue: val})
163 fullbids = BidsWithUtility.maplist(bid, partialbids)
164 if fullbids.size() != 0:
165 fulllist = JoinedList[Bid]([fullbids, fulllist])
166 return fulllist
167
168 @staticmethod
169 def maplist(bid: Bid, partialbids: ImmutableList[Bid]) -> ImmutableList[Bid]:
170 '''
171 this is just to force a scope onto bid
172 '''
173 return MapList[Bid, Bid](lambda pbid: pbid.merge(bid), partialbids)
174
175 def _getRange(self, n:int) ->Interval :
176 '''
177 @param n the maximum issuevalue utility to include. Use n=index of last
178 issue s= (#issues in the domain - 1) for the full range of this
179 domain.
180 @return Interval (min, max) of the total weighted utility Interval of
181 issues 0..n. All weighted utilities have been rounded to the set
182 {@link #precision}
183 '''
184 value = Interval(Decimal(0),Decimal(0))
185 for i in range(0,n+1): # include end point
186 value = value.add(self._issueInfo[i].getInterval())
187 return value
188
189class OneIssueSubset (AbstractImmutableList[Bid]):
190 '''
191 List of all one-issue bids that have utility inside given interval.
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.