|
|
| Home | Products & services | Support & downloads | My account |
 |
 |
Researchers at IBM recently devised the Volume Algorithm which provides approximate solutions to certain classes of linear programming problems. This benchmarking service gives you an opportunity to check whether the Volume Algorithm is suitable for your problems. We have found it very effective for large set partitioning problems. In general, the problems best suited for the Volume Algorithm are tightly constrained (like 0 <= x <= 1). At the moment the code for the Volume Algorithm cannot handle problems with unbounded variables at all. If you want to test drive the Volume Algorithm, just send an email to volumopt@watson.ibm.com with your problem and you will receive a reply with the output of the solution process. Suggestions, wish lists for improving this service are welcome. A motivation for starting this service comes from the lack of a large problem set of hard linear programming problems. As a result recent improvements in hardware and algorithms NETLIB contains too few really hard problems. It is time to create a larger, more varied problem set. In order to create this new problem set each problem submitted to the benchmarking service will be saved, and eventually the more interesting ones will be made publicly available. However, it is easy to opt out if one wants to. Submitters can specify a keyword in their email that causes the system to delete the problem after it has been solved. In this case only the submitter's email address, the size of the problem and the solution time is stored.
Interpreting the output | Contact Person
The submitted problems are solved one at a time on a "first come first serve" basis. For each problem submitted a confirmation email will be sent indicating how many problems are in the queue at the time. The platform The Volume Algorithm will be run on is an IBM RS6000/43P-240 machine with 896M memory and two 604e processors running at 166MHz (only one of the processors is used for the benchmarking). The operating system is AIX 4.3.2. According to the SPEC website the SPECint95 and SPECfp95 values for such a machine are approximately 6.2 and 5.0 respectively. The executable is compiled with "xlc -O3".
If you have a linear programming problem in which every variable is bounded and you wish to submit to the automated benchmarking service, send an email to volumopt@watson.ibm.com. The subject of the email must be "Solve LP". In the body of the email first specify your control commands (see below), then include the problem description in MPS format. If you prefer, instead of including the mps file in the body of your email, you can send it as an attachement. If you choose the attachment method then you can compress your problem file (which must have a ".mps" before compression) using any of the following utilities: compress, gzip, bzip2 and zip. In return to your email you will receive a reply in the same format that you have used (i.e., if you have used, say, a gzip'd attachment then you'll receive the result in a gzip'd attachment). The reply will contain the full output of the Volume Algorithm.
You can specify one control command on each line. A control command consists of a pair of strings, a keyword and a numeric value. Where the keyword indicates a true/false selection, 1 stands for true, 0 stands for false. A sample control command is: "VOL_save_problem 1". Currently the following keywords are accepted:
At the moment the Volume algorithm is geared towards solving minimization problems. Therefore if a maximization problem is submitted then all the objective coefficients are multiplied by -1 before computation starts. At the beginning of the output there are a few OSL messages. OSL is used to parse the MPS input. Afterwards the recognized control commands are shown (this is for the convenience of the submitter). Then information is given at every 100th iteration. A sample output is like this:
600. L = 396.816412, P = 402.288287,
xrc = 7.253824, vu = 1.781949, infeas = 0.003711
Here L (P) is what the current dual (primal) solution
evaluates to (note that the dual solution is always dual feasible,
hence L is a lower bound on the optimum); xrc is the
inner product of the primal solution vector and the reduced cost vector;
vu is the inner product of the "violation vector" (that is,
b-Ax) and the dual vector and finally infeas is the average of the
absolute constraint deviations. The same information is given at the terminating iteration. Finally the running time and the requested solution values are given.
Contact: |
|
