  In recent years, RTB(Real Time Bidding) becomes a popular online
advertisement trading method. During the auction, each DSP(Demand Side
Platform) is supposed to evaluate current opportunity and respond with an ad
and corresponding bid price. It's essential for DSP to find an optimal ad
selection and bid price determination strategy which maximizes revenue or
performance under budget and ROI(Return On Investment) constraints in P4P(Pay
For Performance) or P4U(Pay For Usage) mode. We solve this problem by 1)
formalizing the DSP problem as a constrained optimization problem, 2) proposing
the augmented MMKP(Multi-choice Multi-dimensional Knapsack Problem) with
general solution, 3) and demonstrating the DSP problem is a special case of the
augmented MMKP and deriving specialized strategy. Our strategy is verified
through simulation and outperforms state-of-the-art strategies in real
application. To the best of our knowledge, our solution is the first dual based
DSP bidding framework that is derived from strict second price auction
assumption and generally applicable to the multiple ads scenario with various
objectives and constraints.
