1 /*
2 Copyright 2015 Skytechnology sp. z o.o.
3
4 This file is part of LizardFS.
5
6 LizardFS is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, version 3.
9
10 LizardFS is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with LizardFS. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #pragma once
20
21 #include "common/platform.h"
22
23 #include <algorithm>
24 #include <array>
25 #include <cassert>
26 #include <limits>
27
28 namespace linear_assignment {
29
30 namespace detail {
31
32 template <typename M, typename A, typename P, typename V>
auctionStep(M & value_matrix,A & assignment,A & object_assignment,P & prices,const V & eps,int size)33 void auctionStep(M &value_matrix, A &assignment, A &object_assignment, P &prices, const V &eps,
34 int size) {
35 std::fill(assignment.begin(), assignment.begin() + size, -1);
36 std::fill(object_assignment.begin(), object_assignment.begin() + size, -1);
37
38 assert(size > 1);
39
40 int unassigned_idx = 0;
41 int assigned_count = 0;
42 while (assigned_count < size) {
43 while (assignment[unassigned_idx] >= 0) {
44 ++unassigned_idx;
45 if (unassigned_idx >= size) {
46 unassigned_idx = 0;
47 }
48 }
49
50 V w = std::numeric_limits<V>::lowest(); // second highest (or highest if there is
51 // more than one element with highest
52 // value)
53 V v = std::numeric_limits<V>::lowest(); // highest value
54 int v_idx = -1;
55 for (int i = 0; i < size; ++i) {
56 V c = value_matrix[unassigned_idx][i] - prices[i];
57 assert(c > std::numeric_limits<V>::lowest());
58 if (c > v) {
59 w = v;
60 v = c;
61 v_idx = i;
62 } else {
63 w = std::max(c, w);
64 }
65 }
66
67 assert((v - w + eps) > V());
68
69 prices[v_idx] += v - w + eps;
70
71 int idx = object_assignment[v_idx];
72 if (idx >= 0) {
73 assignment[idx] = -1;
74 assigned_count--;
75 }
76
77 object_assignment[v_idx] = unassigned_idx;
78 assignment[unassigned_idx] = v_idx;
79 assigned_count++;
80 }
81 }
82
83 } // detail
84
85 /*! \brief Implementation of Bertsekas auction algorithm.
86 *
87 * The function implements Bertsekas [1] auction algorithm for integer value/benefit matrix
88 * with epsilon scaling.
89 *
90 * [1] Bertsekas, D.P. 1998. Network Optimization Continuous and Discrete Models.
91 *
92 * \param cost value matrix with integer values - matrix dimension should be (size,size).
93 * Values in matrix should be considerably lower than MAX_INT.
94 * \param assignment return vector with optimal assignment (maximizing value).
95 * Each value in vector represent index of object that is assigned to that
96 * person.
97 * \param object_assignment return vector with optimal assignment of object-person pairs.
98 * Value at index i represents index of person to which this object is
99 * assigned.
100 * \param size problem size (number of person-object pairs to match).
101 */
102 template <typename M, std::size_t N>
auctionOptimization(M & value_matrix,std::array<int,N> & assignment,std::array<int,N> & object_assignment,int size)103 void auctionOptimization(M &value_matrix, std::array<int, N> &assignment,
104 std::array<int, N> &object_assignment, int size) {
105 std::array<int, N> prices;
106
107 assert(size <= (int)N);
108
109 if (size <= 0) {
110 return;
111 }
112 if (size == 1) {
113 assignment[0] = 0;
114 object_assignment[0] = 0;
115 return;
116 }
117
118 std::fill(prices.begin(), prices.begin() + size, 0);
119
120 // heuristic for setting epsilon
121 int max_a = std::numeric_limits<int>::lowest();
122 for (int i = 0; i < size; ++i) {
123 for (int j = 0; j < size; ++j) {
124 value_matrix[i][j] *= (size + 1); // we scale by (size + 1) so that epsilon=1
125 // guarantees optimal solution
126 max_a = std::max(value_matrix[i][j], max_a);
127 }
128 }
129 int eps = (max_a + 12) / 25;
130
131 while (eps > 1) {
132 detail::auctionStep(value_matrix, assignment, object_assignment, prices, eps, size);
133 eps = (eps + 2) / 5;
134 }
135
136 eps = 1;
137 detail::auctionStep(value_matrix, assignment, object_assignment, prices, eps, size);
138 }
139
140 /*! \brief Implementation of Bertsekas auction algorithm.
141 *
142 * \param cost value matrix with integer values - matrix dimension should be (size,size).
143 * Values in matrix should be considerably lower than MAX_INT.
144 * \param assignment return vector with optimal assignment (maximizing value).
145 * Each value in vector represent index of object that is assigned to that
146 * person.
147 * \param size problem size (number of person-object pairs to match).
148 */
149 template <typename M, std::size_t N>
auctionOptimization(M & value_matrix,std::array<int,N> & assignment,int size)150 void auctionOptimization(M &value_matrix, std::array<int, N> &assignment, int size) {
151 std::array<int, N> object_assignment;
152 auctionOptimization(value_matrix, assignment, object_assignment, size);
153 }
154
155 } // linear_assignment
156