Ruby interface for the RELAX IV code for minimum cost network flow problems, which include transportation problems and assignment problems. In the words of the code's authors:
PURPOSE - THIS ROUTINE IMPLEMENTS THE RELAXATION METHOD OF BERTSEKAS AND TSENG (SEE , ) FOR LINEAR COST ORDINARY NETWORK FLOW PROBLEMS.  BERTSEKAS, D. P., "A UNIFIED FRAMEWORK FOR PRIMAL-DUAL METHODS ..." MATHEMATICAL PROGRAMMING, VOL. 32, 1985, PP. 125-145.  BERTSEKAS, D. P., AND TSENG, P., "RELAXATION METHODS FOR MINIMUM COST ..." OPERATIONS RESEARCH, VOL. 26, 1988, PP. 93-114. THE RELAXATION METHOD IS ALSO DESCRIBED IN THE BOOKS:  BERTSEKAS, D. P., "LINEAR NETWORK OPTIMIZATION: ALGORITHMS AND CODES" MIT PRESS, 1991.  BERTSEKAS, D. P. AND TSITSIKLIS, J. N., "PARALLEL AND DISTRIBUTED COMPUTATION: NUMERICAL METHODS", PRENTICE-HALL, 1989. THIS CODE WAS WRITTEN BY DIMITRI P. BERTSEKAS AND PAUL TSENG, WITH A CONTRIBUTION BY JONATHAN ECKSTEIN IN THE PHASE II INITIALIZATION. THE ROUTINE AUCTION WAS WRITTEN BY DIMITRI P. BERTSEKAS AND IS BASED ON THE METHOD DESCRIBED IN THE PAPER:  BERTSEKAS, D. P., "AN AUCTION/SEQUENTIAL SHORTEST PATH ALGORITHM FOR THE MINIMUM COST FLOW PROBLEM", LIDS REPORT P-2146, MIT, NOV. 1992.
The original source can be downloaded from:
require 'rubygems' require 'relax4'
A general network flow problem:
# # From Figure 29.3 of Cormen, Leiserson, Rivest and Stein (2001). # Introduction to Algorithms, 2nd Edition. # # (2) edges are directed ((1,2), (1,3), ...) # / | \ each edge has a cost and a capacity # / | \ # (1) | (4) the aim is to find the flow on each edge such that we # \ | / move four units of flow from (1) to (4) at minimum cost # \ | / # (3) # Relax4.solve( :demands => [-4, 0, 0, 4], :start_nodes => [ 1, 1, 2, 2, 3], :end_nodes => [ 2, 3, 3, 4, 4], :costs => [ 2, 5, 3, 7, 1], :capacities => [ 5, 2, 1, 2, 4]) #=> [2, 2, 1, 1, 3]
A lower-level interface is also available; see the docs for the Relax4 module.
A transportation problem:
# # From http://www.me.utexas.edu/~jensen/models/network/net8.html # A nil cost means that the flow is not allowed. # Relax4.solve_transportation_problem( :costs => [[ 3, 1, nil], [ 4, 2, 4], [ nil, 3, 3]], :demands => [ 7, 3, 5], :supplies => [ 5, 7, 3]) #=> [[2, 3, 0], [5, 0, 2], [0, 0, 3]]
An assignment problem:
# # From http://www.me.utexas.edu/~jensen/models/network/net9.html # A nil cost means that the assignment is not allowed. # Relax4.solve_assignment_problem(:costs => [[ nil, 8, 6, 12, 1], [ 15, 12, 7, nil, 10], [ 10, nil, 5, 14, nil], [ 12, nil, 12, 16, 15], [ 18, 17, 14, nil, 13]]) #=> [4, 2, 3, 0, 1]
Has been tested on:
ruby 1.8.7 (2011-06-30 patchlevel 352) [i686-linux] and [x86_64-linux]
ruby 1.9.2p290 (2011-07-09 revision 32553) [i686-linux] and [x86_64-linux]
The following packages were required to install with the system ruby on Ubuntu 10.04:
ruby, ruby-dev, rubygems
The bindings were generated with f2c (FORTRAN to C converter) and SWIG (www.swig.org), but you don't need either to build the gem.
gem install relax4
Get the source from github (github.com/jdleesmiller/relax4_ruby) and use bundler to get the development dependencies:
gem install bundler bundle rake -T # list development tasks
there are some hard-coded parameters that could be exposed
problem state is global (cf. FORTRAN), so can have only one instance at a time
reorganized gem to be consistent with guides.rubygems.org/c-extensions
now using gemma 2 for development tasks
added major, minor and patch version constants (no other API changes)
wrapper regenerated with swig 2.0.4 (was 1.3.38)
added wrappers for transportation and assignment problems
fix in previous version didn't quite solve the problem; new fix applied
fixed apparent bug in ascnt2_ that caused memory corruption or infinite loop
switched to gemma for basic rake tasks
now uses RELAX4_UNCAPACITATED by default for uncapacitated problems
added RELAX4_UNCAPACITATED; setting capacities to RELAX4_DEFAULT_LARGE to represent uncapacitated arcs was found to cause overflow for some problems
now have only the necessary parts of the standard f2c headers
set platform in gemspec to Ruby (not a binary gem)
The authors of RELAX IV (D.P. Bertsekas and P. Tseng) released the code with the following user guidelines:
THIS ROUTINE IS IN THE PUBLIC DOMAIN TO BE USED ONLY FOR RESEARCH PURPOSES. IT CANNOT BE USED AS PART OF A COMMERCIAL PRODUCT, OR TO SATISFY IN ANY PART COMMERCIAL DELIVERY REQUIREMENTS TO GOVERNMENT OR INDUSTRY, WITHOUT PRIOR AGREEMENT WITH THE AUTHORS. USERS ARE REQUESTED TO ACKNOWLEDGE THE AUTHORSHIP OF THE CODE, AND THE RELAXATION METHOD. THEY SHOULD ALSO REGISTER WITH THE AUTHORS TO RECEIVE UPDATES AND SUBSEQUENT RELEASES.
The main author of the RELAX IV code is:
DIMITRI P. BERTSEKAS LABORATORY FOR INFORMATION AND DECISION SYSTEMS MASSACHUSETTS INSTITUTE OF TECHNOLOGY CAMBRIDGE, MA 02139 (617) 253-7267, DIMITRIB@MIT.EDU
The code for these Ruby bindings is released under the MIT license.
Copyright © 2010 John Lees-Miller
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the 'Software'), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.