[ Performance World Home | Board | Tools | PerformanceLib | Links | GamsWorld group | Search | Contact ]

Benchmarking the GAMS Branch-and-Cut-and-Heuristic Facility

We present benchmarking of the GAMS Branch-and-Cut-and-Heuristic Facility (hereafter BCHF) on a set of test instances, provided by Ortega and Wolsey (Ortega F. & Wolsey L., Networks, 41, 2003, no. 3, 143--158; more detailed description of model instances can be found in their discussion paper). We developed a set of programs to port the test instances to GAMS framework, and compared performance of different solvers (CPLEX, XPRESS, XA) to the performance of CPLEX with BCHF enabled. Please first read the Introduction, where we explain the explicit goals of this project and briefly describe the final products. Then, if you want to

• go through all steps of our processing, from test instances provided by Ortega & Wolsey to the performance graphs, proceed from Sec. 2;
• only repeat the test runs on your computer using the test instances prepared by us, start from Sec. 3;
• just have a look at our comparison of performance of different solvers, skip over to Sec. 4.

The project pursued the following goals:

1. Create a common GAMS model file which would allow to load data (matrices) of each instance as include-files.
2. Translate data (matrices) of each model instance from XPRESS to GAMS format and arrange them as a set of include-files (hereafter translated instances).
3. Automatically convert model instances from MPS to GAMS format (hereafter converted instances).
4. Check matrix statistics of both translated and converted instances to ensure accuracy of translation.
5. Run GAMS on both translated (without BCHF) and converted model instances to ensure accuracy of translation, at RMIP stage -- for all instances, at MIP stage -- for easy instances only.
6. For hard instances (not solved to optimality by CPLEX without BCHF during specified interval of time), determine at which values of the objective function we should start to apply cuts and heuristics provided by BCHF to keep performance optimal.
7. Use this set of instances to compare performace of various solvers (in particular, CPLEX, XPRESS, and XA were used in our test runs) to performance of CPLEX with cuts/heuristics provided by BCHF.

1. bchf-scripts.tgz -- a set of Unix shell scripts and GAMS programs to perform steps I--VI from the list above. The scripts are tested working on Linux platform. For description of these programs see Sec. 2.
2. bchf-inst.tgz -- a set of GAMS include-files with model instances (prepared at step II).
3. bchf-conv.zip -- a set of converted gms- and gdx-files with model instances (prepared at step III).
4. bchf-gms.tgz -- a set of GAMS model files (prepared at step I) which, together with include-files, allow to repeat step VII on all platforms supported by GAMS. For description of these programs see Sec. 3.
5. bchf-agr.tgz -- source files (for Grace) of graphs presented in Sec. 4.

In this Section we describe how to process the set of test instances to translate them to the GAMS framework and make sure that the translation was performed correctly. We describe each program and give examples of typical usage.

The archive bchf-scripts.tgz contains the following files:

1. togams -- a shell script to convert model instances from XPRESS format to GAMS format
2. rungams -- a shell script to run GAMS on specified instances for a specified period of time
3. compgams -- a shell script to compare results of different runs of GAMS on a set of instances
4. runall -- a shell script to run scripts togams, rungams, compgams and perform some other processing in one command
5. param.conf -- a configuration file for all the above scripts in shell format
6. printnice.gms -- a GAMS script to convert instances of type "2" to nice-looking format
7. bchfcnet.gms -- a general GAMS model file for use with rungams. Inc-files are called via directive "$include".
8. bchdicut.inc - a GAMS model file which implements dicut inequalities.
9. 13rm -- an auxiliary script for conversion of ASCII files from DOS to UNIX format (used by runall).

Syntax: runall [steps]

steps is a string containing one or more letters from the list below. If the given letter is included, the corresponding step is performed. If parameter steps is omitted, the default configurations from param.conf is used. There are 10 steps:

1. Preparations. There is a separate directory for each instance in the source archive. Each directory contain XPRESS-file, MPS-file and accompanying ASCII data files. We retain this structure while we do translation and cheking of instances. At this step, in the directory of each instance all ASCII files are converted from DOS to Unix text format; additional copies of param.conf for RMIP-relaxed and other modes of operation are created; hardlinks to commonly used files are created, etc.
2. Translate instances from XPRESS format to GAMS with togams; to complete translation of instances of type "2", GAMS is called with printnice.gms.
3. Solve translated instances with "rungams optfile=0" (i.e., without BCHF).
4. Solve translated instances with "rungams optfile=1" (i.e., with BCHF).
5. Convert instances from MPS format to GAMS format: mps2gms (which is a part of GAMS distribution) is called to convert all instances automatically. Then all instances are run at RMIP stage just to create corresponding gdx-files.
6. Solve converted instances with rungams.
7. Utilize compgams to comapre results of different runs of rungams, e.g., runs of the translated and converted instances.
8. Determine startcut and startheur parameters for hard instances. To use BCHF effectively, it should not be called from the very beginning if the solver provides its own BCHF, as CPLEX does. We start to call BCHF when the solver is finished with the root node. The values of objective function reached when the root node is finished are calculated at this step using "rungams nodlim=1". They are then saved in data.gms.
9. Run converted and translated instances in RMIP mode to compute matrix statistics and RMIP objective values.
10. Copy model instances in GAMS format, converted gms- and gdx-files to the directory specified in param.conf.
11. Compare matrix statistics of the translated and converted instances.

2.2. togams

Syntax: togams datatype filename.xxx

datatype is two-digit specification of the model type, the first digit is a number in the range 1--8, the second one is an arbitrary alphanumeric symbol. The datatype must be defined in param.conf. Model types are the following:

1. Instances with variable costs equal to zero (Steiner trees; 8 instances).
2. Instances with multiple cost options per arc; the data reside in MPS-file (multi-segment; 2 instances).
3. Instances with multiple cost options per arc; the data reside in separate ASCII files (multi-segment; 6 instances).
4. Instance with fixed or variable cost equal to zero for some open arcs (from MIPLIB; 1 instance).
5. Various types of instances (grid, complete graph, lot-sizing, planar, random; 49 instances).
6. Instances with multiple cost options per arc; the number of cost options is not specified explicitly (series-parallel; 9 instances).
7. Instances of type "complete graph and one node" (Hochbaum; 5 instances).
8. Instances of type "complete graph and one node" with forbidden flow from any node to itself (Hochbaum; 3 instances).

filename.xxx should be a model file in XPRESS format. The filename extension is arbitrary but should be of 3 symbols length, default extension is "mod". Translated GAMS-file is stored in the same directory as a source XPRESS-file.

2.3. rungams

Syntax: rungams filename(s).xxx

filename(s).xxx is a list of inc-files prepared by togams.

First, RMIP problem is solved by gams by performing runs with infile (default is bchfcnet.gms) with each of filename(s).xxx. Then, if the parameter cpulim is non-zero, gams is run for MIP problem. In both cases, gams command line parameters are set via parameter gamspar.

During computations the running time (either elapsed time or CPU time; set by parameter timecounter) of gmscp_ux.out reported by ps is monitored (every check seconds). One can set additional parameters for ps via parameter psopts (e.g., to account for time consumed by child processes of gams). Once the running time reaches cpulim, the signal INT is sent to the process gmscp_ux.out. Then rungams waits for the initial gams process to complete, extracts output information from the tracefile and appends it to the output file.

The name of the output file is formed from two parameters: infile.extt (default is bchfcnet.tab). It is started with 3 header lines, each of which begins with the comment symbol "#". For each instance, the following data are reported:

1. A datatype to which the instance belongs.
2. Instance name.
3. Optimal objective value of the RMIP problem.
4. Minimum objective value (this and remaining fileds relate to the MIP problem).
5. Best bound.
6. Relative gap.
7. Number of nodes.
8. Elapsed time reported in the GAMS listing file.
9. Wall time reported by time.
10. User time reported by time.
11. Time consumed by gmscp_ux.out reported by ps.
12. Value of psopts and command line parameters of ps used to monitor execution time.

Syntax: compgams out_file in_file(s)

in_file(s) are output files of rungams, minimum 2 names must be given. The first file is considered to be a reference file, only model instances from this file participate in the comparison.

It is determined by the parameter objvcomp, which of the values (RMIP objective, MIP objective, best bound, gap) should be compared. The result of the comparison can be present as a difference of the values or as their ratio (parameter objvdr). Parameter timecomp is responsible for chosing the time values to compare. They can also be presented as differences or as ratios (parameter timedr).

Output table out_file contains 3 lines of header, beginning with "#", and one line per instance with the results of comparison.

2.5. param.conf

The parameters set in this file are as follows:

• steps -- which steps should be performed by runall. There are 11 steps, from "a" to "k" (see runall for their description). The format of this parameter is string, and if the character is present in this string, the corresponding step is performed. The letters can be listed in arbitrary order, without spaces. efault values for this parameter is to perform all steps but "i", which is needed only if steps "c" and "f" are skipped.
• types -- a list of datatypes to be processed by rungams or togams. It is a quoted string of type names, 2 symbols each, separated by spaces.
• filesND -- several parameters describing which instances belong to each datatype. "ND" denotes datatype, where "N" is a number in the range 1--8, and "D" is an alphanumeric symbol. See also Ddir.
• Ddir -- a parameter associated with filesND -- a directory name in which directories with the instances of type "ND" reside.
• oinfile -- the name of the GAMS model file with the optfile turned on. This file is produced by runall from bchfcnet. Extension gms to be omitted.
• orinfile -- the name of the GAMS model file with optfile turned on, to be used at RMIP stage. It is produced by runall from bchfcnet. Extension gms to be omitted.
• infname -- the name of the GAMS model file produced by mps2gms from the instance source files.
• rinfname -- the name of the GAMS model file produced by runall from each infname.
• infile -- the name of the initial GAMS model file for the MIP stage, defaulted to bchfcnet.gms. Extension gms to be omitted.
• rinfile -- the name of the initial GAMS model file for the RMIP stage, produced by runall from infile. Extension gms to be omitted.
• logfile -- the name of the file to which runall appends each command performed. Could be useful for on-line monitoring of the execution of runall.
• extt -- an extension for the output files, default is "tab".
• gamslibpath -- GAMS installation directory (to be added to LD_LIBRARY_PATH environment).
• mptab -- the name of the table to contain comparison of model parameters (see step "k").
• hardtypes -- datatypes hard enough so BCHF is worthy applying to them. Therefore for these datatypes parameters startcut and startheur should be determined at step "h". This parameter is a quoted string of datatypes separated by spaces.
• cutheurtrcfile -- trace file name for the stage of determining of startcut and startheur.
• cutheuroutfile -- output file name for the stage of determining of startcut and startheur.
• nicedir -- the directory to which all nicely printed inc-, gms- and gdx-files will be copied (step "j").
• cpulim -- time limit for the MIP problem computations in seconds; when exceeded, corresponding GAMS process will be killed (see rungams). If zero, the MIP problem will be skipped.
• reslim -- sets the time limit for the MIP problem for CPLEX (default is value of cpulim).
• gamspar -- a list of command line parameters for gams, will be used while running gams from rungams.
• tracefile -- the name of the tracefile to be appended by gams while running from rungams.
• check -- time interval in seconds to check the running time of GAMS solver run by rungams.
• timecounter -- specifies which running time to use for the solver monitoring, etime for elapsed time, and cputime for actual CPU time (see rungams).
• timecomm -- the full path to the Unix command time used to monitor running time of gams run by rungams (it is needed to avoid time supplied by shell, because their output formats are different).
• psopts -- additional command line parameters to pass to ps while monitoring gams running time. One possible option is "-S" to include child processes into the running time.
• psswitch -- command line parameter for ps to detect processes not associated with any terminal (default is "-x").
• ppdiopt -- command line parameter for ps to find PID by PPID (default is "-jx").
• objvcomp -- determines which parameters compgams should use for the comparison of results. It is a string consisting of symbols, if the symbol is present, the corresponding parameter should be included into the comparison. The symbols can be the following: "r" for the RMIP objective value, "m" for the MIP objective value, "e" for the MIP bound estimate, "g" for the gap.
• objvdr -- should the objvcomp value be output as a differece (use "d") or as ratio (use "r")?
• timecomp -- determines which parameters compgams should use for the comparison of running times. It is a string consisting of symbols, if the symbol is present, the corresponding parameter should be included into the comparison. The symbols can be the following: "e" for the elapsed time extracted from the GAMS listing file, "w" for the wall time reported by time, "u" for user time reported by time, "p" for time reported by ps last time when the process was ruinning (inaccuracy for the value of check is assumed).
• timedr -- should the timecomp value be output as a differece (use "d") or as ratio (use "r")?

Syntax: gams printnice --nicefile outfile.inc --gdxfile infile.gdx

2.7. Matrix statistics comparsion

RMIP objective values are consistent for all instances. All instances show consistency by all 4 matrix parameters except for 3 models of datatype 8 (namely, h80x6320[bcd]). The reasons for that are purely technical: GAMS formulation of the linear programming problem for translated instances is slightly different from that in the XPRESS files. Number of equations and number of variables are consistent. Number of discrete variables and number of non-zoros are by 79 less for translated models. This is because in XPRESS models the constraint of zero flows from 79 demanding nodes to themselves is presented as a zero condition for corresponding binary forcing constraint variables (y=0), and GAMS models it is presented as condition for the upper limit (y=eps), which effectively excludes these variables from consideration.

2.8. Examples

1. runall
   To perform all processing provided by the pipeline: create directory structure, translate instances, convert XPRESS-files, compare results of runs of converted and translated instances, compare matrix statistics, collect all instances in a specified directory.
2. runall abi
   To translate all instances to GAMS format and copy them to the specified directory.
3. togams 2s singlesource-web/beavma/beavma.mod
   To translate one particular model instance to GAMS format.
4. rungams singlesource-web/berlin/berlin.inc singlesource-web/brasil/brasil.inc
   To run GAMS model with two specific test instances.

The archive bchf-gms.tgz contains the following files:

1. data.gms - a GAMS command file to run gams on a set of instances with a specified solver.
2. schulz.gms - a GAMS command file to interrupt GAMS processes which do not terminate in the prespecified time limit.
3. pprofile.gms - a GAMS command file to compare performance of different solvers based on trace-files provided by data.gms.
4. bchfcnet.gms - a GAMS model file for use with data.gms.
5. bchdicut.inc - a GAMS model file which implements dicut inequalities.
6. bchfcheu.inc - a GAMS model file which implements heuristics.

Syntax: gams data.gms [options]
The following options are possible:

• --xoptfile opt
  The "opt" is a decimal number specifying whether GAMS option file should be used (not used if "0", used if "1" or higher, default is "0"). Option file is created automatically by bchfcnet.gms which is called by data.gms. The name of the output file of data.gms is composed accounting for this parameter.
• --step [bch|mps]
  Which instances to use, translated from XPRESS to GAMS ("bch"; default), or converted from MPS to GAMS ("mps").
• --reslim #
  The "#" is a decimal number specifying time in seconds allotted to each instance, defaulted to 1800.
• --solver [cplex|xpress|xa]
  The solver to be used, default is cplex.
• --nicedir dirname
  Directory name where the translated model files reside, defaulted to the current directory.
• --cutsoff [1|0]
  Whether to use cuts, "0" means "to use", default is "0" (currently only available with CPLEX).
• --heuroff [1|0]
  Whether to use heuristics, "0" means "to use", default is "0" (currently only available with CPLEX).
• --suffix suffix
  Value of string used to create the name of the output trace-file.
• --overwrite [1|0]
  If "1", the trace-file will be overwritten if present. If "0", the program exits with the error message to the lst-file. This is intended to prevent accidental loss of results of previous runs when restarting computations in the same directory. Default is "0".

Run this program in parallel with your computations to monitor running time of GAMS jobs.

Syntax: gams schulz [options]
The following options are possible:

• --watch proc_name
  "proc_name" is a regular expression defining the process name to watch.
• --time type
  "type" is a type of time to be monitored. For Windows, possible values are etime|cputime|kerneltime. For Unix, every possible value of the option "-o" of the command time.
• --sleep #
  The "#" is a decimal number specifying time checking interval in seconds.
• --resseq #:#:#
  This options specifies 3 values of time (in seconds), at which a corresponding signals (see next option) should be sent.
• --sigseq #:#:#
  This option specifies 3 values of signal number, which should be sent at corresponding times (see previous option).

1. relative number of instances solved during specified time vs relative gap reached during this time (all instances are counted);
2. relative number of instances solved to optimality by at least one of the solvers vs time consumed;
3. relative number of instances solved during specified time vs relative gap reached during this time;
4. relative number of instances solved during specified time vs best objective value reached during this time;
5. relative number of instances solved during specified time vs best bound value reached during this time.

All internal processing is performed by awk, which is called several times: for each output table, it is called to produce a list of instances of all participating solvers and to perform the comparison.

Syntax: gams pprofile.gms
This program does not have command line parameters. All parameters are specified within the body of the program. If you just follow the example given below, the default parameters will work. If you need to change them, below is the description of the parameters. Input trace-file lists are defined as GAMS sets, so it is easy to add other solvers to them if necessary.

• if1
  A list of names of the input trace-files produced by different solvers, used to compute table of type I. (Defined as a GAMS set, each element of the set must be quoted.)
• if2
  A list of names of the input trace-files produced by different solvers, used to compute table of type II. (Defined as a GAMS set, each element of the set must be quoted.)
• if3
  A list of names of the input trace-files produced by different solvers, used to compute table of types III, IV, and V. Only those instances are counted, which all solvers from the list if4 failed to solve to optimality. (Defined as a GAMS set, each element of the set must be quoted.)
• if4
  A list of names of the input trace-files produced by different solvers, used to determine instances, not solved to optimality by all solvers from this list. For tables of types III, IV, and V. (Defined as a GAMS set, each element of the set must be quoted.)
• of#
  Name of the output table of type #, where "#" is a decimal digit in the range 1--5. (Defined as a GAMS parameter.)

Create a separate directory for each run (different solvers, with/without cuts/heuristics)
Unpack the archives bchf-gms.tgz and bchf-inst.tgz into each directory
gams schulz --watch gmscp_ux.out --time etime --sleep 60 --resseq 2:3:9 --sigseq 1800:1850:1900
In corresponding directories:
gams data --solver cplex --optfile 0 --cutsoff 1 --heuroff 1 --suffix cplex
gams data --solver cplex --optfile 1 --cutsoff 0 --heuroff 1 --suffix cplex.cuts
gams data --solver cplex --optfile 1 --cutsoff 0 --heuroff 0 --suffix cplex.cutsheur
gams data --solver xpress --optfile 0 --cutsoff 1 --heuroff 1 --suffix xpress
gams data --solver xa --optfile 0 --cutsoff 1 --heuroff 1 --suffix xa
Copy all files bchrun*txt to a separate directory and run there
gams pprofile

4. Results of our test runs

We performed our computations on a computer with two Athlon MP 2800+ CPUs and 2 Gb of RAM. 1800 seconds were allotted for each of 83 instances. Performace of solvers CPLEX, XPRESS and XA was compared to the performace of CPLEX with cuts enabled and CPLEX with both cuts and heuristics enabled, illustrated on the graphs below (source files for these graphs in Grace format can be found in the archive bchf-agr.tgz).

Relative number of instances solved durng 1800 s vs relative gap reached during this time (all instances are counted).

Relative number of instances solved to optimality by XPRESS and/or CPLEX vs time consumed.

Relative number of instances solved during 1800 s vs relative gap reached during this time ("super-solver" is a synthetic solver, for each instance it is a solver providing best value of the gap). Only instances not solved by both CPLEX and XPRESS are counted.

Relative number of instances solved during 1800 s vs best objective value reached during this time. Only instances not solved by both CPLEX and XPRESS are counted.

Relative number of instances solved during 1800 s vs best bound value reached during this time. Only instances not solved by both CPLEX and XPRESS are counted.