Date: Thu, 04 Dec 1997 17:45:57 +1200
From: Sheryl Coyle <swcoyle@iprolink.co.nz>
Subject: help with dynamic programming wanted
Hi there.

I am trying to solve a problem and I am using dynamic programming. This is my first time I have tried DP's. I can use DP to solve a simpler version of the problem, but I am stumped now that I am trying to extend it.

The problem is: I have a tree structure with demands at the nodes which need to be met (the demands are passed up the tree via arcs to the root), and certain types of arcs which I can use to join the nodes. Each type of arc has a certain cost, and a certain capacity, and only some arcs can be joined up at a node with others (eg if a node has arc type A going into it, it may be allowed to have arc types A B and D leave it but not arc type C leave it as arc C is not compatible with arc A).

I have created a DP which will solve the above problem, given a single set of demands. It starts from the leaves and works its way up the tree. Then once at the top, it finds what the optimal soln should be. (the exact formula can be provided if it is required)

My problem is that I cannot figure out how to do it over time ie, I have demands changing over time eg the demand at node 12 might be 10 in the first year, 12 in the 2nd year, 12 in the 3rd year 15 in the 5th year etc....

I need to know what type of arc to use between each node, and, if an arc needs to change to a new type at some stage, which time period to change it. All this has to be done while keeping in mind that the arcs need to stay compatible with each other over time eg changing on arc on a node in the 2nd year needs to be compatible with the arc on the parent node (and children nodes) in the 2nd year.

Can anyone please help me with this or point me to some papers/books/resources which deal with this type of problem?

all replies will be greatly appreciated

regards

andrew

PS: please reply to email as my access to newsgroup postings is a little unstable

Date: 18 Nov 1997 17:27:09 GMT
From: "Alain Vercambre" <Alain.Vercambre@ping.be>
Subject: problem optimizing timber cutting
Hi,

Looking for program that optimises the cutting of timber logs (circular) in slats (rectangular).

If somebody could put me on the right track, I'll be gratefull. I have completely no experience with optimalisation methods, but I'm willing to learn.

Thanks

Alain

Date: 19 Nov 1997 12:07:38 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: problem optimizing timber cutting
A bibliograhy is written by Harald Dyckhoff, Ute Finke: Cutting and packing in Production and Distribution, Physica Verlag, Heidelberg, 1991.

check out http://prodlog.wiwi.uni-halle.de/sicup/index.html
http://www.maths.mu.oz.au/~worms/digest/cuting_stock96.html

The german book "Grundlagen zur Integration der Zuschneideplanung in Produktionsplanungs- -steuerungssystem" from Ute Finke, LIT Verlag, Mnster, 1995, contains quite a lot of references to bin packing and cutting problem.

Any one interested in 1&2D cutting stock optimization software can take a look at http://www2.hyper.gr/escape/guillotine.html this is information I assembled from answers in this newsgroup. hope it helps (a bit)

peter

Date: Wed, 19 Nov 1997 13:34:53 -0800
From: Jim Funck <funckj@frl.orst.edu>
Subject: problem optimizing timber cutting
If I understand your question correctly, you're really asking about log breakdown optimization for lumber production. The only freeware I am aware of is Best Opening Face (BOF), which is a cylinder/truncated cone model that uses a heuristic search approach. It can be obtained from the USDA Forest Products Lab, Madison, WI.

Only a few of the software programs utilize something other than a heuristic approach. We (Oregon State University, Department of Forest Products) have a program called SAW3D that uses a dynamic programming algorithm, and a researcher in Australia named Geerts also used dynamic programming. There are a number of optimization programs being developed at universities that have widely varying levels of sophistication regarding log shape and breakdown optimization considerations. They also vary depending upon whether they are for hardwood (deciduous) or softwood (coniferous) species.

There are many private companies that have models, although most of them are heuristic-based and utilize some form of cylindrical or truncated cone representation of the log. (Our program (SAW3D) has shown that true log shape (3-D) representation is very important.) A few of the private companies are:

• Halco Software Systems - Vancouver, B.C., Canada
• Porter Engineering - Richmond, B.C., Canada
• Nanoose - Parkersville, B.C., Canada
• MPM Engineering - Langley, B.C., Canada
• Inovec - Chattanooga, TN, USA
• Coe Manufacturing - Portland, OR, USA

Date: 28 Aug 1997 14:05:43 GMT
From: rkwmfk@ (MF Kruger)
Subject: Dynamic Programming
Hi

I have a 0-1 optimization problem which I want to solve by using Dynamic Programming. I have a good approximate solution and want to use it as a starting point in my program. From this starting point I want to move to the exact solution by changing only a few of the variables.

Can anybody give me some pointers to literature?

Thanks in advance.

Machiel Kruger (rkwmfk@puknet.puk.ac.za)

Date: Wed, 02 Jul 1997 00:24:54 GMT
From: collin.carbno@sk.sympatico.ca (collin)
Subject: dynamic programming?
Dynamic programming essentially is a technique whereby you break the problem down into a series of smaller -- chained problems. If you can solve each one in the chain, then you can chain your way back to the global solution.

Collin

Date: 3 Jul 1997 01:12:56 -0400
From: rhoads@sceloporus.rutgers.edu (Glenn Rhoads)
Subject: dynamic programming?
Dynamic programming is essentially bottom-up recursion where you store the answers in a table starting from the base case(s) and building up to larger and larger parameters using the recursive rule(s). You would use this technique instead of recursion when you need to calculate the solutions to all the sub-problems and the recursive solution would solve some of the sub-problems repeatedly.

Trivial example: fibonacci numbers.

Recursive Solution:

function FIB(N):
if N=1 or N=2 return(1);
else return (FIB(N-1) + FIB(N-2));
This works but it is VERY inefficient because it repeatedly solves the same subproblems over and over again. To see this, just draw a tree of the recursive calls generated for, say 10. You'll find that FIB(8) gets solved 2 times, FIB(7) 3 times, FIB(6) 5 times, FIB(5) 8 times, FIB(4) 13 times, etc.

Dynamic Programming solution:

function FIB(N):
declare integer array A[1..N]
A[1] <-- A[2] <-- 1
for I = 3 to N by 1
A[N] = A[N-1] + A[N-2]

This function solves every subproblem exactly once. The recursive program performs an exponential number of additions (FIB(N) - 1 to be exact) while the dynamic programming solution does only a linear number of additions.

Date: Wed, 25 Jun 1997 17:10:17 +0100
From: Rudolf Moosburger <
moosbur@sun6hft.ee.tu-berlin.de>
Subject: dynamic programming?
Where can I find an introduction and other material for DYNAMIC PROGRAMMING in the internet?

I'd like to see, whether this technique can be applied to my technical optimization problem.

Thanks

RuMo

Marco A.G. Dias

Date: 24 Jun 1997 13:55:56 GMT
From: focana@platon.ugr.es
Subject: dynamic programming in economics and finance

Date: Mon, 16 Jun 1997 13:23:45 -0400
From: Keith Sill <ksill@voicenet.com>
Subject: dynamic programming in economics and finance
An excellent text, widely used in graduate courses, is:

"Recursive Methods in Economic Dyanmics" by Nancy L. Stokey and Robert E. Lucas Jr. with Edward Prescott. Harvard Univ Press 1989.

Enjoy,

Keith Sill

Date: Wed, 11 Jun 1997 11:46:23 +0200
From: Fabio Alessandrini <fabio.alessandrini@unifr.ch>
Subject: dynamic programming in economics and finance
Does anyone have good references on the topic "dynamic programming in the field of finance and economics" ?

Date: 16 Jun 1997 02:46:59 GMT
From: Rodney Beard <R.Beard@mailbox.uq.edu.au>
Subject: dynamic programming in economics and finance

Rodney Beard
University of Queensland

Date: 21 Apr 95 10:14:08 MDT
From: sl1mx@cc.usu.edu
Subject: DP Stage problems
Hello everyone;
This is the first time that I'm posting here so, I don't know if this is the proper place or not. In case I am wrong, please accept my apologies in advance.
The nature of my problem is optimization(minimization). I am trying to minimize two cost components of a network in Dynamic Programing.
Since, each element of the network is connected (a flow throw the element, very much like critical events of a critial path), I'm designating each element as a stage. However, this causes one problem, I have to minimize over discrete time periods. Since, I have my network elements as stages, I have run out of stages to designate the time to.
The path I'm taking now is to divide the problem into two master problem and sub-problem. In brief(I'm leaving out the policies and discounted costs that are part of both sub and master problem); Sub-problem minimizes the costs of elements for any given two time periods, therefore, stages are the components. Master problem minimizes the shortests path through planning horizon, therefore, stages become time steps.
I know my explanation may be confusing, however, my question is have you seen any examples that deal with this type of problem in this way or any other way. I would be more than greatful if you have any references or anything to help out a rookie in DP.
Thanx in advance, you can e-mail to sl1mx@cc.usu.edu
mj

I am looking for dynamic programming type software. Anything from a C/C++ library to Mathematica toolkit to a turnkey setup. I did not see any reference in the FAQ's.

My interest is in stochastic dynamic programming, to be exact. I will post a list if it is significant.

Mike Yukish, Penn State

This new two-volume textbook, used in a first-year graduate course at the Massachusetts Institute of Technology, is a greatly expanded and pedagogically improved version of the author's "Dynamic Programming: Deterministic and Stochastic Models," (Prentice-Hall, 1987). It treats simultaneously stochastic optimal control problems popular in modern control theory and Markovian decision problems popular in operations research. New features include:

---

• neurodynamic programming/reinforcement learning techniques, a recent breakthrough in the practical application of dynamic programming to complex problems.
• deterministic discrete- and continuous-time optimal control problems, including the Pontryagin Minimum Principle.
• an extensive treatment of deterministic and stochastic shortest path problems.

The first volume is oriented towards modeling, conceptualization, and finite-horizon problems, but also includes a substantive introduction to infinite horizon problems that is suitable for classroom use.

The second volume is oriented towards mathematical analysis and computation, and treats infinite horizon problems extensively. The text contains many illustrations, worked-out examples, and exercises.

Date: 1 Feb 1996 16:21:10 GMT
From: gunner1+@pitt.edu (Gunner)
Subject: Integer Programming / Dynamic Programming Questions...

First...

This summer I plan to teach an introductory graduate course in Integer Programming, worth roughly 1.5 credits. I was wondering if I could get some feedback on (a) what you might consider an appropriate mix of topics, given that it's only about half a semester's worth of time, and (b) what are some decent introductory texts that I could recommend to students ? I do plan on making up instructional notes of my own based on the material I finally choose to cover, so the texts would probably be used for supplementary reading (and for me to prepare my material).

Second...

I have an identical request as the one above, except that I ask you to substitute Dynamic Programming for Integer Programming in the previous paragraph :-)

Thanks muchos for any feedback. You could either post to this newsgroup or send me e-mail - either way is fine.

--jr--

Date: 11 Feb 1996 13:56:52 -0500
From: schwah2@cii3116-03.its.rpi.edu (Henry Frederick Schwarz)
Subject: neuro-dynamic programming text
Recently I read that there is a new book titled "Neuro-dynamic programming" by, I believe, Dimitri Bertsekas. Does anyone know the publisher of this book?

Thanks in advance,

Quique

Date: 19 Sep 1996 21:04:23 GMT
From: dyoung@econ.ualberta.ca (Denise Young)
Subject: programme for iterating on Bellman equation
I originally sent this to sci.econ.research and someone suggested that I try sending the request to sci.op-research.

I am sending this on behalf of a graduate student in our department. He is looking for a programme that will "help me iterate on the Bellman equation to find an approximation of the maximum value function in a dynamic constrained optimization problem." I suggested that he might try something like GQOPT, but he is hoping that there is something out there that would not require him to programme in fortran.

Any suggestions would be appreciated.

Date: 8 Nov 1996 08:54:41 GMT
From: moshe@mundoe.maths.mu.OZ.AU (Moshe Sniedovich)
Subject: Branch and Bound and Dynamic Programming
G'day:

You might be interested in polishing your branch and bound and dynamic programming skills using two interactive JavaScripts that I have just put on my web site. These can be very effective teaching tools.

The URL are as follows:

http://www.maths.mu.oz.au/~moshe/recor/easy/easy.html
http://www.maths.mu.oz.au/~moshe/recor/hanoi/hanoi.html

You'll need Netscape 3 for this adventure.

Have fun!

Best wishes

Moshe Sniedovich

Crawl back to front page.