Thème Num

Kameshwaran Sampath

Lyès Benyoucef

Xiaolan Xie

apport de recherche

Keywords: e-procurement, auctions, integer programming, transportation problem, branch-and-bound, linear programming relaxation, duality, valid inequalities

Advent of business over Internet have given rise to a number of innovative trading mechanisms. In this work we propose a new auction mechanism, called as discount auctions, for procuring heterogeneous items. The buyer, who is the auctioneer, has an unit demand for M distinct items. The suppliers, who are the bidders, specify individual costs for each of the items. In addition, a supplier also specifies a discount function: a non-decreasing function over the number of items. This discount bid, in essence, conveys the individual costs for each of the items and the discount that can be availed based on the number of items bought. The winner determination problem faced by the buyer is to choose the optimal set of winning suppliers and their respective winning items such that the total cost of procurement is minimized. First we show that this problem is N P-hard upon reduction from the set covering problem. Next we propose two exact algorithms to solve the problem to optimality. The first one is a branch-and-bound algorithm, called as branch-on-supply (BoS), which does not use mathematical programming formulation but rather exploits the embedded network structure. The second is a suite of branch-and-cut algorithms. We derive valid inequalities to the integer programming formulation, which serve as cuts for the LP relaxation. A heuristic branching technique, called as branch-on-price (BoP), is proposed that branches on the current price of an item, which is partially supplied by more than one supplier. The design philosophies of the above are different in the sense that BoS searches for the optimal number of items from the suppliers, whereas BoP searches for the optimal price of the items. We compare the performance of these algorithms with extensive computational experiments.

Enchère de type pondéré pour l'acquisition d'articles multiples

Résumé : L'arrivée de l'Internet dans le monde des affaires a provoqué la naissance d'un certain nombre de mécanismes de ventes (relations client-fournisseur) innovants. Dans cette étude, nous proposons un nouveau mécanisme d'enchère appelé discount auctions pour l'acquisition d'articles multiples (de types et de tailles différents). Un acheteur (client dans notre cas) exprime une demande unitaire pour M différents articles. Un ensemble de vendeurs (fournisseurs dans notre cas) vont cherché à répondre à ces demandes. L'offre d'un vendeur est composée du prix de chacun des articles séparément et d'une fonction de pondération qui indique la remise offerte sur la base du nombre d'articles achetés (plus d'articles achetés et plus la remise sur le prix de vente est importante). Le problème rencontré par l'acheteur est d'identifier, parmi l'ensemble des tous les vendeurs, les vendeurs dits vainqueurs ainsi que les articles achetés chez chacun d'eux en minimisant le coût d'achat total. Dans un premier temps, nous avons prouvé que ce problème d'optimisation est N P-difficile en utilisant une réduction du problème dit de recouvrement. Nous avons développé deux algorithmes exacts de types banch-and-bound. Le premier, appelé branch-on-supply (BoS), n'utilise pas la formulation mathématique du problème mais exploite sa structure de type réseau. Le second est un ensemble d'algorithmes de types branch-and-cut. En effet, nous avons introduit des inégalités dites valides dans le programme linéaire en nombres entiers modélisant le problème pour servir comme des coupes pour la relaxation de type LP. Une heuristique de branchement, appelée branch-on-price (BoP), est proposée. Les philosophies de conception des deux algorithmes sont différentes. BoS cherche à déterminer le nombre optimal d'articles à acheter de chaque fournisseur. A l'inverse, BoP cherche à déterminer le prix optimal de chaque article. Pour comparer les performances de deux algorithmes, des expériences numériques ont été réalisées et analysées.

Mots-clés : e-procurement, enchères, programmation en nombres entiers, problème de transport, méthode de séparation et évaluation, relaxation, dualité, inégalités valides

Introduction

Procurement is the process by which a company obtains materials and services necessary for its manufacturing and/or operations. Traditionally, the procurement process begins with the buyer sending a request for quotation (RFQ) to the potential suppliers. The RFQ contains details about the demands of the buyer and the suppliers respond with bids. The buyer evaluates the bids and chooses the suppliers, based on the purchasing policies. The dynamics of procurement process, involving suppliers responding with bids and the buyer evaluating the bids, borders on the auction mechanism. Auction is a market mechanism with well-defined set of rules for determining the terms of an exchange of something for money [START_REF] Mcafee | Auctions and bidding[END_REF]. In auction parlance, buyer is the auctioneer and the suppliers are bidders in procurement. The auction mechanism is more structured than the procurement process. However, it forms the core of the many procurement scenarios. For example, consider a government tender for procuring a service like construction of a bridge. The constructors are the suppliers and they respond with sealed bids, quoting the cost of construction, among the other required things. Assuming that the cost is the only negotiable criterion, the constructor with the least quoted cost is chosen as the winner and he is supposed to provide the service at the quoted cost. This is the well known first price sealed bid auction, where the lowest bidder is awarded the contract for the quoted price.

The advent of Internet and Internet-based technologies have led to new and innovative auction mechanisms for procurement. Initially, in the past few years, naive use of Internet and information technologies saw complex back-end applications supporting supply chains of large companies, with simple front-end e-catalog systems supporting procurement. Recent trends are focusing on user friendly Business-to-Business e-procurement applications that embed sophisticated business logic and algorithms. With the Internet technologies enabling an interactive front end for human interaction and back end computers that can support complex computations, the research in e-procurement is focused on auction mechanisms, bidding languages, and bid evaluation techniques to make the process computationally and economically efficient. This has led to new generation of procurement techniques: volumediscount [START_REF] Davenport | Price negotiations for procurement of direct inputs[END_REF][START_REF] Eso | Bid evaluation in procurement auctions with piece-wise linear supply curves[END_REF], combinatorial [START_REF] Elmaghraby | Technology for transportation bidding at the home depot[END_REF][START_REF] Hohner | Combinatorial and quantity discount procurement auctions provide benefits to mars, incorporated and to its suppliers[END_REF], and multi-attribute [START_REF] Bichler | Multi-attribute auctions for electronic procurement[END_REF][START_REF] Beil | An inverse-optimization-based auction mechanism to support a multiattribute RFQ process[END_REF][START_REF] Kameshwaran | e-Procurement using goal programming[END_REF]. For a more general review of auction techniques in e-commerce and e-procurement, see [START_REF] Elmaghraby | Auctions and pricing in e-marketplaces[END_REF][START_REF] Chandrashekar | Auction based mechanisms for electronic procurement[END_REF].

The auction mechanism used for e-procurement primarily depends on the type and number of items procured. In the above tender example, the demand was for a single indivisible item and the first price sealed bid auction was used. For an industrial procurement of large quantity of a single good (like raw material), volume discount auctions [START_REF] Eso | Bid evaluation in procurement auctions with piece-wise linear supply curves[END_REF][START_REF] Kothari | Approximately strategy proof and tractable multi-unit auctions[END_REF][START_REF] Kameshwaran | A Lagrangian heuristic for bid evaluation in e-Procurement auctions[END_REF] are appropriate candidates. The bid submitted by a supplier is a cost function defined over the quantity. The function, in essence, can capture the discount offered by the supplier based on the quantity procured. Combinatorial auctions (CA) [START_REF] Peter Cramton | Combinatorial Auctions[END_REF], are useful for procuring a set of heterogeneous, but related items. CA allows package bidding, that is, quoting a single cost for a bundle (subset) of items. In this way, the bidders can capture the complementarity or substitutability existing among the items in a bundle. For M items, a bidder could thus possibly submit 2 M -1 combinatorial bids, one for each of the possible bundles. The volume discount and combinatorial auctions have led to several profitable industrial procurements INRIA [START_REF] Hohner | Combinatorial and quantity discount procurement auctions provide benefits to mars, incorporated and to its suppliers[END_REF][START_REF] Elmaghraby | Technology for transportation bidding at the home depot[END_REF][START_REF] Bichler | Industrial procurement auctions[END_REF]. In this work, we propose a new auction mechanism called as discount auctions for procuring heterogeneous items.

The proposed discount auctions (DA) is applicable in scenarios where the items do not exhibit complementarity or substitutability. Consider the procurement of office supplies: stationary, computers, and furniture. A supplier has positive cost for each of the items and his profits may not change substantially by selling them separately or together. If he cannot sell the furniture in this auction, he can sell it elsewhere. This is not the case with items that exhibit complementarity. Bundles of items that cannot be split and items that cannot be bundled together are not uncommon in scenarios with complementarity and substitutability, respectively. Given that such conditions do not exist, the supplier is not concerned about which bundle of items, but rather about how much worth of items he can sell. The proposed DA is useful for such scenarios. The supplier has positive cost for each of the items, and in order to promote sales he gives incentive to the buyer by providing discounts on the number of items procured. The discount bid consists of two parts: (1) individual cost for each of the items and (2) discounts for different number of items (for example, if three items are bought then the discount is 5%, for four items 6%, etc.). The difference between DA and CA is obvious: the costs in the CA are defined over the subsets of the items whereas the discounts in the DA are defined over the cardinality of the subsets of the items.

In this work, we focus on the winner determination or bid evaluation problem of DA. The winner determination problem faced by the buyer is to choose a set of winning bids and a set of winning items for each of the winning bids, such that all demanded items are procured at minimal (total) cost. We show that this problem is N P-hard and propose two branch and bound algorithms to solve the problem to optimality. The preliminary versions of this work have been presented in [START_REF] Kameshwaran | Discount auctions for procuring heterogeneous items[END_REF][START_REF] Kameshwaran | Winner determination in discount auctions[END_REF][START_REF] Kameshwaran | Branch on price: A fast winner determination algorithm for discount auctions[END_REF].

The rest of the report is organized as follows. In Section 2, we formally introduce the DA and the winner determination problem is modeled as an integer program. The problem is shown to be N P-hard, upon reduction from the set covering problem, in Section 3. The exploitable combinatorial and network structures of the problem are studied in Section 4. The linear programming relaxation of the problem and its relation to a network structure are discussed in Section 5. This network structure, in particular, the transportation structure is exploited in Section 6.1, to develop the branch-and-bound algorithm, called as branch-onsupply. A tight LP relaxation with valid inequalities is developed in Section 7. A suite of branch-and-cut algorithms are developed in Section 8, which uses the tight LP relaxation as the lower bounding technique. Computational experiments are presented in Section 9. Conclusions and future work are discussed in Section 10.

Discount Auctions

Problem Definition

The buyer is interested in procuring M different items. Each of the item is indivisible, i.e. it can be supplied by only one supplier. An item need not refer to a single unit. It can be a computer or a computer and printer or hundred computers, but it cannot be split and supplied by multiple suppliers. Let there be N suppliers. An item is denoted by index m and a supplier by index j. Each supplier can submit only one discount bid and hence the index j is used to denote both the supplier and his bid. The discount bid j (i.e. from supplier j) consists of two parts: (1) cost Q m j for each item m and (2) non-decreasing discount θ i j for i (= 1, . . . , M ) number of items. The bid can be compactly expressed as an ordered pair of M -tuples:

((Q 1 j , . . . , Q m j , . . . , Q M j ), (θ 1 j , . . . , θ i j , . . . , θ M j )).
Note that m denotes a particular item and i denotes number of items. If the buyer procures items 2, 4, and 7 from bid j, then the cost of procurement is (1

-θ 3 j )(Q 2 j + Q 4 j + Q 7 j
). The i = 3 in θ 3 j , as three items 2, 4, and 7 were procured. Note that this is different from the volume discounts, which are used in procuring multiple units of the same item. All the Q m j are positive (possibly infinite for an unavailable item) and the θ i j are non decreasing over i (the discount cannot decrease with the number of items bought). One of the main issues in auction design is bid preparation and communication. In CAs, the number of possible combinatorial bids from a supplier is 2 M-1 (one bid for each subset). Thus both the bid preparation and communication (to the buyer) is costly. In DAs, only one discount bid is submitted from a supplier and its length is linear (2M ) in the number of items.

Winner Determination Problem

The winner determination problem (WDP) faced by the buyer is to choose a set of winning bids and a set of winning items for each of the winning bids, such that all demanded items are procured at total minimal cost. Without the discount function, the problem can be solved in O(N M ) time (choose the minimum bidder for each of the items). Due to the discount function, the cost of an item bought from a bid depends on the total number of items bought from that bid. Hence, the formulation should also take into account the total number of items bought from a bid. If i items are bought from a bid j, then the cost of an item m is (1θ i j )Q m j . With two different decision variables to choose an item m and the number of items i from bid j, the cost of an item would be a nonlinear function. To linearize the objective function, we define the effective cost of an item m if i items are bought from bid j as

p im j = (1 -θ i j )Q m j (1)
The WDP can be restated as choosing the items with minimal sum of effective costs subject to the demand and discount constraints. Following is an integer programming (IP) formulation for the bid evaluation problem.

min j i m p im j w im j (2)
subject to

i v i j ≤ 1 ∀j (3)
m w im j = iv i j ∀i, j (4)
INRIA j i w im j = 1 ∀m (5)
w im j , v i j ∈ {0, 1} ∀j, i, m (6)
In the remainder of this report, the notation ∀j denotes j = 1, . . . , N . Similarly, ∀i and ∀m denote i = 1, . . . , M and m = 1, . . . , M , respectively. The binary decision variable w im j is to choose an item m from bid j with effective cost p im j and binary variable v i j is to choose i items from j. A constraints in (3) is a multiple choice constraint for variables v i j in i that determines the number of items i bought from j. If i v i j = 0, then no items are chosen from j and if v i j = 1, i items are bought from j. Constraints (4) ensure that the items chosen from j are consistent with their effective cost: if i items are chosen, then they have the cost with discount for i items. Constraints [START_REF] Chandru | Integer programming[END_REF] ensure that every item is procured from only one supplier. Thus the constraint sets (3) and ( 4) are for supply and constraint set ( 5) is for the demand.

Complexity of the Winner Determination Problem

Theorem 1 The WDP of the discount auctions is N P-hard.

Proof: We prove the hardness of the WDP by showing that the decision version of the WDP is N P-complete upon reduction from the minimum set cover.

Definition 1 ([DAuc]) INSTANCE:

Set of goods G = {1, . . . , M }, set of discount bids J = {1, . . . , N }, where a discount bid j ≡ ((Q 1 j , . . . , Q M j ), (θ 1 j , . . . , θ M j )) with Q m j ≥ 0 ∀m ∈ G and 0 ≤ θ i j ≤ θ i+1 j ≤ 1, 1 ≤ i < M , and a goal K ≥ 0. QUESTION: Does there exist a winning set J ′ ⊆ J, which defines a partition P = {B j :

B j ⊆ G, j ∈ J ′ } of G, such that the total cost of procurement j∈J ′ (1 -θ |Bj | j ) m∈Bj Q m j ≤ K? Definition 2 ([SCov]) INSTANCE:
Collection C of subsets of finite set F , positive weight w R ∀R ∈ C, and a goal H ≥ 0. QUESTION: Does there exist a cover C ′ ⊆ C for F such that R∈C ′ w R ≤ H?

The minimum set cover [SCov] is N P-complete [START_REF] Garey | Computers and Intractability[END_REF]. First we note that [DAuc] is in N P: given a winning set J ′ ⊆ J, one can verify whether it defines a partition and the procurement cost is less than K in polynomial time. Let an instance of [SCov] be given. We construct an instance of [DAuc] in the following way:

• G = F , |J| = |C|
• Create a bid j for each of the subset R ∈ C as follows:

Q m j = w R if m ∈ R ∞ otherwise , ∀m θ i j = i -1 i , 1 ≤ i ≤ M RR n°6084 • K = H
The above reduction can be clearly done in polynomial time. We now show that the reduction is valid by showing that an instance of [SCov] is an yes iff if its reduction [DAuc] is an yes instance.

(⇐) Let there exist an yes instance of [DAuc] with J ′ ⊆ J defining a partition of G with procurement cost ≤ K. A cover C ′ for [SCov] can be constructed as follows. For every

j ∈ J ′ , include the corresponding subset R in C ′ . Note that B j ⊆ R as m ∈ R implies Q m j = ∞.
The cost of procurement from winning bid j is given by

(1 -θ |Bj | j ) m∈Bj Q m j = 1 |B j | |B j |w R = w R
Thus the cost of procurement from each bid is equal to the weight of the corresponding subset in C ′ . Since the winning bids partition G, the collection C ′ covers F with cost ≤ K = H. (⇒) Let there exist an yes instance for [SCov] with cover C ′ . The solution to [DAuc] can be constructed as follows. For every subset R ∈ C ′ , include its corresponding bid j in J ′ . Since C ′ covers F , J ′ also covers G. If an item is supplied by more than one supplier then it can be removed from its respective suppliers except one. Note that removing an item from bid will not change the cost because of the assumed discount and cost structure. Hence, we have a partition of G that satisfies the goal.

Proposition 1 Following special cases are solvable in polynomial time:

1. Same Cost: Q m j = Q ≥ j 0, ∀j, m 2. Same Discount: θ i j = θ * j , ∀j, i 3. |M | ≤ 2
(1) This special case is a multi-unit auction of a single good. The requirement of the buyer is M units of a single good and the suppliers submit a bid with unit cost Q * j and a discount function. The WDP can be formulated as the following integer programming problem:

(P) : min j i (1 -θ i j )iQ * j v i j (7) subject to i v i j ≤ 1, ∀j (8)
INRIA j i iv i j = M (9) v i j ∈ {0, 1}, ∀j, i (10)
The above formulation is a multiple choice knapsack problem [START_REF] Pisinger | Knapsack problems[END_REF] with [START_REF] Peter Cramton | Combinatorial Auctions[END_REF] as the multiple choice constraints and (9) as the knapsack constraint. Though the generic multiple choice knapsack problem is N P-hard, the above problem is solvable in linear time due to its cost structure. We show this using the duality theory. Let β j be the dual variable for the multiple choice constraint for j in [START_REF] Peter Cramton | Combinatorial Auctions[END_REF] and π be the dual variable for the knapsack constraint [START_REF] Davenport | Price negotiations for procurement of direct inputs[END_REF]. The linear programming dual of the above problem is:

(D) : max πM + j β j (11)
subject to

iπ + β j ≤ (1 -θ i j )iQ * j , ∀j, i (12)
β j ≥ 0, ∀j (13)
Let

j ′ = arg min j {(1 -θ M j )M Q * j }. Assign β j ′ = (1 -θ M j ′ )M Q * j ′
and β j = 0, ∀j = j ′ and π = 0. This is a feasible dual solution with objective value β j ′ . A feasible solution to the primal problem can be constructed from this dual solution. Assign V M j ′ = 1, V i j ′ = 0, ∀i = M , and V i j = 0, ∀j = j ′ and ∀i. This is a feasible primal solution with the same objective value as of the dual and hence by duality theory it is an optimal solution to the linear relaxation. This optimal solution to the linear relaxation is integral and hence it is also optimal to the original integer programming problem. Thus the optimal solution to this WDP is min j (1θ M j )M Q * j , which can be solved in linear time.

(2) If the discounts are the same for each bidder, then it is equivalent to no discount, which can be solved in polynomial time (O(M N )) by choosing the bidder with minimum cost for each item.

(3) If M = 1, then WDP can be solved in linear time by choosing the bid with minimum cost. For M = 2, there are only two possibilities: buy at most one item from each buyer and buy both the items from a single buyer. The first problem is an assignment problem and the second is choosing the minimum cost for both items from N bidders. The optimal solution is the one with the minimum cost among the above two solutions.

Exploitable Structures

Knowledge of a structure in a problem can be exploited in designing the solution techniques and algorithms for solving the problem. The WDP is explored in this section for such structures in terms of both problem definition and formulation.

(Bids)

(Items)

1 m M 1 j N (1) (1) (1)

Combinatorial Structure

In CA, the bidder provides a single price for a subset of items, and he can submit different bids for different subsets. The bids submitted in DA can be easily converted into combinatorial bids. A combinatorial bid for bundle (subset) B from supplier j has a single price P (B, j). From a discount bid j, the cost of a combinatorial bid for each bundle B can be easily obtained as follows:

P (B, j) = (1 -θ |B| j ) m∈B Q m j (14)
Thus given the discount bids, one can construct combinatorial bids. The solution of the bid evaluation problem for the combinatorial bids is also the solution to that of the discount auction. The restriction of choosing at most one bundle from each supplier need not be imposed, as there will always exist an optimal solution with at most one bundle from a supplier due to the non-decreasing discount function. The winner determination algorithms for CAs are well studied [START_REF] Sandholm | Cabob: A fast optimal algorithm for winner determination in combinatorial auctions[END_REF][START_REF] Lehmann | The winner determination problem[END_REF] and hence one can use them for solving the discount auctions. However, the DA is only an instance of the CA, and hence it is possible to develop more efficient solution techniques by exploiting the other possible structures.

Network Structure

The WDP of DA can be considered as a transportation network with N supply nodes (bids) and M demand nodes (one for each item). Each supply node has a supply of M units and

INRIA

each demand node has a unit demand. The embedded transport structure is shown in Figure 1. A flow in the network connecting node j to node m indicate that bid j is supplying item m. Due to the unit demand at each demand node, the flow in any given arc will be at most one. The complicating feature of the model is the cost c(j, m) of the flow in the arc (j, m), which is the function of number of units supplied from node j. Note that this is different from the conventional nonlinear cost network models, where the cost will vary based on the flow through the arc, whereas in this case the cost varies on the total flow from the supply node. Let δ j be the total supply from node j in a solution. Then the cost of the flow in an arc (j, m) is given by c(j, m)

= (1 -θ sj j )Q m j .
The solution is feasible only if the total supply j δ j = M . It is worth noting that for a given feasible supply, determining the optimal flow is a transportation problem. Thus the problem can be solved without the integer restrictions on the flow. In terms of the IP formulation presented in Section 2, if the binary variable {v i j } are fixed in a feasible way, {w im j } can be easily obtained by solving a transportation problem. Once the {v i j } are fixed, the discounts are known and hence the problem is easy. The binary variables {w im j } can indeed be relaxed to take continuous values, as there will always exist an optimal solution with integer values.

Linear Programming Relaxation

In this section we study the linear programming (LP) relaxation of the IP formulation presented in Section 2. The LP relaxation provides the lower bound on optimal cost, which is useful in pruning the search space in branch-and-bound algorithms. Moreover, for this problem, the LP relaxation is equivalent to solving a transportation problem. We study the LP relaxation by investigating its dual.

Let {γ j }, {λ i j }, and {γ m } be the dual variables corresponding to the constraints (3), (4), and (5), respectively. The dual of the linear relaxation is given by:

max m γ m - j γ j (15)
subject to

γ m + λ i j ≤ p im j ∀j, i, m (16)
-γ j -iλ i j ≤ 0 ∀i, j (17)
γ j ≥ 0 ∀j (18)
A feasible solution to the above problem can be easily obtained. The nonnegative variables γ j have negative coefficients in the objective function and hence can be equated to zero. The variables λ i j are common to both the constraints and can be eliminated by equating to zero. Thus γ m = min j,i {p im j }. The θ i j are non-decreasing over i by assumption. Hence the p im j are non-increasing and therefore γ m = min j {p Mm j }. From this dual solution one can easily construct a feasible solution to the linear relaxation and these both are optimal solutions to their respective problems.

Proposition 2 {π j = 0, λ i j = 0, γ m = min j {p Mm j }} is the optimal dual solution and

v i j = 0 for i < M , v M j = m w M m j M
, where

w Mm j ′ = 1 if j ′ = arg min j {p Mm j } 0 otherwise (19)
is the optimal solution to the linear relaxation.

It can be easily seen that the solutions are feasible to their respective problems. Moreover, they both have the same objective value. Hence by strong duality theorem, they are optimal solutions. The LP relaxation considers only the maximum discounted cost (with discount for M items) and allocates the items based on this minimum cost. As a consequence, it violates the discount constraint by procuring less number of items from a supplier but with a maximum discount for M items. It is worth noting that only variables {v i j } take continuous values.

The linear relaxation problem can be solved in O(M N ) by taking the minimum of p Mm j over j, for each m. If the {v M j } are fractional, then it is not an optimal solution to the WDP. One can easily construct a feasible integer solution ({v m j }, {w im j }) to the WDP from the fractional ({v M j }, {w Mm j }).

1. δ j = m w Mm j , ∀j; v m j = v m j , ∀j, m; w im j = w im j , ∀j, i, m; 2. ∀j do: (a) if (v M j > 0) v sj j ← 1, v M j ← 0; (b) ∀m if (w Mm j = 1) w δj ,m j ← 1, w Mm j ← 0;
6 Branch-and-Bound Algorithm B&B is an exact intelligent enumerative technique that attempts to avoid enumerating a large portion of the feasible integer solutions [START_REF] Chandru | Integer programming[END_REF][START_REF] Murty | Linear and Combinatorial Programming[END_REF]. It is a widely used approach for solving discrete optimization, combinatorial optimization, and integer programming problems in general. The B&B approach first partitions the overall set of feasible solutions into two or more sets and as the algorithm proceeds the set is partitioned into many simpler and smaller sets, which are explored for the optimal solution. Each such set is represented by a candidate problem (CP). A typical iteration of B&B consists of:

• Selection/Removal of a CP from the list of CPs The algorithm first starts with a single CP in the list representing the entire feasible set of solutions. As the algorithm proceeds, numerous CPs are added to the list, each containing a set of feasible solutions. The CPs partition the search space and at every iteration, a prospective CP is chosen to search for the optimal solution. The CP though containing less number of solutions than the original problem, could still be hard to solve, and hence a easily solvable lower bounding technique is applied to obtain a good lower bound on the objective value. This lower bound is for the solutions in that particular CP. If a feasible solution had been obtained so far in the algorithm, it can be used to prune a CP with lower bound greater than the cost of the known solution. A CP can be fathomed (removed from further search) if the best solution in that CP is found. If not fathomed, it is then split into smaller CPs and added to the list of CPs. As the algorithm proceeds, the best known feasible solution is maintained and when the list of CPs become empty, the best known feasible solution is the optimal solution.

Although the B&B technique is easy to understand, the implementation for a particular problem is a nontrivial task [START_REF] Chandru | Integer programming[END_REF] requiring:

• An efficient lower bounding technique that can be solved with less computational efforts and also guarantee a tight lower bound

• Efficient data structures for handling the rather complicated book-keeping of the list of CPs,

• Clever strategies for selecting promising CPs, and

• Branching strategies that could effectively prune the enumeration tree.

The conventional techniques for implementing the above are to use the LP relaxation as the lower bounding technique with variable dichotomy as the branching technique. If the LP relaxation provides a solution with non-integer values for integer variables, then one such variable is chosen and CPs are created by imposing bounds on the variable. The CPs are searched using the best first search (BFS). These techniques are generic and are used by many commercial solvers. In this work, we develop two B&B techniques that exploit the structure of the DA. They differ in the lower bounding techniques and the branching strategies. Both algorithms guarantee a feasible solution at every iteration, using heuristic techniques. The BFS is used as the search technique. The higher level algorithm, without the implementation details of the specific strategies is presented next. (e) if Z(is) < Z(bs) bs ← is;

(f) if Z(ls) < Z(bs) pq.insert(cp-);

(g) Create(cp+);

(h) ls ← LowerBound(cp+); is ← Heuristic(ls);

(i) if Z(is) < Z(bs) bs ← is; (j) if Z(ls) < Z(bs) pq.insert(cp+);
The list of CPs is stored in a priority queue pq. The deletemin operation of the priority queue returns the CP with the least lower bound. If the selected CP is not pruned, two child CPs are generated and added to the priority queue if they are not infeasible/fathomed/pruned. The priority queue is implemented using the binary heap data structure. Every insertion and deletion is of complexity O(log P ), where P is the current size of the queue [START_REF] Cormen | Introduction to Algorithms[END_REF]. The routine LowerBound determines the lower bound and returns the lower bound solution (possibly infeasible to the WDP). The Heuristic constructs a feasible incumbent solution to the WDP from the lower bound solution. Using the branching technique two candidate problems cp-and cp+ are created from cp using the routine Create, partitioning the solution space of cp. The implementation details of these routines for the proposed algorithms will be presented later. The is, bs, and ls store the incumbent solution, the best incumbent solution, and the lower bound solution, respectively. The Z(• ) denotes the optimal objective value of the solution (• ). At the end of the algorithm, bs contains the optimal solution to the WDP.

Branch-on-Supply

The B&B algorithm developed in this work, called as branch-on-supply (BoS) does not use the IP formulation of the WDP, but rather uses the network structure. Note that if the optimal number of winning items for each of the bid is known, then finding the respective winning items is an easy problem. The BoS uses this principle to search for optimal number of winning items.

INRIA CP: [S j , S j ] © d d d d CP-: [S j , δ j ] CP+: [δ j + 1, S j ]
Figure 2: Branching Strategy of BoS

Candidate Problem and the Lower Bounding Technique

The CP represents the set of feasible solutions it contains. BoS uses the following CP: each bid j has a supply in range [S j , S j ]. Thus the first CP, which contains all the feasible solutions has S j = 0 and S j = M , ∀j. The CP is feasible iff S j ≤ S j , ∀j and j S j ≤ M ≤ j S. The lower bound to the CP is obtained by solving it as an interval transportation problem with supply for j bounded in the interval [S j , S j ] and with cost on the link (j, m) as p

Sj m j

. Clearly the optimal objective value of the interval transportation problem is the lower bound to the associated CP, as the considered cost is the maximum discounted cost.

Branching Strategy

If a CP is not fathomed or pruned or infeasible, then it is partitioned into two subproblems CP-and CP+. Let δ j be the number of items supplied by bid j in the lower bound solution. Obviously δ j ∈ [S j , S j ]. If δ j = S j , ∀j then the lower bound solution is the optimal solution of that CP and the CP said to be fathomed. If δ j < S j for at least one bid j, then the bid supplies δ j items for a discount of S j items, violating the discount constraint. Two subproblems CP-and CP+ are created by branching on a discount violating bid as shown in Figure 2. The upper bound on the supply of CP-is changed to δ j and the lower bound of CP+ is changed to δ j + 1. The supply range of the other bids are not changed. Note that, the solution space of the CP is partitioned into two and the lower bound solution of CP is not feasible to the interval transportation problems of CP-and CP+. Thus, when these problems are solved, the same lower bound solution is not encountered. If there are several such discount violating bids, one of them is chosen to create two subproblems. The branching bid as follows:

j ′ = arg min j {(S j -δ j ) : δ j < S j } (20)

Primal Heuristics to Determine Incumbent Solutions

The lower bound solution with supplies {δ j } and the flow is a feasible solution to the WDP as j δ j = M . However, the cost of the solution is not compatible, as it determined using {p Sj m j }, instead of {p δj m j }. Therefore, the allocation of winning items may not be optimal to the supplies {δ j }. To get the optimal allocation, a transportation network is constructed with supplies {δ j } and flow costs {{p δjm j }. The flow to this new network is a feasible solution to the WDP. Thus BoS is an anytime algorithm that can be terminated anytime guaranteeing a feasible solution.

BoS vs LP Relaxation based B&B

At the outset, the design philosophy of BoS looks very different from that of conventional LP relaxation based B&B. However, a deep investigation shows that both share many similarities with respect to the lower bounding technique and the branching strategy. As mentioned in Section 5, the LP relaxation is the transportation problem with flow cost equal to the maximum discounted cost. This is the same with the interval transportation problem, which uses the maximum discounted cost (p

Sj m j

) for item m from j. However, there is a lower bound S j on the number of items that can be supplied from j. Thus, the problem is more constrained than the LP relaxation and one can expect a more tightened lower bound.

In the LP relaxation of the WDP, only the integrality of the binary variables {v i j } are violated. If variable dichotomy branching is used, then a fractional v i j is chosen and two subproblems are created by imposing v i j = 0 in of them and v i j = 1 in the other. The constraints (3) involving {v i j } are specially ordered set of type1 (SOS1) constraints. SOS1 constraints impose at most one variable in the constraint to be positive. The effective branching strategy for SOS1 is to choose an index i ′ and create two CPs by imposing i≤i ′ v i j ≤ 1 in of them and i>i ′ v i j ≤ 1 in the other. This essentially means that in the first CP, bid j can supply at most i ′ items and in the second CP, it can possibly supply more than i ′ . This is similar to the branching used in BoS. However, in BoS the respective constraints are of form i≤i ′ v i j = 1 and i>i ′ v i j = 1.

Valid Inequalities as Cuts

A valid inequality for an IP problem is an inequality that is satisfied by all the feasible solutions. Valid inequalities that are not part of a formulation are essentially redundant constraints. However, they may serve as cuts if they are not satisfied by all feasible solutions of the LP relaxation [START_REF] Wolsey | Integer Programming[END_REF]. A cut that is not satisfied by an optimal solution of the LP relaxation is called as a violated cut. Addition of a violated cut to the LP relaxation tightens it and provides a better bound. In this way, the formulation is changed in such a way that the LP feasible region becomes smaller but the IP feasible region is unaffected. Identification

INRIA

of violated cuts, adding them to the LP relaxation, and resolving them to find better bounds, can be iterated till no violated cuts can be found. The optimal LP solution to the IP formulation (Section 2.2) had binary values for {w im j } and fractional values for {v i j }. Hence the following valid inequalities serve as cuts to the LP relaxation:

w im j ≤ v i j ∀j, i, m (21)
They are obviously valid for the IP formulation and they exclude the optimal solution of the original LP relaxation. Hence, the bounds obtained can be expected to be tighter than the original formulation. The above family of cuts were generated by studying the LP relaxation solution. This does not involve solving separation problems and hence no algorithmic efforts involved. Further the size of the family of cuts is polynomial: O(N M 2 ). However, these cuts are not facet defining and hence not strong enough to remove all the infeasible linear solutions.

The optimal solution of the LP relaxation with cuts satisfies the following properties:

1. If v i j > 0, then number of non-zero w im j s are greater than or equal to i.

2. The {w im j } take binary values only if {v i j } are binary. The first property is a direct consequence of the valid inequalities and the constraint set (4). The second property follows from the first.

Branch-and-Cut Algorithms

Branch-and-cut [START_REF] Mitchell | Integer programming: Branch-and-cut algorithms[END_REF] is a generalization of B&B, which includes the cut routine to identify and add violated cuts. The generation of tighter bounds with addition of violated cuts helps in pruning the B&B nodes, thereby reducing the search space. At each node, the LP relaxation is repeatedly solved with addition of new cuts each time. There are several variations of B&C with respect to cuts generation and addition. For a detailed exposure, see [START_REF] Cordier | bc-opt: A branchand-cut code for mixed integer programs[END_REF][START_REF] Mitchell | Branch-and-cut algorithms for combinatorial optimization problems[END_REF]. Cuts can be added to the B&B tree in various ways, leading to different algorithms.

Cut-and-branch (C&B) is a B&C variant where a family of cuts are added to the formulation and B&B is applied to the modified formulation. This technique is useful if generation of cuts are easier and are known a priori (as is the case in our problem). It is advantageous as the cuts added are valid throughout the tree and no further cuts are required to be added. Usually the number of cuts added are very large and many of them may not be useful. With large number of constraints, the time taken to solve the LP relaxation can increase considerably. An alternate approach is to add the cuts that are only violated by the current LP solution. In this way, cuts are progressively added. There are two possible approaches here: B&C-global, in which cuts added are valid throughout the search tree and B&C-local, where the cuts added are valid only to the subtree of the current node.

Branch-on-Price

In this section, we propose a new heuristic branching technique called as branch-on-price (BoP). According to the properties of the optimal LP solution mentioned in Section 7, either all variables are binary (in which case optimal to the IP) or many variables are fractional. The variable dichotomy branching is to chose a particular fractional v i j or w im j to create two CPs by imposing the variable to equal to 0 and 1, respectively. The branching on a v i j is more generic than that on a w im j . The former splits the solution space based on the number of items supplied by a bid, whereas the latter is more specific about an item, supplied by a particular bid that supplies a certain number of other items. We propose here a novel technique to create candidate problems by branching on the price of an item.

Most of the integer variables in an IP formulation of combinatorial or discrete optimization problems are auxiliary variables created to impose logical constraints or linear constraints. Hence branching on such variables directly may not have logical or natural implication on the way the subsequent candidate problems are created. Further, the size of the solution set of these candidate problems may not be balanced, thus resulting in a unbalanced search tree. For example, a candidate problem created by fixing w im j = 1 may have very less number of solutions compared with the CP created by fixing w im j = 0. Instead of creating CPs by branching on fractional variables, we create by branching on the price of an item, which is fractionally supplied by more than one supplier.

Let w im j be fractional. Due to the constraint [START_REF] Chandru | Integer programming[END_REF], there exist at least one another w i ′ m j ′ with i = i ′ , which is fractional. Let β m be the price of the item m as dictated by the LP solution:

β m = j i p im j w im j ( 22
)
We create two CPs, CP-and CP+, by branching on the above price. The CP-is created by adding the following constraints:

w im j = 0 if p im j ≥ β m , ∀j, i, m (23)
The CP+ is created by adding constraints

w im j = 0 if p im j < β m , ∀j, i, m (24)
The two CPs partition the IP feasible solution space. The optimal LP solution (which is infeasible) does not belong to the solution space of the relaxations of the either of the CPs. To facilitate this branching, we represent a CP by using bounds on the prices of each of the items.

The CP is compactly represented by using an allowable price range [β m , β m ) for each item m. Algebraically, this is achieved by imposing the following bounds in the IP formulation: price range for m. This is illustrated in Figure 3. Note that the price range of other items will remain the same as that of the parent CP.

w im j = 0 if p im
The above branching scheme imposes many variables to be zero, across several bids, rather than just fixing one variable to 0 or 1, as in the variable dichotomy branching. Further, such a branching is more meaningful in terms of the WDP. The β m can be considered as the price of the item m and the BoP algorithm is searching for the optimal price from the set of {p im j }, subject to the discount and demand constraints. Violation of the discount and the demand constraints leads β m to be a convex combination of some of the prices from the set {p im j }. The proposed branching scheme partitions the set such that the same convex combination cannot be encountered again, thereby removing the violation in the constraints. In this way, one can expect that the algorithm will converge fast towards the optimal prices. It is worth noting that even though the β m is a real number and thus the branching could be infinitely divisible, the possible optimal values it can take is N M and hence the number of branches is finite.

If there are more than one item which have fractional allocations, the algorithm has to choose one item to branch. Let β m be the price of item m defined by the convex combination [START_REF] Kothari | Approximately strategy proof and tractable multi-unit auctions[END_REF] and B m be the set of bids that partially supply item m. The item m ′ to branch on is chosen by one of the following rules:

BoP1 : m ′ = arg min m {β m -β m : β m > β m , |B m | > 1} ( 25
)
BoP2 : m ′ = arg min m {β m -β m : β m > β m , |B m | > 1} (26)
BoP3 : m ′ = arg max m {|B m | : β m > β m , |B m | > 1} (27)
BoP1 chooses the item with price closest to its lower bound, BoP2 chooses the item with price closest to its upper bound, and BoP3 chooses the item with maximum number of allocated bids. In all the three rules, the branching item is chosen such that its price

Bids Items m1 m2 m3 j1 j2 j3 (1) (1)
(1)

(3) (3)
(3) (Supply) (Demand) (1)

(1) (2)
(2)

(2) (Supply) (Demand)

Figure 5: With no feasible IP solution is strictly greater than its lower bound. According to the rules of the creation of CPs, branching on an item with β m = β m will create an infeasible CP-with range [β m , β m ) and CP+ with range [β m , β m ), which is same as its parent CP. To avoid an infinite loop, only items β m > β m are considered. However, a pathological case is encountered when all items having their prices equal to their respective lower bounds. In this situation, we chose an item m randomly and create only CP+ with range [β m + ǫ, β m ). The ǫ > 0 is chosen such that it is small enough to exclude just the price β m . Note that there is no CP-created and with this new CP+ creation, it is possible that a feasible IP solution with prices {β m } might be excluded in the search, thus not guaranteeing optimality.

No Strict Convex Price

Let there exist a non-integer solution such that

β m = β m if |B m | > 1.
The cost of this solution is m β m and it is possible that there exists an integer solution with the same cost. Consider the LP solution shown in Figure 4 as a transportation network. A link between a bid and an item denotes the allocation. The (Supply) denotes the number of items that the bid should supply. The option is to either accept the bid with a supply of three items or reject the bid entirely. Note that modifying the supply will result in change of discount and hence in the change of solution cost. The solution shown in the figure is infeasible as each item is supplied by more than one bid. However, if allocation from any two bids are removed then it is a feasible IP solution with the same cost as that of the LP solution. It can be easily seen that the LP solution in Figure 5 has no feasible IP solution. Thus when a LP solution is encountered with no item to branch on, it is required to find a feasible IP solution with the same cost or prove that no such solution exists. Let M be the set of items with |B m | > 1 and β m = β m . Note that the rest of the items will have |B m | = 1 and hence satisfy the integrality constraints. Let I j be the set of items that are being supplied by bid j with allowed supply in the range [S j , S j ]. The allowed INRIA supply range is determined by the discounts at which the current partial allocation is made. If S j < S j then θ S j j = θ Sj j . Let J be the set of bids that supply items partially. Given such a solution, one has to find a feasible IP solution with the following properties:

• |B m | = 1, m ∈ M • |I j | ∈ {0} ∪ [S j , S j ], j ∈ J
The second property ensures that either the bid supplies in the allowable range such that the cost of the solution is not altered or it is rejected. This is a capacitated facility location problem, where the bids are the facilities that can be opened or closed and if opened their capacity is in the allowable supply range.

Consider an item m ′ ∈ M and let j ′ ∈ B m ′ be chosen to supply this item. This allocation results in the following sequence of allocations:

1. Other bids in B m ′ have to be removed:

B m ′ ← B m ′ \ {j}, j = j ′ ∈ B m ′ 2. Item m ′ is removed from corresponding I j : I j ← I j \ {m ′ } 3.
If removal of m ′ from I j violates the supply constraints, then it is removed:

|I j | < S j ⇒ B m ← B m \ {m}, m ∈ I j ⇒ I j ← ∅
The above sequence will result in one of the following cases:

1. A feasible IP solution.

A infeasible IP solution with any of |B

m | = 0.

At least there exists one

m such that |B m | > 1.
If a feasible solution is encountered then the search can be stopped. If an infeasible solution is encountered, then m ′ cannot be supplied by j ′ and hence j ′ can be removed. In this case, the next bid from B m ′ is considered for allocation. For case 3, a bid from B m is chosen and allocated to m and the search proceeds iteratively. If all bids of B m ′ were allocated and no feasible solution was found, then there exists no IP solution. This is a depth first search that can be implemented using a recursive algorithm.

Primal Heuristics to Determine Incumbent Solutions

Let w im j be the optimal LP solution. If all are binary, then it is a feasible solution to the IP. The following heuristic constructs a feasible solution from the fractional LP solution.

1. (Initialize) S j = 0, ∀j 2. do ∀m: k = arg j max j,i {w im j }; S k ← S k + 1;

3. Construct a transportation network with winning bids as sources and items as sinks.

The source corresponding to winning bid j has a supply of S j > 0 and each sink has a unit demand. The cost of flow from j to m is p Sj ,m j

. Let x m j be the optimal flow. Assign V Sj j = 1 and w Sj ,m j = x m j .

The winning bid for an item m is chosen as the one with the largest w im j value. This is used to determine the number of winning items S j for each winning bid. This is in turn used to determine the winning items with the consistent discount prices p Sj,m j . This will provide a better IP solution than directly rounding the largest w im j to 1. Using this heuristic, an incumbent solution is obtained whenever a new CP is created and the best known solution is updated and stored.

Computational Experiments

In this section, we present the results of the extensive computational experiments conducted using the various proposed algorithms across various problem types.

Discount Auctions Test Suite

A test suite called as discount auctions test suite (DATS) was created to randomly generate different types of problem instances. The intention is to study the effects of the varying discount and cost structures on the computational requirements of the problem. A problem instance is defined by M , N , {Q m j }, and {θ i j }. Given M and N , the cost and the discounts can be generated in many ways. Firstly, there are two kinds of cost differences: relative market costs across the items and for each item, relative bid costs quoted by the suppliers. We assume a normalized market cost rc m for each item m, which is uniformly distributed in range [rc, 1] with 0 < rc < 1. The rc is an input parameter and rc m are randomly chosen in the above range. At least one item is chosen to have value 1 and another rc. The rc is the minimum relative cost in the portfolio of items that are being procured. For example, to model the scenario where the procured items have a maximum of 15% relative difference in the cost, rc = 0.85.

For any given item, the bid price quoted by the suppliers vary. The minimum cost quoted for an item m is captured using a parameter mc m . The mc is the input parameter and mc m are randomly chosen in range [mc, 1). The individual cost of m for bid j in chosen in the following way:

Q m j = Random[mc m , 1] × rc m (28)
The above costs are chosen such that at least one bid has rc m and one has the minimum cost mc m × rc m . As rc m denotes the market value, it is maximum price quoted that can be quoted by the suppliers.

For generating the discount functions, a discount range is input to the DATS. For example, if the input discount range is [θ, θ], then all the maximum discounts {θ M j } are chosen INRIA randomly in this range. There is no discount for one item: θ 1 j = 0. The intermediate values are chosen according to type of the discount function. The DATS currently supports following types of discount functions: 1. Linear:

θ i j = (i -1) × θ M j M-1
2. Marginally Decreasing:

θ i j = - θ M j (M-1) 2 × (M -i) 2 + θ M j 3. Marginally Increasing: θ i j = θ M j (M-1) 2 × (i -1) 2 4.
Step 5. Arbitrary 6. Random: The discount type for a bid j is chosen randomly from one of the above.

All functions are strictly increasing, except for the type Step. The Arbitrary is strictly increasing without any notable structure like the preceding types.

The experiments were carried out on a Windows XP based PC equipped with a 2.8GHz Intel P4 processor with 1GB RAM. The algorithms were coded in Java, and for the model building and solving of LP relaxations and transportation problems in primal heuristics, ILOG Concert Technology of CPLEX 10.0 [START_REF] Ilog Cplex | ILOG Concert Technology 1.1 User's Manual[END_REF] was used.

LP Experiments

The first set of experiments were conducted to study the tightness of the LP relaxation with cuts. The performance criterion is the duality gap, calculated as follows:

Duality Gap (%) = Relaxed Value -Optimal Value Optimal Value × 100 (29)
The rationale for studying the duality gap is that it greatly influences the search time of the branch-and-cut algorithms. The bounds given by the relaxation is used to prune the search tree and hence tighter the bound, less the time taken to explore the tree. Extensive experiments were conducted by varying the problem parameters shown in Table 1. The rc and mc were varied from low to high values. The discounts [θ, θ] were chosen from three different sets of values representing close range, medium range, and high range. M and N were chosen to in two sets to study the effect of varying N for the same M and vice versa. All the six discount types currently supported by DATS were tested. Fifty problem instances were created for each of the different combination of values of the parameters and the average duality gap for the LP relaxation with and without the cuts were calculated. Following are the main inferences from the experimentation: 1. The LP relaxation with cuts gives significantly tighter bounds. Problem instances with duality gap as high as 70% had a duality gap of less than 1% with cuts. Indeed for all the problem instances considered, the average duality gap was less than 1% with the addition of cuts.

+ + + + + + Marg. Inc. × × × × × × × × × × × × × × × × × × × Step △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ 0
2. The parameter rc had no effect on the duality gap. Thus items with varying costs or similar costs have no influence on the duality gap.

3. The discount types did not affect the duality gap significantly for LP relaxation without cuts. However, with the addition of cuts, the discount types had the maximum average duality gap in the following increasing order: arbitrary (0.005%), marginally increasing (0.03%), linear (0.04%), random (0.3%), step (0.6%), and marginally decreasing (0.9%). For most of the problem instances, linear, marginally increasing, and arbitrary discount types had zero duality gap.

4. The parameter mc showed significant changes in the duality gap for both the LP relaxations with and without cuts (see figures 6 to 8). As mentioned above, the duality gap also depended on the discount types for relaxation with cuts.

5. Significant changes in the duality gap were observed for discounts chosen in close range. As shown in figures 9 to 11, the duality gap increased with the increase of θ for LP relaxation without cuts but showed a reverse behavior with cuts. Again, the gap depended on the discount type for relaxation with cuts.

6. For M = 10, the average duality gap increased steadily with the increase of N till 50 and became negligible for N = 75 and almost zero for N = 100. Similar results were observed for varying M with fixed N . When the size of N becomes relatively larger than that of M , the duality gap is negligible as with more N , the possibility of better bids is high.

Branch-and-Cut Experiments

To study the performance of the branch-and-cut, a suite of algorithms were created by combining different cut addition techniques and branching rules. Following cut addition techniques were considered:

Cut-and-Branch (C&B) : All the N M 2 cuts (w im j ≤ v i j , ∀j, i, m) are added to the IP formulation at the root node.

Branch-and-Cut Global-w (B&C-Gbl-w) : After each simplex iteration (that solves the LP relaxation), only those variables that violate the inequality w im j ≤ v i j induce the corresponding cuts and are added globally to all the nodes in the search tree.

Branch-and-Cut Global-V (B&C-Gbl-V ) : After each simplex iteration, if an w im j violates the inequality w im j ≤ v i j then cuts for all items for that j and i are added as global cuts.

Branch-and-Cut Local-w (B&C-Loc-w) : Same as B&C-Gbl-w, except that the cuts are local cuts.

Branch-and-Cut Local-V (B&C-Loc-V ) : Same as B&C-Gbl-V , except that the cuts are local cuts.

The different branching techniques include the traditional variable dichotomy (Var-Dic) along with the three BoP techniques proposed in Section 8.1. With the above combinations of cut addition and branching techniques, twenty branch-and-cut algorithms were used for experimentation. The performance parameters considered were:

• CPU time (in milliseconds)

• number of nodes explored • number of simplex iterations Preliminary experimentation with BoS showed that the branch-and-cut was many folds faster than BoS. This is not surprising given the tighter bounds obtained with the addition of cuts. Hence, BoS was excluded from further experimentation and only the twenty branchand-cut algorithms were considered. The values for parameters mc, rc, [θ, θ] were chosen based on the duality gap that was observed with LP relaxation. The entries in tables 2 to 6 are the triplet CPU time (ms), nodes explored, and simplex iterations. With more than three hundred instances solved, following inferences were made: • Problem instances with linear, marginally increasing, and arbitrary discount types required no branching and were solved at the root node itself. Even for problem instances with non-zero duality gap, the primal heuristic proposed in Section 8.2 found the optimal solution at the root node.

INRIA

• For the rest of the discount types, the nodes explored and time taken were purely instance specific and was not much influenced by the parameter values. Tables 2 and3 show the widely varying performance of two problem instances with the same set of parameter values.

• Every problem instance was solved using the commercial solver CPLEX using the IP formulation with cuts. CPLEX uses branch-and-cut with built pre-processing, cut generation routines, advanced branching techniques, and primal heuristics [START_REF] Ilog Cplex | ILOG CPLEX 10.0 User's Manual[END_REF]. For most of the problem instances, the minimum time taken by the proposed branch-andcut algorithms (shown in bold face in the tables) was less than that of CPLEX.

• The no strict convex price case was encountered only for the problems with step discount function.

• Performance of algorithms with local cuts was relatively poor for all the instances.

• In almost all the cases, BoP branching techniques (in particular BoP1 and BoP3) showed better performance than variable dichotomy.

• Cut-and-branch is computationally better than the other cut addition techniques, though in few cases global cuts showed superior performance.

Conclusions and Future Work

In this work, we proposed a new auction mechanism called as discount auctions for procuring single units of multiple items. This is useful in industrial procurement scenarios, where an organization is interested in buying M distinct, possibly related, items from a pool of N suppliers. The M items are assumed to be independent and compatible with each other even if brought from different suppliers. For this scenario, traditional combinatorial bids for INRIA subsets of items are redundant, and the proposed discount bids are more meaningful. Further the bids to be communicated are linear in the number of items, in contrast to exponential number of combinatorial bids. However, despite its simplicity, the winner determination problem was proved to be N P-hard upon reduction from the set covering problem. We proposed two intelligent optimal search algorithms. The first algorithm, called as BoS (branch-on-supply) is a branch-and-bound algorithm, which uses the embedded network structure in the problem to determine the optimal number of items supplied by each seller. The algorithm preserves the combinatorial structure of the problem and uses special branching technique to search for the optimal solution. The second is a suite of branch-andcut algorithms that use valid inequalities added as cuts to the IP formulation. The valid inequalities that are added as cuts are not facet-defining. However, the size of the entire family of the cuts is polynomial (N M 2 ) and can be determined directly from the LP solution. Computational experiments showed that the duality gap is considerably less and hence the algorithm is many-folds faster than that of BoS. A novel branching technique called as BoP (branch-on-price) was proposed. It branches on the price of an item that is infeasible allocated to more than one supplier. Extensive computational experiments were performed using the problems generated by a test suite.

This work was devoted mainly to the computational aspects of solving the winner determination problem to optimality. There are several interesting research fronts in which the discount auctions could be explored further.

• Iterative Discount Auctions: We considered here an one-shot discount auctions with just a single round of bidding. Iterative auctions with several rounds of bidding are preferable for auctions with large number of items. The suppliers need not communicate the entire discount bid, but can progressively express the bids based on the dynamics of the auction. The commonly used approach is the mechanism design technique with duality theory of mathematical programming.

• Eliciting Bidder Preferences: One of the important problems in auctions is the bid preparation. For discount auctions, the bidder has to specify individual costs for M items and a discount function. Determining the discount for the number of items may not be easy and one need a preference elicitation mechanism to determine the discounts.

• Multiunit Discount Auctions: In this paper, we considered single unit of multiple units. An useful extension is to look at multiple units of multiple items. Inclusion of multiple items adds another layer of complexity and the proposed algorithms in this work are not directly extendable.

• Discounts based on Cost: The discount structure considered in this paper depends on the number of items bought. Another meaningful perspective is to define the discounts based on the total cost of the items procured.

• 0-1 Knapsack with GUB Constraints: We added a family of valid inequalities from the LP relaxation. The formulation also has a 0-1 knapsack structure [START_REF] Wolsey | Integer Programming[END_REF] with GUB (gen-eralized upper bound) constraints [START_REF] Wolsey | Integer Programming[END_REF]. In particular, the following set of constraints constitute a multiple choice knapsack structure.

i v i j ≤ 1 ∀j (30)
j i iv i j = M (31)
Generation of valid cover inequalities for 0-1 knapsacks with generalized upper bound constraints were studied in [START_REF] Wolsey | Valid inequalities for 0-1 knapsacks and MIPs with generalized upper bound constraints[END_REF]. The generation of cuts would involve solving the hard separation problem, either optimally or approximately. It is worth investigating the hardness of the separation problem for the above constraints and studying the tradeoffs of investing resources in generation of the cover inequalities against the savings in the convergence of the algorithm.

Figure 1 :

 1 Figure 1: Embedded network structure

•

  Determining the lower bound of the selected CP • Fathoming or pruning, if possible, the selected CP • Determining and updating the incumbent solution, if possible INRIA • Branching strategy: If the CP is not fathomed, branching creates subproblems which are added to the list of CPs

1 .

 1 (Initialize) cp ← {WDP}; pq = ∅; ls = ∅; is = ∅; bs = ∅; 2. ls ← LowerBound(cp); is ← Heuristic(ls); bs ← is; 3. if Z(ls) = Z(is) end;4. pq.insert(cp); 5. while pq = ∅ do: (a) cp ← pq.DeleteMin(); (b) if Z(LowerBound(cp)) ≥ Z(bs) end; (c) Create(cp-); (d) ls ← LowerBound(cp-); is ← Heuristic(ls);

jFigure 3 :

 3 Figure 3: Branching Strategy of BoP

Figure 4 :

 4 Figure 4: With feasible IP solution

Figure 7 :Figure 8 :Figure 9 :Figure 11 :

 78911 Figure 7: LP relaxation with cuts: N = 50, M = 15, rc = 0.5, [θ, θ] = [0.3, 0.4]

Table 2 :

 2 Discount Type: Marginally Decreasing

		N = 75, M = 15, mc = 0.4, rc = 0.3, [θ, θ] = [0.2, 0.3] , CPLEX Time = 38183
		Var-Dic	BoP1	BoP2	BoP3
	C&B	69437, 12, 25	14262, 1, 3	21923, 2, 5	41865, 4, 9
	B&C-Gbl-w	76225, 19, 593	19910, 1, 316	22985, 2, 351	36735, 4, 444
	B&C-Gbl-V	149721, 28, 210	14844, 1, 107	18292, 2, 119	39076, 4, 148
	B&C-Loc-w	428295, 21, 10308	34547, 1, 692	56266, 2, 1190	118037, 4, 2312
	B&C-Loc-V	182156, 12, 2622	22655, 1, 269	41894, 2, 431	84364, 4, 860

Table 3 :

 3 Discount Type: Marginally Decreasing

		N = 75, M = 15, mc = 0.4, rc = 0.3, [θ, θ] = [0.2, 0.3] , CPLEX Time = 34174
		Var-Dic	BoP1	BoP2	BoP3
	C&B	273008, 63, 127	122619, 13, 27	193618, 17, 35	128974, 15, 31
	B&C-Gbl-w	187098, 66, 673	77276, 13, 431	119650, 18, 513	82121, 15, 489
	B&C-Gbl-V	249583, 66, 281	118355, 13, 158	182611, 18, 178	132086, 15, 166
	B&C-Loc-w	1673004, 79, 40747	302033, 13, 6153	396731, 18, 8226	404872, 15, 6641
	B&C-Loc-V	1313137, 79, 16811	250748, 13, 2818	341685, 17, 3735	299482, 15, 2918

Table 4 :

 4 Discount Type: Step

		N = 50, M = 15, mc = 0.4, rc = 0.3, [θ, θ] = [0.2, 0.3] , CPLEX Time = 19904
		Var-Dic	BoP1	BoP2	BoP3
	C&B	14171, 8,	178249, 1, 3	8281, 1, 3	7484, 1, 3
	B&C-Gbl-w	11499, 4, 238	10499, 1, 220	10484, 1, 220	10874, 1, 251
	B&C-Gbl-V	9577, 4, 98	9093, 1, 91	9062, 1, 91	7733, 1, 94
	B&C-Loc-w	69401, 4, 1696	23545, 1, 539	23404, 1, 539	23795, 1, 550
	B&C-Loc-V	133146, 10, 1784	18490, 1, 252	18396, 1, 252	19351, 1, 267

Table 5 :

 5 Discount Type: Random

		N = 50, M = 15, mc = 0.4, rc = 0.3, [θ, θ] = [0.2, 0.3] , CPLEX Time = 2735
		Var-Dic	BoP1	BoP2	BoP3
	C&B	2048, 2, 5	1767, 1, 3	1766, 1, 3	1720, 1, 3
	B&C-Gbl-w	3111, 3, 190	2830, 1, 177	2876, 1, 177	2783, 1, 176
	B&C-Gbl-V	3126, 3, 81	2877, 1, 75	2892, 1, 75	2861, 1, 75
	B&C-Loc-w	19026, 3, 1176	8082, 1, 460	8286, 1, 460	7754, 1, 458
	B&C-Loc-V	18072, 3, 501	7832, 1, 206	7879, 1, 206	7520, 1, 202
	RR n°6084

Table 6 :

 6 Discount Type: Random

		N = 75, M = 15, mc = 0.4, rc = 0.3, [θ, θ] = [0.2, 0.3] , CPLEX Time = 8125
		Var-Dic	BoP1	BoP2	BoP3
	C&B	4422, 5, 11	17281, 7, 15	22563, 7, 15	3516, 1, 3
	B&C-Gbl-w	4875, 5, 160	20093, 7, 296	15562, 7, 257	4672, 1, 152
	B&C-Gbl-V	4547, 5, 96	18953, 7, 145	15125, 7, 121	4219, 1, 88
	B&C-Loc-w	43234, 5, 1570	66891, 7, 2056	57422, 7, 2046	12937, 1, 424
	B&C-Loc-V	41109, 5, 847	59500, 7, 1249	58281, 7, 1316	11391, 1, 228

RR n°6084

Arbitrary ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆

Arbitrary ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆

Arbitrary ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ Random

× Arbitrary ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ Figure 10: LP relaxation with cuts: N = 50, M = 15, mc = 0.5, rc = 0.5, θ = θ -0.1 INRIA