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.

2010-03-24