Keywords

1 Introduction

An auction involves an auctioneer wishing to maximize his/her selling revenue and a set of bidders wishing to minimize their cost according to their valuations of the items that they want to acquire. Examples of the most widely known auctions are the English auction, the Holland’s auction, the Sealed envelope auction, and the Vickrey auction [12]. These auctions typically handle one item per sell.

Combinatorial auctions are multi-item auctions, which allow bids on combinations of items [5, 11]. In a combinatorial auction, we are given a set of items exposed to buyers. Buyers offers different bids, each bid being defined by a subset of items with a price (bidder’s valuation). Two bids are conflicting if they share at least one item. The Winners Determination Problem (WDP) is to determine a conflict-free allocation of items to bidders (the auctioneer can keep some of the items) that maximizes the auctioneer’s revenue defined as the sum of the valuations of the winning bids [14]. The WDP is known to be a NP-hard problem with a number of practical applications like e-commerce, games theory and resources allocation in multi-agents systems [11, 21].

Formally, given a set of items \(M = \{1,2, ...,m\}\) and a set of \(n\) bids \(N = \{1,2,...n\}\). Each bid \(j\) is a tuple \({<}S_{j}, P_{j}{>}\) where \(S_{j}\) is a subset of items covered by bid \(j\), and \(P_{j}\), the price of bid \(j\). Let \(B\) be a \(m \times n\) binary matrix such that \(B_{ij}=1\) if object \(i \in S_{j}\), \(B_{ij}=0\) otherwise. Furthermore, define a decision variable \(x_{j}\) for each bid \(j\) such that \(x_{j}=1\) if bid \(j\) is a winning bid, 0 otherwise. Then, the WDP can be stated as the following binary integer optimization problem.

$$\begin{aligned} Maximize \ f(x) = \sum _{j\in N}P_{j} x_{j} \end{aligned}$$
(1)

subject to

$$\begin{aligned} \sum _{j\in N}B_{ij} x_{j}\le 1,i\in M \end{aligned}$$
(2)

The objective function (1) allows to maximize auctioneer’s gain calculated by the sum of prices of the winning bids while the constraints expressed by formula (2) ensure that an item appears at most in one winning bid.

The computational challenge of the WDP and its practical applications have motivated a number of solution approaches including exact methods [18] and metaheuristic methods. Representative examples of exact methods include: Branch-on-Items (BoI), Branch-on-Bids (BoB) [19], Combinatorial Auctions BoB (CABoB) [20], Combinatorial Auction Structural Search (CASS) [6] and Combinatorial Auctions Multi-unit Search (CAMUS) [15]. A dynamic programming approach is introduced in [17] while a linear programming method is investigated in [16]. An algorithm based on integer programming is shown in [1], a constraint programming approach is used to solve a particular combinatorial Vickrey auction [9]. On the other hand, several stochastic methods were proposed for the WDP. They include a local search method named Casanova [10], a hybrid algorithm combining simulated annealing with Branch-and-Bound (SAGII) [8], and more recently a tabu search method [3] and a memetic algorithm [4].

The rest of the paper is organized as follows. Section 2 describes the proposed algorithm which is based on two complementary neighborhoods and a recombination operator. Experimental results are reported in Sect. 3 and compared with five representative algorithms for the WDP. Finally, Sect. 4 concludes the paper.

2 Recombination-Based Tabu Search for the WDP

TSX_WDP uses two complimentary move operators to explore effectively the search space and a recombination operator as an additional means to escape deep local optima. In this section, we presents in detail these key components.

2.1 The Solution Representation

A candidate solution is represented by an allocation \(A\) (a dynamic vector). Each element of this allocation \(A\) receives the winning bid. Each bid is an object composed of the list of items and the associated prices.

2.2 The Evaluation Function

The objective function defined in Eq. (1) is used to measure the quality of a candidate solution. So if an allocation \(A\) contains \(k\) bids {\(B_1,B_2,...,B_k\)}, (\(B_i={<}S_{i}, P_{i}{>}, 1 \le i \le k, k \le n\)), its quality is just equal to \(f(A)=\sum _{i=1}^k P_{i}\), i.e., the sum of the valuations of the winning bids. Given two candidate solutions, the one with a higher objective value is considered to be better. This relation is used to compare neighboring solutions which are developed below.

2.3 The Basic Move Operators and the Neighborhoods

Our TSX_WDP algorithm explores the search space by using two complementary neighborhood relations which are defined by an intensification move operator and a perturbation move operator.

Intensification Move. The intensification move operator chooses bids among candidate bids to be inserted in the current allocation A. During one iteration of the algorithm, several bids can be selected if they improve the current allocation. To create a neighboring allocation, the following steps are followed:

  • The initial candidate bids are sorted according to their utility prices;

  • For each candidate bid \(B_{x}\), a binary gain function is used to verify if the bid can increase the revenue of the current allocation when the bid is inserted;

  • Let \(Q\) be the set of winning bids that are in conflict with the current candidate bid \(B_{x}\), Let \(f(Q)\) be the revenue of the set of winning bids \(Q\), and \(f(B_{x})\) the price of the candidate bid \(B_{x}\). The gain function returns true if \(f(Q)<f(B_{x})\) and returns false otherwise;

  • Based on the function \(f\), a candidate bid \(B_{x}\) can be added to the current allocation only if its price \(f(B_{x})\) is higher than the revenue of other winning bids which are conflicting with \(B_{x}\) in the current allocation (i.e., the gain function is true);

  • The gain of \(B_{x}\), when it is selected to be added in the current allocation, is calculated by: \(Gain(B_{x})=f(A)-f(Q)+f(B_{x})\);

  • When a bid \(B_{x}\) is inserted in the current allocation A, the bids of \(Q\) which are conflicting with \(B_{x}\) are removed from \(A\);

  • The steps mentioned previously are iterated until all the initial candidate bids are visited and possibly added in the current allocation \(A\).

Perturbation Move. The perturbation move operator chooses randomly one candidate bid from the available ones. This move is activated only if no bid among the candidate bids can improve the current solution. In fact, the application of the intensification move can make the search to be trapped into local optima during the search process, when no more bid can be found that improves the revenue of the current allocation. Notice that this move operator can decrease temporarily the revenue of the solution, but hopefully, it helps the search to escape local optima by displacing the search to new zones of the search space. This move operator plays thus a diversification role.

2.4 Tabu List and Tabu Tenure Management

Tabu search uses a tabu list to forbid recently visited solutions from being revisited. The TSX_WDP algorithm considers the following general prohibition rule: a bid that is chosen to be inserted in the current allocation \(A\) (by an intensification move or a perturbation move) is forbidden to be removed for the next \(tt\) iterations (called tabu tenure). \(tt\) is calculated dynamically by the function proposed in [7]: \(tt=L+\leftthreetimes +f(A)\) where \(L\) is randomly chosen from the interval [0, 9] and \(\leftthreetimes \) is empirically fixed to 0.6. Experimentations show this dynamic tabu tenure is robust and allows TSX_WDP to reach high quality solutions. Notice that we permit a move to be accepted in spite of being tabu if the move leads to a solution better than any found so far. This is called the aspiration criterion.

2.5 Elite Solution Archive

The proposed algorithm also relies on a solution recombination operator (see next section) which aims to blend elite solutions (high-quality local optima). This technique is based on an archive \(P\) which is built as follows. During the search, if the current best solution \(A^*\) is not improved within a fixed number \(p\) of consecutive iterations, \(A^*\) is considered as a good local optimum and is added into the archive \(P\). At the same time, this allocation corresponds to a deep local optimum which is difficult to escape. For this purpose, we trigger a recombination operation to create a new starting point for the tabu search procedure, which is explained in the next selection.

2.6 Recombination Operator

The recombination operator aims to transfer good properties of parents to their descendants. The recombination pseudo-code is given in Algorithm 1.

figure a

Given two parent allocations \(I_{1}\) and \(I_{2}\) from the elite solution archive which share the highest number of bids, the recombination operator constructs the offspring \(I_{0}\) in k steps until all the bids of the two parents are visited. Our recombination operator is inspired by the idea of backbone used in [2, 22]. In the first step, the set of bids shared by the parents are identified and directly transferred to \(I_{0}\). Then the following steps are performed:

  • Choose the bid with the lowest price from each parent (lines 4 and 5, Algorithm 1).

  • The two selected bids are candidate bids that can be inserted in the offspring, if they are not conflicting bids. This is done by conserving the best bids with the highest revenue (lines 6 and 7, Algorithm 1).

  • Remove the selected bids from their parents, even if they are not inserted in the offspring (lines 9 and 10, Algorithm 1).

  • Repeat the previous steps until all the bids of the parents are examined and removed.

An example of this recombination operation is provided in Fig. 1.

Fig. 1.
figure 1

An example of the recombination operator

Full size image

2.7 The TSX_WDP Algorithm

The general TSX_WDP algorithm is formalized in Algorithm 2. The algorithm starts with an empty allocation in which no bid is chosen and tries to improve it by looking for a better solution in the current neighborhood. In each iteration, the best authorized bids are selected among the candidate bids to be included in the current allocation. This is achieved with the intensification move (lines 7–9 of Algorithm 2). When no bid can be found to increase the revenue with the intensification move, TSX_WDP switches to the perturbation move by choosing a random bid from the candidate bids (line 11 of Algorithm 2). In both cases, the choice of the bids depends on the status of the tabu list which is updated after each move. Any conflicting bids in the current allocation, when new bids are considered, are removed (lines 13 and 14 of Algorithm 2). The search process is repeated for a fixed number Itermax of iterations. During these Itermax iterations, if the current best solution cannot be updated for consecutive \(p\) (fixed experimentally) moves, the best local optimum found so far is inserted into the archive \(P\) and the recombination operator is activated to generate a new starting point for a new round of the tabu search procedure (lines 20–25 of Algorithm 2).

2.8 Discussion

The proposed TSX_WDP algorithm distinguishes itself from the existing heuristic approaches by several features. First, its tabu search procedure is based on two complementary move operators to generate neighboring solutions. In particular, the intensification move can add several bids (instead of a single bid like in most local search based heuristics). The tabu search procedure adopts a dynamic tabu tenure which is missing in the existing methods. Second, the recombination operator is based on the idea of backbone which proves to be quite useful for the WDP.

3 Experimentation

This section presents experimental results of the proposed algorithm which is implemented in Java. The program is run on a computer with a processor of 2.5 GHz and 8 GB of RAM. To assess our TSX_WDP algorithm, we run TSX_WDP on various benchmarks of diverse sizes defined in [13] and used in several studies like [3, 4, 8]. Theses benchmarks take into account several factors like the prices, bidders preferences and object distribution on bids. They can be divided into five groups where each group contains 100 instances.

-REL 500-1000: From in101 to in200: m = 500, n = 1000

-REL 1000-1000: From in201 to in300: m = 1000, n = 1000

-REL 1000-500: From in401 to in500: m = 1000, n = 500

-REL 1000-1500: From in501 to in600: m = 1000, n = 1500

-REL 1500-1500: From in601 to in700: m = 1500, n = 1500

We calibrated the parameters of the proposed algorithms by an experimental study: The maximum number of iterations (\(itermax\)) is fixed to 200 and the parameter responsible for the tabu tenure \(\leftthreetimes \) is fixed to 0.00006. Each of the 500 instance is solved 40 times independently by the TSX_WDP algorithm with different random seeds.

figure b
Table 1. Results obtained by TSX_WDP for WDP benchmarks
Full size table
Table 2. Comparative results of TSX_WDP with Casanova, MA, SLS, TS, SAGII on the WDP benchmarks: \(\mu \) is the average of the best objective value of the 100 instances in each group. \(time\) is the average time to reach the best solution.
Full size table

3.1 Experimental Results

In Table 1, we present the computational results of the TSX_WDP algorithm on the five groups of benchmarks. Given that there are 500 instances, we show only some results of each group, like in some recent papers [4]. For each presented instance, the following computational statistics are indicated: the maximum revenue obtained by the TSX_WDP algorithm over the 40 independent trials (Rbest), the average revenue over the 40 trials (Ravg), the worst revenue over the 40 trials (Rworst) and the average CPU time in seconds (AvgTime). As one can observe, the values of Ravg are very close to the values of Rbest in most of cases and these two values are even equal for certain instances (for example for in101, in102, in205 etc.). This table shows the proposed algorithm can consistently reach high quality solutions for the tested problems.

3.2 Comparative Results for the WDP

In order to further show the effectiveness of the TSX_WDP algorithm, we present a comparative study with five state of the art algorithms from the literature: Casanova [10], SAGII [8], SLS [3], TS [3], MA [4].

In Table 2, we show the general comparative results for each group. In this table, rows \(\mu \) correspond to the average of best objective value of the 100 instances in each group. Rows \(time\) represent the average time to reach the best solution. \(\delta (\%)\) is the deviation of the TSX_WDP algorithm with respect to each reference algorithm. The deviations are calculated respectively as follows: \(\mu _{TSX\_WDP}-\mu {}_{algo\_X})/\mu {}_{TSX\_WDP}\) where algo_X is one of the five reference algorithms. Since the compared algorithms are implemented in different languages and run on different platforms, the comparison is focused on solution quality that can be reached by each algorithm. The computing time is provided only for indicative purposes. The results of the reference algorithms are extracted from the corresponding papers except the results of Casanova which are from [8].

Fig. 2.
figure 2

A comparison of the solution quality between TSX_WDP, Casanova, TS, SLS, MA and SAGII

Full size image

Table 2 discloses that TSX_WDP gives an improvement between 31 % and 47 % in solution quality compared to Casanova. TSX_WDP finds better solutions with shorter times than Casanova. TSX_WDP shows good performances compared to SLS. The improvement is between 4 % and 8 %. The results of TSX_WDP are better than TS in quality and in time (with an improvement rate between 4 % and 9 %). TSX_WDP outperforms MA. The deviation is between 2 % and 7 %. Finally, TSX_WDP produces better results than SAGII which is currently the most successful algorithm for the WDP and is based on sophisticated Branch-and-Bound and preprocessing tools (The deviation is between 1 % and 7 %). Thus, we can conclude that TSX_WDP discovers new best results for the five groups of benchmarks.

To further illustrate the results of Table 2, we consider the comparative curves of Fig. 2. The X-axis of the curves represent the 5 groups of the WDP benchmarks and their Y-axis are the gain of each group (\(\mu \)). These curves confirm that TSX_WDP competes favorably with each of the reference algorithms for each group of instances.

4 Conclusion

In this work, we have presented a tabu search algorithm for the winner determination problem based on a two different neighborhood structures and a recombination operator. The algorithm uses the intensification move to improve progressively the quality of the current solution. When the solution cannot be further improved, the TSX_WDP algorithm switches to a perturbation move by choosing a random bid. In both cases, a tabu list is used to prevent the search from revisiting the previous examined solutions. To escape deep local optima, the proposed algorithm employs a backbone-based recombination operator which relies on an elite solution archive which is built and updated during the search. This recombination operator generates new starting points for tabu search with the aim of leading the algorithm into new promising search areas. The proposed TSX_WDP algorithm is evaluated on a set of 500 benchmark instances. The comparative study with five reference algorithms shows the proposed algorithm is able to reach solution of very high quality.