Linear assignment problems, part II

In a previous post I talked a bit about the linear assignment problem:  finding the minimum cost matching in a bipartite graph.  In my next post I will give a simple self-contained C# program for solving LAP based on some Fortran code from my colleague Rainer Burkard.  First a few notes and disclaimers!

The input to the code is a matrix which represents the adjacency matrix of the graph.  In my application (solving quadratic assignment problems) I am concerned with input matrices that are relatively small and dense.   The code is a port of Fortran code by Burkard and Ulrich Derigs:  Assignment and matching problems: Solution methods with Fortran programs, volume 184 of Lecture Notes in Economics and Mathematical Systems.  Springer, Berlin, 1980.  The original code is available on the QAPLIB site.  Rainer has given me permission to post this code, although if you look at the terms on the original you will see that it is freely distributable.  This code is offered under the same conditions and I make no claims about its correctness, value, etc.  But it works okay for me.

My port is relatively “conservative” in that I have tried to retain the original structure and flow as much as possible because I don’t want to introduce any bugs.  I want to keep the implementation clean, so like many numerical optimization codes there isn’t much input validation.  I have chosen to use arrays rather than trying to encapsulate the input and output into matrix and vector classes.  I kept it simple so you can adapt it to your needs.

Lastly, I wanted to mention that this is not the most efficient LAP solver available.  At the time I wrote my thesis the fastest code over the domain I was working on was the code of Jonker and Volgenant, which is available on this site.  I notice that the code is used by others as well, see here and here.  This code is really quite slick and I had a great experience working with it all those years ago.  It’s not hard to port it over to C#, so go for it!

What makes a good software developer

A colleague asked me to jot down some thoughts on what makes a good developer at Microsoft.  This is by no means complete, but three statements come to mind when I think about strong developers:

  • We are engineers, not hackers.
  • A strong dev should be able to fill any engineering role in the company.
  • Senior devs improve their teams by action and by example.
  • We are engineers, not hackers.  My dev manager in Project (my previous team) said this years ago and it has stuck with me ever since.  Engineering is a craft whereas hacking is a hobby, and I expect a Microsoft dev to seek to become a master of the craft.  Engineers understand common patterns underlying the problems they solve and seek to make their code predictable and reliable.  (This doesn’t suck the creativity or joy out of the process, rather it should liberate us.)  For an engineer, process is not an end to itself but a tool for arriving at solid designs and trustworthy code.  Engineers take great pride in their creations and stand behind them.
    Engineering practices apply to all stages of software development.  In the design phase I expect a structured approach that leads to a design that clearly meets the needs described in the spec.  The deliverable is a design doc that describes how the feature is implemented.  A good design doc is an aid to the developer, his/her peers, as well as Test/PM.  I don’t want to get into details about what makes a good design doc, but it should describe the primary design and implementation challenges and how they are addressed, and why other reasonable approaches were rejected.  On a services team it’s particularly important to think of the impact the feature has on setup, deployment, and monitoring, and account for these early.
    Everyone has things to say about coding guidelines, so I won’t dwell on them much here.  I assembled a set of team-wide guidelines and I expect those to be followed.  I always look for simplicity and consistency.  As a services team I particularly value unit tests and tracing. 
    Finally, I expect a positive handoff to test.  By this I mean a detailed TRD (test release document) that describes what the feature does, what works, what doesn’t work, and suggestions for testing the feature.  I expect code to be structured so that it is easy to test as possible.  I don’t particularly care for metrics based on the number of bugs a dev fixes.  I value developers who prevent bugs from happening in the first place, and it’s easiest to do this in the earliest stages of the project before any code is written.  This begs the question of how do we measure the quality of a feature relative to the time spent on it.  I don’t have easy answers except to say that if leads and peers are involved in the entire development process, it is easier to come to a collective understanding of how challenging a feature is and how well the developer has done at implementing it.  In other words, it comes down to judgment.
    A strong dev should be able to fill any engineering role in the company.   The statement applies in two ways.  First, a dev should be able to wear their "PM hat" or "test hat" and operate effectively within that role.  Perhaps this is statement is too "old school Microsoft", and I certainly don’t mean to detract from the roles of Test and PM.  After all, Test and PM are also engineering disciplines.   I simply mean that devs have a deep understanding of customer requirements and are able to make their own assessments of the relative priority of features and work items, and can make suggestions as to how to improve the experience.  Devs should be able to be ruthless testers of their own (and their teammates) features and provide actionable feedback that results in improvements.  They write unit tests, which guarantee a certain level of quality.  Having the ability to operate in another role also prevents a dev from becoming blocked, and provides broader perspectives which assist devs in interacting with their Test and PM counterparts.  Everyone understands where everyone else is coming from, and that makes for a more enjoyable working environment.
    Secondly the statement means that a dev is not dependent on domain-specific knowledge to be effective.  A deep understanding of specific technologies, code bases, and design patterns is essential for good engineers.  But a strong dev is not a "one trick pony" that can only work in one area (though they may prefer to do so, and may be asked to do so from time to time).  A dev has technical depth, but also technical breadth, which allows them to see how their code functions to serve a larger purpose.  I’d like to think that I could be dropped into the middle of Windows, and though I would probably hate it, I would be effective.
    Senior devs improve their teams by action and by example.  There are only so many hours in a day, so at a certain point it becomes more difficult to provide more value by simply coding more or working longer.  Actions that make others better have a compounding benefit that can have a huge impact over time.  Most of us can think of old timers that seem to have an awesome level of productivity, to the extent that it’s hard to understand how they can be that effective.  I suggest that in most cases, these old timers have mastered the art of making others better.  First, they typically do not worry themselves about things like "scope" or "area".  Making Microsoft better is their "area", and that extends to fixing bugs in other dev’s code, fixing build problems, improving processes, giving feedback to other teams.  Master devs share knowledge, through conversations, whiteboard sessions, documents, blogs.  They cringe when they hear people talk about "their code"; it’s "our code".  Their movements are not hurried, but always with purpose.   They’ve got time for other people, and still get their work done.  They’re able to do this because they identify patterns in their work and automate them, either by defining a design pattern, or by architecting the system appropriately, or by writing tools that do their work for them.  Then they share this knowledge with the rest of the team and build a culture where others do the same.  Lastly, they continually seek new opportunities to make themselves and their team better.  These opportunities come up all the time in a product cycle; a master dev spots them first and steps in to fill a need, for example by forwarding an email to someone who knows the answer; seeing that a new platform component could help implement features in two different projects; adding a new unit test that enforces a coding or stylistic convention.
    I love it when devs are passionate about delivering something that works and is useful!

Linear assignment problems, part I

I’m going to devote a few posts to my thesis topic, the quadratic assignment problem.  Quadratic assignment problems are a type of matching problem that are NP hard and have some interesting applications.  I’ll start out by describing linear assignment problems, which are simpler but still fun.

As the name suggests, in a linear assignment problem objects in one set are to be assigned to an equal number of objects in a second set. The cost of assigning objects in the first set to objects in the second set are given, and the objective is to find the assignment that minimizes the total assignment cost.  For example, the problem may be to assign workers to jobs so as to minimize the total amount of working time.  A more formal description of the problem can be found on this page (and I recommend the book, BTW).

LAP can also be posed as the problem of finding the minimum cost matching on a bipartite graph.  For this reason, in algorithms texts this problem is also sometimes referred to as “minimum cost weighted bipartite matching”.  LAPs are linear programs and so they can be solved in polynomial time.  As the wikipedia article on the problem states, there are algorithms that take advantage of the special structure of LAP to solve them more efficiently than general purpose LP solvers.

Next time I’ll go through one possible solution approach for LAP.

Why writing software is like moving

Me and my brother helped my mom move over the weekend.  Advice for movers and software developers:

  • Don’t move anything you don’t actually want or need.  Throw out your SAT study guide, your old copies of Maxim, the Michigan starter jacket, the annotated James Joyce that you’ve never read but impresses people.
  • Invite the right number of people.  It’s a sinking feeling to show up and find out that you and your friend are going to move the whole house.  It’s fun, but not terribly productive to show up and find 7 other people there – you end up spending a lot of time paging through other people’s books, or drinking, or both.
  • Pack before people show up.  Nothing kills me more than showing up to help a friend move to find that they haven’t done the prep work.  I don’t want to show up at 9:00 to find that I’m supposed to help you pack your t-shirts.
  • Figure out how to load the truck before lifting anything.  If it turns out that you don’t have enough room then you will waste a lot of time moving stuff around, or worse yet, leaving stuff behind.  Taking more than one trip is disastrous.  That second trip is never very fun.
  • Wrap fragile items, or items with sharp edges.  It’s worth the extra time.  Once the truck starts moving objects will tend to bump into each other so it’s wise to protect the ones that might break.
  • Do the heavy stuff first.  That way you’ll know if you’ve got enough room in the truck, besides, it’s better for morale.
  • Don’t try to do it all by yourself.  Yes, you have superhuman strength, and that ottoman isn’t all that heavy.  But if you’ve got help then why not take advantage.
  • Spring for the extra five bucks and unhook the dolly.  Then you can stack up all those boxes of books and move them in one trip.
  • When you get to the new place, just worry about getting the boxes out of the truck and into the right rooms.  Worry about arranging the furniture and unpacking boxes later.

And – the appropriate payment is always a six pack.

Management advice from Satchel Paige

Actually it’s not management advice — somehow I doubt Satchel Paige would have much patience for that sort of thing.  I don’t really like baseball, but I do like the personalities (particularly from the past) and the stats.  When I was growing up we had an old baseball stats reference on the bookshelf and I used to pore over the numbers, why I don’t really know.

Anyway, Satchel Paige said: “Don’t look back. Something might be gaining on you.” I think that’s pretty good advice.

Here are a bunch of other Satchel Paige quotes.