TTK
Loading...
Searching...
No Matches
AssignmentAuction.h
Go to the documentation of this file.
1
13
14#pragma once
15
16#include <AssignmentSolver.h>
17
18#include <limits>
19#include <queue>
20
21namespace ttk {
22
23 template <class dataType>
24 class AssignmentAuction : virtual public Debug,
25 public AssignmentSolver<dataType> {
26
27 public:
28 AssignmentAuction() = default;
29
30 ~AssignmentAuction() override = default;
31
32 int run(std::vector<MatchingType> &matchings) override;
33 void runAuctionRound(std::vector<std::vector<dataType>> &cMatrix);
34
35 void initFirstRound();
37 void initEpsilon();
38 void epsilonScaling();
39 void makeBalancedMatrix(std::vector<std::vector<dataType>> &matrix);
40
41 bool stoppingCriterion(std::vector<std::vector<dataType>> &cMatrix);
42 dataType getRelativePrecision(std::vector<std::vector<dataType>> &cMatrix);
43 dataType getMatchingDistance(std::vector<std::vector<dataType>> &cMatrix);
44
45 inline void setBalanced(bool balanced) override {
47 if(this->balancedAssignment)
48 goodPrices.resize(this->colSize, 0);
49 else
50 goodPrices.resize((this->colSize - 1) + (this->rowSize - 1), 0);
51 }
52
53 inline void setNumberOfRounds(int noRounds) {
54 numberOfRounds = noRounds;
55 }
56
57 inline int getIter() {
58 return iter;
59 }
60
61 inline void setEpsilon(double eps) {
62 epsilon = eps;
63 }
64
65 inline void setEpsilonDiviserMultiplier(double div) {
66 epsilonDiviserMultiplier = div;
67 }
68
69 inline void setPrices(std::vector<double> prices) {
70 goodPrices.resize(prices.size(), 0);
71 for(unsigned int i = 0; i < prices.size(); ++i)
72 goodPrices[i] = prices[i];
73 }
74
75 inline std::vector<double> &getPrices() {
76 return goodPrices;
77 }
78
79 private:
80 int numberOfRounds = -1;
81 int iter = 0;
82 double epsilon = -1;
83 double epsilonDiviserMultiplier = 0;
84 double delta_lim = 0.01;
85
86 dataType lowerBoundCostWeight = 1 + delta_lim;
87
88 // Filled
89 std::vector<int> bidderAssignments{1, -1}, bestBidderAssignments;
90 std::vector<int> goodAssignments{};
91 std::vector<double> goodPrices{};
92 dataType lowerBoundCost;
93 }; // AssignmentAuction Class
94
95 template <typename type>
96 static type abs(const type var) {
97 return (var >= 0) ? var : -var;
98 }
99
100 template <class dataType>
101 dataType getMaxValue(std::vector<std::vector<dataType>> &matrix,
102 bool balancedAsgn) {
103 unsigned int const nRows = matrix.size();
104 unsigned int const nCols = matrix[0].size();
105 dataType maxValue = std::numeric_limits<dataType>::lowest();
106 for(unsigned int i = 0; i < nRows; ++i) {
107 for(unsigned int j = 0; j < nCols; ++j) {
108 if(not balancedAsgn and i == nRows - 1 and j == nCols - 1)
109 continue;
110 maxValue = (matrix[i][j] > maxValue) ? matrix[i][j] : maxValue;
111 }
112 }
113 return maxValue;
114 }
115
116 template <typename dataType>
118 if(epsilon == -1.0) {
119 dataType maxValue
120 = getMaxValue<dataType>(this->costMatrix, this->balancedAssignment);
121 epsilon = maxValue / 4.0;
122 if(epsilon == 0.0)
123 epsilon = 1.0;
124 epsilon
125 /= ((epsilonDiviserMultiplier == 0) ? 1 : epsilonDiviserMultiplier * 5);
126 }
127 }
128
129 template <typename dataType>
131 epsilon /= 5;
132 /*if(epsilon < 1e-6)
133 epsilon = 1e-6;*/
134 }
135
136 template <typename dataType>
138 bidderAssignments.clear();
139 goodAssignments.clear();
140 if(this->balancedAssignment) {
141 bidderAssignments.resize(this->rowSize, -1);
142 goodAssignments.resize(this->colSize, -1);
143 } else {
144 bidderAssignments.resize((this->rowSize - 1) + (this->colSize - 1), -1);
145 goodAssignments.resize((this->colSize - 1) + (this->rowSize - 1), -1);
146 }
147 }
148
149 template <typename dataType>
151 iter = 0;
152 bidderAssignments[0] = -1;
153 }
154
155 template <typename dataType>
157 std::vector<std::vector<dataType>> &matrix) {
158 unsigned int const nRows = matrix.size();
159 unsigned int const nCols = matrix[0].size();
160 matrix[nRows - 1][nCols - 1] = 0;
161
162 // Add rows
163 for(unsigned int i = 0; i < nCols - 2; ++i) {
164 std::vector<dataType> const newLine(matrix[nRows - 1]);
165 matrix.push_back(newLine);
166 }
167 // Add columns
168 for(unsigned int i = 0; i < (nRows - 1) + (nCols - 1); ++i) {
169 for(unsigned int j = 0; j < nRows - 2; ++j) {
170 matrix[i].push_back(matrix[i][nCols - 1]);
171 }
172 }
173 }
174
175 // ----------------------------------------
176 // Main Functions
177 // ----------------------------------------
178 template <typename dataType>
180 std::vector<std::vector<dataType>> &cMatrix) {
181 std::queue<int> unassignedBidders{};
182 for(unsigned int i = 0; i < bidderAssignments.size(); ++i)
183 unassignedBidders.push(i);
184
185 while(!unassignedBidders.empty()) {
186 int const bidderId = unassignedBidders.front();
187 unassignedBidders.pop();
188
189 // Get good with highest value
190 dataType bestValue = std::numeric_limits<dataType>::lowest();
191 dataType bestSecondValue = std::numeric_limits<dataType>::lowest();
192 int bestGoodId = -1;
193 for(unsigned int goodId = 0; goodId < goodPrices.size(); ++goodId) {
194 if(cMatrix[bidderId][goodId] == static_cast<dataType>(-1))
195 continue;
196 dataType goodPrice = goodPrices[goodId];
197 dataType value = -cMatrix[bidderId][goodId] - goodPrice;
198 if(value > bestValue) {
199 bestSecondValue = bestValue;
200 bestValue = value;
201 bestGoodId = goodId;
202 } else if(value > bestSecondValue)
203 bestSecondValue = value;
204 }
205
206 // Update assignments
207 bidderAssignments[bidderId] = bestGoodId;
208 if(goodAssignments[bestGoodId] != -1)
209 unassignedBidders.push(goodAssignments[bestGoodId]);
210 goodAssignments[bestGoodId] = bidderId;
211
212 // If there is only one acceptable good for the bidder
213 if(bestSecondValue == std::numeric_limits<dataType>::lowest())
214 bestSecondValue = bestValue;
215
216 // Update price
217 double const delta = abs<dataType>(bestValue - bestSecondValue) + epsilon;
218 double newPrice = goodPrices[bestGoodId] + delta;
219 if(newPrice > std::numeric_limits<double>::max() / 2) {
220 // Avoid price explosion
221 newPrice = goodPrices[bestGoodId] + epsilon;
222 }
223 goodPrices[bestGoodId] = newPrice;
224 }
225 }
226
227 template <typename dataType>
228 dataType getLowerBoundCost(std::vector<std::vector<dataType>> &costMatrix) {
229 std::vector<dataType> minCol(
230 costMatrix[0].size(), std::numeric_limits<dataType>::max()),
231 minRow(costMatrix.size(), std::numeric_limits<dataType>::max());
232 for(unsigned int i = 0; i < costMatrix.size(); ++i) {
233 for(unsigned int j = 0; j < costMatrix[i].size(); ++j) {
234 if(costMatrix[i][j] < minCol[j])
235 minCol[j] = costMatrix[i][j];
236 if(costMatrix[i][j] < minRow[i])
237 minRow[i] = costMatrix[i][j];
238 }
239 }
240 dataType minColCost = 0, minRowCost = 0;
241 for(unsigned int i = 0; i < minCol.size(); ++i)
242 minColCost += minCol[i];
243 for(unsigned int i = 0; i < minRow.size(); ++i)
244 minRowCost += minRow[i];
245 dataType lowerBoundCost = std::max(minColCost, minRowCost);
246
247 return lowerBoundCost;
248 }
249
250 template <typename dataType>
251 int AssignmentAuction<dataType>::run(std::vector<MatchingType> &matchings) {
252 initEpsilon();
253 dataType bestCost = std::numeric_limits<dataType>::max();
254
255 // Try to avoid price war
256 double const tempPrice
257 = *std::max_element(goodPrices.begin(), goodPrices.end());
258 std::vector<double> savedPrices;
259 for(unsigned int i = 0; i < goodPrices.size(); ++i) {
260 auto old = goodPrices[i];
261 goodPrices[i]
262 = goodPrices[i] * epsilon / ((tempPrice == 0) ? 1 : tempPrice);
263 auto t = old - goodPrices[i];
264 savedPrices.push_back(t);
265 }
266
267 // Make balanced cost matrix
268 if(not this->balancedAssignment)
269 this->makeBalancedMatrix(this->costMatrix);
270
271 // Get lower bound cost
272 lowerBoundCost = getLowerBoundCost(this->costMatrix);
273
274 // Run auction
275 initFirstRound();
276 while(not stoppingCriterion(this->costMatrix)) {
277 initBiddersAndGoods();
278 runAuctionRound(this->costMatrix);
279
280 dataType cost = getMatchingDistance(this->costMatrix);
281 if(cost < bestCost) {
282 bestCost = cost;
283 bestBidderAssignments = bidderAssignments;
284 }
285
286 epsilonScaling();
287 iter++;
288
289 if(numberOfRounds != -1 and iter >= numberOfRounds)
290 break;
291 }
292 bidderAssignments = bestBidderAssignments;
293
294 // Create output matching
295 for(unsigned int bidderId = 0; bidderId < bidderAssignments.size();
296 ++bidderId) {
297 int const i = bidderId;
298 int const j = bidderAssignments[bidderId];
299 if(this->balancedAssignment
300 or (not this->balancedAssignment
301 and not(i >= this->rowSize - 1 and j >= this->colSize - 1))) {
302 matchings.push_back(std::make_tuple(i, j, this->costMatrix[i][j]));
303 }
304 }
305
306 // Set prices as before
307 for(unsigned int i = 0; i < goodPrices.size(); ++i)
308 goodPrices[i] += savedPrices[i];
309
310 return 0;
311 }
312
313 // ----------------------------------------
314 // Stopping Criterion Functions
315 // ----------------------------------------
316 // Adapted from Persistence Diagrams Auction
317 template <typename dataType>
319 std::vector<std::vector<dataType>> &cMatrix) {
320 if(bidderAssignments[0] == -1) // Auction not started
321 return false;
322 dataType delta = 5;
323 delta = getRelativePrecision(cMatrix);
324 return not(delta > delta_lim);
325 }
326
327 // Adapted from Persistence Diagrams Auction
328 template <typename dataType>
330 std::vector<std::vector<dataType>> &cMatrix) {
331 dataType d = this->getMatchingDistance(cMatrix);
332 if(d < 1e-6 or d <= (lowerBoundCost * lowerBoundCostWeight)) {
333 return 0;
334 }
335 dataType denominator = d - bidderAssignments.size() * epsilon;
336 if(denominator <= 0) {
337 return 1;
338 } else {
339 return d / denominator - 1;
340 }
341 }
342
343 // Adapted from Persistence Diagrams Auction
344 template <typename dataType>
346 std::vector<std::vector<dataType>> &cMatrix) {
347 dataType d = 0;
348 for(unsigned int bidderId = 0; bidderId < bidderAssignments.size();
349 ++bidderId) {
350 int const i = bidderId;
351 int const j = bidderAssignments[bidderId];
352 d += cMatrix[i][j];
353 }
354 return d;
355 }
356
357} // namespace ttk
void setEpsilon(double eps)
void runAuctionRound(std::vector< std::vector< dataType > > &cMatrix)
~AssignmentAuction() override=default
void setPrices(std::vector< double > prices)
bool stoppingCriterion(std::vector< std::vector< dataType > > &cMatrix)
void makeBalancedMatrix(std::vector< std::vector< dataType > > &matrix)
void setEpsilonDiviserMultiplier(double div)
dataType getRelativePrecision(std::vector< std::vector< dataType > > &cMatrix)
void setBalanced(bool balanced) override
int run(std::vector< MatchingType > &matchings) override
std::vector< double > & getPrices()
void setNumberOfRounds(int noRounds)
dataType getMatchingDistance(std::vector< std::vector< dataType > > &cMatrix)
virtual void setBalanced(bool balanced)
Minimalist debugging class.
Definition Debug.h:88
T var(const T *v, const int &dimension=3)
The Topology ToolKit.
dataType getLowerBoundCost(std::vector< std::vector< dataType > > &costMatrix)
dataType getMaxValue(std::vector< std::vector< dataType > > &matrix, bool balancedAsgn)