NEOS Server Home

NEOS Interfaces to RELAX4

Sample Submissions
WWW Form - Email - XML-RPC

RELAX4

RELAX4 solves linear minimum-cost flow problems and returns to the user information about the optimization problem, the solution process, and the solution.

The NEOS Server interface to RELAX4 will accept inputs in either the DIMACS minimum-cost flow format or the RELAX4 format. The code can be used for any non-commercial research purposes and for comparative test purposes but cannot be used to satisfy commercial deliverables to government or industry without prior agreement with the authors.

RELAX4 is a solver for minimum cost flow problems that combines the RELAX code (see two papers by Bertsekas and Tseng (1988)) with an initialization based on an auction/sequential shortest path algorithm. This initialization is shown to be extremely helpful in speeding up the solution of difficult problems, involving for example long augmenting paths, for which the relaxation method has been known to be slow. On the other hand, this initialization procedure does not significantly deteriorate the performance of the relaxation method for the types of problems where it has been known to be very fast.

The original RELAX4 solver for minimum-cost flow problems was written by Dimitri Bertsekas (Massachusetts Institute of Technology) and Paul Tseng (University of Washington).

The RELAX4 code is publicly available via: http://web.mit.edu/dimitrib/www/RELAX4.txt

References


Using the NEOS Server for RELAX4/DIMACS


To use RELAX4 to solve a minimum-cost network flow problem, the user must submit a problem in DIMACS standard format.

Web Submission Form
DIMACS File
Enter the location of the DIMACS input file
INIT:
Select the method for the initial solution. Relax-IV is the default initialization. The auction/shortest path subroutine, which is used for getting the initial price-flow pair, is recommended for difficult problems where the default initialization yields long solution times.
Relax-IV
Auction/Shortest
Comments
Additional Settings
Dry run: generate job XML instead of submitting it to NEOS
Short Priority: submit to higher priority queue with maximum CPU time of 5 minutes
E-Mail address:
Please do not click the 'Submit to NEOS' button more than once.