Transportation Algorithm in F#, Part 3

After programming all the steps of the algorithm in the last post, the code in Solver.fs now puts it all together. This is a class type that can be instantiated with the problem (namely, the source and destination capacity lists, and the cost matrix) and then runs the different bits of the algorithm until an optimal solution has been found.

The only task of the constructor is to check if the input data make sense. The total source and destination capacity need to be the same, and the dimensions of the matrix need to match with the lengths of source and destination lists.

type Solver(costMatrix: int Microsoft.FSharp.Math.Matrix,
            srcCapacity: int list,
            dstCapacity: int list) =
    (*  To start with, we check if the data makes sense. If the problem
        is not balanced, or if the dimensions of the cost matrix are wrong,
        there's no point in starting the algorithm.     *)
    do if costMatrix.Dimensions <> (List.length srcCapacity, List.length dstCapacity)
        || List.sum srcCapacity <> List.sum dstCapacity then
        failwith "Invalid Data."

The most important bit of the class is the Steps member. What needs to be done here is to step through the different parts of the algorithm, check for optimality, and repeat until an optimal solution is found. A simple looping construct would suffice; I found it quite instructive, though, to be able to see the iterations with their intermediate results. Steps therefore creates a sequence that has all solutions from the initial up to the last, where the last solution in the sequence is the optimal one.

    (*  Create a sequence that gives us one intermediate solution at
        a time. The last element of the sequence is the optimal
        solution                *)
    member s.Steps =
        let rec steps sol =
            seq {
                // current solution = sequence element
                yield sol 
                // find dual values for current solution
                let duals = Dual.calc_dual_values costMatrix sol
                // for dual values, find new entering cell
                match NewBasisCell.find costMatrix duals with
                | Some(new_cell) ->
                    // use stepping stone to find path for new cell
                    let new_path = SteppingStone.find_path new_cell sol
                    // adjust values for path
                    let new_path_adjusted = NewSolution.new_path new_path
                    // from current solution and new cell's path,
                    // make new solution
                    let transformed_solution = NewSolution.transform_basis_solution sol new_path_adjusted 
                    // do it all again, with the new solution
                    yield! steps transformed_solution
                // if there's no entering cell, we're done
                | _ -> ()
            }
        // Initialisation: solution found with the North West corner method
        InitialFeasibleSolution.find_feasible_nwc srcCapacity dstCapacity |> steps

The Solution member goes directly to the end of the sequence, thus returning the optimal solution.

    (*  Go directly to last solution, which is the optimal one 
        -- See http://msdn.microsoft.com/en-us/library/system.linq.enumerable_methods.aspx
        -- for more .NET extension methods that can be used on F# sequences  *)
    member s.Solution =
        System.Linq.Enumerable.Last s.Steps

And finally, there’s a little helper method, where you can feed in a solution (e.g. one that you got out of the sequence returned by Steps) and calculate the total cost associated with that solution.

   (*  Calculate total costs for a given solution  
       -- See http://stackoverflow.com/questions/3912821/f-instance-syntax/3914236#3914236
       -- for use of __.       *)
   member __.Cost(solution: (int*int*int) list) =
       solution |> List.fold (fun acc (r, c, v) -> acc + costMatrix.[r, c] * v) 0

Running it all

Program.fs has a few lines of code that create a Solver and run it with some sample data. The code comes with two sets of data, Sample1.fs has the one used as example here, and Sample2 is a bit bigger.

let solver = Solver.Solver(costMatrix, srcCapacity, dstCapacity)

// Go through all the solutions in the sequence and
// observe the total cost going down. costs has these
// numbers in a list to print or look at in the debugger.
let costs = solver.Steps |> Seq.mapi (fun i s -> (i, solver.Cost s)) |> Seq.toList

Previous

Transportation Algorithm in F#, Part 1 explains the algorithm.

Transportation Algorithm in F#, Part 2 has the F# code for all the steps of the algorithm.