Examples of Complex Marketplaces: Customers, Models and Solution Methods

Monday, December 4, 2000 - 9:30am - 10:30am
Keller 3-180
We discuss three classes of complex marketplaces: direct procurement, indivisible supply/demand, and combinatorial bids with type constraints. For each, we describe the commerce environment, the mathematical models and the solution methods.

In weekly direct procurement, suppliers submit bundled bids for multiple commodities. The goal is to select a minimum ocst set of bids that meet all requirements while satisfying additional constraints such as a minimum number of suppliers for each commodity and maximum number os suppliers.

Certain commodities such as steel and paper need to be sourced from a single supplier; a bid for a 2 feet wide galvanized coil cannot be satisfied by two 1 foot wide coils. The introduction of such indivisability constraints makes the problem of finding the set of winning bids and asks NP-hard and can be modeled as a generalized assignment problem.

Based on a liability limiting constraint proposed by the FCC for its license auction, we formulate a more general type-based bidding system for combinatorial auctions, and discuss a column generation approach for solving such auctions.