English
资源说明：The RELAX IV code for Minimum Cost Network Flow Problems.
= relax4
http://relax4.rubyforge.org
http://github.com/jdleesmiller/relax4_ruby
{
}[http://travis-ci.org/jdleesmiller/relax4_ruby]
== DESCRIPTION
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 [1], [2]) FOR LINEAR
COST ORDINARY NETWORK FLOW PROBLEMS.
[1] BERTSEKAS, D. P., "A UNIFIED FRAMEWORK FOR PRIMAL-DUAL METHODS ..."
MATHEMATICAL PROGRAMMING, VOL. 32, 1985, PP. 125-145.
[2] 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:
[3] BERTSEKAS, D. P., "LINEAR NETWORK OPTIMIZATION: ALGORITHMS AND CODES"
MIT PRESS, 1991.
[4] 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:
[5] 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:
* http://elib.zib.de/pub/Packages/mathprog/mincost/relax-4
See also:
* http://www-neos.mcs.anl.gov/neos/solvers/lno:RELAX4/RELAX4.html
* http://web.mit.edu/afs/athena.mit.edu/user/d/i/dimitrib/www/RELAX4.txt
== SYNOPSIS
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]
== REQUIREMENTS
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.
== INSTALL
gem install relax4
== DEVELOPMENT
Get the source from github (http://github.com/jdleesmiller/relax4_ruby) and
use bundler to get the development dependencies:
gem install bundler
bundle
rake -T # list development tasks
== TODO
* 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
== HISTORY
1.2.1 20131202
* fixed error with gem installation (wrong path; issue #1)
* now using gemma 3
1.2.0 20110905
* reorganized gem to be consistent with http://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)
1.1.0
* added wrappers for transportation and assignment problems
* updated docs
1.0.5
* fix in previous version didn't quite solve the problem; new fix applied
1.0.4
* fixed apparent bug in ascnt2_ that caused memory corruption or infinite loop
* switched to gemma for basic rake tasks
1.0.3
* now uses RELAX4_UNCAPACITATED by default for uncapacitated problems
* updated docs
1.0.2
* 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
* more tests
1.0.1
* set platform in gemspec to Ruby (not a binary gem)
1.0.0
* first release
== LICENSE
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 (c) 2013 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.
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
