Tree Manager parameters

TM_verbosity - integer (0).

[p]Tree Manager Parameters!TM_verbosity The verbosity of the TM module.

lp_exe, cg_exe, cp_exe - strings (``lp'', ``cg'', ``cp'').

[p]Tree Manager Parameters!lp_exe [p]Tree Manager Parameters!cg_exe [p]Tree Manager Parameters!cp_exe 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).

[p]Tree Manager Parameters!lp_debug [p]Tree Manager Parameters!cg_debug [p]Tree Manager Parameters!cp_debug Whether the modules should be started under a debugger or not.

max_active_nodes - integer (1).

[p]Tree Manager Parameters!max_active_nodes The maximum number of active search tree nodes--equal to the number of LP and CG tandems to be started up.

max_cp_num - integer (0).

[p]Tree Manager Parameters!max_cp_num The maximum number of cut pools to be used.

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

[p]Tree Manager Parameters!lp_mach_num [p]Tree Manager Parameters!cg_mach_num [p]Tree Manager Parameters!cp_mach_num 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).

[p]Tree Manager Parameters!use_cg Whether to use a cut generator or not.

TM_random_seed - integer (17).

[p]Tree Manager Parameters!TM_random_seed The random seed used in the TM.

unconditional_dive_frac - double (0.0).

[p]Tree Manager Parameters!unconditional_dive_frac The fraction of the nodes on which SYMPHONY randomly dives unconditionally into one of the children.

diving_strategy - integer (BEST_ESTIMATE{0}).

[p]Tree Manager Parameters!diving_strategy 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).

[p]Tree Manager Parameters!diving_k [p]Tree Manager Parameters!diving_threshold See above.

fractional_diving_ratio, fractional_diving_num - integer (0.02, 0).

[p]Tree Manager Parameters!fractional_diving_ratio [p]Tree Manager Parameters!fractional_diving_num

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}).

[p]Tree Manager Parameters!node_selection_rule 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).] [p]Tree Manager Parameters!load_balance_level 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).] [p]Tree Manager Parameters!load_balance_iter Works in tandem with the load_balance_level to attempt some simple load balancing. See the above description.

keep_description_of_pruned - integer (DISCARD{0}).

[p]Tree Manager Parameters!keep_description_of_pruned 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).

[p]Tree Manager Parameters!keep_warm_start 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).

[p]Tree Manager Parameters!warm_start_node_limit 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).

[p]Tree Manager Parameters!warm_start_node_ratio 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).

[p]Tree Manager Parameters!warm_start_node_level 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).

[p]Tree Manager Parameters!warm_start_node_level_ratio 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}).

[p]Tree Manager Parameters!logging 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).

[p]Tree Manager Parameters!logging_interval Interval (in seconds) between writing out the above log files.

warm_start - boolean (0).

[p]Tree Manager Parameters!warm_start 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}).] [p]Tree Manager Parameters!vbc_emulation 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).

[p]Tree Manager Parameters!price_in_root Whether to price out variables in the root node before the second phase starts (called repricing the root).

trim_search_tree - boolean (FALSE).

[p]Tree Manager Parameters!trim_search_tree 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).

[p]Tree Manager Parameters!colgen_in_first_phase [p]Tree Manager Parameters!colgen_in_second_phase 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).

[p]Tree Manager Parameters!time_limit 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).

[p]Tree Manager Parameters!node_limit 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).

[p]Tree Manager Parameters!gap_limit Target gap limit allowed for solution. 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. A gap limit less than 0 means there is no limit.

find_first_feasible - boolean (FALSE).

[p]Tree Manager Parameters!find_first_feasible Whether to stop after finding the first feasible solution or not.

sensitivity_analysis - boolean (FALSE).

[p]Tree Manager Parameters!sensitivity_analysis 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.