| 1 |
****************************************************************************** |
| 2 |
* SYMPHONY SPP Application * |
| 3 |
****************************************************************************** |
| 4 |
|
| 5 |
The SYMPHONY SPP application solves the standard Set Partitioning |
| 6 |
Problem. This application is a pure branch and bound solver and does not |
| 7 |
utilize cutting planes. It is simply intended as an illustration of how to |
| 8 |
develop an application with SYMPHONY. For a more sophisticated solver, please |
| 9 |
download the SYMPHONY SPP+CUTS application. See below for usage. |
| 10 |
|
| 11 |
****************************************************************************** |
| 12 |
* INSTALLATION * |
| 13 |
****************************************************************************** |
| 14 |
|
| 15 |
Please see the INSTALL file for a guide to compile SYMPHONY CNRP application. |
| 16 |
|
| 17 |
******************************************************************************* |
| 18 |
* USING THE SOLVER * |
| 19 |
******************************************************************************* |
| 20 |
|
| 21 |
The set partitioning problem (SPP) is a difficult (NP-complete, large size of |
| 22 |
problems) combinatorial optimization problem mainly applied to scheduling |
| 23 |
problems. SPP can be defined as finding the minimum cost partition of a matrix |
| 24 |
having binary entities where a partition is the union of disjoint subsets to |
| 25 |
cover all the row indices and a subset -associated to each column- consists of |
| 26 |
the row indices if the corresponding entity is 1. |
| 27 |
|
| 28 |
To execute the SPP application you are just required to specify the location |
| 29 |
of the data file by typing "-F 'filename'" as an argument after the executable |
| 30 |
name. There is a sample file called sample.spp that you can try to make sure |
| 31 |
the solver is working. More data files may become available. Please check |
| 32 |
http://www.branchandcut.org/SPP/ for more information. The other user defined |
| 33 |
parameters are the following: |
| 34 |
|
| 35 |
-H: help (user switches) |
| 36 |
-F file: problem instance data is in 'file' |
| 37 |
|
| 38 |
You can also obtain the above list by tying the executable name followed by |
| 39 |
"-H". There are a number of other (for now) undocumented parameters that can |
| 40 |
be used to fine-tune the performance of the solver. These must be set in a |
| 41 |
parameter file. The SYMPHONY User's Manual explains the use of the parameter |
| 42 |
file. |
| 43 |
|
| 44 |
Some of SYMPHONY's native parameters can also be set on the command |
| 45 |
line. Below is a list of these parameters. This list can also be obtained by |
| 46 |
typing the executable name with no command-line arguments. Note that all |
| 47 |
SYMPHONY parameters are denoted by a lowercase letter. Note that there are |
| 48 |
dozens of other parameters that can be set with the use of a parameter |
| 49 |
file. These parameters are listed in the SYMPHONY User's Manual. |
| 50 |
|
| 51 |
-h: help |
| 52 |
-a: no cut timeout |
| 53 |
-d: enable graph drawing |
| 54 |
-g: use cut generator |
| 55 |
-r: do repricing in root |
| 56 |
-t: trim the tree |
| 57 |
-b: don't perform branch and cut |
| 58 |
-u ub: use upper bound 'ub' |
| 59 |
-p procs: allow 'procs' active nodes |
| 60 |
-n i: use node selection rule 'i' |
| 61 |
-v i: set verbosity to level 'i' |
| 62 |
-s cands: use 'cands' candidates for strong branching |
| 63 |
-c i: use rule 'i' to compare candidates |
| 64 |
-k i: use rule 'i' to select child |
| 65 |
-m n: allow a max of 'n' cuts to enter per iteration |
| 66 |
-e n: allow a max of 'n' cut pools |
| 67 |
-l n k: load balance level 'n' and iterations 'k' |
| 68 |
-i n: allow a max of 'n' iterations in presolve |
| 69 |
-z n: set diving threshold to 'n' |
| 70 |
-f file: read parameters from parameter file 'file' |
| 71 |
|
| 72 |
AUTHORS |
| 73 |
|
| 74 |
The SYMPHONY SPP application was developed by Marta Eso |
| 75 |
([email protected]). |
| 76 |
|
| 77 |
BUG REPORTS |
| 78 |
|
| 79 |
Please submit bug reports at https://projects.coin-or.org/SYMPHONY |