SBIR Phase I: Advertising Sales and Traffic Optimization: Difficult Customer-Requested Optimization Constraints and Scalability on Real Data

This SBIR Phase I project proposes to develop a new optimization engine that supports important allocation constraints requested by potential customers, and make it scalable using novel techniques and real customer data. Determining who buys what items from whom under rich expressiveness is a provably hard optimization problem that requires sophisticated algorithms. The PI?' academic group has developed technology for novel tree search / integer programming as well as automated problem (re)formulation, and they have adapted it to address the advertising market's needs. Proposed work includes developing new optimization techniques. The broader/commercial impact involves a significant efficiency improvement - i.e., improvement in the allocation that benefits both buyers and sellers - in a huge industry. The US TV ad market is $75 billion annually. Experiences from deploying approaches similar to that proposed here into other markets suggest 12% - 41% efficiency improvements. The efficiency gains will significantly enhance US competitiveness. The structured, optimized market begets a fairer playing field and broader access - also for new entrants. Consumers also benefit because they will see more relevant ads rather than having their time and attention taken by irrelevant ones. The on-ramp to the advertising market is a single-seller, multi-buyer setting. Later the footprint can be generalized to expressive exchanges. The approach and technology also apply to other markets such as those for electricity and pollution rights. The proposed optimization technology applies to applications beyond markets also. The company has a plan for disseminating the results broadly via academic outlets, courses, industrial contacts, and government contacts. They will also plan to engage minorities and undergraduates. The effort describes a symbiotic relationship between an innovation ecosystem and the proposed project.