Mathematical Programming and Combinatorial Optimization


MS&E212/112/CME 208; Spring 2005-06

Instructor: Ashish Goel

Handout 5: Project Descriptions

Given: 4/27/2006. Groups due: 5/3/2006.


You are also allowed to (and encouraged to) develop project proposals of your own. We would like to enforce group sizes of 4 as far as possible, but will allow groups of size 3 if absolutely necessary. If you need help forming groups, please consult with Brad Null at least a day or two before the deadline. We will make additional information (such as the constraints for the sports league project, more details of the travel engine project) available soon to the groups who choose those projects. Please send us your groups and a first and a second choice project by May 3rd.


Suggested projects:


Sports League Scheduling

Capacity: 2 groups

Description: In this project we ask the groups to develop a "good" schedule for the 2006-07 NBA season. The groups will be given a number of real world constraints and will be asked to derive one or more additional realistic constraints as well as a reasonable objective function on their own. The subsequent task will be to develop an algorithm that can be applied to these constraints and objective to produce a schedule. Be careful though, developing a "good" (much less "optimal") sports schedule is not a trivial problem and will likely require the groups to devise some heuristic extensions beyond the algorithms developed in this class.


Travel Engine Optimization

            Capacity: 2 groups

Finding optimum travel routing given the diverse sources of information on the web is a hard problem. This project involves developing and implementing an algorithm that can take in multiple criteria (pricing, flight length, start and stop times, etc.) and determine the k-best travel itineraries for a user.  You will be expected to supply running, functioning code that can be applied to a data format that will be provided. In addition, certain design details (such as the definition of "best" and the determination of k) will be left up to the group.


Universal Portfolio Optimization

            Capacity: 2 groups

Read the paper “Efficient Algorithms for Online Game Playing and Universal Portfolio Management” by Agarwal and Hazan (and the papers by Cover referenced threrein for background). Then implement the universal portfolio optimization techniques of Agarwal and Hazan. Finally, compare the performance of your algorithm on the stocks included in the S&P 500 (or the Nasdaq 100) to the respective index over a five year period.


Keyword Pricing

            Capacity: 2 groups

Description: You are given a set of merchants who want to buy ad space on a search engine for a set of keywords. Merchant k has utility U(k,j) (which is known only to him) per user-click on an advertisement that appear when a user searches for keyword j. If the merchant is at position i on the list of ads displayed for keyword j, his ad will get Q(j,k)P(i) total clicks over the course of a day. The merchant has a budget B(k).The position of a merchant’s ad for a specific keyword is determined by the outcome of an online auction. Develop reasonable models for the distributions of U, B, P, and Q and try to compute equilibrium bidding strategies for a set of merchants. Requires either some minimal prior knowledge of game theory or some willingness to read up the first two chapters of a game theory text, as well as the willingness to read a couple of relevant papers by faculty in MS&E.


In addition, a student has submitted the following project. You can contact Brad if you would like to work on this project and we will put you in touch with the student.


Predicting depth from images.

I had proposed a algorithm that can predict depth from single still

images for 3-d reconstruction. To learn parameters, and predict depth

is a optimization problem. I would like to explore if depth prediction

accuracy improves with stereo images, and/or explore different

optimization for learning and prediction.