Introduction

GAMS/ODHCPLEX is a solver from Optimization Direct Inc. that implements a set of heuristic methods (named ODHeuristics) for finding feasible solutions to Mixed Integer Programming (MIP and MIQCP) models that uses IBM CPLEX as its underlying solver engine. It is designed for large-scale models which a MIP solver would find intractable: either by it being unable to find feasible solutions at all or; more usually, by being unable to find feasible solutions of adequate quality in the time available to its user.

It is intended for users who are familiar with MIP modelling and have some knowledge of using the GAMS/CPLEX solver. GAMS/ODHCPLEX does not demand expert specialism in this field.

ODHCPLEX can be used in two ways: it is implemented as a stand-alone ODHeuristic engine, which can be used on its own (ODHeuristicMethod=STANDALONE); and also within the CPLEX optimizer, within which it can supply and receive solutions from the main CPLEX caller (ODHeuristicMethod=ODH-CPLEX (default)) thereby accelerating optimization compared with GAMS/CPLEX run on its own.

The ODHeuristic engine has a heuristic method for finding an initial feasible solution that it designed to complement, those of CPLEX. Since its main algorithmic procedure works by improving an incumbent feasible solution, getting an initial one is important and may consume a significant part of its total runtime. When used on its own (i.e. ODHeuristicMethod=STANDALONE), users should experiment to discover whether ODHeuristics' or CPLEX's initial feasible solution methods work best, but within ODH-CPLEX (i.e. ODHeuristicMethod=ODH-CPLEX) both methods are run in parallel and the winner is chosen automatically.

ODHeuristics' principal algorithm works by solving a sequence of sub-models. An innovative aspect of this process is its ability to use the model's symbolic structure to achieve the sub-model decomposition. It does this by analyzing the symbolic names that the user gives to the decision variables and careful specification of how this should be done this is worthwhile. ODHCPLEX can work without this analysis, but it usually takes about twice as much runtime.

Specifying Model Structure

The ODHeuristic method needs to break the model down into sub-models. It can do this in one of three ways:

Automatically using its decomposition heuristic;
Using information specified by the user in the IndexKey parameter;
By simply assigning each variable to a different block (or key); or
By using the dot option notatation with the option .key.

By default, the program will use information specified by the IndexKey parameter if it is set and its automatic decomposition heuristic otherwise. This may be overridden by the Decomposition parameter. If it is set to 0 (zero), option 3 above is selected. If it is set to 1, its automatic decomposition method is used, and if it is set to 2, option 4 above is selected.

Whilst the automatic decomposition method often works well, there may be an advantage to specifying decomposition through the IndexKey parameter. After performing the decomposition in whatever way, the program analyses the decomposition and displays statistics showing the maximum and minimum number of variables in each key or block and showing a percentage score to the decomposition as a whole. A typical display is of the form:

Variables/key 205.58 (+/-304.79), max/min variables/key 933(32) / 60(113).
There are 227 keys (4149 keys were dropped) with 46872 values.
Decomposition score 13.66%, graph score 2074/3135232.

Other things (such as the distribution of variables in keys and the number of keys) being equal, the smaller the percentage decomposition score, the better the decomposition is and the more effective the program will be.

Using the IndexKey parameter

The program needs to associate sets of variables with distinct values of a single index. The user can specify this association with a pattern to which some or all of the variables conform. The pattern is in standard C scanf format (see, for example, Kernighan and Ritchie's 2nd edition of The C Programming Language, section B1.3 Formatted Input). Currently allowable index values must be non-negative integers, so the pattern must include d. For example, if we have variables x whose first index names starts with a number of letters then an underscore followed by a numeric index value (like x(firstone_1), x(another_1), x(firstone_2), x(another_2), ..) the pattern

x(%*[a-z]_%d)

associates those variables whose name ends in _1 with index value 1, those whose name ends in _2 with index value 2 and so on. The pattern is called an index key referred to by the program as the option parameter IndexKey, for example

IndexKey=%*[xy](t_%d)

It may, however, be desirable to consider variables whose names are, say, x(t_2) and y(t_2), to belong to different index values, i.e. to belong to different groups. One way of doing this is to identify them with separate index keys. These can be supplied to IndexKey as two fields separated by a semi-colon, for example

IndexKey=x(t_%d);y(t_%d)

Up to 10 fields can be specified in this way.

On the other hand, it may be desirable to consider such variables as having the same index key and their nomenclature may not permit their identification by a single key field. For example, suppose there are variables john(t_1), john(t_2),.., jane(t_1), jane(t_2),.. and johnny(t_1), johnny(t_2),.. and we want to associate john(t_x) and jane(t_x) as belonging to key value x, but want to ignore johnny(t_x).

Two key fields can be used to do this by

INDEXKEY=john(t_%d);jane(t_%d)

By default john(t_2) and jane(t_2) would not share the same index value, but if the option parameter KeyType, is set to 1, the heuristic will group them together so as to share the same index.

If IndexKey is not specified, the program uses a default decomposition.

The program divides the model up into parts associated with different values of the IndexKey (if specified), using an integer interval divisor. Initially this is a number not less than 2 and it is increased as the search progresses. When no improved solution is found after a number, MaxRepeat, of attempts with the maximum interval divisor, MaxInterDiv, the program terminates. Default values are provided for MaxRepeat and MaxInterDiv, so these do not have to be specified by the user.

Heuristic Parameters

There are a number of other parameters which control the behaviour of the heuristic program. These may be left at their default values or specified on the GAMS/ODHCPLEX option file. In addition, all GAMS/CPLEX options can be supplied in the GAMS/ODHCPLEX option file to tweak the CPLEX behavior.

Parameter names and their meanings are summarized in the table below.

Option	Description	Default
cpxpresolve	Applies CPLEX presolve to full model `-1`: Do not apply `0`: Automatically determined `1`: Always applied	`0`
decompdensity	Matrix density above which automatic decomposition assigns each variable to a separate key	`0.3`
decomposition	Model decomposition method. `-1`: Automatically determined `0`: Assign each variable to a separate key `1`: Use automatic decomosition method `2`: Use decomposition based on dot option .key	`-1`
deterministic	Specifies whether the solution improvement heuristic is run in deterministic or opportunistic (i.e. non-deterministic) mode `0`: Opportunistic `1`: Deterministic	`1`
divisor	Initial divisor for sub models Initial sub model size is model_size times 1 over Divisor. Ignored if InterDiv is set.	`automatic`
dynamicsearch	Search strategy for CPLEX caller and sub-model solves `-1`: Automatically determined `0`: Use traditional branch & cut `1`: Use dynamic search	`-1`
extracplexlog	Write addition CPLEX output to log `0`: Do not write extra CPLEX informtion `1`: Write extra CPLEX information	`0`
feastol	Feasibility tolerance Range: [`1e-9`, `0.1`]	`1e-6`
firstfeas	Use first feasible heuristic for finding an initial feasible solution The default for ODH-CPLEX is 1 while for the heuristic engine the default is -1. `-1`: Do not use `0`: Use if no solution found during initial presolve `1`: Always use	`-1`
firstfeascontinue	Whether first feasible heuristic continues when it achieves feasibility `0`: Do not continue `1`: Continue	`0`
firstfeaseffort	Effort limit on first feasible heuristic If the option value is positive the exact value is used as the level of effort. If the value is negative no more than the absolute value of the option is used as the level of effort. The larger the effort level, the more effort is expended before giving up.	`-500`
firstfeasshift	First feasible heuristic variable shifting in found solutions `0`: Do not shift `1`: Moderate shifting `2`: Aggressive shifting	`1`
globalbounds	Use of global bounds from CPLEX caller `0`: Never use `2`: Always use `1-4`: Intensity of use	`2`
indexkey	Pattern used to match variable names for grouping into sub-models discussed above
integeronly	Variables to include in INDEXKEY `-1`: Automatically determined `0`: All variables `1`: Only non-continuous variables	`-1`
integertol	Integrality tolerance for variable values	`1e-5`
interdiv	Initial divisor value	`4`
.key	Variable block or key number	`0`
keytype	Treatment of multiple INDEXKEYs `0`: Considered separately e.g. INDEXKEY=x_d;y_d means x_2 and y_2 belong to separate groups `1`: Considered together e.g. INDEXKEY=x_d;y_d means x_2 and y_2 belong to the same group	`0`
maxbacktrack	The maximum number of backtracks permitted in sub-model solves `-1`: Automatically determined `0`: Infinite `>0`: Use this value if a better solution is available	`-1`
maxbound	The largest(smallest) non infinite bound value ODH will accept for upper(lower) bounds If this value is positive, bounds exceeding MAXBOUND are reduced to MAXBOUND; if this value is negative, bounds exceeding -MAXBOUND are ignored.	`1e+9`
maxinfrepeat	Maximum divisor value when solution is infeasible `0`: Automatically determined `>0`: Use this value	`0`
maxinterdiv	Maximum divisor value	`0`
maxrepeat	Maximum number of sub-model repeat solves for each divisor value `0`: Automatically determined `>0`: Use this value	`0`
newcallback	CPLEX call-back type used `0`: Use legacy call-backs `1`: Use new call-backs for main CPLEX solve `2`: Use new call-backs for sub-model solves `3`: Use new call-backs for main CPLEX solve and sub-model solves	`1`
objtarget	Target objective value ODHeuristics terminates when this value is reached. Defaults to -infinity for minimization or +infinity for maximization models.	`0`
odheuristicmethod	ODHeuristic method section `ODH-CPLEX`: ODHeuristic within the CPLEX optimizer `STANDALONE`: Stand-alone ODHeuristic engine	`ODH-CPLEX`
odhfeasopt	Optimization method for sub-models in phaseI	`0`
odhpresolve	Indicator for the ODHeuristics engine using a separate presolve within ODH-CPLEX `0`: Do not do a separate presolve `1`: Do a separate presolve	`1`
odhthreads	The number of heuristic threads used by ODH-CPLEX or STANDALONE `-1`: Automatically determined `0`: Run in serial mode `>0`: Use the specified number of threads	`-1`
odhtimelimit	Elapsed time limit in seconds	`GAMS ResLim`
penalty	The objective function coefficient value for penalties The objective function coefficient value for the penalties introduced to deal with infeasibilities in the solution improvement heuristic. It is set by default when required and if not specified.	`-1`
penperturb	Perturbation tolerance for penalties coefficients	`0`
phase12	Specifies whether to use a phaseI/phaseII method to remove infeasibilities `0`: Use composite objective method `1`: Use phaseI/phaseII method	`1`
processorlock	Thread allocation `0`: Do not lock threads to processors `1`: Lock threads to processors	`0`
quickfirstsolve	Accelerate initial CPLEX solve `0`: Do not unless presolve applied to full model `1`: Use existing presolved model	`0`
recurse	Recurse using heuristic to solve sub-models when a feasible solution has been obtained `0`: Do not recurse `1`: Recurse thread 0 only `2`: Recurse odd numbered threads `3`: Recurse all threads `<0`: Recurse when working with an infeasible solution. values are negated (e.g. -3 = recursion of all threads)	`0`
recursedecomp	Recursed model decomposition method `-1`: Use initial model decomposition `0`: Assign each variable to a separate key `1`: Use automatic decomposition method	`0`
recurseiterlim	Recursed heuristic iteration limit for sub-solves	`40`
recurselog	Write thread log files for recursed sub-solves	`0`
recurseminiterlim	Recursed heuristic minimum iterations before a solution is found in sub-solves	`0`
recursesoliterlim	Recursed heuristic sub-solves quit after these iterations if a solution is found	`maxint`
rejectinfsol	Reject infeasible solutions to sub-models `0`: Do not check feasibility or reject `1`: Check feasibility and warn if infeasible, but accept `2`: Check feasibility and reject if infeasible	`2`
relaxsos2	Treatment of SOS2 members `0`: Aggressive use in reducing sub-model size `1`: Moderate use in reducing sub-model size `2`: Ignored in sub-model creation	`1`
seed	Initial random number seed	`1234`
strategy	ODH-Cplex Strategy The aggressive setting attempt to make more progress with each sub-model solve at the cost of more expensive sub solves. Amongst other changes, it sets InterDiv, MaxInterDiv and MaxRepeat if they are not explicitly set by the user. `0`: Conservative `1`: Normal `2`: Aggressiv	`1`
subnodelimit	Node limit for submodel searches `-1`: Automatically determined `>0`: Set node limit to this value	`-1`
suborder	Use of priority order in sub-solves `0`: Do not use any supplied priority order information in sub-solves `1`: Use any supplied priority order information in sub-solves	`1`
subpresolve	Use of CPLEX presolve in sub-solves `1`: Use normal presolve `2`: Use two-step presolve	`1`
sub_cpx_threads	Threads availble for the solves within ODHeuristic	`1`
syncfreq	Thread synchronization frequency in deterministic parallel mode `0`: Low frequency `1`: High frequency	`1`
threadlog	Write thread log files	`0`
threadzerosync	Which CPLEX threads to use for synchronization `0`: Synchronize with multiple CPLEX threads `1`: Only synchronize with CPLEX thread 0	`0`
variableclean	Clean variable values from sub-models `0`: No cleaning `1`: Quick cleaning and allow feasible uncleaned solutions if unable to clean `2`: Quick cleaning and disallow uncleaned solutions `3`: Thorough cleaning	`0`
zerotol	Zero tolerance for variable values	`1e-9`

Parallel execution using multiple threads

Both ODHeuristicMethods STANDALONE and ODH-CPLEX can use multiple simultaneous threads. ODH-CPLEX must use separate threads for the main CPLEX solve and for the ODHeuristics engine. The STANDALONE just uses the ODHeuristics engine which may use multiple simultaneous threads. Thus the processing capability of multi-core hardware can be exploited effectively.

GAMS/ODHCPLEX will ignore the GAMS threads parameter and use its own default. The default ODHeuristic method (i.e. ODH-CPLEX) requires multiple threads to works and with the GAMS threads default of 1 this will not work.

Whilst there are good defaults for allocating available threads, it may be worthwhile to give some attention to the allocation of threads between the main CPLEX solver and the ODHeuristics engine for ODH-CPLEX and STANDALONE.

If the option ODHThreads is set to n, n threads are allocated in total, otherwise the total number of threads allocated for both ODH-CPLEX and STANDALONE is set to the number of physical processors available on the computer. If the ODHThreads option is set to a number greater than the number of available processors, multiple threads will have to share the same processor, which may severely degrade performance.

In general, the more threads allocated to the main CPLEX solver, the faster it will run, and similarly, the more allocated to the ODHeuristics engine, the faster it will run. The best balance depends on the model being solved and whether it is intended to run to optimality or to an optimality gap of (say) 0.05 or 0.1. If the GAMS/Cplex Threads is not set, ODH-CPLEX defaults to allocating a quarter of the threads to the ODHeuristics engine and the remainder to the main CPLEX solve. Otherwise it allocates the specified number of threads to the main CPLEX solver and the remainder to the ODHeuristics engine.

Within the ODHeuristics engine, the principal heuristic algorithm can run in parallel on multiple threads. Each algorithmic thread uses CPLEX to solve sub-models and each such instance of CPLEX can itself run on multiple threads. So some attention needs to be given to the allocation of threads between them. If SUB_CPX_THREADS is not set, the CPLEX solver will use one thread for each available logical processor to solve the sub-models. This means that only one thread will be available for the solution improvement heuristic. If the option SUB_CPX_THREADS is set, then by default the heuristic engine sets its number of algorithmic threads to

number_of_available_processors / SUB_CPX_THREADS

where number_of_available_processors is: the number of logical processors for STANDALONE; and for ODH-CPLEX it is this number less those allocated to the main CPLEX solver.

Many Intel and compatible processors support hyperthreading (where this is enabled on the computer and operating system) and if so there will be two logical processors for every physical core. Using them can severely degrade performance, so if they are enabled it is often a good idea to set ODHThreads to the number of physical processors. Note that on machines with a large number of processors (cores), the principal bottleneck for large scale optimization is usually memory access. In practice it is often better to use only about half of the available cores on (say) a 24 core Intel Xeon system. This is model dependent and some experimentation is worthwhile.

Although the operating system's scheduler usually allocates threads to logical processors so that they run on separate physical cores where possible, it will have more threads to manage than those of the heuristic or CPLEX and so will change this allocation as the heuristic and CPLEX run so as to balance its workload effectively. There is a performance penalty to doing this from the perspective of the heuristic run time. For the ODHeuristics STANDALONE, this can be avoided by locking the heuristic threads to specific processors by setting the heuristic option parameter ProcessorLock to 1. It is not supported for ODH-CPLEX. Under Windows, beware that the threads need to be locked at an above normal priority so this may have a negative impact on other programs concurrently running on the machine.

Determinism

Many users require that repeated runs of their applications under the same conditions give the same results, albeit in slightly variable times. The heuristic runs in this way by default. However, there is a performance penalty that has to be paid for synchronizing the threads. On average, performance can be considerably improved performance at the expense of non-repeatable execution by setting the heuristic option parameter Deterministic to 0. This is often preferred by users with particularly large and difficult models.

Table of Contents