Indiana Jones has broken into an ancient temple and wants to bring back as much highly valued treasure to the university museum. There is a vast variety of items to choose from, each with a particular value. But his treasure sack can hold only 20 pounds of loot, so he needs to choose wisely. Should he take just a couple heavy but highly valuable items, or should he take several lighter but less valuable items?

It all depends on the particular values and weights of the items, but even if we knew those details with precision the problem becomes very complicated beyond a handful of potential items. Even with only 12 items to choose from, there are 2^12 = 4096 possible combinations of booty.

This happens to be a classic optimization problem, known unsurprisingly as the knapsack problem. Solving the knapsack problem tells you exactly which items Indiana should grab to bring back the most valuable collection of items possible. As you may imagine, this problem has many real-world applications, one of which will become fairly obvious in a moment.

Imagine that instead of Indiana Jones we’re talking about a GM. And instead of items of treasure we’re talking about players. Instead of weight we’re talking about salaries. And instead of the treasure sack and its weight limit, we’re talking about a salary cap.

As a fun exercise only intended to demonstrate the power of using optimization, let’s build an all-pro offense from 2014. This all-pro team will be like any other, however, as it will need to adhere to a salary cap. We’ll say that our starting 11 players need to come in under $40M of salary. (That’s not too far from reality, supposing a team would spend $40M on offensive starters, $40M on defensive starters, and $40M more on reserves, specialists, and dead money.)

As our measure of player value we’ll use Approximate Value (AV), a composite score developed at Pro-Football-Reference.com.

There are hundreds of players to choose from, each with their own combination of salary and AV. We’ll tell a computer to tell us the best possible total AV for 11 players as long as their total cap hit for 2014 is less than $40M. The problem is staggering in its complexity already, and we haven’t even started to worry about some important details.

Right away the computer would probably tell us to include 11 QBs, because their AV scores tend to be biggest due to the nature of the position. But that’s no good. Let’s add some constraints that tell the computer we want 1 starting QB, 1 starting RB, 2 starting OT’s, etc. Now the problem is outrageously complicated to a human brain. Even if you stumbled on a pretty good solution you couldn’t be sure that there aren’t much better solutions available.

Fortunately, this kind of problem is a piece of cake for optimization algorithms. It took my laptop only .07 seconds to solve the problem. The best possible total AV for a starting 11 from 2014 for under $40M is 167. Here’s the optimum lineup:

Pos	Player	Team	Cap Hit ($)	AV
QB	R.Wilson	SEA	880,474	19
C	M.Pouncey	PIT	5,387,139	15
T	T.Smith	DAL	5,360,645	14
T	D.Bakhtiari	GB	655,910	10
G	M.Yanda	BAL	9,103,128	17
G	Z.Martin	SEA	1,756,536	14
RB	D.Murray	DAL	1,720,033	19
WR	A.Brown	PIT	4,866,672	16
WR	R.Cobb	GB	1,100,109	16
WR	J.Nelson	GB	6,382,962	18
TE	T.Kelce	KC	761,459	9
Total			37,975,068	167

In this case we’ve got over $2M of spare cap space to use elsewhere. We could go further and determine how stable this solution is. In other words, how much could I fudge the cap limit before the solution changes and we get a different roster of starters?

No GM can reach in and grab players from any team whenever he feels like it. And, of course, a single year of AV isn’t gospel when it comes to player valuation. We still need to worry about backups, defense, and special teams, but that’s really just a matter of scale.

Even though this was a highly unrealistic exercise I think you can see where I’m going here. Starting with an existing roster and existing contracts, I can optimize a potential future roster given a menu of plausible free agents and their likely contracts. All that’s needed is some measure of player value. In this exercise I used AV, but it could be scouting grades or a personnel department’s qualitative rating on a player. I can even formulate the program to consider releasing existing players, triggering dead cap charges if applicable. Things get complicated when we consider future years, but's it's possible to do that very well by stipulating constraints on the minimum AV I keep on my roster and maximum salary eaten by legacy contracts.

It may be unrealistic to expect decision makers to adhere to the solution due to several factors, but at a minimum a more sophisticated application of this approach can provide insight into how best to build a roster. For example, the exercise here tells us a few interesting things:
-The AV values of the players are fairly evenly spread. There's no single guy with 35 and a bunch of 3s and 4s. (This is consistent with previous research on a similar concept.)
-It's OK to spend on veteran FAs, within limits.
-No one is making more than $10M.
-It's easy to build a great roster with a guy like Wilson making 3rd-round money! But we already knew that.