پشتیبانی تصمیم گیری مبتنی بر بهینه سازی برای تجزیه و تحلیل سناریو در بازارهای سپارش الکترونیکی همراه با تخفیف حجم

E-Sourcing software has become an integral part of electronic commerce. Beyond the use of single-lot auction formats, there has been an emerging interest in using e-sourcing software for complex negotiations. Procurement markets typically exhibit scale economies leading to various types of volume discounts which are in wide-spread use in practice. The analysis of bids in such negotiations typically leads to computationally hard optimization problems. Scenario analysis describes a process, in which procurement managers compute different award allocations as a result of different allocation constraints and parameters that they put in place. This paper discusses an optimization model and computational methods which allow for effective scenario analysis with allocation problems in the presence of different types of discount policies and allocation constraints. The model reduces the number of parameter settings to explore considerably. The models are such that they can often not be solved exactly for realistic problem sizes in practically acceptable time frames. Therefore, we provide results of numerical experiments using exact algorithms and heuristics to solve the problem. We find that RINS and Variable Neighborhood Search can be effectively used in traditional branch-and-cut algorithms for this problem. Overall, new computational approaches allow procurement managers to evaluate offers even in markets with a complex set of volume discounts and multiple allocation constraints.

Electronic auctions and requests for quotes play a central role in the sourcing operations of companies today (Limberakis 2012). Also, much research in electronic commerce has focused on the electronic sourcing markets (Amelinckx et al. 2008) and the design of procurement auction formats and bid evaluation algorithms (Sun and Sadeh, 2009, Ray et al., 2011 and Huang et al., 2011). Our paper contributes to this line of research, and is also motivated by the increasing popularity of mathematical optimization in e-sourcing practice (Limberakis 2012). Volume discounts are ubiquitous in such procurement negotiations and a result of economies of scale that a supplier experiences. For example, a supplier might charge a lower unit price, if a procurement manager buys more than thousand units of a commodity due to economies of scale on a finishing line. Overall, scale economies of this sort can arise from lower input costs to reductions in unit cost as the size of a facility and the usage levels of other inputs increase. Whereas economies of scale primarily refer to efficiencies associated with supply-side changes, such as increasing or decreasing the scale of production of a single product type, economies of scope refer to efficiencies primarily associated with demand-side changes, such as increasing or decreasing the scope of marketing and distribution of different types of products. Traditional auction formats as used in e-sourcing software, typically do not allow bidders to specify such volume discounts or consider them in the award allocation. Procurement managers often try to take volume discounts into account using spreadsheet programs. Unfortunately, the consideration of volume discounts leads to hard computational problems as we will see in the following and it is unlikely that a procurement manager would find cost minimal solutions using heuristics in a spreadsheet program. Combinatorial auctions allow for bids on packages of items and are one possibility to address volume discounts in the auction design. There are a growing number of publications on combinatorial auctions in the Information Systems literature (Ono et al., 2003, Bichler et al., 2011, Adomavicius et al., 2012, Scheffel et al., 2011 and Hsieh and Lin, 2012), and they seem to be a natural solution for markets with economies of scale. CAs can be seen as the most general type of market mechanism as they allow bidders to express general valuations including substitutes and complements. Combinatorial auctions can well be used for procurement decisions with multiple line items and large volumes of each. A multi-unit combinatorial auction allows for the specification of volume discounts for different quantities of an item with a bundle price. While the winner determination is straightforward to model, the elicitation of bidder preferences becomes a problem. For a single-unit combinatorial auction with n items, a bidder can submit 2n possible bids. In a multi-unit combinatorial auction, the number of possible bids grows super-exponentially with View the MathML source∑i=0n-1kn-ini, with k being the number of units for each item. For example, with 10 items and 6 allowable quantities for each of them the supplier could specify more than 270 million bids. Clearly, suppliers will only be able to specify a small proportion of bids, and the auctioneer will most likely not find the efficient, maybe not even a feasible allocation. Compact bid languages provide a remedy for such markets. Davenport and Kalagnanam (2000) were among the first authors to discuss volume discount bids. Their bidding language requires suppliers to specify continuous supply curves for each item, allowing them to express economies of scale. They apply discounts only to additional units above a threshold of a specific price interval. In contrast to these Incremental (Volume Discount) Bids, Goossens et al. (2007) proposed tiered bids, which we refer to as Total Quantity Bids. The latter are valid for the entire volume of goods purchased after a certain quantity threshold. Fig. 1 provides an example of tiered bids, where a procurement manager has a demand of 3000 units of one item only, and suppliers are restricted to 2000 units. Supplier 1 charges a unit price of $3.50 for up to 2000 units, while supplier 2 charges $4 for up to 1500, but only $2.50 per unit for the entire quantity, if the purchasing manager bought 1500–2000 units. A greedy solution would be to purchase 2000 units from supplier 3 and the remaining 1000 units from supplier 1, which would lead to 7500$. The optimal solution is to buy 1500 units from supplier 2 and 1500 units from supplier 3 resulting in a total cost of 1500 * 2$ + 1500 * 2.5$ = 6750$. Typically, there is not a single commodity only but dozens, and the procurement manager needs to consider allocation constraints on the number of winners or the allocation per winner. The problem of finding the cost-minimal solution can be shown to be NP-complete (Goossens et al. 2007). In addition to the above discount policies, suppliers often provide rebates for a certain overall volume, such as a 3% rebate if they sell items for more than a million. Such Lump Sum Rebates are a possibility to express economies of scope across multiple items. In most real-world procurement negotiations different suppliers use different discount policies including incremental volume, total quantity and lump sum rebates, and a procurement manager needs to take all of them into account in an award decision. Bichler et al. (2011) present an optimization formulation allowing for incremental and total quantity discounts, as well as lump sum rebates based on total spend or volume on different items. They formulate the allocation problem as a mixed integer program, and analyze the computational complexity and the empirical hardness of this problem. The formulation allows for a rich bidding language and a large number of discount policies that can be found in procurement practice. The approach has already been applied successfully in the field. Such problems would have been considered intractable only a few years ago for realistic problem sizes, but with recent advances in hardware technology and algorithmic developments in integer programming which allow for effective parallel implementations of advanced branch-and-cut solvers on multiple cores, there is hope to solve relevant problem sizes. However, with the use of such optimization approaches in practice new problems arise, which require new types of decision support for procurement managers. 1.1. Decision support for scenario analysis1 Typically, complex procurement decisions are not met with a single optimization. Procurement managers need to take multiple allocation constraints into account and the cost minimal solution across multiple line items needs to be found. Procurement managers analyze different scenarios in a sequence employing different types of allocation constraints. For example, they want to set lower and upper bounds for the number of suppliers or for the total spend awarded to a single supplier or a group of suppliers, and understand the impact of these constraints on total cost. This process has been referred to as scenario navigation or scenario analysis (Boutilier et al. 2004) and requires re-optimization of different versions of the problem with different constraints interactively in minutes. Such an interactive usage poses tight time constraints of a few minutes only on the solution time of each optimization run. One of the problems in scenario analysis is the large number of parameters to explore. Typically, the parameters of interest are the right hand sides of the allocation constraints, more specifically, bounds on the number of winners, the volume awarded per bidder or the demand of the buyer. Typically, procurement managers seek for even cheaper solutions, or they want to learn about parameters, which yield a total cost below a certain budget constraint. Due to the fact that dual variables cannot readily be interpreted in a mixed integer program, there is little guidance for procurement managers as to which constraints have the biggest impact on total cost or which combination of constraints they should relax in order to achieve their goals. Therefore, scenario analysis often leads to many optimization runs with many different combinations of right-hand side parameters. The problem has not received attention in the literature to our knowledge. However, in our field work, the lack of effective scenario analysis turned out to be an important criterion for the adoption of optimization approaches in e-sourcing. 1.2. Contribution Our contribution is twofold: First, we introduce a formulation of the winner determination problem (SQSSA) that allows for effective scenario analysis. The formulation allows the specification of acceptable bounds on the right-hand side parameters of the winner determination problem and finds optimal allocations, which minimally violate these bounds. So, rather than having to solve many optimization problems with different parameter settings, the procurement manager uses optimization to find the best solution within acceptable bounds of the right hand sides. The model is in the spirit of literature on parametric integer programming (Bradley et al. 1977). It draws on the supplier quantity selection model (SQS) by Bichler et al. (2011), but reduces the effort for procurement managers to find appropriate scenarios significantly. A specific problem in the model is non-linear constraints due to the new right-hand side variables introduced in the model. We will show effective ways to handle such constraints using standard algorithms to solve integer programs. In our experimental evaluation of exact algorithms, we analyzed problems where bidders could individually specify up to 10 discount intervals, to account for the flexibility that suppliers sometimes demand in expressing their discount schedules. These problems are often such that they cannot be solved exactly any more in acceptable time frames for larger problem sizes beyond a few items and suppliers only. The number of discount intervals and the allocation constraints during the scenario analysis can make these problems so hard that only small instances with up to six items and suppliers can be solved exactly within 10 min. Therefore, as a second contribution, we provide numerical experiments of heuristic approaches to solve larger problem sizes of up to 50 items and bidders. Previous work has mainly relied on standard solvers for mixed-integer programs. It turns out that RINS and Variable Neighborhood Search (VNS) can help to improve on exact algorithms in a number of instances. The managerial relevance of the results is twofold. First, we show that with appropriate optimization models and advanced computational methods procurement managers can set up sourcing markets, which allow them to compare the offerings of complex volume discount bids. Such markets provide flexibility to suppliers in expressing their economies of scale, and they allow buyers to select the cost-minimal solution. Second, the time and effort to analyze complex offerings with volume discounts using heuristics in spreadsheet programs is substantial. Adequate decision support tools for scenario analysis can not only improve the quality of the results, but also make the analysis much more effective and less time-consuming.

E-sourcing tools are used in most companies nowadays to conduct electronic auctions and request for quotes via the internet (Limberakis 2012). Often the use of e-sourcing tools is limited to simple reverse auctions on a single lot only. Negotiations including different features of a product, multiple lots, and volume discounts are often considered too complex for e-sourcing. This largely comes from the computational complexity to compute cost-minimal allocations. Often this task is performed using heuristics in spreadsheet programs and the solution is likely to be far from the cost-minimal allocation. The example in Fig. 1 shows, why volume discounts can already lead to hard computational problems with a single lot only. With the help of only a spreadsheet program a procurement manager has little hope of finding good solutions in due time. Mathematical optimization can provide tangible decision support to not only find better solutions, but to also more effective and less time-consuming ones for the procurement manager. This paper combines different modeling approaches and computational methods from combinatorial optimization and the area of meta-heuristics to allow for effective decision support in e-sourcing. We focus on scenario analysis for winner determination problems in markets with economies of scope. The analysis shows that for restricted problem sizes these allocation problems can be solved to optimality. Also, the effort of the procurement manager is largely reduced. Finally, we propose a formulation of the problem that helps procurement managers to reduce the number of scenarios to explore. The type of decision aid discussed in this paper is made possible by the advances in hardware and algorithms in the recent years, and would have been impossible only ten years ago. We expect that with further advances in multi-core hardware architectures and respective parallel implementations of branch-and-cut algorithms larger problems can be solved only a few years from now. This not only improves the quality of the results of the bid analysis, it also makes the analysis itself more effective and less time-consuming. Although realistic problem sizes can often be solved today, larger problem instances with many items, many discount tiers, and allocation constraints still remain a barrier. Reducing the number of discount tiers or standardizing them across suppliers is one possibility to solve larger problem sizes (see also Bichler et al. 2011), but often this is not possible to impose on suppliers in procurement practice. We have shown that combinations of meta-heuristics such as RINS and VNS with exact branch-and-cut approaches are promising approaches for larger problems. While a study of all meta-heuristics is out of the scope of this paper, the analysis illustrates that meta-heuristics often improve the solution process substantially. Yet, this might still not be sufficient for large instances with more than 40 items and procurement managers want ways to compute such instances as well with good if not optimal solutions. Apart from meta-heuristics as described in this paper, custom heuristics are another avenue to explore. For example, a divide-and-conquer approach as is often used in vehicle routing problems can also be used for SQS and SQSSA, where a procurement manager divides the problem in subsets of a size, which allows for an optimal solution and applies the exact algorithms sequentially to all of these sub-problems. Constraints need to be adapted after each sub-problem, such that the overall constraints are met. Obviously, this might not yield the optimal solution as there can be infeasibilities in the last iterations. Still, this allowed us to find very good solutions for large problem sizes with hundreds of items and suppliers. Such experiments are, however, hard to generalize and heavily depend on the characteristics and constraints of particular problem instances. Nevertheless, such computational approaches to the exact problem formulation are typically faster and more accurate than the simple heuristics often deployed in practice based on spreadsheet calculators. Due to the fact that such decision aids are often used to support multi-million dollar procurement decisions, advanced computational approaches are well justified.