We study the Online Advertising Portfolio Optimization Problem (OAPOP) faced by an advertiser in online advertising auctions. An online advertiser manages portfolios of targeting items (keywords, cookies, websites, etc.) across various advertising platforms and formats. The OAPOP allows the advertiser to consolidate campaigns across advertising platforms and formats into a single portfolio and operate under the constraint of an overall advertising budget. Therefore, the number of targeting items in the portfolio may be in the order of tens of millions for large enterprises. The advertiser wishes to determine how much to bid on each targeting item to maximize the return given a specified advertising budget. Using past performance reports, browsing data, and forecasts, the advertiser can estimate expected cost and expected revenue for a targeting item for various bid amounts. The OAPOP can be modeled as the Multiple Choice Knapsack Problem (MCKP) with an overall expected revenue maximization objective where for each targeting item multiple bid amounts corresponding to estimated expected cost and revenue. We discuss structural properties of the MCKP and propose an efficient column generation algorithm for the linear programming relaxation of the problem. We perform computational experiments on online advertising instances generated based on online advertising data collected from Google Adwords Keyword Planner. We demonstrate the column generation algorithm significantly outperforms the state-of-the-art linear time algorithm in online advertising instances.