Discount Auctions for Procuring Hetergeneous Items
Identifieur interne : 005A17 ( Main/Merge ); précédent : 005A16; suivant : 005A18Discount Auctions for Procuring Hetergeneous Items
Auteurs : Kameshwaran Sampath [Inde] ; Lyès Benyoucef [France] ; Xiaolan Xie [France]Source :
English descriptors
- mix :
Abstract
Advents 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 a 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 NP-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.
Url:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 001C70
- to stream Hal, to step Curation: 001C70
- to stream Hal, to step Checkpoint: 004381
Links to Exploration step
Hal:inria-00122327Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Discount Auctions for Procuring Hetergeneous Items</title><author><name sortKey="Sampath, Kameshwaran" sort="Sampath, Kameshwaran" uniqKey="Sampath K" first="Kameshwaran" last="Sampath">Kameshwaran Sampath</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-26430" status="INCOMING"><orgName>Center for Global Logistics & Mfg Strategies</orgName><desc><address><country key="IN"></country></address></desc><listRelation><relation active="#struct-365491" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-365491" type="direct"><org type="institution" xml:id="struct-365491" status="INCOMING"><orgName>Indian School of Business</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Inde</country></affiliation></author><author><name sortKey="Benyoucef, Lyes" sort="Benyoucef, Lyes" uniqKey="Benyoucef L" first="Lyès" last="Benyoucef">Lyès Benyoucef</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2353" status="OLD"><idno type="RNSR">199921393M</idno><orgName>Industrial system modeling, analysis and operation</orgName><orgName type="acronym">MACSI</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/macsi</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Xie, Xiaolan" sort="Xie, Xiaolan" uniqKey="Xie X" first="Xiaolan" last="Xie">Xiaolan Xie</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-26431" status="INCOMING"><orgName>Healthcare Systems Operation Department</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-29212" type="direct"></relation><relation active="#struct-302102" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-29212" type="direct"><org type="laboratory" xml:id="struct-29212" status="VALID"><orgName>École des Mines de Saint-Étienne</orgName><orgName type="acronym">Mines Saint-Étienne MSE</orgName><desc><address><addrLine>158, Cours Fauriel - 42023 Saint Étienne cedex 2</addrLine><country key="FR"></country></address><ref type="url">http://www.mines-stetienne.fr/</ref></desc><listRelation><relation active="#struct-302102" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-302102" type="indirect"><org type="institution" xml:id="struct-302102" status="VALID"><orgName>Institut Mines-Télécom</orgName><desc><address><addrLine>46 rue Barrault -75634 Paris Cedex 13</addrLine><country key="FR"></country></address><ref type="url">http://www.mines-telecom.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00122327</idno><idno type="halId">inria-00122327</idno><idno type="halUri">https://hal.inria.fr/inria-00122327</idno><idno type="url">https://hal.inria.fr/inria-00122327</idno><date when="2006">2006</date><idno type="wicri:Area/Hal/Corpus">001C70</idno><idno type="wicri:Area/Hal/Curation">001C70</idno><idno type="wicri:Area/Hal/Checkpoint">004381</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">004381</idno><idno type="wicri:Area/Main/Merge">005A17</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Discount Auctions for Procuring Hetergeneous Items</title><author><name sortKey="Sampath, Kameshwaran" sort="Sampath, Kameshwaran" uniqKey="Sampath K" first="Kameshwaran" last="Sampath">Kameshwaran Sampath</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-26430" status="INCOMING"><orgName>Center for Global Logistics & Mfg Strategies</orgName><desc><address><country key="IN"></country></address></desc><listRelation><relation active="#struct-365491" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-365491" type="direct"><org type="institution" xml:id="struct-365491" status="INCOMING"><orgName>Indian School of Business</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Inde</country></affiliation></author><author><name sortKey="Benyoucef, Lyes" sort="Benyoucef, Lyes" uniqKey="Benyoucef L" first="Lyès" last="Benyoucef">Lyès Benyoucef</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2353" status="OLD"><idno type="RNSR">199921393M</idno><orgName>Industrial system modeling, analysis and operation</orgName><orgName type="acronym">MACSI</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/macsi</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Xie, Xiaolan" sort="Xie, Xiaolan" uniqKey="Xie X" first="Xiaolan" last="Xie">Xiaolan Xie</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-26431" status="INCOMING"><orgName>Healthcare Systems Operation Department</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-29212" type="direct"></relation><relation active="#struct-302102" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-29212" type="direct"><org type="laboratory" xml:id="struct-29212" status="VALID"><orgName>École des Mines de Saint-Étienne</orgName><orgName type="acronym">Mines Saint-Étienne MSE</orgName><desc><address><addrLine>158, Cours Fauriel - 42023 Saint Étienne cedex 2</addrLine><country key="FR"></country></address><ref type="url">http://www.mines-stetienne.fr/</ref></desc><listRelation><relation active="#struct-302102" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-302102" type="indirect"><org type="institution" xml:id="struct-302102" status="VALID"><orgName>Institut Mines-Télécom</orgName><desc><address><addrLine>46 rue Barrault -75634 Paris Cedex 13</addrLine><country key="FR"></country></address><ref type="url">http://www.mines-telecom.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>auctions</term><term>branch-and-bound</term><term>duality</term><term>e-procurement</term><term>integer programming</term><term>linear programming relaxation</term><term>transportation problem</term><term>valid inequalities</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Advents 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 a 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 NP-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.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 005A17 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 005A17 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= Hal:inria-00122327
|texte= Discount Auctions for Procuring Hetergeneous Items
}}
| This area was generated with Dilib version V0.6.33. |  |