An Approximate Dynamic Programming heuristic to support non-strategic project selection for the Royal Canadian Navy

Abstract

We consider an Approximate Dynamic Programming heuristic to support the selection of defense projects when projects have different values and are originated intermittently but fairly frequently. We show that a simple policy reserving a positive fraction of the available budget for high-value projects not yet originated is superior to a greedy knapsack approach.

Keywords

Defense project selection knapsack problem Online Knapsack Problem Approximate Dynamic Programming

Get full access to this article

View all access options for this article.

References

Brown

Dell

Newman

. Optimization military capital planning. Interfaces 2004; 34: 415–425.

Brown

Clemence

Teufert

. An optimization model for modernizing the Army’s helicopter fleet. Interfaces 1991; 12: 39–52.

Brown

Coulter

Washburn

. Sortie optimization and munitions planning. Mil Oper Res 1994; 1: 13–18.

Brown

Dell

Holtz

. How US Air Force Space Command optimizes long-term investment in space systems. Interfaces 2003; 33: 1–14.

Hurley

Schobel

. Selecting low expenditure defence projects: an estimate of the value of optimization relative to ad hoc procedures. Mil Oper Res 2009; 14: 41–46.

Weingartner

. Capital budgeting of interrelated projects: survey and synthesis. Manag Sci 1966; 12: 485–516.

Senju

Toyoda

. An approach to linear programming with 0–1 variables. Manag Sci 1968; 15: B196-B207.

Toyoda

. A simplified algorithm for obtaining approximate solutions to zero-one programming problems. Manag Sci 1975; 21: 1417–1427.

Martello

Toth

. Knapsack problems: algorithms and computer implementations. New York: John Wiley, 1990.

10.

Kellerer

Pferschy

Pisinger

. Knapsack problems. Berlin: Springer, 2010.

11.

Buffum

. Workforce planning models for the Naval Air Test Center. MS Thesis, Department of Operations Research, Naval Postgraduate School, Monterey, CA, 1978.

12.

Evans

Fairbairn

. Selection and scheduling of advanced missions for NASA using 0–1 integer linear programming. J Oper Res Soc 1989; 40: 971–981.

13.

Ewing

Tarantino

Parnell

. Use of decision analysis in the Army Base Realignment and Closure (BRAC) 2005 military value analysis. Decis Anal 2006; 3: 33–49.

14.

Loerch

Koury

Maxwell

. Value added analysis for army equipment modernization. Nav Res Logist 1999; 46: 233–253.

15.

Kleywegt

Papastavrou

. The dynamic and stochastic knapsack problem. Oper Res 1998; 46: 17–35.

16.

Marchetti-Spaccamela

Vercellis

. Stochastic on-line knapsack problems. Math Program 1995; 68: 73–104.

17.

Van Slyke

Young

. On-line stochastic knapsacks. Technical Report 94–75, Polytechnic University, New York, 1994.

18.

Lueker

. Average-case analysis of off-line and on-line knapsack problems. In: proceedings of the sixth annual ACM-SIAM SODA, 1995, pp.179–188.

19.

Chakrabarty

Zhou

Lukose

. Online knapsack problems. Workshop on internet and network economics (WINE), http://research.microsoft.com/en-us/um/people/dechakr/pubs/czk-full.pdf (2008; accessed Oct 21, 2013).

20.

Han

Makino

. Online knapsack problems with limited cuts. Algorithm Comput Lect Notes Comput Sci 2009; 5878: 341–351.

21.

Han

Makino

. Online Minimization Knapsack Problem. Approx Online Algorithm Lect Notes Comput Sci 2010; 5893: 182–193.

22.

Han

Kawase

Makino

. Online knapsack problem with removal cost. Comput Combinator Lect Notes Comput Sci 2012; 7434: 61–73.

23.

Iwama

Taketomi

. Removable online knapsack problems. Automata Lang Program Lect Notes Comput Sci 2002; 2380: 293–305.

24.

Powell

. Approximate dynamic programming: solving the curses of dimensionality. New York: Wiley, 2007.

25.

Powell

. What you should know about approximate dynamic programming. Nav Res Logist 2009; 56: 239–249.

26.

Powell

Ryzhov

. Optimal learning and approximate dynamic programming. In: Lewis

Liu

. (eds) Approximate dynamic programming. Chaper 18. New York: Wiley and Sons, 2012.