retroLP:

Installation:

Simply put all the files into a directory, and compile
with a C++ compiler (of late I have been using g++
(gcc) version 3.2.2),  using the make file
`simplex.mak'. The executable retroLP should
result. This is free software in the sense of the GNU
General Public License. See the file gpl.txt.

Usage:

  Quick Start:
 
The easiest way to use retroLP is `retroLP file.mps'
where file.mps is a problem description in the MPS
format.  To test your program there are three problems
from the NETLIB collection: adlittle.mps (optimal
value = 2.254949e+05), kb2.mps (optimal value =
-1.749900e+03), and forplan.mps (opotimal solution
-6.642189e+02).  retroLP pretty much takes all
standard MPS representations for LINEAR PROGRAMS with
some exceptions (see below). retroLP with the built in
program parameters is pretty robust and will solve
(eventually) almost any problem that fits in your
computer's memory. However, it is an implementation of
the  standard method of the simplex algorithm, and is
designed for dense problems. Large sparse problems can
run for quite a while.

  Changing Program Parameters:

You can tune the algorithm, or use it for 
experimentation by modifying the program's 
parameters. More or less following John Forrest's 
approach in Clp, you can modify the parameters 
interactively, with arguments on the command line, 
or via a parameter file.

Some examples are:

`retroLP -ccr 1 file.mps' solves file.mps using the
classical (Dantzig) column choice rule instead of the
default, steepest edge method. This is an example of
changing parameters using arguments on the command
line.

'retroLP -- file.mps' puts you in the interactive
mode. You then modify the parameters by just typing in
commands (without leading dashes).  For example if you
now enter `max yes' retroLP will maximize rather than
the default minimization. The command `quit' gets you
back.

Finally, `retroLP -pfile p_file.txt' will change
parameters based on the parameter file p_file.txt. So,
for example, if p_file.txt looks like:

max on 
ccr 1

retroLP will solve file.mps as a maximization problem
using the classical column choice rule.

`retroLP -help' lists the parameters with a short
description.

'retroLP -help ccr' describes the ccr (column choice
rule) parameter, giving the a short description, the
current value, the default value, and bounds on the
appropriate value.

`retroLP -help all' gives the previous information for
all the parameters.

The file `parameters.txt' in this distribution is
essentially `help all'.

A few remarks on all this. The parameter names are
case insensitive.  CCR, Ccr, and ccr all do the same
thing. The name is preceded by a dash as an argument
of the command line. They must be contiguous with no
space betweeen the dash and the name. The name and the
value, if any, are separated by spaces with out
equality signs or any such.  Boolean parameter values
can be on or off, true or false, t or f, yes or no.
And the case doesn't matter. File names; i.e., MPS
files and parameter files are expected to start with
an  alphabetic character. It is probably better to not
modify the float parameters unless you understand the
code pretty well. The values you set are lost when you
leave the program. Each time you start the program the
parameters are set to their default values. If you
want to save them for future runs, put them in a
parameter file.

MPS Problem Description Files:

MPS representations of linear programming problems are
probably the most general, in the sense that most
solvers will take them. See: guide at

http://www-fp.mcs.anl.gov/otc/Guide/OptWeb/continuous/
constrained/linearprog/mps.html

for details.

The MPS format is somewhat ambiguous. We follow the
MINOS conventions (Bruce A. Murtagh and Michael A.
Saunders, MINOS 5.5 USER'S GUIDE, Technical Report SOL
83-20R Revised July, 1998. We make the following
additional assumptions
 
1. There is exactly one objective function 

2. It corresponds to the FIRST row with code "N"
 
3. There is exactly one RHS
 
4. The right hand side may be empty (all zero), but 
   "RHS" must appear; We assume only one RHS; if 
   there is more    than one, we only look at the first,
 
5. If there are any non-zero elements of the RHS the 
   column of elements must be given a name
.  
6. The bounds section is optional
 
7. Lines in the bounds section for free ("FR") and lower 
   bound to -infinity ("MI") should not have numeric 
   values
 
8. The BOUNDS section is optional, but if there is one, 
   we assume there is only one RHS; if there is more 
   than one, we only look at the first.

5/15/05

