Practical Combinatorial Optimization software

An investment example
This example is not really what SizeFitter was intended for, but it demonstrates the possibilities of small scale combinatorial solutions. Suppose we have $1 million to invest in various business ventures within a media group. The ventures each have an estimated rate of likely return on investment, but it is important to stay within budget. How can we cast this into a problem for SizeFitter?

Venture	Capital	Return
Comp game	$119716	28%
Video	$189761	22%
DVD	$214751	19%
CD	$233836	26%
Book	$249381	14%
Film	$262712	19%
Magazine	$271431	27%
Newspaper	$281123	18%

First we must cast the capital numbers into the numerical range for SizeFitter. Since the valid range is between 1 and 10000, we divide the numbers by 1000. As the investments are either on or off, all the bounds are set to 1. The potential value of each venture is calculated from the percentages. Click on maximize from below since the highest value is sought subject to staying within budget. This is the result:

SizeFitter has selected the four ventures: Video, CD, magazine and newspaper. A grand total of $976151 invested with a likely return of $226432.

Notice that the most profitable venture, the computer game, was not selected. If we had "cherry picked" the best ventures and stopped just before exceeding the budget of $1 mill, then we would have ended up with the computer game, video, CD and magazine ventures. But in that case only $814744 would have been invested with a likely return of only $209350. All of the remaining four ventures would each require over $200000, hence none of those fit into the budget after the cherry picking. It follows that the cherry picking is not necessarily the best strategy.

To be strictly fair, the money not invested could attract bank interest, say 5%. The difference in invested capital is $976151-$814744 = $161407, which is not a negligible amount. However, since this amount appears after the solution, it is not easy to see how it can be included in the optimization problem. But here is the trick. If we deduct the 5% from each likely return for the ventures, then we can optimise the surplus return over bank interest; the general statement of the problem is just as before.