Sometimes, TDD doesn’t flow

I have been using test-driven development since I read Kent Beck’s book on the topic. I loved the book, I tried it, and adopted it, simply because it makes my life easier. It helps me think through what I am trying to achieve, and I like the safety net of having a test suite which tells me exactly what I have broken. It also fits well with the type of code I write, which is usually math-oriented, with nice, tight domain objects.

So when I decided recently to write a C# implementation of the Simplex algorithm, a classic method to resolve linear programming optimization problems, I expected a walk in the park.

(Side note:I am aware that re-implementing the Simplex is pointless, I am doing this as an exercise/experiment)

Turns out, I was mistaken. I have been struggling with this project pretty much from the beginning, and unit testing hasn’t really helped so far. Unfortunately, I didn’t reach a point where I fully understand what it is that is not flowing, but I decided I would share some of the problems I encountered. Maybe brighter minds than me can help me see what I am doing wrong!

A bit of context

If you read through the algorithm explanation, you will realize that it is very matrix-oriented. The classic way to represent and solve a linear programming problem is through the “Simplex Tableau” – any LP problem can be expressed as a tableau like the one displayed below, and a succession of pivots on the rows of the tableau will either yield the optimum solution, or conclude that there isn’t such a solution.

Variable 1 Variable 2 Right Hand Side  
___ ___ ___ ___
Constraint 1 1.0 2.5 3.0
Constraint 2 0.0 4.5 2.0
Relative Cost 5.5 1.5 3.5

To decide what transformation to apply to the tableau, the algorithm looks at the relative cost row to pick candidate variables/columns, and at the right-hand side to pick which of the candidate variable to choose and apply the transformation to.

Given the matrix-like structure of the tableau, it is no surprise, then, than the algorithm has traditionally been implemented as a long iterative procedure which modifies an array of doubles.

What’s the problem?

Here are some of the issues I ran into when attempting to implement it in an object-oriented fashion, using test-driven development.

Current conclusion

What bugs me here is not that I can’t find a solution: my current solution works (or almost works…). What bugs me is that I expected this problem to be a very good fit for object-oriented design and TDD, and it has been a struggle every step of the way – and I can’t pinpoint what I did wrong. Had I taken an old-school, procedural approach, modifying an array step by step, I would have been done in an afternoon. And – I just don’t like the way my code looks, it doesn’t feel like a good design.

In the end, I don’t think TDD is to blame. TDD works great if you have good objects, and my problem here is that I didn’t really manage to break down the problem in smaller, well-encapsulated objects. This may have to do with the 2 dimensional array, which is hard to “divide”, but I suspect part of the problem is that drifted off the spirit of TDD: rather than write one test at a time, from requirements, I started with strong pre-conceptions of what the solution would look like, heavily biased by the existing procedural implementations I had seen before.

So what’s next? First, finish off the implementation as I started it, in hopes that the struggle will shed some light. And then, start again, around different ideas. One such idea is to re-write the algorithm not as a “master” procedure, but rather, as a generator of steps; the completion of each step would return what next step should be performed, and the outer-most structure would have no knowledge of what to do, but simply store and execute each step. The other thought is to ditch the representation of the Tableau as a collection of rows, and simply make it a collection of coefficients attached to a variable and a constraint.

Comments

Have a comment or a question? Ping me on Twitter, or use the comments section!