ODHCPLEX

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:

  1. Automatically using its decomposition heuristic;
  2. Using information specified by the user in the IndexKey parameter;
  3. By simply assigning each variable to a different block (or key); or
  4. 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
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
dynamicsearch Search strategy for CPLEX caller and sub-model solves
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
interdiv Initial divisor value 0
.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
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
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
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.
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
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
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.
1 Normal
2 Aggressiv
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
variableclean Clean variable values from sub-models
-1 Automatic
0 No cleaning
1 All variable values cleaned
-1

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.