How to run automated tests with SCIP SCIP comes along with a set of useful tools that allow to perform automated tests. The following is a step-by-step guide from setting up the test environment for evaluation and customization of test runs. ## Setting up the test environmentAt first you should create a file listing all problem instances that should be part of the test. This file has to be located in the the directory Optionally, you can provide a solution file in the `=opt=` stating that a problem name with an optimal objective value follows`=best=` stating that a problem name with a best know objective value follows`=inf=` stating that a problem name follows which is infeasible
With these information types you can encode for an instance named - The instance has a known optimal (objective) value of 10. =opt= instance1 10
- The instance has a best known solution with objective value 15. =best= instance1 15
- The instance is feasible (but has no objective function or we don't know a solution value) =feas= instance1
- The instance is infeasible. =inf= instance1
If you don't know whether the instance is feasible or not (so the status is unknown), you can omit the instance in the =unkn= instance1
## Starting a test runmake TEST=testrun test in the SCIP root directory. Note that ## Evaluating a test runDuring computation, SCIP automatically creates the directory `*.out` - output of`stdout` `*.err` - output of`stderr` `*.set` - copy of the used settings file
`*.res` - ASCII table containing a summary of the computational results`*.tex` - TeX table containing a summary of the computational results`*.pav` - PAVER output
The last three files in the above list, i.e., the files containing a summary of the computational results, can also be generated manually. Therefore the user has to call the The last column of the ASCII summary table contains the solver status. We distinguish the following statuses: (in order of priority) - abort: solver broke before returning solution
- fail: solver cut off a known feasible solution (value of the
`solu` -file is beyond the dual bound; especially if problem is claimed to be solved but solution is not the optimal solution)**or**if a final solution check revealed a violation of one of the original constraints. - ok: solver solved problem with the value in solu-file
- solved: solver solved problem which has no (optimal) value in solu-file (since we here cannot detect the direction of optimization, it is possible that a solver claims an optimal solution which contradicts a known feasible solution)
- better: solver found solution better than known best solution (or no solution was noted in the
`solu` -file so far) - gaplimit, sollimit: solver reached gaplimit or limit of number of solutions (at present: only in SCIP)
- timeout: solver reached any other limit (like time or nodes)
- unknown: otherwise
Additionally the ./evalcheck.sh writesolufile=1 NEWSOLUFILE=<solu-file> <out-file> where Another feature can be enabled by calling: ./evalcheck.sh printsoltimes=1 ... The output has two additional columns containing the solving time until the first and the best solution was found.
check.<test name>.<binary>.<machine name>.<setting name> - <
`test name` > indicates the name of the the test file, e.g.,`testrun` - <
`binary` > defines the used binary, e.g.,`scip-3.2.0.linux.x86_64.gnu.opt.spx` - <
`machine name` > tells the name of the machine, e.g.,`mycomputer` - <
`setting name` > denotes the name of the used settings, e.g.,`default` means the (SCIP) default settings were used
Using the examples out of the previous listing the six file names would have the name: check.testrun.scip-1.1.0.linux.x86.gnu.opt.spx.mycomputer.default.<out,err,set,res,tex,pav> ## Using customized setting filesIt is possible to use customized settings files for the test run instead of testing SCIP with default settings. These have to be placed in the directory
To run SCIP with a custom settings file, say for example make TEST=testrun SETTINGS=fast test in the SCIP root directory. It is possible to enter a list of settings files as a double-quoted, comma-separated list of settings names as ## Advanced optionsWe can further customize the test run by specifying the following options in the `CONTINUE` - continue the test run if it was previously aborted [default: "false"]`DISPFREQ` - display frequency of the output [default: 10000]`FEASTOL` - LP feasibility tolerance for constraints [default: "default"]`LOCK` - should the test run be locked to prevent other machines from performing the same test run [default: "false"]`MAXJOBS=n` - run tests on 'n' cores in parallel. Note that several instances are solved in parallel, but only one thread is used per job (parallelization is not that easy) [default: 1]`MEM` - memory limit in MB [default: 6144]`NODES` - node limit [default: 2100000000]`TIME` - time limit for each test instance in seconds [default: 3600]`SETCUTOFF` - if set to '1', an optimal solution value (from the`.solu` -file) is used as objective limit [default: 0]`THREADS` - the number of threads used for solving LPs, if the linked LP solver supports multithreading [default: 1]`VALGRIND` - run valgrind on the SCIP binary; errors and memory leaks found by valgrind are reported as fails [default: "false"]
## Comparing test runs for different settingsOften test runs are performed on the basis of different settings. In this case, it is useful to have a performance comparison. For this purpose, we can use the Suppose, we performed our test run with two different settings, say check.testrun.scip-3.2.0.linux.x86_64.gnu.opt.spx.mycomputer.fast.res check.testrun.scip-3.2.0.linux.x86_64.gnu.opt.spx.mycomputer.slow.res For a comparison of both computations, we simply call allcmpres.sh results/check.testrun.scip-3.2.0.linux.x86_64.gnu.opt.spx.mycomputer.fast.res \
results/check.testrun.scip-3.2.0.linux.x86_64.gnu.opt.spx.mycomputer.slow.res in the `Nodes` - Number of processed branch-and-bound nodes.`Time` - Computation time in seconds.`F` - If no feasible solution was found, then '#', empty otherwise.`NodQ` - Equals Nodes(i) / Nodes(0), where 'i' denotes the current solver and '0' stands for the reference solver.`TimQ` - Equals Time(i) / Time(0).`bounds check` - Status of the primal and dual bound check.
`proc` - Number of instances processed.`eval` - Number of instances evaluated (bounds check = "ok", i.e., solved to optimality within the time and memory limit and result is correct). Only these instances are used in the calculation of the mean values.`fail` - Number of instances with bounds check = "fail".`time` - Number of instances with timeout.`solv` - Number of instances correctly solved within the time limit.`wins` - Number of instances on which the solver won (i.e., the solver was at most 10% slower than the fastest solver OR had the best primal bound in case the instance was not solved by any solver within the time limit).`bett` - Number of instances on which the solver was better than the reference solver (i.e., more than 10% faster).`wors` - Number of instances on which the solver was worse than the reference solver (i.e., more than 10% slower).`bobj` - Number of instances on which the solver had a better primal bound than the reference solver (i.e., a difference larger than 10%).`wobj` - Number of instances on which the solver had a worse primal bound than the reference solver (i.e., a difference larger than 10%).`feas` - Number of instances for which a feasible solution was found.`gnodes` - Geometric mean of the processed nodes over all evaluated instances.`shnodes` - Shifted geometric mean of the processed nodes over all evaluated instances.`gnodesQ` - Equals nodes(i) / nodes(0), where 'i' denotes the current solver and '0' stands for the reference solver.`shnodesQ` - Equals shnodes(i) / shnodes(0).`gtime` - Geometric mean of the computation time over all evaluated instances.`shtime` - Shifted geometric mean of the computation time over all evaluated instances.`gtimeQ` - Equals time(i) / time(0).`shtimeQ` - Equals shtime(i) / shtime(0).`score` - N/A
`all` - All solvers.`optimal auto settings` - Theoretical result for a solver that performed 'best of all' for every instance.`diff` - Solvers with instances that differ from the reference solver in the number of processed nodes or in the total number of simplex iterations.`equal` - Solvers with instances whose number of processed nodes and total number of simplex iterations is equal to the reference solver (including a 10% tolerance) and where no timeout occured.`all optimal` - Solvers with instances that could be solved to optimality by*all*solvers; in particular, no timeout occurred.
Since this large amount of information is not always needed, one can generate a narrower table by calling: allcmpres.sh short=1 ... where If the allcmpres.sh printsoltimes=1 ... As in the evaluation, the output contains the two additional columns of the solving time until the first and the best solution was found. ## Statistical testsThe ## McNemar testAssume that we compare two settings
Under the null hypothesis, is chi-squared distributed with one degree of freedom. This allows to compute a -value as the probability for obtaining a similar or even more extreme result under the null hypothesis. More explicitly, - : The null hypothesis is accepted (marked by "X").
- : The null hypothesis might be false (marked by "!").
- : The null hypothesis can be false (marked by "!!").
- : The null hypothesis is very likely false (marked by "!!!").
As an example consider the following output: McNemar (feas) x2 0.0000, 0.05 < p X McNemar (opt) x2 6.0000, p ~ (0.005, 0.05] ! Here, In this case, the test with respect to the number of found feasible solutions is irrelevant, since their number is equal. In particular, the null hypothesis gets accepted (i.e., there is no difference in the settings - this is marked by "X"). With respect to the number of instances solved to optimality within the timelimit, we have that (marked by ## Wilcoxon signed rank testAssume that we compare two settings The Wilcoxon test statistic is then
which we assume to be (approximately) normally distributed (with zero mean) and allows to compute the probability that one setting is faster than the other. (Note that for , we apply a correction by subtracting 0.5 from the numerator). As an example consider the following output: Wilcoxon (time) z -0.1285, 0.05 <= p X Wilcoxon (nodes) z -11.9154, p < 0.0005 !!! While the -value is close to zero for the run time, it is extremely negative regarding the solving nodes. This latter tendency for the number of nodes is significant on a 0.05 % level, i.e., the probability that setting However, the null hypothesis is not rejected with respect to the run time. In the concrete case, setting ## Testing and Evaluating for other solversAnalogously to the target - for cplex make testcplex
- for gurobi make testgurobi
- for cbc make testcbc
- for mosek make testmosek
- for glpk make testglpk
- for symphony make testsymphony
- for blis make testblis
- for gams For this target, the option GAMSSOLVER has to be given to specify the name of a GAMS solver to run, e.g. GAMSSOLVER=SCIP. Additional advanced options specific to this target are: GAMS to specify the GAMS executable (default: gams), GAP to specify a gap limit (default: 0.0), CLIENTTMPDIR to specify a directory where GAMS should put its scratch files (default: /tmp), CONVERTSCIP to specify a SCIP which can be used to convert non-gams files into gams format (default: bin/scip, if existing; set to "no" to disable conversion). The following options are NOT supported (and ignored): DISPFREQ, FEASTOL, LOCK. A memory limit (MEM option) is only passed as workspace option to GAMS, but not enforced via ulimit (it's up to the solver to regard and obey the limit).make testgams GAMSSOLVER=xyz
Note: This works only if the referred programs are installed globally on your machine. The above options like For cbc, cplex, gams, and gurobi another advanced option is available: `THREADS` - number of threads used in the solution process
After the testrun there should be an Furthermore you can also use the script |