Assume there are m potential projects. For now, assume that the projects are independent; that is, it is reasonable to select any combination of projects and the cost and value of any project do not depend on what other projects are selected. Define, for each project i = 1, 2,..., m the zero-one variable xi. The variable xi is one if the project is accepted and zero if it is rejected. Let ci be the incremental value (b for “benefit”) of the i’th project and ci be its cost. Let C be the total available budget. The goal is to select from the available projects the subset of projects with a total cost less than or equal to C that produces the greatest possible total value.
The problem may be expressed mathematically as:
Maximize m∑i=1bixi Subject to: m∑i=1cixi≤C and xi= 0 or 1 for i = 1, 2,...,m.
This is a zero-one integer optimization problem. It is NP-Complete, i.e. the time required to solve such a problem using any currently known algorithm increases rapidly as the size of the program grows. Naturally, because allocating resources/planning is involves combinations of actions and combinations tend to explode. It can be okay if there the number of possible actions/projects is relatively small, but remember that even 10! is already 3.6 million.
The equation above isn’t comprehensive enough to capture the full detail of real-world planning, but it should suffice to indicate that planning is often of the combinatorially explosive class. (If you want to see how more factors can be included, see the rest of Merkhofer’s paper where he models mutually exclusive/sequential projects, multi-period planning, and sensitivity to delay of projects.)
Note however that this treatment assumes that the benefits and costs are perfectly known when performing the optimization. In the real world, we only have distributions over the benefits and costs. A true formalism of real-world prioritization would be couched in statistical terms.
Plus, the benefits and costs in the above formalism are scalars which can be added and compared, e.g. dollars. In the real world, the benefits and costs we weigh are of disparate types which at best have vague conversion rates between them. So you might imagine that a comprehensive formalism would deal in vectors and would include a complicated function for comparing those vectors.
The point here is not that we should attempt to create or use mathematical models in our planning, but to recognize that it is precisely this math which our brains must find some way of crunching. Understanding that this is the immense problem we are tasked with, we can start to look for ways to handle it better than our default.
And, you know, also give ourselves a bit of break when we find planning hard.
Nitpick: Just because a problem can be formalized as a zero-one integer optimization problem doesn’t mean it’s NP-complete; you need to show that some NP-complete problem reduces to the planning problem. For example, the problem of finding the largest number in a set {ni} is a zero-one optimization problem (it can be formalized as max∑ixini subject to ∑ixi=1 with each xi being zero or one) but it isn’t NP-complete.
That said, the problem you specified is identical to the knapsack problem, which is known to be NP-complete, so your point stands.
That’s a fair nitpick, thanks. I was aware it was identical to the knapsack problem, though I do see that my phrasing implied that being a zero-one integer optimization problem automatically makes it NP-Complete. That was sloppy of me.
Appendix: Formalism of the Computation Problem
A simple formalism illustrates that planning quickly becomes computationally intractable. Borrowing from Lee Merkhofer’s Mathematical Theory for Prioritizing Projects and Optimally Allocating Capital.
This is a zero-one integer optimization problem. It is NP-Complete, i.e. the time required to solve such a problem using any currently known algorithm increases rapidly as the size of the program grows. Naturally, because allocating resources/planning is involves combinations of actions and combinations tend to explode. It can be okay if there the number of possible actions/projects is relatively small, but remember that even 10! is already 3.6 million.
The equation above isn’t comprehensive enough to capture the full detail of real-world planning, but it should suffice to indicate that planning is often of the combinatorially explosive class. (If you want to see how more factors can be included, see the rest of Merkhofer’s paper where he models mutually exclusive/sequential projects, multi-period planning, and sensitivity to delay of projects.)
Note however that this treatment assumes that the benefits and costs are perfectly known when performing the optimization. In the real world, we only have distributions over the benefits and costs. A true formalism of real-world prioritization would be couched in statistical terms.
Plus, the benefits and costs in the above formalism are scalars which can be added and compared, e.g. dollars. In the real world, the benefits and costs we weigh are of disparate types which at best have vague conversion rates between them. So you might imagine that a comprehensive formalism would deal in vectors and would include a complicated function for comparing those vectors.
The point here is not that we should attempt to create or use mathematical models in our planning, but to recognize that it is precisely this math which our brains must find some way of crunching. Understanding that this is the immense problem we are tasked with, we can start to look for ways to handle it better than our default.
And, you know, also give ourselves a bit of break when we find planning hard.
Nitpick: Just because a problem can be formalized as a zero-one integer optimization problem doesn’t mean it’s NP-complete; you need to show that some NP-complete problem reduces to the planning problem. For example, the problem of finding the largest number in a set {ni} is a zero-one optimization problem (it can be formalized as max∑ixini subject to ∑ixi=1 with each xi being zero or one) but it isn’t NP-complete.
That said, the problem you specified is identical to the knapsack problem, which is known to be NP-complete, so your point stands.
That’s a fair nitpick, thanks. I was aware it was identical to the knapsack problem, though I do see that my phrasing implied that being a zero-one integer optimization problem automatically makes it NP-Complete. That was sloppy of me.