Reusable dynamic programming with C# generics

• Download source - 37 Kb

Contents

• Introduction
• Background
  • Dynamic programming
  • Generics
  • Why I wrote this article
• Using the code
  • Open the solution
  • Sample problems
  • Step 1: Define states and decisions
    • An example
  • Step 2: Choose your method of customization
    • Method 1: Derive a new dynamic program class from DynamicProgramBase
    • Method 2: Use the delegates defined on DynamicProgram
    • Method 3: Implement the IState<> interface
  • Step 3: Pass the initial state to the Solve method
  • Step 4: Iterate through the solutions in the SolutionSet<> class
• Points of Interest
  • Using a non-generic base class to share enums
  • Generic methods
  • Some notes on designing states and decisions
    • Option 1: simple approach - one decision/stage per denomination
    • Options 2: Store an array of remaining denominations on the State class
    • Option 3: Store the index of the next available denomination on the State class
    • The trade-off I made
  • A plug for unit testing
  • A suggestion for the Visual Studio team
• Conclusions
• History

Introduction

Generics are a new feature added in .Net 2.0.

• Do they make it easier to write highly flexible and reusable library code?
• Can they make complex systems easier to model?

I recently conducted an experiment to investigate these questions. This article is about the experiment and what I learnt from it.

Dynamic programming is a mathematical optimization technique closely related to recursion. The downloadable code implements the dynamic programming algorithm in a highly reusable fashion, and solves some sample problems.

.Net generics are the primary means for providing flexibility and reusability. However 3 additional methods of code customization are also demonstrated:

• inheritance from an abstract base class
• implementation of interfaces
• “callbacks” implemented through delegates

Background

Dynamic programming

Dynamic programming breaks a problem into a sequence of decisions.

Each decision modifies the state of the system, usually creating a smaller problem to be optimized at the next stage. This is solved recursively, with each stage being the next level in the recursion stack.

All possible decisions are considered at each stage. This limits the algorithm's usefulness, as most real world problems have intractably large state spaces, making exhaustive search impractical.

Nevertheless it is a simple technique. This makes it ideal for comparing different approaches for writing generic, reusable code.

It is also a good stepping stone to a variety of more advanced techniques, such as adaptive/forward dynamic programming, stochastic programming, neighbourhood search, tabu search, alpha beta pruned search trees (such as Chess programs may use) and so on.

You can read more about dynamic programming on wikipedia.

Generics

Generics are my favourite new feature in .Net 2.0. They enable “template classes” to be written which take 1 or more types as parameters. Concrete classes are constructed from these templates by binding types of your choice to these type parameters.

The true power of .Net generics is that the metadata for the template class is stored in the assembly. This makes it far more practical for code reuse, since the source code for the template class doesn't have to be provided to the "re-user".

Why I wrote this article

I did my honours degree in Operations Research (OR) many years ago. OR is a discipline where logistical and organizational problems are solved using mathematics, statistics and computing. I don’t get much opportunity to practise OR these days, but I still maintain an interest in the subject.

For many years I have had a strong interest in how best to write reusable generic code (my experience being that one should generally try to resist the temptation!)

This article combines these 2 interests.

This is also my first article on CodeProject. I'm hoping to use the experience to improve my writing style. So your comments, suggestions and criticism are very welcome.

Using the code

Open the solution

The code was written using Visual Studio 2005. I have also used NUnit 2.3.0 for unit testing.

If you don’t have NUnit installed, then you will receive error messages when opening the solution because the references to the NUnit assemblies can’t be resolved. Ignore these and consider removing the unit testing project from the solution.

Better yet, just download NUnit. And consider downloading TestDriven.Net too. This is a very useful Visual Studio extension which integrates NUnit, and other testing frameworks, into the IDE.

An FxCop project is also included. I have followed some, but not all of the FXCop advice (this is experimental code after all, and achieving "perfection" is not the point). If you need to, you can use the FXCop project to see what still needs to be done.

Sample problems

Three sample problems are provided.

Two have their own projects:

• DynamicProgramming.SampleCode.ChangeMaker.
• DynamicProgramming.SampleCode.KnapsackProblem.

The third is part of a unit test:

• EquipmentReplacementProblem.cs in DynamicProgramming.UnitTests.

I will be using the ChangeMaker utility to demonstrate the concepts. This utility lists the different ways of making change for an amount of money, given coins of various denominations to choose from.

Step 1: Define states and decisions

Firstly define types to represent a state of the system, and the decisions which can be made at each stage.

In simpler problems, you may be able to get away with using simple data types, such as doubles, ints and bools. An example is provided in EquipmentReplacementProblem.cs, where the state is an int (the age of a machine), and the decision is a bool (replace machine this year?).

Usually though you will need to use classes or structs to represent states and decisions.

An example

In the ChangeMaker example, the initial state consists of:

• the amount of money to make change for, and
• an array listing the available denominations.

Each decision specifies a denomination, and the number of coins of that denomination to use (but at least one). The new state generated by the decision should contain the remaining amount of money to make change for, plus an array of remaining denominations (i.e. all denominations after the one that was chosen by the decision).

This isn't the only way to define states and decisions for this problem. Near the end of this article I discuss the other options I considered, why I chose this particular option, and how going through this process helped to improve the design of the generic code.

Step 2: Choose your method of customization

Three methods of customization can be used:

1. Derive your custom dynamic program class from DynamicProgramBase<>, and override its abstract methods.
2. Create an instance of the DynamicProgram<> class, and assign methods to its delegates.
3. Create a state class which implements the IState<> interface. Pass the initial state to the Solve() method of the StateCentricDynamicProgram<> class.

Method 1 is the way I would recommend, particularly in larger programs where elegance and readability are more important.

Method 2 is the “quick and dirty” way. Use it to get a solution quickly, particularly when code elegance is less important (such as for smaller problems).

Method 3 is the way I like least. The dynamic program delegates most of its responsibilities to the state class. Decisions become the responsibility of the state class, not the algorithm class. I prefer not to couple the state and decision classes so closely. I also feel that decisions are naturally the algorithm’s responsibility, and prefer the object model to reflect this.

Method 3 is also more restrictive, in that the state class must implement the IState<> interface. This prevents simple data types from being used for the state. It also makes it harder to use third party classes, as you will probably need to derive a class to wrap the third party state class and implement the interface.

Method 1: Derive a new dynamic program class from DynamicProgramBase

Your dynamic program algorithm class should inherit from DynamicProgramBase<TState, TDecision>, replacing TState and TDecision with the names of the state and decision types defined previously.

In the example, ChangeMaker is defined as:

public class ChangeMaker : DynamicProgramBase<State, Decision>
{
    ...
}

DynamicProgramBase is an abstract base class with a number of methods to override:

protected abstract IEnumerable<TDecision> GenerateDecisions(
        TState state);

protected abstract BranchStatus GetBranchStatus(TState state, int stage);

protected abstract double GetDecisionValue(TState priorState,
        TDecision decision, int stage);

/* GenerateNewState() should create a new state
 * from the existing state.
 * NB: The new state can't just be a modified copy
 *     of the state passed to the method.
 *     i.e. The TState class should be treated as immutable.
 */

protected abstract TState GenerateNewState(
        TState state, TDecision decision, int stage);

GetBranchStatus is the first method called when a new branch is being investigated by the algorithm. It must return either:

• BranchStatus.Infeasible, if the branch must be abandoned,
• BranchStatus.Complete, if the branch does not need to be investigated because a valid solution has been found, or
• BranchStatus.Incomplete, if the branch should be expanded further.

Here’s an example from ChangeMaker:

protected override BranchStatus GetBranchStatus(State state,
    int stage)
{
    if (state.TotalRemaining == 0)
        return BranchStatus.Complete;

    if (state.Denominations.Count == 0)
        return BranchStatus.Infeasible;

    return BranchStatus.Incomplete;
}

GenerateDecisions returns an IEnumerable. You can simply return an array or generic collection here. Alternatively you can use the new yield statement added in C# 2.0.

For example, ChangeMaker defines GenerateDecisions as follows:

protected override IEnumerable<Decision> GenerateDecisions(
    State state)
{
    foreach (Denomination denom in state.Denominations)
    {
        int maxCount = Math.Min(denom.QuantityAvailable,
            state.TotalRemaining / denom.CoinValue);

        if (maxCount == 0)
        {
            yield break;
        }
        else
        {
            for (int coinCount = 1;
                coinCount <= maxCount;
                coinCount++)
            {
                yield return new Decision(denom, coinCount);
            }
        }
    }
}

GetDecisionValue returns the contribution of the new decision to the value of the solution of which it will be a part. The value of the solution is just the value of all its decisions. The algorithm maximizes this value. If you want to solve a minimization problem instead, just multiply the value by -1. If you are interested in finding all feasible solutions, instead of the "best" solution, just return a value of 0 for all decisions.

ChangeMaker illustrates both these tricks. It can either find all ways of making change for an amount of money, or it can find the way that uses the least number of coins. It uses a Goal property, which can have values of GoalType.UseLeastNumberOfCoins or GoalType.AllWaysOfMakingChange, to decide which method to use:

protected override double GetDecisionValue(State priorState,
    Decision decision, int stage)
{
    if (goal == GoalType.UseLeastNumberOfCoins)
    {
        return -decision.CoinCount;
    }
    else
    {
        return 0.0;
    }
}

GenerateNewState should create a new state object from the existing one, based on the decision chosen. It mustn’t just modify the existing state instance, as this will cause the algorithm to break. To prevent this, you should ideally implement the State type so that it is immutable, and can’t be modified after it has been created (hint: use ReadOnlyCollection<> to expose immutable array or collection members).

protected override State GenerateNewState(
    State state, Decision decision, int stage)
{
    int index = -1;
    int ignoreCount = 0;
    Denomination[] availableDenominations = null;

    foreach (Denomination denom in state.Denominations)
    {
        if (index == -1)
        {
            /* Ignore all denominations up to and including
             * the one chosen by the decision:
             */
            ignoreCount++;

            if (decision.CoinDenomination == denom)
            {
                /* The denomination has been found, and now there is
                 * enough information to choose the size of the array:
                 */
                index = 0;

                availableDenominations = new Denomination[
                    state.Denominations.Count - ignoreCount];
            };
        }
        else
        {
            /* The remaining denominations are copied to the array: */
            availableDenominations[index] = denom;

            index++;
        }
    }

    State newState = new State(state.TotalRemaining
        - decision.CoinCount * decision.CoinDenomination.CoinValue,
        availableDenominations);

    return newState;
}

Method 2: Use the delegates defined on DynamicProgram

The DynamicProgram class inherits from DynamicProgramBase. It implements each of DynamicProgramBase’s abstract methods by delegating the work to "event handlers" with similar signatures. This can make it very quick and easy to set up dynamic programs without having to create new classes.

For example, EquipmentReplacementProblem.cs contains the following code:

/* The problem is to optimise the profit over 5 years
 * of a machine which is currently 1 year old.
 * At each time period, the decision is whether to
 * replace the machine (at a cost of 22).
 * The profit is zero on a machine that is 5 years old.
 * Otherwise the profit is 26 - 2t - 0.5 t^2
 * where t is the age of the machine at the start of the period
 * (but after the decision is made).
 *
 *   [Problem taken from my postgraduate university
 *    course notes in dynamic programming.]
 *
 */

/* The state variable is the age of the equipment.
 * The decision is whether to replace it.
 */
DynamicProgram<int, bool> problem
    = new DynamicProgram<int, bool>();

problem.ValueCalculator
    = delegate(int age, bool replace, int stage)
        {
            if (replace)
            {
                return 4;
                    /* Profit of 26 less
                     * replacement cost of 22
                     */
            }
            else
            {
                if (age >= 5)
                {
                    return 0;
                }
                else
                {
                    return 26 - 2 * age - 0.5 * age * age;
                }
            }
        };

problem.DecisionGenerator = delegate(int age)
{
    bool[] choices = { false, true };
    return choices;

    /* Note:
     * If we were using a normal delegate
     * instead of an anonymous delegate,
     * we could do the following instead:

    yield return false;
    yield return true;

     */
};

problem.StoppingTest = delegate(int age, int stage)
{
    if (stage == 6)
    {
        return CommonDynamicProgramBase.BranchStatus.Complete;
    }
    else
    {
        return CommonDynamicProgramBase.BranchStatus.Incomplete;
    }
};

problem.StateTransformation
    = delegate(int age, bool replace, int stage)
{
    if (replace)
    {
        return 1;
       /* The new machine will be 1 year old in the next stage */
    }
    else
    {
        return ++age; /* The same machine is 1 year older */
    }
};

SolutionSet<int, bool> solutions = problem.Solve(1);
    /* Pass 1 as initial state as this
     * is the current age of the machine
     */

Method 3: Implement the IState<> interface

The third alternative is for your state class to implement the IState interface. Then create an instance of StateCentricDynamicProgram binding to this state class (and the decision class, as normal).

StateCentricDynamicProgram has the following definition:

public class StateCentricDynamicProgram<TState, TDecision>
    : DynamicProgramBase<TState, TDecision>
    where TState : class, IState<TDecision>
{
    ...
}

StateCentricDynamicProgram delegates the responsibility for generating decisions, generating new states, evaluating decisions and deciding whether to continue recursing, to the state class.

Step 3: Pass the initial state to the Solve method

Regardless of which method you choose, the next step is the same. Create an initial state. Pass this state to the Solve method of the dynamic program class.

Step 4: Iterate through the solutions in the SolutionSet<> class

The Solve method returns an instance of the SolutionSet<TState, TDecision> class.

This class wraps a tree of decisions and/or states for all optimal, feasible solutions. This is an efficient storage mechanism, as common solution nodes can be shared by multiple solutions. The SolutionNode class represents nodes in this tree. 

SolutionSet contains useful utility methods for iterating through solutions, and returning each solution as a separate array of decisions, states or solution nodes. SolutionSet[i] returns the ith solution as an array of SolutionNodes.

Note that a solution can be thought of as a sequence of decisions, or as a sequence of successive states. Both approaches are supported, with SolutionNodes having both a DecisionChosen and a PostDecisionState property. But some problems will only require one or the other approach, and in this case it is inefficient to store both the decision and state on the solution node.

This is addressed by having protected methods on DynamicProgramBase - GetSolutionStorageType() and SetSolutionStorageType(). In the DynamicProgram and StateCentricDynamicProgram classes, these 2 methods are used to implement the SolutionStorageType property.

A SolutionNodeStorageTypeException is thrown when one tries to access a SolutionNode's DecisionChosen or PostDecisionState property if that information isn’t being stored on the solution nodes. This approach was less "pure" than I would have liked, but it seemed like the most pragmatic compromise to me.

Points of Interest

Using a non-generic base class to share enums

Initially the BranchStatus enumeration was part of DynamicProgramBase. This quickly became problematic.

Firstly, because typing out...

return DynamicProgram<MyState, MyDecision>.BranchStatus.Complete;

... is tedious.

But secondly because IState was defined as follows...

public interface IState<TDecision>
{
    ...
    DynamicProgramBase<IState<TDecision>, TDecision>.BranchStatus
        GetBranchStatus(int step);
    ...
}

This caused compilation errors in StateCentricDynamicProgram, because there was no way for the compiler to know that this return type would be the same as StateCentricDynamicProgram<,>.BranchStatus.

A possible solution was to separate BranchStatus into its own non-generic helper class. But I felt uncomfortable with this. I felt that I shouldn’t be changing the object model because of a purely technical issue.

The underlying issue is that DynamicProgramBase<MyState, MyDecision> and DynamicProgramBase<YourState, YourDecision> share none of their members or nested types (such as BranchStatus).

I addressed this by creating a common base class – CommonDynamicProgramBase - which didn’t have generic type parameters, and hence could be shared. I think I will do this by default for all generic classes in future.

Generic methods

Generics are most commonly used with classes. But methods and delegates can also be generic.

The SolutionSet class has 3 methods which return an array of either SolutionNodes, decisions or states. The only difference between the methods was in the return type, and in the way that the type was obtained from a SolutionNode.

It was a simple thing to replace the 3 methods with a single generic method having a type parameter of type TReturnType. A generic delegate was used to convert a SolutionNode to a TReturnType:

private delegate TReturnType SolutionNodeConverter<TReturnType>(
    SolutionNode<TState, TDecision> solNode);

private void PopulateListFromSolutionNodes<TReturnType>(
    int solutionIndex, List<TReturnType> sequence,
    ReadOnlyCollection<SolutionNode<TState, TDecision>>
        solutionNodesAtStage,
    SolutionNodeConverter<TReturnType> convert)
{
    int offset = 0;
    int index = 0;

    foreach (SolutionNode<TState, TDecision> solNode
        in solutionNodesAtStage)
    {
        if (solNode.SolutionCount > solutionIndex - offset)
        {
            SolutionNode<TState, TDecision> nextSolNode
                = solutionNodesAtStage[index];

            if (convert != null)
            {
                sequence.Add(convert(nextSolNode));
            }

            PopulateListFromSolutionNodes<TReturnType>(
                solutionIndex - offset, sequence,
                nextSolNode.NextSolutionNodes, convert);

            break;
        }
        else
        {
            offset += solNode.SolutionCount;
            index++;
        }
    }
}

This could then be used as follows:

public TState[] GetStatesForSolution(int solutionIndex)
{
    if ((solutionIndex < 0) || (solutionIndex >= SolutionCount))
    {
        throw new ArgumentOutOfRangeException();
    }

    List<TState> stateList = new List<TState>();

    /* Recursively build up the sequence of states
     * for the solution with the given index:
     */
    PopulateListFromSolutionNodes<TState>(solutionIndex,
        stateList, initialSolutionNodes,
        delegate(SolutionNode<TState, TDecision> solNode)
        {
            return solNode.PostDecisionState;
        });

    return stateList.ToArray();
}

Some notes on designing states and decisions

Let's go back to the ChangeMaker example.

I chose to store an array of remaining denominations on every State object. What considerations led me to this design?

Let's look at some alternative designs:

Option 1: simple approach - one decision/stage per denomination

The simple approach was to make each stage correspond to the next index in the array of denominations. But this would make "zero coins" a possible decision, which feels like a null decision to me. By skipping these null decisions, fewer levels of recursion will be needed, and less states and decisions will need to be stored in the final solution.

Options 2: Store an array of remaining denominations on the State class

To skip over unused denominations, one could instead choose any denomination in the array to represent the next denomination to use. The new state could then store the remaining denominations by copying a sub-array of the previous state's denominations (i.e. after that denomination).

This was conceptually very clean. But it had a practical problem. It gives every state its own array of remaining coin denominations, leading to lots of array copying.

It’s also less memory-efficient, since all states which lie along a feasible branch of the recursion tree are stored in the final solution set.

Option 3: Store the index of the next available denomination on the State class

A third option is to store the array only once, and have the state class store the index in this array of the next available denomination. This would be a very efficient implementation, but a very “dirty” design, because the state class would be closely coupled to the internals of the class holding the array. This would violate the principle of encapsulation.

The trade-off I made

When faced with alternatives, I find it's a good idea to go back to your overall goals.

My first goal was to have an example which illustrated the concepts well. The second approach seemed more elegant (albeit less efficient).

My second goal was to make the library highly reusable. I used this example to improve the flexibility of the library in two ways:

Firstly, I modified most of the generic methods so that they passed the stage variable to the algorithm's methods. This was to improve support for the first of the three options.

Secondly, I made it optional for the set of solutions to store the states and decisions. This improved support for the second option. It enabled ChangeMaker to only store the decisions in the solution set, not the states. This minimised the memory impact of storing the arrays of denominations on the State objects.

A plug for unit testing

Our industry is characterized by a constant flood of techniques with the promise of increasing productivity, simplifying code, and making projects more predictable.

Object-orientation, RAD, functional programming, CMM, product line practices, N-tier development, component-oriented programming, extreme programming, test-driven development, pair programming, dynamic languages, Perl, PHP, Python, Ruby, WPF, LinQ, DLinq, DSL’s… the list is endless.

Who can find the time to investigate all these technologies and their promise? In the face of so many promises, I believe the best attitude is one of open-minded skepticism!

But unit testing has proven itself repeatedly in this project. I can highly recommend it (but beware: it can be a humbling experience, particularly if you pride yourself on your low bug counts!)

Let me confess: I don’t (yet) do test-driven development (i.e. writing the tests before the code it will test). Nor do I write comprehensive tests. But unit testing is not an "all or nothing" technique. You can do it partially and still enjoy many of the benefits. This makes it a relatively simple technique to grow into.

The usual justification for unit testing is that one can quickly and safely refactor code. I believe there are two other important benefits as well:

1. The gap between introducing and finding the bug is much shorter, so one’s intuition about the source of bugs improves.
2. Writing a unit test encourages you to look at the code from the point of view of a consumer of that code.

This second benefit provides an important justification for writing the unit test before writing the code. On the few occasions where I have done this in the past, I have found my designs becoming simpler and more elegant.

A suggestion for the Visual Studio team

The following refactorings would be useful in future:

• convert to generic class
• convert to generic method

Conclusions

I am generally very happy with this experiment in using generics to write reusable code. The code feels elegant to me, which is usually a good sign.

I do have a few concerns though…

Firstly, this elegance has been enabled by a number of the new features in .Net 2.0 – such as generics, generics with where conditions, generic methods and delegates, the yield statement and anonymous methods. These are all great new features with a lot of potential for reducing the amount of code that needs to be written. But they are powerful techniques which many programmers simply won’t bother to learn. I can see the gap widening between the “groks” and the “grok nots” (and C# 3.0 will only worsen the problem).

Secondly, this was a simple application of generics. Nested angle brackets quickly become unreadable, as do lots of type parameters (with the added frustration of the extra typing required). So I wonder how “scalable” the syntax of generics will be.

But what of the original questions I set out to answer?...

Without a doubt!

Generics enabled the model (states and decisions) to be separated from the algorithm (dynamic programming), without placing restrictions on the former. In this sense, generics certainly did make the system easier to model.

But generics weren't directly used to make the states and decisions easier to code. I think there may be further opportunity for generics in this area (but also more risk of failure because of the greater scale and complexity of the problem).

Clearly more experiments are needed...

History

23 July 2006

• Initial version submitted.