A description of the various control options that can be set in an lpSolve linear program model object using the lp.control function.
a character vector containing one or more of the following options. If any element is "none" then no anti-degeneracy handling is used.
"none": | No anti-degeneracy handling. |
"fixedvars": | Check if there are equality slacks in the basis and try to drive them out in order to reduce chance of degeneracy in Phase 1. |
"columncheck": | |
"stalling": | |
"numfailure": | |
"lostfeas": | |
"infeasible": | |
"dynamic": | |
"duringbb": | |
"rhsperturb": | Perturbation of the working RHS at refactorization |
"boundflip": | Limit bound flips that can sometimes contribute to degeneracy in some models. |
The default is c("infeasible", "stalling", "fixedvars").
a character string specifying the basis crash mode to use. When no basis crash is done the initial basis from which lpSolve starts is the basis containing all slack or artificial variables. When basis crash is enabled, a heuristic crash procedure is executed before the first simplex iteration to quickly choose a basis matrix that has fewer artificial variables. This procedure tends to reduce the number of iterations required by the solver. The choices for this option are given in the following table.
"none": | No basis crash. |
"mostfeasible": | Most feasible basis. |
"leastdegenerate": | Construct a basis that is in some sense the least degenerate. |
The default is "none".
a single integer value specifying the maximum branch-and-bound depth. A positive value means that the depth limit is absolute. A negative value means a relative branch-and-bound depth limit. The order of an MIP problem is defined to be 2 times the number of binary variables plus the number of semi-continuous (SC) and special-ordered-sets (SOS) variables. A relative value of -x results in a maximum depth of x times the order of the MIP problem.
This control option only applies if there are integer, SC or SOS variables in the model (i.e., when the branch-and-bound algorithm is used). The branch-and-bound algorithm will not go deeper than this level. Limiting the depth speeds up the solving time but there is a chance that the solution obtained is sub-optimal. Be aware of this. Another possible consequence is that no solution will be found.
The default value is -50; a value of zero implies no limit to the depth.
a character string from among the following choices specifying which branch to take first in the branch-and-bound algorithm.
"ceiling": | Take ceiling branch first. |
"floor": | Take floor branch first. |
"auto": | lpSolve decides which branch to take first. |
The value of this option can influence solving times considerably. However, the real-world performance will be model dependent. The default is "auto".
a character vector specifying the branch-and-bound rule. The first element must be chosen from the following table.
"first": | Select the lowest indexed non-integer column. |
"gap": | Selection based on the distance from the current bounds. |
"range": | Selection based on the largest current bound. |
"fraction": | Selection based on the largest fractional value. |
"pseudocost": | Simple, unweighted pseudo-cost of a variable. |
"pseudononint": | An extended pseudo-costing strategy based on minimizing the number of integer infeasibilities. |
"pseudoratio": | An extended pseudo-costing strategy based on maximizing the normal pseudo-cost divided by the number of infeasibilities. Effectively, it is similar to (the reciprocal of) a cost/benefit ratio. |
Additional modes (if any) may be appended to augment the rule specified in the first element of bb.rule.
"weightreverse": | Select by criterion minimum (worst), rather than by criterion maximum (best). |
"branchreverse": | When bb.floorfirst is "auto", select the direction (lower/upper branch) opposite to that chosen by lpSolve. |
"greedy": | |
"pseudocost": | Toggle between weighting based on pseudocost or objective function value. |
"depthfirst": | Select the node that has been selected before the most number of times. |
"randomize": | Add a randomization factor to the score for all the node candidates. |
"gub": | This option is still in development and should not be used at this time. |
"dynamic": | When "depthfirst" is selected, switch it off once the first solution is found. |
"restart": | Regularly restart the pseudocost value calculations. |
"breadthfirst": | Select the node that has been selected the fewest number of times (or not at all). |
"autoorder": | Create an optimal branch-and-bound variable ordering. Can speed up branch-and-bound algorithm. |
"rcostfixing": | Do bound tightening during branch-and-bound based on the reduced cost information. |
"stronginit": | Initialize pseudo-costs by strong branching. |
The value of this rule can influence solving times considerably. However, the real-world performance will be model dependent. The default value is c("pseudononint", "greedy", "dynamic", "rcostfixing").
a logical value. If TRUE then the branch-and-bound algorithm stops at the first solution found. The default (FALSE) is to continue until an optimal solution is found.
a numeric value. The branch-and-bound algorithm stops if the objective function becomes better than this value. The default (\(\pm\)infinity) is to continue until an optimal value is found.
a character string providing a simplified way of specifying multiple tolerance thresholds in a logically consistent way. The following values are set: epsel, epsb, epsd, epspivot, epsint and mip.gap.
"tight": | Use tight tolerance values. |
"medium": | Use medium tolerance values. |
"loose": | Use loose tolerance values. |
"baggy": | Use very loose tolerance values. |
The default is "tight".
a single positive numeric value specifying the tolerance used to determine whether a right-hand-side value should be considered zero. Rounding error in floating-point calculations may result in a loss of precision. A very small value (for example, 1e-99) could be the result of such errors and should be considered zero by the solver. If the absolute value of a right-hand-side value is less than epsb then it is treated as zero by the solver. The default value is 1.0e-10.
a single positive numeric value specifying the tolerance used to determine whether a computed reduced cost should be considered zero. Rounding error in floating-point calculations may result in a loss of precision. A very small value (for example, 1e-99) could be the result of such errors and should be considered zero by the solver. If the absolute value of a computed reduced cost is less than epsd then it is treated as zero by the solver. The default value is 1.0e-9.
a single positive numeric value specifying the tolerance used for rounding values to zero. Rounding error in floating-point calculations may result in a loss of precision. A very small value (for example, 1e-99) could be the result of such errors and should be considered zero by the solver. If the absolute value of a computed value is less than epsel then it is rounded to zero by the solver. The default value is 1.0e-12. This parameter is used in situations where none of epsint, epsb, epsd, epspivot norepsperturb apply.
a single positive numeric value specifying the tolerance used to determine whether a floating-point number is an integer. This parameter only applies when there is at least one integer variable so that the branch and bound algorithm is used. Integer variables are internally stored as floating-point. A tolerance is therefore needed to determine whether a value should be considered an integer. If the absolute value of the variable minus the closest integer is less than epsint then it is considered an integer. The default value is 1.0e-7.
a single positive numeric value specifying the perturbation scalar for degenerate problems. The default is 1.0e-5.
a single positive numeric value specifying the tolerance used to determine whether a pivot element is zero. Rounding error in floating-point calculations may result in a loss of precision. A very small value (for example, 1e-99) could be the result of such errors and should be considered zero by the solver. If the absolute value of a computed pivot element is less than epspivot then it is treated as zero by the solver. Pivots will be performed on elements smaller (in absolute terms) than epspivot when no other larger pivot element can be found. The default value is 2.0e-7.
a character vector specifying the iterative improvement level. The possible values are given in the following table.
"none": | None. |
"solution": | Running accuracy measurement of solved equations based on \(Bx=r\) (primal simplex), remedy is refactorization. |
"dualfeas": | Improve initial dual feasibility by bound flips (highly recommended). |
"thetagap": | Low-cost accuracy monitoring in the dual, remedy is refactorization. |
"bbsimplex": | By default there is a check for primal/dual feasibility at the optimum only for the relaxed problem, this also activates the test at the node level. |
The default is c("dualfeas", "thetagap").
a positive numeric value specifying the practical value for infinity. This value is used for very large numbers, for example the upper bound of a variable without an upper bound. The default is 1.0e30.
a positive integer value specifying the maximum number of pivots between re-inversion of the matrix. For stability, lpSolve periodically re-inverts the matrix. However, the more often this is done, the slower the solver becomes. The default is 250.
a numeric vector of length two specifying respectively the absolute and relative MIP gaps used in the branch-and-bound algorithm. This tolerance is the difference between the best-found solution yet and the current solution. If the difference is smaller than this tolerance then the solution (and all the sub-solutions) is rejected. This can result in faster solving times, but results in a solution which is not the perfect solution. The default is 1.0e-11.
a nonpositive numeric value below which variables are split into negative and positive parts. The default is -1.0e6.
a logical value specifying whether the objective function is stored in the matrix. The default is to store the objective function in the top row of the constraint matrix. If FALSE then the objective function is moved to separate storage. When the objective function is not stored in the basis the computation of reduced costs is somewhat slower. In the later versions of v5.5 there is the option to calculate reduced cost in the textbook way: completely independently of the basis.
a character vector specifying the pivot rule (the rule for selecting row and column entering/leaving) and mode. The first element of this vector must be one of the four pivot rules listed in the first table. Remaining elements (if any) specify modes that modify this rule. The rule/mode can influence solving times considerably.
"firstindex": | Select first. |
"dantzig": | Select according to Dantzig. |
"devex": | Devex pricing from Paula Harris. |
"steepestedge": | Steepest edge. |
"primalfallback": | When using the steepest edge rule, fall back to "devex" in the primal. |
"multiple": | A preliminary implementation of the multiple pricing scheme. Attractive candidate columns from one iteration may be used in subsequent iterations thus avoiding full updating of reduced costs. In the current implementation, lpSolve only reuses the second best entering column alternative. |
"partial": | Enables partial pricing. |
"adaptive": | Temporarily use an alternative strategy if cycling is detected. |
"randomize": | Adds a small randomization effect to the selected pricer. |
"autopartial": | Indicates automatic detection of segmented/staged/blocked models. It refers to partial pricing rather than full pricing. With full pricing, all non-basic columns are scanned, but with partial pricing only a subset is scanned for every iteration. This can speed up several models. |
"loopleft": | Scan entering/leaving columns left rather than right. |
"loopalternate": | Scan entering/leaving columns alternating left/right. |
"harristwopass": | Use Harris' primal pivot logic rather than the default. |
"truenorminit": | Use true norms for Devex and steepest edge initializations. |
The default is c("devex", "adaptive").
a character vector specifying presolve steps to be carried out before solving. Presolve looks at the model and tries to simplify it so that solving times are shorter. For example a constraint on only one variable is converted to a bound on this variable (and the constraint is deleted) - the model dimensions can change because of this. Both rows and columns can be deleted by the presolve. Also, note that the "lindep" presolve option can result in the deletion of rows (the linear dependent ones). The get.constraints function will then return only the values of the rows that are kept.
The presolve options are given in the following table. If any element of presolve is "none" then no presolving is done.
"none": | No presolve. |
"rows": | Presolve rows. |
"cols": | Presolve columns. |
"lindep": | Eliminate linearly dependent rows. |
"sos": | Convert constraints to special ordered sets (SOS), only SOS1 is handled. |
"reducemip": | Constraints found redundant in phase 1 are deleted. This is no longer active since it is rarely effective and also because it adds code complications and delayed presolve effects that are not captured properly. |
"knapsack": | Simplification of knapsack-type constraints through the addition of an extra variable. This also helps bound the objective function. |
"elimeq2": | Direct substitution of one variable in 2-element equality constraints; this requires changes to the constraint matrix. |
"impliedfree": | Identify implied free variables (releasing their explicit bounds). |
"reducegcd": | Reduce (tighten) coefficients in integer models based on GCD argument. |
"probefix": | Attempt to fix binary variables at one of their bounds. |
"probereduce": | Attempt to reduce coefficients in binary models. |
"rowdominate": | Identify and delete qualifying constraints that are dominated by others, also fixes variables at a bound. |
"coldominate": | Delete variables (mainly binary) that are dominated by others (only one can be non-zero). |
"mergerows": | Merges neighboring >= or <= constraints when the vectors are otherwise relatively identical into a single ranged constraint. |
"impliedslk": | Converts qualifying equalities to inequalities by converting a column singleton variable to a slack variable. The routine also detects implicit duplicate slacks from inequality constraints and fixes and removes the redundant variable. This removal also tends to reduce the risk of degeneracy. The combined function of this option can have a dramatic simplifying effect on some models. |
"colfixdual": | Variable fixing and removal based on the signs of the associated dual constraint. |
"bounds": | Bound tightening based on full-row constraint information. This can assist in tightening the objective function bound, eliminate variables and constraints. At the end of presolve, it is checked if any variables can be deemed free, thereby reducing any chance that degeneracy is introduced via this presolve option. |
"duals": | Calculate duals. |
"sensduals": | Calculate sensitivity if there are integer variables. |
The default is c("none").
a numeric value specifying the relative scaling convergence criterion for the active scaling mode; the integer part specifies the maximum number of iterations. The default is 5.
a character vector specifying the scaling algorithm used and zero or more augmentations. The first element must be one of the scaling algorithms given in the following table.
"none": | No scaling (not advised). |
"extreme": | Scale to convergence using largest absolute value. |
"range": | Scale based on the simple numerical range. |
"mean": | Numerical range-based scaling. |
"geometric": | Geometric scaling. |
"curtisreid": | Curtis-Reid scaling. |
Additional elements (if any) from the following table can be included to augment the scaling algorithm.
"quadratic": | |
"logarithmic": | Scale to convergence using logarithmic mean of all values. |
"power2": | Power scaling. |
"equilibrate": | Make sure that no scaled number is above 1. |
"integers": | Scale integer variables. |
"dynupdate": | Recompute scale factors when resolving the model. |
"rowsonly": | Only scale rows. |
"colsonly": | Only scale columns. |
By default, lpSolve computes scale factors once for the original model. If a solve is done again (most probably after changing some data in the model), the scaling factors are not recomputed. Instead, the scale factors from the original model are used. This is not always desirable, especially if the data has changed considerably. Including "dynupdate" among the scale algorithm augmentations instructs lpSolve to recompute the scale factors each time solve is called. Note that the scaling done by "dynupdate" is incremental and the resulting scale factors are typically different from those computed from scratch.
The default is c("geometric", "equilibrate", "integers").
one of "max" or "min" specifying whether the model is a maximization or a minimization problem.
a character vector of length one or two composed of "primal" and "dual". If length two then the first element describes the simplex type used in phase 1 and the second element the simplex type used in phase 2. If length one then that simplex type is used for both phases. The default is c("dual", "primal").
a positive integer value specifying the number of seconds after which a timeout will occur. If zero, then no timeout will occur.
a character string controlling the severity of messages reported by lp_solve. The possible choices are given in the table below. All errors/warnings in lp_solve have a particular severiy: for example, specifying a wrong row or column index is considered a severe error. All messages equal to and below the set level are reported (in the console).
"neutral": | No reporting. |
"critical": | Only critical messages are reported. Hard errors like instability, out of memory, etc. |
"severe": | Only severe messages are reported. Errors. |
"important": | Only important messages are reported. Warnings and Errors. |
"normal": | Normal messages are reported. |
"detailed": | Detailed messages are reported. Like model size, continuing B&B improvements, etc. |
"full": | All messages are reported. Useful for debugging purposes and small models. |
Kjell Konis kjell.konis@me.com
lp.control