by Ruby

Mentioned in
New Comment

# 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.

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 . The variable is one if the project is accepted and zero if it is rejected. Let be the incremental value (b for "benefit") of the i'th project and 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
Subject to: and 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.

This is a zero-one integer optimization problem. It is NP-Complete

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 is a zero-one optimization problem (it can be formalized as subject to with each 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.

This is so helpful. Thank you.

One other aspect I would include is that even figuring out the set of actions available to you can be difficult. This post seems to be arguing that "thinking inside the box" is already hard; I think figuring out how to "think outside the box" is also both important and hard.

Also, you'll probably enjoy Research as a Stochastic Decision Process.

That's very true. I need to think through that more and figure out how to incorporate into my models. I think there's a lot there which is missing from here.

The discussion of planning across domains seems to ignore the fact that often the best solution to planning a project in a domain with which you're not familiar is to hire/get help from another person. Of course, once you turn planning into a multi-person activity, which I think any comprehensive model of planning should treat it as, you also need to factor in uncertainty about others' plans, which complicates the model quite a bit.

Each plan realisation consists of several stages, which are similar in very different types of tasks:

2) Preparation: buying instruments, collecting data for this task, register on Tinder etc.

3) Creating "first draft". Writing the draft, building a prototype, trying to go to the first date.

4) Perfecting the product. Editing, testing with users, many dates.

5) "Selling it" and getting the output. E.g: getting article published and cited, startup becomes unicorn, or stable relation. Selling means that the output of the project becomes useful for some other projects, not necessary money or relation with other people.

6) Ending. It is the moment when you press stop button (or you become internally "peperclipy" by producing more and more thing which you do not need already). For example, you need to stop dating if you get wife. Stopping is not easy, as we tend to do the same things again and again. Stopping is especially difficult if the project fail and I have an option: try more or stop trying.

The most difficult here is the 5th step, selling – this is there plans tend to fail. Because on the first 4 levels I just spend resources and measure the progress by my internal metrics. At the end I finally compare it with the outside world, which could be just my bigger project.

Plans (or tasks) could be presented as blackboxes, which consume X and output Y.

X is:

• money
• time
• other material or immaterial resources (contacts, objects)