Bid Optimization for Internet Graphical Ad Auction Systems via Special Ordered Sets

Ralphe Wiggins, John A. Tomlin

.

DOI: 10.4236/ib.2010.23032                

Abstract

This paper describes an optimization model for setting bid levels for certain types of advertisements on web pages. This model is non-convex, but we are able to obtain optimal or near-optimal solutions rapidly using branch and cut open- source software. The financial benefits obtained using the prototype system have been substantial.

Keywords

Optimization, Advertising, Electronic Business

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	B. Edelman, M. Ostrovsky and M. Schwarz, “Internet Advertising and the Generalizaed Second Price Auction: Selling Billions of Dollars Worth of Keywords,” 2nd Workshop on Sponsored Search Auctions, Ann Arbor, June 2006.
[2]	E. M. L. Beale and J. A. Tomlin, “Special Facilities in a General Mathematical Programming System for Non- Convex Problems Using Ordered Sets of Variables,” In: J. Lawrence, Ed., Proceedings 5th IFORS Conference, Tavistock, London & Wiley, New York, 1970, pp. 447-454.
[3]	S. Bollapragada, H. Chen, M. Phillips and M. Garbiras, M. Scholes, T. Gibbs and M. Humphreville, “ ’s Optimization Systems Increase Revenues and Productivity,” Interfaces, Vol. 32, No. 1, 2002, pp. 47-60.
[4]	Z. Abrams, O. Mendelevitch and J. A. Tomlin, “Optimal Delivery of Sponsored Search Advertisements Subject to Budget Constraints,” Proceedings of ACM EC’07, San Diego, June 2007.
[5]	N. Abe, “Improvements to the Linear Programming Based Scheduling of Web Advertisements,” Journal of Electronic Commerce Research, Vol. 5, No. 1, 2005, pp. 75-98.
[6]	R. Lougee-Heimer, F. Barahona, B. L. Dietrich, J. P. Fasano, J. J. Forrest, R. Harder, L. Ladanyi, T. Pfender, T. Ralphs, M. Saltzman and K. Scheinberg, “The Initiative: Accelerating Operations Research Progress through Open-Source Software,” ORMS Today, Vol. 28, No. 5, 2001, pp. 48-49.
[7]	COIN-OR Foundation. http://www.coin.or.org
[8]	J. Forrest and J. Tomlin, “Branch and Bound, Integer, and Non-Integer Programming,” Annals of Operations Research, Vol. 149, No. 1, 2007, pp. 81-87.