# US 7,610,236 B2 · Method and apparatus for forming expressive combinatorial auctions and exchanges > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,610,236 B2 - Document ID: US7610236B2 - Status: Granted - Kind: B2 - Application number: 10/254,241 - Filed: 2002-09-25 - Published: 2003-10-16 - Granted: 2009-10-27 - Earliest claimed: 2002-04-10 - Assignees: CombineNet, Inc. - Inventors: Tuomas Sandholm; Subhash Suri; David L. Levine; Andrew G. Gilpin; John Heitmann; Robert Lawrence Shields, Jr. - Web page: https://patentgrep.com/patent/US7610236B2 ## CPC - G06Q 30/08: Auctions - G06Q 40/00: Finance; Insurance; Tax strategies; Processing of corporate or income taxes - G06Q 40/03: Credit; Loans; Processing thereof - G06Q 40/04: Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR ## Abstract A method of processing an exchange includes providing a solver/analyzer for determining a solution that includes at least one of a winning allocation and feasible allocations. At least one bid is received at the solver/analyzer, with each bid including at least one item and an associated price. Exchange description data (EDD) is associated with the at least one bid. The EDD is also received at the solver/analyzer. The processing of the at least one bid is modified in accordance with the at least one feature included in the EDD. ## Claims ### Claim 1 A computer-implemented method of conducting a combinatorial exchange comprising: (a) electronically storing in a computer storage a plurality of bids of a combinatorial exchange, wherein each bid includes at least one item and an associated bid price; (b) electronically associating exchange description data (EDD) stored in the computer storage with at least one of the following: a subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself, wherein the EDD stored in the computer storage comprises a representation of at least one of the following features: a non-price attribute of a bid; a non-price attribute of an item; an item adjustment; a bid adjustment; a cost constraint; a unit constraint; a cost requirement; a unit requirement; a counting constraint; a counting requirement; a homogeneity constraint; a mixture constraint; cost conditional pricing; or unit conditional pricing; (c) a model builder electronically constructing a model of (1) the bids received in step (a) and (2) the EDD electronically associated in step (b) with at least one of the following: the subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself; (d) a solver/analyzer electronically processing the model constructed in step (c) to determine for the combinatorial exchange an infeasible allocation, a winning allocation or a feasible allocation of received bids and a value for said allocation; and (e) electronically outputting the allocation and the value determined in step (d). ### Claim 2 (depends on 1) The method as set forth in claim 1, wherein: the non-price attribute of a bid is one of credit history, shipping cost, bidder credit worthiness, bidder business location, bidder business size, bidder zip code, bidder reliability, bidder reputation, bidder timeliness, freight terms and conditions, insurance terms and conditions, bidder distance and bidder flexibility; and the non-price attribute of an item is one of size, color, weight, delivery date, width, height, purity, concentration, pH, brand, hue, intensity, saturation, shade, reflectance, origin, destination, volume, earliest pickup time, latest pickup time, earliest dropoff time, latest dropoff time, production facility, packaging and flexibility. ### Claim 3 (depends on 1) The method as set forth in claim 1, wherein: the item adjustment includes a condition and a value that is utilized to modify the bid price of the associated bid when the condition is satisfied, wherein the item adjustment is based on an item attribute of at least one item of the associated bid; and the bid adjustment includes a condition and a value that is utilized to modify the bid price of the associated bid when the condition is satisfied, wherein the bid adjustment is based on a bid attribute of the at least one bid. ### Claim 4 (depends on 3) The method as set forth in claim 3, wherein: the item attribute is one of the following: size, color, weight, delivery date, width, height, purity, concentration, pH, brand, hue, intensity, saturation, shade, reflectance, origin, destination, volume, earliest pickup time, latest pickup time, earliest dropoff time, latest dropoff time, production facility, packaging and flexibility; and the bid attribute is one of the following: a size of one or more items of the bid, a color of one or more items of the bid, a weight of one or more items of the bid, delivery date, bidder credit history, shipping costs, bidder credit worthiness, freight terms and conditions, insurance terms and conditions, bidder distance and bidder flexibility. ### Claim 5 (depends on 1) The method as set forth in claim 1, wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following objectives: a surplus, a traded ask volume, a traded bid volume, a traded average volume, a number of winning bidders, or a number of losing bidders. ### Claim 6 (depends on 1) The method as set forth in claim 1, wherein: the cost constraint causes an amount of an exchange value that is allocated to a bid group to be limited to no more than a predetermined percent or cost of the exchange value, where the bid group includes at least one bid; the unit constraint causes a quantity of an item that is awarded to a bid group to be limited to no more than a predetermined maximum quantity or percentage, where the bid group includes at least one bid; the cost requirement causes a bid group to be allocated at least a predetermined percent or cost of an allocation value, or nothing, where the bid group includes at least one bid; the unit requirement causes a bid group to be allocated at least a predetermined quantity or percentage of an allocation, or nothing, where the bid group includes at least one bid; the counting constraint causes an allocation to be generated that includes a number of winning bid groups within a specified range, where each bid group includes at least one bid; the counting requirement causes an allocation to be generated that includes at least one of the following: no winning bid groups or a number of winning bid groups within a specified range, where each bid group includes at least one bid; the homogeneity constraint causes an allocation to be generated that includes a uniformity of items or bids as a function of an item attribute description associated with the items or bids; and the mixture constraint causes an allocation to be generated that includes a specified average limit of an item or bid attribute of a bid group. ### Claim 7 (depends on 1) The method as set forth in claim 1, wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation of a constraint relaxer that causes at least one soft constraint placed on an exchange to be relaxed. ### Claim 8 (depends on 7) The method as set forth in claim 7, wherein the exchange includes at least one hard constraint that the solver/analyzer cannot relax. ### Claim 9 (depends on 7) The method as set forth in claim 7, wherein a value is associated with the relaxation of the at least one relaxed soft constraint. ### Claim 10 (depends on 9) The method as set forth in claim 9, wherein the value is aggregated across at least two relaxed soft constraints. ### Claim 11 (depends on 10) The method as set forth in claim 10, wherein the aggregate constraint relaxation value is a function of how much each soft constraint is relaxed. ### Claim 12 (depends on 11) The method as set forth in claim 11, wherein: each soft constraint is assigned a weight; the aggregate constraint relaxation value is a sum of the relaxation values of the relaxed soft constraints; and the relaxation value of each relaxed soft constraint is one of the following: (i) a weight associated with the constraint, (ii) the weight of the constraint multiplied by a percentage amount that said constraint is relaxed, or (iii) the weight of the constraint multiplied by the absolute amount that said constraint is relaxed. ### Claim 13 (depends on 10) The method as set forth in claim 10, wherein the allocation (i) satisfies each hard constraint of the exchange that the solver/analyzer cannot relax and (ii) maximizes or minimizes a value of the exchange minus or plus, respectively, the aggregate constraint relaxation value. ### Claim 14 (depends on 10) The method as set forth in claim 10, wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation of a feasibility obtainer that causes an allocation to be output that (i) satisfies each hard constraint of the exchange that the solver/analyzer cannot relax and (ii) minimizes the aggregate constraint relaxation value. ### Claim 15 (depends on 1) The method as set forth in claim 1, wherein: the cost conditional pricing causes a value of an allocation to be modified based on a difference between (i) a total currency volume awarded to a first bid group, or a total currency volume awarded to a subset of the items of the first bid group and (ii) a total currency volume awarded to a second bid group, or a total currency volume awarded to a subset of the items of the second bid group, wherein the first bid group includes at least one bid; and the unit conditional pricing causes a value of an allocation to be modified based on a difference between (i) a unit volume awarded to a first bid group, or a unit volume awarded to a subset of the items of the first bid group and (ii) a unit volume awarded to a second bid group, or a unit volume awarded to a subset of the items of the second bid group, wherein the first bid group includes at least one bid. ### Claim 16 (depends on 1) The method as set forth in claim 1, wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation, for each item, of whether there is free disposal of the item, wherein free disposal of the item enables the solver/analyzer to either (i) allocate less than an offered quantity of the item for sale without affecting the price of the bid that includes the item or (ii) allocate more than an offered quantity of the item for purchase without affecting the price of the bid that includes the item. ### Claim 17 (depends on 1) The method as set forth in claim 1, further comprising at least one of the steps of: (i) modifying at least one feature of the EDD associated with the at least one bid and processing the at least one bid in accordance with said modified feature; (ii) including another feature with the EDD associated with the at least one bid and processing the at least one bid in accordance with said other feature; and (iii) associating with the bid another EDD that includes another feature and processing the at least one bid in accordance with said other feature. ### Claim 18 (depends on 1) The method as set forth in claim 1, further comprising terminating processing of the model in step (d) in response to at least one of the following: (i) elapse of predetermined time interval, (ii) a current best solution being within a predetermined numerical distance of an optimal solution, or (iii) a manual abort command. ### Claim 19 (depends on 1) The method as set forth in claim 1, wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation of a quote request that causes, for a bid associated with the quote request, a price to be determined that would result in the bid being included in an allocation. ### Claim 20 (depends on 1) The method of claim 1, wherein the representation of step (b) is a computer language. ### Claim 21 (depends on 20) The method of claim 20, wherein the computer language is XML. ### Claim 22 (depends on 1) The method as set forth in claim 1, wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation, for each item, of the free disposal quantity of the item, wherein free disposal of the item enables the solver/analyzer to either (i) allocate as little as an offered quantity of the item for sale, minus the free disposal quantity, without affecting the price of the bid that includes the item or (ii) allocate as much as an offered quantity of the item for purchase, plus the free disposal quantity, without affecting the price of the bid that includes the item. ### Claim 23 A computer readable medium having stored thereon instructions which, when executed by a processor, cause the processor to perform the steps of: (a) electronically store a plurality of bids of a combinatorial exchange in a computer storage, with each bid including at least one item and an associated bid price; (b) cause exchange description data (EDD) stored in the computer storage to be electronically associated with at least one of the following: a subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself, wherein the EDD stored in the computer storage comprises a representation of at least one of the following features: a non-price attribute of a bid; a non-price attribute of an item; an item adjustment; a bid adjustment; a cost constraint; a unit constraint; a cost requirement; a unit requirement; a counting constraint; a counting requirement; a homogeneity constraint; a mixture constraint; cost conditional pricing; or unit conditional pricing; (c) cause a model builder to electronically build a model of the received plurality of bids and the EDD associated with each bid of the subset of the plurality of bids; (d) cause a solver/analyzer to electronically process said model to determine an infeasible allocation, a winning allocation or a feasible allocation and an allocation value for said exchange; and (e) electronically output the allocation determined in step (d). ### Claim 24 A computer-implemented method of conducting a combinatorial exchange comprising: (a) electronically storing in a computer storage a plurality of bids of a combinatorial exchange, wherein each bid includes at least one item and an associated bid price; (b) electronically associating exchange description data (EDD) stored in the computer storage with at least one of the following: a subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself, wherein the EDD stored in the computer storage comprises a representation of at least one of the following features: a non-price attribute of an item, an item adjustment, a cost requirement, a unit requirement, a counting requirement, a mixture constraint, a homogeneity constraint, cost conditional pricing, or unit conditional pricing; (c) a model builder electronically constructing a model of (1) the bids received in step (a) and (2) the EDD electronically associated in step (b) with: the subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself; (d) a solver/analyzer electronically processing the model constructed in step (c) to determine for the combinatorial exchange an infeasible allocation, a winning allocation or a feasible allocation of received bids and a value for said allocation, subject to the EDD electronically associated in step (b); and (e) electronically outputting the allocation and the value determined in step (d). ### Claim 25 (depends on 24) The method of claim 24, wherein the non-price attribute of an item includes one of the following: size, color, weight, delivery date, width, height, purity, concentration, pH, brand, hue, intensity, saturation, shade, reflectance, origin, destination, volume, earliest pickup time, latest pickup time, earliest dropoff time, latest dropoff time, production facility, packaging, and flexibility. ### Claim 26 (depends on 24) The method of claim 24, wherein: the item adjustment includes a condition and a value that is utilized to modify the bid price of an associated bid when the condition is satisfied; and the condition is based on a non-price attribute on an item of the associated bid. ### Claim 27 (depends on 24) The method of claim 24, wherein the cost requirement causes a bid group that includes at least one bid to be allocated either a predetermined percent of an allocation value, a predetermined cost of the allocation value, or nothing. ### Claim 28 (depends on 24) The method of claim 24, wherein the unit requirement causes a bid group that includes at least one bid to be allocated either a predetermined quantity of an allocation, a predetermined percentage of an allocation, or nothing. ### Claim 29 (depends on 24) The method of claim 24, wherein the counting requirement causes an allocation to be generated that includes either no winning bid groups or a number of winning bid groups within a specified range, wherein each bid group includes at least one bid. ### Claim 30 (depends on 24) The method of claim 24, wherein the mixture constraint causes an allocation to be generated that includes a specified average limit of either an item attribute of a bid group or a bid attribute of a bid group. ### Claim 31 (depends on 24) The method of claim 24, wherein the homogeneity constraint causes an allocation to be generated that includes a uniformity of items or bids based on a non-price attribute of the items or bids, respectively. ### Claim 32 (depends on 24) The method of claim 24, wherein the cost conditional pricing causes a value of an allocation to be modified based on a difference between the total awarded currency volume of a first bid group and the total awarded currency volume of a second bid group, where the first bid group includes at least one bid. ### Claim 33 (depends on 24) The method of claim 24, wherein the unit conditional pricing causes a value of an allocation to be modified based on a difference between an awarded unit volume of a first bid group and an awarded unit volume of a second bid group, where the first bid group includes at least one bid. ### Claim 34 (depends on 24) The method of claim 24, wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation, for each item, of whether there is free disposal of the item, wherein free disposal of the item enables the solver/analyzer to either (i) allocate less than an offered quantity of the item for sale without affecting the price of the bid that includes the item or (ii) allocate more than an offered quantity of the item for purchase without affecting the price of the bid that includes the item. ### Claim 35 (depends on 24) The method of claim 24, wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following non-price attributes on a bid: credit history, shipping cost, bidder credit worthiness, bidder business location, bidder business size, bidder zip code, bidder reliability, bidder reputation, bidder timeliness, freight terms and conditions, insurance terms and conditions, bidder distance and bidder flexibility. ### Claim 36 (depends on 24) The method of claim 24, wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of a bid adjustment that includes a condition and a value that is utilized to modify the bid price of the associated bid when the condition is satisfied. ### Claim 37 (depends on 24) The method of claim 24, wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following constraints: a cost constraint that causes an amount of an exchange value that is allocated to a bid group to be limited to no more than a predetermined percent or cost of the exchange value, where the bid group includes at least one bid; a unit constraint that causes a quantity of an item that is awarded to a bid group to be limited to no more than a predetermined maximum quantity or percentage, where the bid group includes at least one bid; or a counting constraint that causes an allocation to be generated that includes a number of winning bid groups within a specified range, where each bid group includes at least one bid. ### Claim 38 (depends on 24) The method of claim 24, wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following: a feasibility obtainer that causes an allocation to be output that (i) satisfies each hard constraint of the exchange that the solver/analyzer cannot relax and (ii) minimizes a value associated with said relaxation; a constraint relaxer that causes at least one constraint placed on an exchange to be relaxed and to determine a value associated with said relaxation, or a quote request that causes, for a bid associated with the quote request, a price to be determined that would result in the bid being included in an allocation. ### Claim 39 (depends on 24) The method of claim 24, wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following objectives: a surplus, a traded ask volume, a traded bid volume, a traded average volume, a number of winning bidders, or a number of losing bidders. ### Claim 40 (depends on 24) The method of claim 24, further comprising at least one of the steps of: (i) modifying at least one feature of the EDD associated with the at least one bid and processing the at least one bid in accordance with said modified feature; (ii) including another feature with the EDD associated with the at least one bid and processing the at least one bid in accordance with said other feature; and (iii) associating with the bid another EDD that includes another feature and processing the at least one bid in accordance with said other feature. ### Claim 41 (depends on 24) The method of claim 24, further comprising terminating processing of the model in step (d) in response to at least one of the following: (i) elapse of predetermined time interval, (ii) a current best solution being within a predetermined numerical distance of an optimal solution, or (iii) a manual abort command. ### Claim 42 (depends on 24) The method of claim 24, wherein the representation of step (b) is a computer language. ### Claim 43 A computer-implemented method of conducting a combinatorial exchange comprising: (a) electronically storing in a computer storage a plurality of bids of a combinatorial exchange, wherein each bid includes at least one item and an associated bid price; (b) electronically associating exchange description data (EDD) stored in the computer storage with at least one of the following: a subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself, wherein the EDD stored in the computer storage comprises a representation of at least one of the following features: an item adjustment, a cost requirement, a unit requirement, a counting requirement, cost conditional pricing, or unit conditional pricing; (c) a model builder electronically constructing a model of (1) the bids received in step (a) and (2) the EDD electronically associated in step (b) with: the subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself; (d) a solver/analyzer electronically processing the model constructed in step (c) to determine for the combinatorial exchange an infeasible allocation, a winning allocation or a feasible allocation of received bids and a value for said allocation, subject to the EDD electronically associated in step (b); and (e) electronically outputting the allocation and the value determined in step (d). ### Claim 44 (depends on 43) The method of claim 43, wherein: the item adjustment includes a condition and a value that is utilized to modify the bid price of an associated bid when the condition is satisfied; and the condition is based on a non-price attribute on an item of the associated bid. ### Claim 45 (depends on 43) The method of claim 43, wherein: the cost requirement causes a bid group that includes at least one bid to be allocated either a predetermined percent of an allocation value, a predetermined cost of the allocation value, or nothing; the unit requirement causes a bid group that includes at least one bid to be allocated either a predetermined quantity of an allocation, a predetermined percentage of an allocation, or nothing; and the counting requirement causes an allocation to be generated that includes either no winning bid groups or a number of winning bid groups within a specified range, wherein each bid group includes at least one bid. ### Claim 46 (depends on 43) The method of claim 43, wherein: the cost conditional pricing causes a value of an allocation to be modified based on a difference between (i) a total currency volume awarded to a first bid group, or a total currency volume awarded to a subset of the items of the first bid group and (ii) a total currency volume awarded to a second bid group, or a total currency volume awarded to a subset of the items of the second bid group, wherein the first bid group includes at least one bid; and the unit conditional pricing causes a value of an allocation to be modified based on a difference between (i) a unit volume awarded to a first bid group, or a unit volume awarded to a subset of the items of the first bid group and (ii) a unit volume awarded to a second bid group, or a unit volume awarded to a subset of the items of the second bid group, wherein the first bid group includes at least one bid. ### Claim 47 (depends on 43) The method of claim 43, wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following features: free disposal, a non-price attribute on a bid, a non-price attribute on an item, a bid adjustment, an objective, a cost constraint, a unit constraint, a counting constraint, a homogeneity constraint, a mixture constraint, a feasibility obtainer, a constraint relaxer, and a quote request. ### Claim 48 (depends on 43) The method of claim 43, wherein the representation of step (b) is a computer language. ### Claim 49 A computer-implemented method of conducting a combinatorial exchange comprising: (a) electronically storing in a computer storage a plurality of bids of a combinatorial exchange, wherein each bid includes at least one item and an associated bid price; (b) electronically associating exchange description data (EDD) stored in the computer storage with at least one of the following: a subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself, wherein the EDD stored in the computer storage comprises a representation of at least one of the following features: an item adjustment, a cost requirement, a counting requirement, or cost conditional pricing; (c) a model builder electronically constructing a model of (1) the bids received in step (a) and (2) the EDD electronically associated in step (b) with: the subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself; (d) a solver/analyzer electronically processing the model constructed in step (c) to determine for the combinatorial exchange an infeasible allocation, a winning allocation or a feasible allocation of received bids and a value for said allocation, subject to the EDD electronically associated in step (b); and (e) electronically outputting the allocation and the value determined in step (d). ### Claim 50 (depends on 49) The method of claim 49, wherein: the item adjustment includes a condition and a value that is utilized to modify the bid price of an associated bid when the condition is satisfied; and the condition is based on a non-price attribute on an item of the associated bid. ### Claim 51 (depends on 49) The method of claim 49, wherein: the cost requirement causes a bid group that includes at least one bid to be allocated either a predetermined percent of an allocation value, a predetermined cost of the allocation value, or nothing; and the counting requirement causes an allocation to be generated that includes either no winning bid groups or a number of winning bid groups within a specified range, wherein each bid group includes at least one bid. ### Claim 52 (depends on 49) The method of claim 49, wherein the cost conditional pricing causes a value of an allocation to be modified based on a difference between the total awarded currency volume of a first bid group and the total awarded currency volume of a second bid group, where the first bid group includes at least one bid. ### Claim 53 (depends on 49) The method of claim 49, wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following features: free disposal, a non-price attribute on a bid, a non-price attribute on an item, a bid adjustment, an objective, a cost constraint, a unit constraint, a counting constraint, a homogeneity constraint, unit conditional pricing, a mixture constraint, a feasibility obtainer, a constraint relaxer, and a quote request. ### Claim 54 (depends on 49) The method of claim 49, wherein the representation of step (b) is a computer language.