ROSE
----
INTRODUCTION
The ROSE (Reformulation/Optimization Software Engine) is a software
for performing symbolic reformulations to Mathematical Programs
(MP). MPs are formal representations of optimization problems, and
reformulations could be defined as rewriting systems taking MPs to
other MPs which also conserve some property, such as e.g. the set of
optima.
The ROSE is usually used as an AMPL solver, and is itself a collection
of sub-solvers (most of which perform either some symbolic
reformulation or analysis task). Once a model (with data) has been
loaded into the AMPL workspace, the user types
option solver roseamp;
option roseamp_options "mainsolver=N [other options]";
solve;
to call ROSE. ROSE's subsolvers are selected through an ordinal
N. Typing "roseamp" from the shell command line will list the
subsolvers that have built in the locally installed systems.
Originally, we distributed a ROSE system with many numerical solvers
as well as symbolic reformulators. We eventually made the decision of
limiting ROSE to what it does best - reformulations only. Thus, you
might find some options which refer to solvers that have are not
actually present (sorry).
MPs can be classified in two types: flat and structured. Flat MPs are
those whose constraints are not indexed and whose variables consist of
one symbol only, indexed by a scalar. Numerical solvers usually
require flat MPs as input. Structured MPs allow variables and
constraints to be quantified over complicated set structures. AMPL
itself takes structured MPs as input. AMPL, however, does not allow
solvers either to access the structured MP or to change the MP
internally. Thus, ROSE's action is usually limited to reading a flat
MP and outputting a text-formatted version of the (reformulated) flat
MP.
ROSE uses the Ev3 library (developed by the same team and distributed
according to the same license as ROSE) in order to store and
reformulate mathematical expressions occurring in MPs. Expressions are
represented as n-ary trees, where leaf nodes correspond to variables
and constants (0-ary operators) and non-leaf nodes with n subnodes
correspond to n-ary operators. An arc (u,v) occurs in an expression
tree if v is an argument of the operator u. See Ev3/ for more details.
INSTALLATION
Uncompress the ROSE archive, enter the directory (either rose/ or
rose-x.y/) and type "make". "make install" will copy some binaries in
/usr/local/bin (you need to be root for this). The examples in
examples/ rely on rose, roseamp and ampl being installed somewhere in
your path.
SOLVERS
ROSE consists of a collection of (numerical) solvers and
reformulators. Most reformulator names are prefixed by a capital
letter 'R'. Solvers solve a problem numerically; reformulators operate
on the symbolic structure of the instance to output a different
representation (e.g. a relaxation, or an input format for a different
software).
In this distribution all numerical solvers have been disabled (most of
them require different subsolvers, some of which are not free).
Solver/Reformulator list:
- gomory: numerical solver, disabled
- limitedbranch: numerical solver, disabled
- localbranch: numerical solver, disabled
- null: the null solver (use only if developing ROSE)
- Rcdd: reformulator, transforms an LP into an inequality
representation input file incdd.ine for the CDD software package
- Rconvexifier: reformulator, outputs a convex relaxation of the
problem in the output file Rconvexifier_out.ros
- Rconvexifiermod: reformulator, outputs a pair of AMPL files
Rconvexifier_out.mod and Rconvexifier_out.dat encoding a linear
relaxation of the problem
- Rcopy: reformulator, creates a new, identical problem in memory (use
only if developing new solvers within ROSE)
- Rdisaggr: reformulator, incomplete, don't use
- Rfbbtfp: reformulator, outputs a .dat file for use within a project
for testing FBBT by fixed points (the .mod is not output, this
reformulator is only useful to participants to that specific project)
- Roa: reformulator, incomplete
- Rporta: reformulator, transforms an LP into an inequality
representation input file inporta.ieq for the PORTA software package
- Rprintdat: reformulator, outputs an LP into a pair of AMPL files
Rprintdat.mod and Rprintdat.dat
- Rprint: reformulator, prints the problem to screen [DEFAULT]
- Rprintmod: reformulator, outputs a problem into an AMPL file
Rprintmod_out.mod
- Rprintncvxdiscr: reformulator, disabled
- Rprodbincont: reformulator, linearizes x*y products where x is
binary by means of Fortet's inequalities, prints to screen
- RQuarticConvex: reformulator, outputs a convex relaxation of quartic
problems by means of McCormick's bilinear envelopes composed with
Meyer&Floudas' trilinear ones
- Rrelaxation: reformulator, incomplete
- Rsmith: reformulator, prints the Smith relaxation of a problem to screen
- Rsymmgroup: reformulator, outputs a nauty-formatted (actually,
dreadnaut-formatted) file called Rsymmgroup_out.nauty encoding
the DAG representation of the problem
- Rvinci: reformulator, transforms an LP into an inequality
representation input file invinci.ine for the VINCI software package
- sbb: numerical solver, disabled
- subgradient: numerical solver, disabled
- tabu: numerical solver, disabled
- vns: numerical solver, disabled
USAGE
From command line: you need a mathematical program encoded in the ROSE
format (extension: .ros). This format is proprietary but it's easy
to read and understand. See examples/bilinear.ros for a (hopefully)
self-explanatory example. Typing 'rose' without arguments prints the
following help message:
Syntax: rose [options] file
where file specifies the optimization problems (.ros format),
and options can be:
-h for this help
-p parameter_list ("param val, param val, ...", quote the list)
-n no automatic simplifier
-q for quiet mode
-s solvername (gomory limitedbranch localbranch null Rcdd
Rconvexifier Rconvexifiermod Rcopy Rdisaggr Rfbbtfp Roa Rporta
Rprintdat Rprint Rprintmod Rprintncvxdiscr Rprodbincont
RQuarticConvex Rrelaxation Rsmith Rsymmgroup Rvinci sbb subgradient
tabu vns )
-t table output
Rose may also be used as an AMPL solver -- rename it as "roseamp" and
put it in the path, then call ampl with "option solver roseamp"
From AMPL: you need 'rose', 'roseamp' and 'ampl' to be installed
somewhere in your path. Get AMPL to read a model and optionally a data
file, then specify the roseamp solver with the command
option solver roseamp;
within AMPL, then specify the ROSE solver/reformulator to use. These
are identified by means of an integer ID. Use the AMPL command
option roseamp_options "mainsolver=ID";
to specify the solver to be used. Different solvers might have
different outputs. Some output to screen, some to files with default
names usually referring to the solver name. Typing 'roseamp' at the
command line will print out some help:
Syntax: roseamp is an AMPL (www.ampl.com) solver
insert "option solver roseamp" in your AMPL directives
after making sure that the executable "roseamp" is in the path
AMPL solver options (use "option roseamp_options" AMPL directive)
convexifieroutampl (0=no, 1=yes)
limitedbrancharbitrary (double in [0,1])
limitedbranchlocalsolver (solver code)
limitedbranchmaxtime (in seconds)
localbranchwarmup (0 or 1)
mainsolver (solver code)
nosimplifier (0 or 1)
quiet (0 or 1)
relaxinteger (0 or 1)
symmgroupouttype (0=nauty[default], 1=AMPL .dat)
vnsepsilon (double)
vnskmax (max VNS neighbourhood size (int))
vnskmin (min VNS neighbourhood size (int))
vnslocalsolver (solver code)
vnsmaxtime (seconds)
vnssamples (number of starting points in each neighbourhoods)
vnswarmup (0 or 1)
where the solver code is an integer defined as follows:
1: tabu(letsgo)
3: vns
4: gomory
5: limitedbranch
6: localbranch
7: analyser
8: prodbincont
9: print
10: smith
11: copy
12: disaggr
13: oa
14: symmgroup
15: printmod
17: rvinci
18: rporta
19: rquarticconvex
20: rconvexifier
21: rprintdat
22: rcdd
23: rrelaxation
24: subgradient
25: rconvexifiermod
26: rprintncvxdiscrepancy
27: rfbbtfp
LICENSE
The ROSE is licensed under the Common Public License (CPL).
CONTACT, SUPPORT, FEATURES REQUEST, BUG REPORT
David Savourey : savourey@lix.polytechnique.fr
WEB PAGE
http://www.lix.polytechnique.fr/sysmo/rose/
DEVELOPER'S NOTES
To access the source code, type:
svn checkout svn+ssh://hammer.lix.polytechnique.fr/home/savourey/svnrepository/rose
Procedure to create a new solver:
1. cp and edit solver_TEMPLATE.cxx/.h to new solver name (search/replace)
2. Makefile: add new object to OBJS
3. newsolver.cxx (add new solver / delete new solver / include .h)
4. problem.cxx (add solvername/params in the ampl interface)
5. rose.cxx (add help)