Tree Manager parameters

TM_verbosity – integer (0).

The verbosity of the TM module.

lp_exe, cg_exe, cp_exe – strings (“lp”, “cg”, “cp”).

The name of the LP, CG, and CP module binaries. Note: when running in parallel using PVM, these executables (or links to them) must reside in the PVM_ROOT/bin/PVM_ARCH/ directory. Also, be sure to note that the executable names may have extensions that depend on the configuration of the modules, but the defaults will always be set to the name that the makefile produces.

lp_debug, cg_debug, cp_debug – boolean (all FALSE).

Whether the modules should be started under a debugger or not.

max_active_nodes – integer (1).

The maximum number of processors/threads to be used.

max_cp_num – integer (0).

The maximum number of cut pools to be used.

lp_mach_num, cg_mach_num, cp_mach_num – integers (all 0).

The number of processors in the virtual machine to run LP (CG, CP) processes. If this value is 0 then the processes will be assigned to processors in round-robin order. Otherwise the next xx_mach_num lines describe the processors where the LP (CG, CP) modules must run. The keyword – value pairs on these lines must be TM_xx_machine and the name or IP address of a processor (the processor names need not be distinct). In this case the actual processes are assigned in a round robin fashion to the processors on this list.

This feature is useful if a specific software package is needed for some module, but that software is not licensed for every node of the virtual machine or if a certain process must run on a certain type of machine due to resource requirements.

use_cg – boolean (FALSE).

Whether to use a cut generator or not.

TM_random_seed – integer (17).

The random seed used in the TM.

unconditional_dive_frac – double (0.0).

The fraction of the nodes on which SYMPHONY randomly dives unconditionally into one of the children.

diving_strategy – integer (BEST_ESTIMATE{0}).

The strategy employed when deciding whether to dive or not.

The BEST_ESTIMATE{0} strategy continues to dive until the lower bound in the child to be dived into exceeds the parameter upper_bound_estimate, which is given by the user.

The COMP_BEST_K{1} strategy computes the average lower bound on the best diving_k search tree nodes and decides to dive if the lower bound of the child to be dived into does not exceed this average by more than the fraction diving_threshold.

The COMP_BEST_K_GAP{2} strategy takes the size of the gap into account when deciding whether to dive. After the average lower bound of the best diving_k nodes is computed, the gap between this average lower bound and the current upper bound is computed. Diving only occurs if the difference between the computed average lower bound and the lower bound of the child to be dived into is at most the fraction diving_threshold of the gap.

Note that fractional diving settings can override these strategies. See below.

diving_k, diving_threshold – integer, double (1, 0.05).

See above.

fractional_diving_ratio, fractional_diving_num – integer (0.02, 0).

Diving occurs automatically if the number of fractional variables in the child to be dived into is less than fractional_diving_num or the fraction of total variables that are fractional is less than fractional_diving_ratio. This overrides the other diving rules. Note that in order for this option to work, the code must be compiled with FRACTIONAL_BRANCHING defined. This is the default. See the makefile for more details.

node_selection_rule – integer (LOWEST_LP_FIRST{0}).

The rule for selecting the next search tree node to be processed. This rule selects the one with lowest lower bound. Other possible values are: HIGHEST_LP_FIRST{1}, BREADTH_FIRST_SEARCH{2} and DEPTH_FIRST_SEARCH{3}.

load_balance_level

– integer (-1).] A naive attempt at load balancing on problems where significant time is spent in the root node, contributing to a lack of parallel speed-up. Only a prescribed number of iterations (load_balance_iter) are performed in the root node (and in each subsequent node on a level less than or equal to load_balance_level) before branching is forced in order to provide additional subproblems for the idle processors to work on. This doesn't work well in general.

load_balance_iter

– integer (-1).] Works in tandem with the load_balance_level to attempt some simple load balancing. See the above description.

tighten_root_bounds

– boolean (TRUE).] Whether to tighten the global bounds on variables using the reduced costs from the root node.

status_interval

– integer (5).] How often to print status messages to the screen.

keep_description_of_pruned – integer (DISCARD{0}).

Whether to keep the description of pruned search tree nodes or not. The reasons to do this are (1) if the user wants to write out a proof of optimality using the logging function, (2) for debugging, or (3) to get a visual picture of the tree using the software VBCTOOL. Otherwise, keeping the pruned nodes around just takes up memory.

There are three options if it is desired to keep some description of the pruned nodes around. First, their full description can be written out to disk and freed from memory (KEEP_ON_DISK_FULL{1}). There is not really too much you can do with this kind of file, but theoretically, it contains a full record of the solution process and could be used to provide a certificate of optimality (if we were using exact arithmetic) using an independent verifier. In this case, the line following keep_description_of_pruned should be a line containing the keyword pruned_node_file_name with its corresponding value being the name of a file to which a description of the pruned nodes can be written. The file does not need to exist and will be over-written if it does exist.

If you have the software VBCTOOL, then you can alternatively just write out the information VBCTOOL needs to display the tree (KEEP_ON_DISK_VBC_TOOL{2}).

Finally, the user can set the value to of this parameter to KEEP_IN_MEMORY{2}, in which case all pruned nodes will be kept in memory and written out to the regular log file if that option is chosen. This is really only useful for debugging. Otherwise, pruned nodes should be flushed.

keep_warm_start – boolean (FALSE).

Turning this parameter on will have exactly the same impact with setting the keep_description_of_pruned to KEEP_IN_MEMORY{2}. This will allow SYMPHONY to keep all the necessary information obtained from the branching tree of the original problem to be able to warm start after a parameter or problem data modification. Thus, if it is intended to warm start later, the user should set this parameter before solving the original problem.

warm_start_node_limit – integer (SYM_INFINITY).

Setting this parameter will start the warm start routine using only the first warm_start_node_limit nodes generated during the previous solve procedure. The rest of the tree will be trimmed.

warm_start_node_ratio – double (0.0).

Setting this parameter will start the warm start routine using only the first warm_start_node_ratio% of the nodes generated during the previous solve procedure.

warm_start_node_level – integer (SYM_INFINITY).

Setting this parameter will start the warm start routine using all the nodes above the level warm_start_node_level of the tree generated during the previous solve procedure. The rest of the tree will be trimmed.

warm_start_node_level_ratio – double (0.0).

Setting this parameter will start the warm start routine using all the nodes above the level warm_start_node_level% of the warm start tree depth. The rest of the tree will be trimmed

logging – integer (NO_LOGGING{0}).

Whether or not to write out the state of the search tree and all other necessary data to disk periodically in order to allow a warm start in the case of a system crash or to allow periodic viewing with VBCTOOL.

If the value of this parameter is set to FULL_LOGGING{1}, then all information needed to warm start the calculation will written out periodically. The next two lines of the parameter file following should contain the keywords tree_log_file_name and cut_log_file_name along with corresponding file names as values. These will be the files used to record the search tree and related data and the list of cuts needed to reconstruct the tree.

If the value of the parameter is set to VBC_TOOL{2}, then only the information VBCTOOL needs to display the tree will be logged. This is not really a very useful option since a “live” picture of the tree can be obtained using the vbc_emulation parameter described below.

logging_interval – integer (1800).

Interval (in seconds) between writing out the above log files.

warm_start – boolean (0).

Used to allow the tree manager to make a warm start by reading in previously written log files. If this option is set, then the two line following must start with the keywords warm_start_tree_file_name and warm_start_cut_file_name and include the appropriate file names as the corresponding values.

vbc_emulation

– integer (NO_VBC_EMULATION{0}).] Determines whether or not to employ the VBCTOOL emulation mode. If one of these modes is chosen, then the tree will be displayed in “real time” using the VBCTOOL Software. When using the option VBC_EMULATION_LIVE{2} and piping the output directly to VBCTOOL, the tree will be displayed as it is constructed, with color coding indicating the status of each node. With VBC_EMULATION_FILE{1} selected, a log file will be produced which can later be read into VBCTOOL to produce an emulation of the solution process at any desired speed. If VBC_EMULATION_FILE is selected, the the following line should contain the keyword vbc_emulation_file_name along with the corresponding file name for a value.

price_in_root – boolean (FALSE).

Whether to price out variables in the root node before the second phase starts (called repricing the root).

trim_search_tree – boolean (FALSE).

Whether to trim the search tree before the second phase starts or not. Useful only if there are two phases. (It is very useful then.)

colgen_in_first_phase, colgen_in_second_phase – integers (both 4).

These parameters determine if and when to do column generation in the first and second phase of the algorithm. The value of each parameter is obtained by setting the last four bits. The last two bits refer to what to do when attempting to prune a node. If neither of the last two bits are set, then we don't do anything—we just prune it. If only the last bit is set, then we simply save the node for the second phase without doing any column generation (yet). If only the second to last bit is set, then we do column generation immediately and resolve if any new columns are found. The next two higher bits determine whether or not to do column generation before branching. If only the third lowest bit is set, then no column generation occurs before branching. If only the fourth lowest bit is set, then column generation is attempted before branching. The default is not to generate columns before branching or fathoming, which corresponds to only the third lowest bit being set, resulting in a default value of 4.

time_limit – double (-1.0).

Number of seconds of wall-clock time allowed for solution. When this time limit is reached, the solution process will stop and the best solution found to that point, along with other relevant data, will be output. A time limit less than 0.0 means there is no limit.

node_limit – integer (-1).

Number of nodes allowed to be analyzed during the solution. When this node limit is reached, the solution process will stop and the best solution found to that point, along with other relevant data, will be output. A node limit less than 0 means there is no limit.

gap_limit – double (-1.0).

Target gap limit used to determine when the solver should terminate. When the gap between the lower and the upper bound reaches this point, the solution process will stop and the best solution found to that point, along with other relevant data, will be output. This parameter expresses the target gap as a percentage relative to the current lower bound. For example, a gap limit equal to 10 means that the solution process will stop when the best solution is within 10% of the current lower bound (which is a proxy for the optimal value itself). Additionally, a gap limit less than or equal to 0 means the solution produced is the exact optimum.

find_first_feasible – boolean (FALSE).

Whether to stop after finding the first feasible solution or not.

sensitivity_analysis – boolean (FALSE).

If the user wants to do the rudimentary sensitivity analysis, which will give a lower bound for the problem modified by the right hand side, then, this parameter has to be set before solving the original problem. If it is set, SYMPHONY will keep the necessary information from the solution processes of the original problem to be able to do the sensitivity analysis later.