1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
/*
Copyright (c) 2015, M. Kerber, D. Morozov, A. Nigmetov
All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
You are under no obligation whatsoever to provide any bug fixes, patches, or
upgrades to the features, functionality or performance of the source code
(Enhancements) to anyone; however, if you choose to make your Enhancements
available either publicly, or directly to copyright holder,
without imposing a separate written license agreement for such Enhancements,
then you hereby grant the following license: a non-exclusive, royalty-free
perpetual license to install, use, modify, prepare derivative works, incorporate
into other computer software, distribute, and sublicense such enhancements or
derivative works thereof, in binary and source code form.
*/
#ifndef AUCTION_ORACLE_KDTREE_SINGLE_DIAG_H
#define AUCTION_ORACLE_KDTREE_SINGLE_DIAG_H
#include <map>
#include <memory>
#include <set>
#include <list>
#include <ostream>
#include "basic_defs_ws.h"
#include "dnn/geometry/euclidean-fixed.h"
#include "dnn/local/kd-tree.h"
namespace hera {
namespace ws {
template <class Real = double>
struct ItemSlice;
template <class Real = double>
bool operator<(const ItemSlice<Real>& s_1, const ItemSlice<Real>& s_2);
template <class Real = double>
bool operator>(const ItemSlice<Real>& s_1, const ItemSlice<Real>& s_2);
template <class Real>
struct ItemSlice {
public:
using RealType = Real;
size_t item_idx;
Real loss;
ItemSlice(size_t _item_idx, const Real _loss);
void set_loss(const Real new_loss) { loss = new_loss; }
void adjust_loss(const Real delta) { loss -= delta; }
friend bool operator< <>(const ItemSlice<Real>&, const ItemSlice<Real>&);
friend bool operator> <>(const ItemSlice<Real>&, const ItemSlice<Real>&);
private:
};
template <class Real = double>
class LossesHeap {
public:
using ItemSliceR = ItemSlice<Real>;
using KeeperTypeR = std::set<ItemSliceR, std::less<ItemSliceR> >;
using IterTypeR = typename KeeperTypeR::iterator;
LossesHeap() {}
LossesHeap(const std::vector<ItemSliceR>&);
void adjust_prices(const Real delta); // subtract delta from all values
ItemSliceR get_best_slice() const;
ItemSliceR get_second_best_slice() const;
template<typename ...Args>
decltype(auto) emplace(Args&&... args)
{
return keeper.emplace(std::forward<Args>(args)...);
}
IterTypeR begin() { return keeper.begin(); }
IterTypeR end() { return keeper.end(); }
void erase(IterTypeR iter) { assert(iter != keeper.end()); keeper.erase(iter); }
decltype(auto) insert(const ItemSliceR& item) { return keeper.insert(item); }
size_t size() const { return keeper.size(); }
bool empty() const { return keeper.empty(); }
//private:
std::set<ItemSliceR, std::less<ItemSliceR> > keeper;
};
template <class Real>
struct DiagonalBid {
DiagonalBid() {}
std::vector<size_t> assigned_normal_items;
std::vector<Real> assigned_normal_items_bid_values;
std::vector<size_t> best_item_indices;
std::vector<Real> bid_values;
// common bid value for diag-diag
Real diag_to_diag_value { 0.0 };
// analogous to second best item value; denoted by w in Bertsekas's paper on auction for transportation problem
Real almost_best_value { 0.0 };
// how many points to get from unassigned diagonal chunk
int num_from_unassigned_diag { 0 };
};
template <class Real_ = double, class PointContainer_ = std::vector<DiagramPoint<Real_>>>
struct AuctionOracleKDTreeSingleDiag : AuctionOracleBase<Real_, PointContainer_> {
using PointContainer = PointContainer_;
using Real = Real_;
using DnnPoint = dnn::Point<2, Real>;
using DnnTraits = dnn::PointTraits<DnnPoint>;
using IdxValPairR = typename ws::IdxValPair<Real>;
using ItemSliceR = typename ws::ItemSlice<Real>;
using LossesHeapR = typename ws::LossesHeap<Real>;
using LossesHeapIterR = typename ws::LossesHeap<Real>::IterTypeR;
using DiagramPointR = typename ws::DiagramPoint<Real>;
using DiagonalBidR = typename ws::DiagonalBid<Real>;
AuctionOracleKDTreeSingleDiag(const PointContainer& bidders,
const PointContainer& items,
const AuctionParams<Real>& params);
~AuctionOracleKDTreeSingleDiag();
// data members
// temporarily make everything public
Real max_val_;
size_t num_diag_items_;
size_t num_normal_items_;
size_t num_diag_bidders_;
size_t num_normal_bidders_;
dnn::KDTree<DnnTraits>* kdtree_;
std::vector<DnnPoint> dnn_points_;
std::vector<DnnPoint*> dnn_point_handles_;
std::vector<size_t> kdtree__items_;
// this heap is used by off-diagonal bidders to get the cheapest diagonal
// item; index in the IdxVal is a valid item index in the vector of items
// items in diag_assigned_to_diag_slice_ and in diag_unassigned_slice_
// are not stored in this heap
LossesHeapR diag_items_heap_;
// vector of iterators; if item_idx is in diag_assigned_to_diag_slice_ or
// in diag_unassigned_slice_, then diag_items_heap__iters_[item_idx] ==
// diag_items_heap_.end()
std::vector<LossesHeapIterR> diag_items_heap__iters_;
// this heap is used by _the_ diagonal bidder to get the cheapest items
// * value in IdxValPair is price + persistence (i.e., price for
// diagonal items)
// * index in IdxValPair is a valid item index in the vector of items
// items in diag_assigned_to_diag_slice_ and in diag_unassigned_slice_
// are not stored in this heap
LossesHeapR all_items_heap_;
std::vector<LossesHeapIterR> all_items_heap__iters_;
std::unordered_set<size_t> diag_assigned_to_diag_slice_;
std::unordered_set<size_t> diag_unassigned_slice_;
std::unordered_set<size_t> normal_items_assigned_to_diag_;
Real diag_to_diag_price_;
Real diag_unassigned_price_;
// methods
Real get_price(const size_t item_idx) const override;
void set_price(const size_t item_idx,
const Real new_price,
const bool item_is_diagonal,
const bool bidder_is_diagonal,
const OwnerType old_owner_type);
IdxValPair<Real> get_optimal_bid(const IdxType bidder_idx);
DiagonalBidR get_optimal_bids_for_diagonal(int unassigned_mass);
void process_unassigned_diagonal(const int unassigned_mass,
int& accumulated_mass,
bool& saw_diagonal_slice,
int& num_classes,
Real& w,
DiagonalBidR& result,
bool& found_w);
void adjust_prices();
void flush_assignment();
void sanity_check();
bool is_item_diagonal(const size_t item_idx) const;
bool is_item_normal(const size_t item_idx) const { return not is_item_diagonal(item_idx); }
};
} // ws
} // hera
#include "auction_oracle_kdtree_single_diag.hpp"
#endif
|
