Software

At its heart, programming is a communications skill. Writing software encompasses many of my creative interests: numerical problem solving, writing, page layout, and graphic design. It also allows me to test my ability to articulate ideas in a concrete, meaningful form.

Most often, I write software that confirms and expands my understanding of mathematics, but I have a significant amount of programming experience outside my professional career. I first learned to program when I was twelve, writing video games for my own enjoyment. Later, I extended those skills doing small-press tabletop game design. I also design web pages, build desktop computers, and manage websites and small networks. These activities have provided me with a variety of challenges while simultaneously broadening my skill set.


The AUCTION ALGORITHMS IN C++ Project

The auction method was developed by Dimitri Bertsekas in the late 1970s as a relaxation technique for solving integer-valued assignment problems [1]. It resembles a competitive bidding process, where unsatisfied persons (bidders) attempt to claim the objects (lots) offering the best value. In 1989, Bertsekas and David Castañón found a way to apply the auction method to certain transport problems [2]. By transforming integer-valued transport problems into assignment problems, the auction method can be extended to compute optimal transport solutions. In 2016, J.D. Walsh and Luca Dieci generalized the work of Bertsekas and Castañón, developing a more general auction method that can be applied directly to real-valued transport problems [3].

All of these auction methods were described in detailed journal articles, and software implementations of the original auction method for integer-valued assignment are commonly available. However, implementations for integer-valued transport are much more rare. Before now, no implementation of the general auction method for real-valued transport has been published.

The AUCTION ALGORITHMS IN C++ project code was created to fill that gap. It implements four auction algorithms for optimal transport. Three of the algorithms solve integer-based transport problems by expanding them into corresponding assignment problems and applying various optimizing techniques to the standard auction algorithm. These three algorithms, described by Bertsekas and Castañón in [2], are:

The fourth algorithm solves real-valued transport problems without generating assignment problems. This algorithm, described by Walsh and Dieci in [3], is:

The general auction is so-named because it works on a broader class of problems than the standard assignment-based auction.

The AUCTION ALGORITHMS IN C++ project is designed as a teaching tool, to help readers of the journal articles to understand how the various auction algorithms can be implemented in practice. With this goal in mind, the source code favors clarity over efficiency. Error checking is limited. The implementation relies heavily on the Standard Library and a large number of (relatively) simple class objects.

That said, AUCTION is also a working project. The software has been optimized over multiple iterations, and variations of it are currently being applied to research in computational optimal transport. One can use the project as-is to exactly solve integer-valued transport problems and approximate solutions to real-valued problems.

Download AUCTION project files
  1. Bertsekas, D.P. Network Optimization: Continuous and Discrete Models. Athena Scientific, Belmont, Massachusetts, 1998.
  2. Bertsekas, D.P., Castañón, D.A. The auction algorithm for the transportation problem. Annals of Operations Research 20(1): 67-96, 1989.
  3. Walsh, J.D., Dieci, L. General auction algorithm for real valued optimal transport. Preprint, http://gatech.jdwalsh03.com, 2016.

Open Source Contributions

Download cmdscale source code

Research Languages


Operating Systems


Software


Other Languages