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:
- AUCTION : a standard auction algorithm without optimizations
- AUCTION-SO : an auction algorithm optimized for similar objects
- AUCTION-SOP : an auction algorithm for similar objects and persons
The fourth algorithm solves real-valued transport problems without generating assignment problems. This algorithm, described by Walsh and Dieci in [3], is:
- General auction : a transport-based auction algorithm
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.
- Bertsekas, D.P. Network Optimization: Continuous and Discrete Models. Athena Scientific, Belmont, Massachusetts, 1998.
- Bertsekas, D.P., Castañón, D.A. The auction algorithm for the transportation problem. Annals of Operations Research 20(1): 67-96, 1989.
-
Walsh, J.D., Dieci, L. General auction algorithm for real valued
optimal transport. Preprint,
http://gatech.jdwalsh03.com
, 2016.
Open Source Contributions
-
MATLAB, Octave.
cmdscale
function for the Octave-Forge statistics package.
Research Languages
- C++, C.
- Fortran.
- Python.
- MATLAB, Octave.
- Bash.
- LaTeX, PGF/TikZ.
Operating Systems
- Linux. Debian, Ubuntu, RedHat.
- Microsoft Windows. 7, 8, XP, 95.
- Apple OS. OS X, OS 9, OS 8, OS 7.
- cPanel. Web hosting environment.
- MS-DOS.
Software
- MS Office, LibreOffice.
- MS Visual Studio.
- GIMP, Inkscape.
- GDB.
- Notepad++, Kate.
- Kile, Overleaf.
- SSH, SFTP.
- Webwork.
Other Languages
- HTML, CSS, Javascript, PHP. Website design.
- MySQL. Website database design.
- Joomla. CMS-based website design.
- C#.
- Java.
- Assembly language, machine code. 6502, Sun SPARC.
- BASIC.