AUCTION ALGORITHMS IN C++ v1.0.0

Synopsis

The auction method was developed by Dimitri Bertsekas in the late 1970s as a relaxation technique for solving integer-valued assignment problems. 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. 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.

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++ software project 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, are:

AUCTION     : standard auction algorithm without optimizations  
AUCTION-SO  : auction algorithm optimized for similar objects  
AUCTION-SOP : 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, is:

General auction : 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 (see "References" below) to understand how the various auction algorithms can be implemented in practice. With this goal in mind, the source code, provided in C++, 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 ALGORITHMS is also a working project. The code has been optimized over multiple iterations, and variations of it are currently being applied to research in computational optimal transport. Using the file format given in <graph/readme.txt> and the software provided as <auction.out>, one can use the project as-is to exactly solve integer-valued transport problems and approximate solutions to real-valued problems.

Those problems can be quite large; for example, see the graph template <graph/test/R-5000-45000-31500000-99.txt>. Fully constructed, the graph file includes 31.5 million arcs and requires 0.8 GB of storage space. Using a 2.27 GHz i5 processor, the general auction default settings can approximate the solution (within 3e-8 percent) in less than a minute. The main limitation in this case is storage; <graph.out> requires over 5 GB of memory to generate the graph file, and <auction.out> uses 2.7 GB of memory when solving it.

This file is only one piece of the AUCTION ALGORITHMS IN C++ software project. See the document <filelist.txt>, found in the parent folder of <graph>, for a full list of the project files. If <filelist.txt> or any other file is missing, go to http://github.com/jdwalsh03/auction/ to download the complete project.

---

Motivation

The AUCTION ALGORITHMS IN C++ project grew out of my own exploration of the algorithms described by Bertsekas and Castañón. I found very few online examples of software applying the auction method, and none that were clearly designed for optimal transport. A few projects showed how to apply the auction algorithm for integer-based assignment problems. The most helpful, for me, was the original software by Dimitri Bertsekas, written using Fortran 77; see [1] in "References" (below). However, it only covers the integer-based assignment problem.

In the end, I built my own implementation of the auction algorithms of Bertsekas and Castañón, first in Python, and later in C++. The process of writing and understanding those algorithms, and my desire to apply the auction method to real-valued transport, led to the general auction method described in the Walsh and Dieci paper; see [4] in "References" for more information.

I hope this project will save other researchers the work (and missteps) I went through when translating the mathematics of the auction algorithms into effective computer code. I also believe here is a lot be be gained from reading the nitty-gritty details of each implementation, and comparing the performance of the various algorithms. After all, learning how algorithms function on a computer is a necessary prerequisite for understanding their underlying mathematics.

--JD

---

Installation

The project is ready to compile as-is, provided certain dependencies are satisfied. Your computer should have the following installed:

• C++ Standard Library with C++11 support (originally compiled with libstdc++ version 4.9.2)
• g++ compiler version 4.7 or higher (originally compiled with g++ version 4.9.2)
• GNU Make (originally compiled using version 4.0)

See below for information on alternative development environments.

To install the full project in UNIX-based environments (e.g. Linux, MacOS, Cygwin):

Open a terminal window in the top directory of the AUCTION ALGORITHMS IN C++ software project and run the installation script with the command:

$ ./install.sh

(Depending on how the project was packaged, <install.sh> may need to be given permission to execute.) The install script will create the programs <auction.out> and <graph/graph.out>, build a set of example graphs, and place those graphs in the <test> folder.

To install the full project in more generic environments:

1. Compile <graph.out> by entering the <graph> folder and calling make.
2. Build one or more graphs: 1. Choose a graph template XXX.txt from <graph/test/> 2. In the <graph> folder, run the command
   $ ./graph.out -l XXX.txt 3. Move the resulting file XXX.txt to a suitable location (this documentation assumes graphs are in <test>)
3. Compile <auction.out> by calling make from the top directory.

---

Installation Alternatives

The program <auction.out> can be built directly by opening a terminal window in the top directory and typing one of the following commands:

make       : builds an optimized version of the executable <main.out>
make check : checks code for various warning conditions and builds the
              executable <main.out> with built-in debugging symbols  
make debug : builds the executable <main.out> with built-in debugging symbols  
make gprof : builds a custom version of the executable, <mainpg.out>, which
             generates performance analysis data

Note: The project includes two additional (phony) commands that may be useful:

make clean : deletes object files and dependency tracking files for a clean
             recompile of <auction.out>
make wipe  : deletes object files, dependency files, executables, and output
             files from callgrind, gprof, and memtest

The software should compile in any development environment with C++11 support, but the makefiles may require revision. For example, the project can be built with clang++ version 3.8 by changing the compiler declarations (lines 4 and 5) in the makefiles.

Additional graphs can be constructed using the program <graph/graph.out>; see the file <graph/readme.txt> for details on this.

---

Auction Program Examples

Use the general auction method to compute the primal and dual solutions for the graph given in the file <test/R-0500-4500-315000-09.txt>:

$ ./auction.out -l ./test/R-0500-4500-315000-09.txt

Compute both solutions for the file <test/I-0100-0100-001400-09.txt> with each one of the four auction algorithms:

$ ./auction.out -l ./test/I-0100-0100-001400-09.txt -a -g -o -p

Apply the general auction method to <test/R-0100-0100-010000-99.txt>, using the minimum epsilon value 1.0, with verbose command line output. Save the resulting graph, including flows, to the file <result.txt>:

$ ./auction.out -l ./test/R-0100-0100-010000-99.txt -s ./result.txt -v

---

Auction Program <auction.out> Options

-a   : perform assignment auction  
-g   : perform general auction  
-l S : load and process graph file S  
-m # : maximum auction step size [requires # > 0]  
-n # : minimum auction step size [requires #