CONTENTS

1. What is an E-Procurement system ?

2. What is a Configurable offer ?

3. What is RECO ?

4. Compact description of configurable offers

4.1. Functional specification of price for a configurable offer

4.2. Configuration Rules and Promotion Rules

4.3. CPML - an XML schema for configurable products

5. Bid evaluation for configurable offers

5.1. Preference elicitation

5.2. Bid Evaluation

5.2.1. Single Sourcing

5.2.2. Multiple Sourcing

5.2.3. Treatment of logical configuration and discount rules

6. Appendix

7. References

1. What is an E-Procurement system ?

An E-Procurement system provides the automation of negotiations between buyers and sellers using reverse auction. It is a market place where there is one buyer and multiple sellers.

TOP

2. What is a Configurable offer ?

A Configurable offer is made by the seller in response to the RFQ provided by the buyer. Configurable offers allow multiple values for each attribute and they include rules on how to combine the various attribute values and how to price a desired configuration. A Configurable offer consists of collection of configurations where each configuration specifies a selection for each of the many attributes of the component. From a configurable offer, a user can extract offers for individual configurations.

Example :

Consider PCs. PC vendors describe their offerings along number of attributes on their Web site, and each of these attributes can take multiple values. This way, customers can configure and order a PC tailored to their individual needs. For example, suppose a PC has only three attributes, namely processor speed, hard disk size, operating system, and price. A supplier could specify that there are three processors available {850MHz, 950 MHz, and 1GHz}, as well as two sizes of hard disks {10GB and 15GB}. The base configuration (850MHz, 10GB) prices for $1000. A configuration with a 1GHz computer is $100 more, and one with a 15GB hard disk costs an additional $200. Of course, there can be many more rules, which need to be considered. For example, a certain operating system might require a minimal processor speed to function properly, and the supplier might specify a linear decreasing volume discount.

TOP

3. What is RECO ?

• RECO ( Representation and Evaluation of Configurable Offers) is a decision support system for the representation and evaluation of configurable offers.
• RECO provides a representation for configurable bids using propositional logic, and helps user to find top L configurations based on preferences.
• RECO provides the buyer or user to configure an optimal configuration for a single good (possibly for multiple units of same type)
• Since, RECO deals with E-procurement systems, there will be one buyer and multiple sellers .
• The buyer is the auctioneer. Bids are placed by the sellers.
• The auction type might be an open cry auction or closed-bid auction (no restriction)
• The bidding process is not iterative. It is a single round bidding

4. COMPACT DESCRIPTION OF CONFIGURABLE OFFERS

A simple approach to representing a configurable offer is to allow the specification of a set of attributes and a range of allowable values
for each attribute. Therefore any offer i with J attributes can be written as J-tuple where each element is a list of allowable values

where Vj is the set of allowable values for attribute j. This allows for a very large number of configurations based on the size of Vj. The two issues regarding representation are :

• representing the price for each allowable configuration, and
• representing configuration constraints and price promotions.

4.1. Functional specification of price for a configurable offer

This model forces the suppliers to provide a functional description of price as a function of the attributes. Assuming the additive price function where the impact of each attribute on price is additive, this model formalizes the mark up based pricing schemes where a price mark up is associated with each level of an attribute. The price mark-up for each attribute can be non linear as shown below. Assuming additivity of the attributes, the total price pi for a particular bid/offer i can be written as:

where qi is quantity, pbi(qi) is the base price per item as a function of quantity (i.e. specifies a volume discount), and fij(vij) is a functional specification for the impact of particular attribute values vij on the price of a product. The individual functions pbi(qi) and fji(vij) can in general be nonlinear. For any attribute j, the difference fji(vij,=vj,hi) ­ fji(vij = vj,base) represents the price markup for level hi with respect to the base level.

TOP

4.2. Configuration Rules and Promotion Rules

It is often essential for suppliers to express rules, which define constraints on the combination of attribute values, or discounts and mark ups based on some combination of attribute values. If we model each attribute level with a boolean variable that indicates whether this level is chosen for a particular configuration, then we can capture configuration constraints using propositional logic sentences. This is a compact representation for rules that are specified on discrete values rather than on ranges. Similarly, promotion pricing based on discrete levels rather than on ranges leads to compact representations using propositional logic sentences. This model deals with the constraints that can be specified using propositional logic. For instance, a configuration rule may include compatibility restrictions, saying attribute value x112 cannot be connected to attribute value x123, or requirements like attribute value x112 and x132 needs attribute value x123. Here, xijk is a binary indicator variable that takes a value of 1 if the level k of attribute j and offer i is chosen. In this section, configuration rules within an offer are considered and hence the subscript i can be omitted. For example, the proposition

describes the configuration rule that if a certain motherboard, x23 , then the buyer is restricted from using a certain type of CPU, x31. Logical implication (=>) allows, that if any other kind of motherboard is selected, the rules are of the implication variety where the antecedent are propositional sentences.  Another type of rules, which is often found in practice are so called discount rules. For example,

where xjk again describe particular attribute values and p- describes a certain discount (or markup) enforces a discount upon selection of these attribute values. The discount is only given, if and only if x12 ^ x31 is true. If x12 ^ x31 is false, then no discount will be granted. Therefore, the equivalence operator is used for discount rules.

TOP

4.3. CPML ­ an XML schema for configurable products

CPML, an XML schema is used to describe configurable products. The schema defines messages for a product request, for conventional multi-attribute offers, as well as configurable offers. CPML consists of following tags : An offer (TAG: ConfigurableOffer) is represented in a tree structure. A configurable offer defines either a single price for a base configuration and quantity, or a volume discount price (TAG: VolumeDiscountPrice), which is a function of quantity. The offer can have multiple attributes, which are either fixed attributes (TAG: FixedAttr), range attributes (TAG: RangeAttr), optional attributes (TAG: OptionalAttr), or discrete attributes (TAG: DiscreteAttr). Fixed attributes are described as simple attribute-value pairs, similar to the ones one can find in traditional catalogue standards. Range attributes allow the specification of a certain range of values and their impact on price.

In addition a configurable offer can specify so called add on rules (TAG: AddOnRules). Add on rules have the form of a logical equivalence or an implication with an antecedent and a conclusion. The antecedent can be any logical proposition including conjunctions, disjunctions, negations as well as atomic propositions. The conclusion defines in addition a Markup tag, which specifies a certain discount or markup. This way, suppliers can specify a certain discount as a result of the selected attribute values.

A configurable offer is one of a sequence of messages and a response to a particular request, which specifies a buyer's basic requirements. The tags defined in CPML can be used standalone or they can also be embedded to enrich existing catalogue standards.

TOP

5. BID EVALUATION FOR CONFIGURABLE OFFERS

The basic purpose of CPML is to communicate pricing rules about configurable offers in a compact way. This data can then be used to evaluate and compare offerings from various suppliers. The RECO bid evaluation methodology provides a suite of algorithms to evaluate and select the best (or top K) out of the multiple possible configurations of a configurable offer. It helps the user to score and compare the configurable offers of multiple suppliers. RECO operates directly on the rules and functional specifications of a configurable offer without the need to enumerate all possible configurations. This avoids the computationally expensive process of generating, transmitting and evaluating huge amounts of individual configurations by just communicating the rules for a single configurable offer. RECO consists of two consecutive steps, namely preference elicitation and bid evaluation which is based on integer programming techniques.

TOP

5.1. Preference elicitation

Consider I bids (or offers) and J attributes. Each attribute j of J has an attribute space of Kj. A multi-attribute offer, received by the buyer, can then be described as an n-dimensional vector vi. = (vi1 ... viJ) where vij is the level of attribute j. In the case of an additive scoring function S(vi) the buyer evaluates each relevant attribute vij through a scoring function Sj(vij). The overall value S(vi) for a bid vi is given by the sum of all individual scorings of the attributes. It is convenient to scale si and each of the single-attribute utility functions Sj(.) from zero to one. That is, for a bid vi and a scoring function that has weights w1 ... wJ, the overall utility for a bid is given by

The problem a buyer faces is to determine appropriate Sj(.) functions and wj weights. An optimal auction is allocating the deal to the suppliers in a way that maximizes the utility for the buyer, i.e. to the supplier providing the bid with the highest overall utility score for the buyer. The function max si with 1 <=i <= I gives us the utility score of the winning bid and can be determined through open-cry or sealed-bid auction schemes.Several techniques have been proposed in the traditional decision analysis literature to help users assign reasonable weights. One approach is called pricing out because it involves determining the value of one objective in terms of another (e.g. dollars). For example, one might say that 5 days faster delivery time is worth $400. The idea is to find the indifference point, i.e. determine the marginal rate of substitution between two attributes.

TOP

5.2. Bid Evaluation

There are two primary scenarios for bid evaluation:
• Single Sourcing: The buyer receives a configurable bid from one or more sellers and is interested in identify the top K configurations based on his/her preferences. The key assumption for this setting is that all the demand is sourced to a single supplier.
• Multiple Sourcing: In this setting the buyer is willing to split the demand across multiple suppliers. However, when buying multiattribute commodities from different suppliers one has to impose additional constraints over the choice. Two common constraints are :
1. constraints on the total number of winning suppliers, and
2. homogeneity constraints that restrict the choice across suppliers to have the same value for one or more attributes.
TOP
 

5.2.1. Single Sourcing

Here, a simplest setting is modeled where the buyer attempts to identify the top L configurations from a single configurable offer. This model subsequently becomes a kernel that is used in the multiple sourcing setting. Identifying the best configuration can be modeled as a variation of the multiple-choice knapsack problem. The subscript I for the binary decision variable xjk since only one offer is considered here.

The objective function mentioned above maximizes the weighted score. An additive, quasi-linear utility function with a linear (decreasing) scoring function on price, sp(pi) is assumed.

The above constraint specifies that for each attribute exactly one value must be selected.

The above constraint restricts the unit price to be smaller or equal to the buyer's unit reservation price C.

In the above, we determine the value of the continuous variable pi. This constraint could also be omitted, so that the price pi. needs to be determined outside the optimization based on the selected attribute values.

The above constraint specifies the restriction over the binary indicator variable for an attribute x.
This procedure allows suppliers considerably more flexibility in specifying offers, while at the same time, the bids can be ranked and suppliers can compete in an open-cry manner.

For getting the top L solutions, the following constraints are added.
Let us denote the Lth optimal solution by a set of indices NL that indicate the levels chosen for each attribute. For example for the optimal solution this set is N1 and we can eliminate the optimal solution from our search by adding the constraint where | N 1| is the cardinality of the set.
For 2nd best solution add the following constraint:

For 3rd best solution add the following constraint:

For the Lth best solution add the following constraint:

                       TOP

5.2.2. Multiple Sourcing

If the buyer is willing to source her demand (usually specified as an acceptable range [Dmin, Dmax]) from multiple suppliers then identifying the optimal set of configurations (and the appropriate suppliers) is solved as a two-step procedure. In the first step, the best possible configuration for each offer based on the buyer's scoring function using the equations In a second step, the resulting "best configurations" are in the form of conventional multi-attribute offers and can be allocated using a knapsack problem as shown below.

subject to the following constraints

The objective in this optimization is to maximize the overall score, where si is the unit score of the optimal configuration from bid i and qi is the quantity of bid i, so that the supplied quantity satisfies the lower and upper bound for the demand . The binary decision variables r i to indicate the bids selected by the buyer.

TOP

5.2.3 Treatment of logical configuration and discount rules

We use xjk to denote the logical as well as the binary variable in the MIP formulation. The first subscript i for bids is omitted. For the evaluation of a configurable offering, these additional rules have to be considered in the IP formulation. In order to obtain an equivalent mathematical representation for any propositional logic expression, one must first consider basic logical operators to determine how each can be transformed into an equivalent representation in the form of an equation or inequality. The following table describes some of the general transformations which can be used to convert general logical expressions into equivalent mathematical representation.

Nextly, for the binary indicator variable p- which indicates the discount ,the logical expressions in the following table describes the common forms of configuration and discount rules with only conjunctions or only disjunctions in the antecedent and one literal in the consequent.

                                    TOP

6. APPENDIX

7. REFERENCES

• Ahuja, R. K., Mananti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications.: Prentice Hall.
• Bichler, M., Lee, J., Lee, H. S., & Chung, J.-Y. (2001). ABSolute: An Intelligent Decision Making Framework for E-Sourcing. Paper presented at the 3rd International Workshop on Advanced Issues of E-Commerce and Web-Based Information Systems, San Jose, CA.
• Edwards, W. (1977). How to use multiattribute utility measurement for social decisionmaking. IEEE Transactions on Systems, Man, and Cybernetics SMC, 7(5), 326-340.
• Iwaihara, M. (2000). Supporting Dynamic Constraints for Commerce Negotiations. Paper presented at the Second International Workshop on Advanced Issues of E-Commerce and Web-Based Information Systems (WECWIS), Milpitas, CA.
• Iyengar, V. S., Lee, J., & Campbell, M. (2001). Q-Eval: Evaluating Multiple Attribute Items Using Queries (Research Report ). New York: IBM Research.
• Keeny, R. L., & Raiffa, H. (1993). Decision Making with Multiple Objectives: Preferences and Value Tradeoffs. Cambridge, UK: Cambridge University Press.
• Martello, S., & Toth, P. (1990). Knapsack Problems. Chichester, New York: John Wiley & Sons.
• Olson, D. L. (1995). Decision Aids for Selection Problems. New York, et al.: Springer.
• Raman, R., & Grossmann, I. E. (1991). Relation between MILP modelling and logical inference for process synthesis. Computers and chemical engineering, 15(2), 73-84.
• Reeves, D., Grosof, B., & Wellman, M. (2000). Automated Negotiations from Declarative Contract Descriptions. Paper presented at the AAAI-2000 Workshop on Knowledge-Based Electronic Markets, Austin, TX.
• Ribeiro, R. A. (1996). Fuzzy multiple attribut decision making: A review and new preference elicitation techniques. Fuzzy Sets and Systems, 78, 155-181.
• Russell, S. J., & Norvig, P. (1995). Artificial Intelligence - A Modern Approach. Upper Saddle River, New Jersey, USA: Prentice Hall.
• Saaty, T. L. (1980). The Analytic Hierarchy Process. New York, USA: McGraw Hill.

                    TOP