Optimization & Operations Research

How should limited effort be allocated across actions with different value and cost?

A team has a fixed number of hours. Working a list from top to bottom ignores that some actions return more value per hour than others.

This is a knapsack problem. The ratio of value to effort gives a fast rule and a provable bound from the relaxation; exact methods show how far the rule is from the optimum.

x_i is 1 if action i is executed, v_i is its expected value, a_i its effort and b the available capacity.

1. Define the action list with value and effort.

2. Rank by value per unit of effort and compute the relaxation bound.

3. Solve exactly when the size allows (dynamic programming).

4. Compare rule, optimum and bound, and report the gap.

1. Candidate actions

2. Value and effort

3. Ranking by ratio

4. Exact solver

5. Selection

6. Gap report

No published experiments. The Decision Optimization, Mathematical Optimization and Predictive Modeling labs compute these quantities on synthetic data.

Decision Optimization · Mathematical Optimization · Predictive Modeling

No original research results are claimed. This area is presented as a technical perspective with a computable demonstration on synthetic data.

• Values depend on forecasts that may be wrong.
• Interactions between actions are ignored.
• Policy limits must be added as constraints.

Background reading by other authors. These are not Menlo Tech publications, and no Menlo Tech paper is cited because none has been published.

• Bertsimas, D. & Tsitsiklis, J. Introduction to Linear Optimization. Athena Scientific, 1997.
• Martello, S. & Toth, P. Knapsack Problems: Algorithms and Computer Implementations. Wiley, 1990.
• Hyndman, R. & Athanasopoulos, G. Forecasting: Principles and Practice. OTexts.