[ library(bfs) | Reference Manual | Alphabetic Index ]

BfsInstance:solver_setup(+OptSense, +Solver, ++ListOfOptions)

Setup a bfs solver tree for bfs instance BfsInstance.
OptSense
Optimisation direction: min or max
Solver
Node relaxation solver
ListOfOptions
List of solver options

Description

Setup a new solver tree for the bfs instance BfsInstance. The tree will be associated with BfsInstance; BfsInstance must not already have a solver tree associated with it. Once the solver tree is setup, it can be optimised via solve/1. This predicate allow various options to be specified when setting up the solver state via ListOfOptions.

OptSense is the optimisation direction. Note that this is assumed to be the same as the sense of optimisation used in Solver. It is the user's responsibility to ensure that this is in fact the case. OptSense is used internally for bound updates and pruning, and for node ordering with the built-in best-first and best-estimate node selection methods.

Solver is the node relaxed problem solver. It is either a user-defined predicate or an eplex instance or handle, for which a built-in node relaxation solver is available.

ListOfOptions are:

separation(+Separation)
Use the specified method to separate the current node. Separation is either a user-defined predicate, or one of the atoms fracvar, enhanced, strong, deg_est corresponding to the built-in separation methods. Note that the methods enhanced, strong, deg_est are only available when the node relaxation solver involves an eplex instance. Separation defaults to fracvar.

node_select(+Select)
Use the specified method (depth_first, best_first, best_estimate) to select the next open node for solution and separation. Select defaults to best_first.

alpha(?AlphaMin, ?AlphaMax)
When using estimate- or lower-bounding based dichotomic node separation methods the overall value assigned to branching on a particular variable or constraint is calculated as a weighted sum of the estimates obtained for the two branches it would produce. AlphaMin is the weighting given to the minimum of the two estimates and AlphaMax to the maximum. AlphaMin and AlphaMax are numbers and default to 2 and 1 respectively.

beta(?BetaConst, ?BetaPC, ?BetaLB)
When using estimate- or lower-bounding based node separation methods with a problem involving an eplex instance the estimate assigned to each branch produced by branching on a particular variable or constraint is calculated as a weighted sum of the pseudo-cost estimate and the lower bound. BetaPC is the weighting given to the pseudo-cost estimate and BetaLB to the lower bound. BetaConst is a constant offset only used when linear regression is employed to update these values during search. BetaConst, BetaPC, BetaLB are numbers and default to 0, 1, 1 respectively.

pseudo_cost(?PCInit, ?PCUpdate, ?PCRatio)

When using estimate-based dichotomic node separation methods with a problem involving an eplex instance up and down pseudo-costs are assigned to each variable and generalised upper bound constraint branch-point representing the estimated degradation in objective cost per unit change in variable or constraint value incurred on that branch.

PCInit specifies the method used to initialise these values when a variable or constraint branch-point is first considered for branching:

average : the pseudocosts are initialised to the average of the observed changes in cost of all up or down branches in the search tree.
cost : variable pseudocosts are initialised to the objective cost coefficient of the variable, constraint branch-point pseudocosts to the average of the cost coefficients of variables involved.
calculated : the pseudocosts are initialised to a value calculated by performing a number of external solver iterations equal to (PCRatio * #iterations in root node)/(2* #fractional vars in root node).
The default is calculated.

PCUpdate is an atom specifying the method used to update these values throughout the search tree once the variable or constraint has been branched on:

average : the pseudocosts are updated to the average of the observed changes in cost of all up or down branches in the search tree for that variable or constraint.
first : the pseudocosts are fixed to the observed change in cost at the first up or down branch in the search tree for that variable or constraint.
last : the pseudocosts are fixed to the observed change in cost at the last up or down branch in the search tree for that variable or constraint.
The default is average.

PCRatio is a float between 0 and 1 and is used in calculating the number of external solver iterations to perform when explicitly calculating initial pseudo-cost estimates; the default value is 0.05. Setting small ratios will result in faster node separation, but the initial estimates for variables and constraints on which the branching decisions are taken will be less accurate. Setting larger values will result in more work being performed in node separation and better estimates for the branching decisions. The optimum value will be problem specific, although in general the overhead of performing a total number of iterations more than a small ratio of the root node iterations will outweigh the benefit obtained.

lower_bound(+Limit)
When using lower-bounding based node separation methods with a problem involving an eplex instance, specify how many external solver iterations should be performed to calculate the lower bound. Limit is an integer and defaults to 1. Setting small values of iterations will result in faster node separation, but the lower bounds on which the branching decisions are taken will be less tight. Setting larger values will result in more work being performed in node separation and tighter lower bounds for the branching decisions. The optimum value will be problem specific, although in general the overhead of performing more than a few iterations will outweigh the benefit obtained.

int_tolerance(+IntTol)
Specify how far from integrality an integer variable's node solution can fall before it is considered for separation by the built-in separation methods. IntTol is a float and defaults to 0.00001.

info_messages(+OnOff)
Specify whether information messages should be output at various points during solution. This option is most useful for debugging purposes. OnOff is one of the atoms on or off, the default is off.

See Also

integers / 1, bfs_branch / 1, node_info / 5, solver_setup / 2, solve / 1, get / 2, var_get / 3, statistics / 0