 |
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
Static Public Member Functions | |
| static final com.google.protobuf.Descriptors.Descriptor | getDescriptor () |
Protected Member Functions | |
| com.google.protobuf.GeneratedMessage.FieldAccessorTable | internalGetFieldAccessorTable () |
next id = 72
Protobuf type operations_research.glop.GlopParameters
Definition at line 3941 of file GlopParameters.java.
| com.google.ortools.glop.GlopParameters com.google.ortools.glop.GlopParameters.Builder.build | ( | ) |
Definition at line 4046 of file GlopParameters.java.
| com.google.ortools.glop.GlopParameters com.google.ortools.glop.GlopParameters.Builder.buildPartial | ( | ) |
Definition at line 4055 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clear | ( | ) |
Definition at line 3969 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearAllowSimplexAlgorithmChange | ( | ) |
During incremental solve, let the solver decide if it use the primal or dual simplex algorithm depending on the current solution and on the new problem. Note that even if this is true, the value of use_dual_simplex still indicates the default algorithm that the solver will use.
optional bool allow_simplex_algorithm_change = 32 [default = false];
Definition at line 7114 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearBasisRefactorizationPeriod | ( | ) |
Number of iterations between two basis refactorizations. Note that various conditions in the algorithm may trigger a refactorization before this period is reached. Set this to 0 if you want to refactorize at each step.
optional int32 basis_refactorization_period = 19 [default = 64];
Definition at line 6068 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearChangeStatusToImprecise | ( | ) |
If true, the internal API will change the return status to imprecise if the solution does not respect the internal tolerances.
optional bool change_status_to_imprecise = 58 [default = true];
Definition at line 6538 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearCostScaling | ( | ) |
optional .operations_research.glop.GlopParameters.CostScalingAlgorithm cost_scaling = 60 [default = CONTAIN_ONE_COST_SCALING];
Definition at line 5878 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearCrossoverBoundSnappingDistance | ( | ) |
If the starting basis contains FREE variable with bounds, we will move any such variable to their closer bounds if the distance is smaller than this parameter. The starting statuses can contains FREE variables with bounds, if a user set it like this externally. Also, any variable with an initial BASIC status that was not kept in the initial basis is marked as FREE before this step is applied. Note that by default a FREE variable is assumed to be zero unless a starting value was specified via SetStartingVariableValuesForNextSolve(). Note that, at the end of the solve, some of these FREE variable with bounds and an interior point value might still be left in the final solution. Enable push_to_vertex to clean these up.
optional double crossover_bound_snapping_distance = 64 [default = inf];
Definition at line 8546 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearDegenerateMinistepFactor | ( | ) |
During a degenerate iteration, the more conservative approach is to do a step of length zero (while shifting the bound of the leaving variable). That is, the variable values are unchanged for the primal simplex or the reduced cost are unchanged for the dual simplex. However, instead of doing a step of length zero, it seems to be better on degenerate problems to do a small positive step. This is what is recommended in the EXPAND procedure described in: P. E. Gill, W. Murray, M. A. Saunders, and M. H. Wright. "A practical anti- cycling procedure for linearly constrained optimization". Mathematical Programming, 45:437\u2013474, 1989. Here, during a degenerate iteration we do a small positive step of this factor times the primal (resp. dual) tolerance. In the primal simplex, this may effectively push variable values (very slightly) further out of their bounds (resp. reduced costs for the dual simplex). Setting this to zero reverts to the more conservative approach of a zero step during degenerate iterations.
optional double degenerate_ministep_factor = 42 [default = 0.01];
Definition at line 7818 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearDevexWeightsResetPeriod | ( | ) |
Devex weights will be reset to 1.0 after that number of updates.
optional int32 devex_weights_reset_period = 33 [default = 150];
Definition at line 7170 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearDropMagnitude | ( | ) |
Value in the input LP lower than this will be ignored. This is similar to drop_tolerance but more aggressive as this is used before scaling. This is mainly here to avoid underflow and have simpler invariant in the code, like a * b == 0 iff a or b is zero and things like this.
optional double drop_magnitude = 71 [default = 1e-30];
Definition at line 8822 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearDropTolerance | ( | ) |
In order to increase the sparsity of the manipulated vectors, floating point values with a magnitude smaller than this parameter are set to zero (only in some places). This parameter should be positive or zero.
optional double drop_tolerance = 52 [default = 1e-14];
Definition at line 5776 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearDualFeasibilityTolerance | ( | ) |
Variables whose reduced costs have an absolute value smaller than this tolerance are not considered as entering candidates. That is they do not take part in deciding whether a solution is dual-feasible or not. Note that this value can temporarily increase during the execution of the algorithm if the estimated precision of the reduced costs is higher than this tolerance. Note also that we scale the costs (in the presolve step) so that the cost magnitude range contains one. This is also known as the optimality tolerance in other solvers.
optional double dual_feasibility_tolerance = 11 [default = 1e-08];
Definition at line 5412 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearDualizerThreshold | ( | ) |
When solve_dual_problem is LET_SOLVER_DECIDE, take the dual if the number of constraints of the problem is more than this threshold times the number of variables.
optional double dualizer_threshold = 21 [default = 1.5];
Definition at line 6270 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearDualPricePrioritizeNorm | ( | ) |
On some problem like stp3d or pds-100 this makes a huge difference in speed and number of iterations of the dual simplex.
optional bool dual_price_prioritize_norm = 69 [default = false];
Definition at line 8882 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearDualSmallPivotThreshold | ( | ) |
Like small_pivot_threshold but for the dual simplex. This is needed because the dual algorithm does not interpret this value in the same way. TODO(user): Clean this up and use the same small pivot detection.
optional double dual_small_pivot_threshold = 38 [default = 0.0001];
Definition at line 7490 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearDynamicallyAdjustRefactorizationPeriod | ( | ) |
If this is true, then basis_refactorization_period becomes a lower bound on the number of iterations between two refactorization (provided there is no numerical accuracy issues). Depending on the estimated time to refactorize vs the extra time spend in each solves because of the LU update, we try to balance the two times.
optional bool dynamically_adjust_refactorization_period = 63 [default = true];
Definition at line 6140 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearExploitSingletonColumnInInitialBasis | ( | ) |
Whether or not we exploit the singleton columns already present in the problem when we create the initial basis.
optional bool exploit_singleton_column_in_initial_basis = 37 [default = true];
Definition at line 7426 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearFeasibilityRule | ( | ) |
PricingRule to use during the feasibility phase.
optional .operations_research.glop.GlopParameters.PricingRule feasibility_rule = 1 [default = STEEPEST_EDGE];
Definition at line 4962 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearHarrisToleranceRatio | ( | ) |
This impacts the ratio test and indicates by how much we allow a basic variable value that we move to go out of bounds. The value should be in [0.0, 1.0) and should be interpreted as a ratio of the primal_feasibility_tolerance. Setting this to 0.0 basically disables the Harris ratio test while setting this too close to 1.0 will make it difficult to keep the variable values inside their bounds modulo the primal_feasibility_tolerance. Note that the same comment applies to the dual simplex ratio test. There, we allow the reduced costs to be of an infeasible sign by as much as this ratio times the dual_feasibility_tolerance.
optional double harris_tolerance_ratio = 13 [default = 0.5];
Definition at line 5588 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearInitialBasis | ( | ) |
What heuristic is used to try to replace the fixed slack columns in the initial basis of the primal simplex.
optional .operations_research.glop.GlopParameters.InitialBasisHeuristic initial_basis = 17 [default = TRIANGULAR];
Definition at line 5940 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearInitialConditionNumberThreshold | ( | ) |
If our upper bound on the condition number of the initial basis (from our heurisitic or a warm start) is above this threshold, we revert to an all slack basis.
optional double initial_condition_number_threshold = 59 [default = 1e+50];
Definition at line 8314 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearInitializeDevexWithColumnNorms | ( | ) |
Whether we initialize devex weights to 1.0 or to the norms of the matrix columns.
optional bool initialize_devex_with_column_norms = 36 [default = true];
Definition at line 7366 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearLogSearchProgress | ( | ) |
If true, logs the progress of a solve to LOG(INFO). Note that the same messages can also be turned on by displaying logs at level 1 for the relevant files.
optional bool log_search_progress = 61 [default = false];
Definition at line 8378 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearLogToStdout | ( | ) |
If true, logs will be displayed to stdout instead of using Google log info.
optional bool log_to_stdout = 66 [default = true];
Definition at line 8434 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearLuFactorizationPivotThreshold | ( | ) |
Threshold for LU-factorization: for stability reasons, the magnitude of the chosen pivot at a given step is guaranteed to be greater than this threshold times the maximum magnitude of all the possible pivot choices in the same column. The value must be in [0,1].
optional double lu_factorization_pivot_threshold = 25 [default = 0.01];
Definition at line 6674 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearMarkowitzSingularityThreshold | ( | ) |
If a pivot magnitude is smaller than this during the Markowitz LU factorization, then the matrix is assumed to be singular. Note that this is an absolute threshold and is not relative to the other possible pivots on the same column (see lu_factorization_pivot_threshold).
optional double markowitz_singularity_threshold = 30 [default = 1e-15];
Definition at line 6990 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearMarkowitzZlatevParameter | ( | ) |
How many columns do we look at in the Markowitz pivoting rule to find a good pivot. See markowitz.h.
optional int32 markowitz_zlatev_parameter = 29 [default = 3];
Definition at line 6922 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearMaxDeterministicTime | ( | ) |
Maximum deterministic time allowed to solve a problem. The deterministic time is more or less correlated to the running time, and its unit should be around the second (at least on a Xeon(R) CPU E5-1650 v2 @ 3.50GHz). TODO(user): Improve the correlation.
optional double max_deterministic_time = 45 [default = inf];
Definition at line 6802 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearMaxNumberOfIterations | ( | ) |
Maximum number of simplex iterations to solve a problem. A value of -1 means no limit.
optional int64 max_number_of_iterations = 27 [default = -1];
Definition at line 6862 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearMaxNumberOfReoptimizations | ( | ) |
When the solution of phase II is imprecise, we re-run the phase II with the opposite algorithm from that imprecise solution (i.e., if primal or dual simplex was used, we use dual or primal simplex, respectively). We repeat such re-optimization until the solution is precise, or we hit this limit.
optional double max_number_of_reoptimizations = 56 [default = 40];
Definition at line 6606 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearMaxTimeInSeconds | ( | ) |
Maximum time allowed in seconds to solve a problem.
optional double max_time_in_seconds = 26 [default = inf];
Definition at line 6730 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearMaxValidMagnitude | ( | ) |
Any finite values in the input LP must be below this threshold, otherwise the model will be reported invalid. This is needed to avoid floating point overflow when evaluating bounds * coeff for instance. In practice, users shouldn't use super large values in an LP. With the default threshold, even evaluating large constraint with variables at their bound shouldn't cause any overflow.
optional double max_valid_magnitude = 70 [default = 1e+30];
Definition at line 8754 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearMinimumAcceptablePivot | ( | ) |
We never follow a basis change with a pivot under this threshold.
optional double minimum_acceptable_pivot = 15 [default = 1e-06];
Definition at line 5712 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearNumOmpThreads | ( | ) |
Number of threads in the OMP parallel sections. If left to 1, the code will not create any OMP threads and will remain single-threaded.
optional int32 num_omp_threads = 44 [default = 1];
Definition at line 7990 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearObjectiveLowerLimit | ( | ) |
The solver will stop as soon as it has proven that the objective is smaller than objective_lower_limit or greater than objective_upper_limit. Depending on the simplex algorithm (primal or dual) and the optimization direction, note that only one bound will be used at the time. Important: The solver does not add any tolerances to these values, and as soon as the objective (as computed by the solver, so with some imprecision) crosses one of these bounds (strictly), the search will stop. It is up to the client to add any tolerance if needed.
optional double objective_lower_limit = 40 [default = -inf];
Definition at line 7654 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearObjectiveUpperLimit | ( | ) |
optional double objective_upper_limit = 41 [default = inf];
Definition at line 7694 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearOptimizationRule | ( | ) |
PricingRule to use during the optimization phase.
optional .operations_research.glop.GlopParameters.PricingRule optimization_rule = 2 [default = STEEPEST_EDGE];
Definition at line 5020 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearPerturbCostsInDualSimplex | ( | ) |
When this is true, then the costs are randomly perturbed before the dual simplex is even started. This has been shown to improve the dual simplex performance. For a good reference, see Huangfu Q (2013) "High performance simplex solver", Ph.D, dissertation, University of Edinburgh.
optional bool perturb_costs_in_dual_simplex = 53 [default = false];
Definition at line 8058 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearPreprocessorZeroTolerance | ( | ) |
A floating point tolerance used by the preprocessors. This is used for things like detecting if two columns/rows are proportional or if an interval is empty. Note that the preprocessors also use solution_feasibility_tolerance() to detect if a problem is infeasible.
optional double preprocessor_zero_tolerance = 39 [default = 1e-09];
Definition at line 7566 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearPrimalFeasibilityTolerance | ( | ) |
This tolerance indicates by how much we allow the variable values to go out of bounds and still consider the current solution primal-feasible. We also use the same tolerance for the error A.x - b. Note that the two errors are closely related if A is scaled in such a way that the greatest coefficient magnitude on each column is 1.0. This is also simply called feasibility tolerance in other solvers.
optional double primal_feasibility_tolerance = 10 [default = 1e-08];
Definition at line 5320 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearProvideStrongOptimalGuarantee | ( | ) |
If true, then when the solver returns a solution with an OPTIMAL status, we can guarantee that: - The primal variable are in their bounds. - The dual variable are in their bounds. - If we modify each component of the right-hand side a bit and each component of the objective function a bit, then the pair (primal values, dual values) is an EXACT optimal solution of the perturbed problem. - The modifications above are smaller than the associated tolerances as defined in the comment for solution_feasibility_tolerance (*). (*): This is the only place where the guarantee is not tight since we compute the upper bounds with scalar product of the primal/dual solution and the initial problem coefficients with only double precision. Note that whether or not this option is true, we still check the primal/dual infeasibility and objective gap. However if it is false, we don't move the primal/dual values within their bounds and leave them untouched.
optional bool provide_strong_optimal_guarantee = 24 [default = true];
Definition at line 6478 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearPushToVertex | ( | ) |
If the optimization phases finishes with super-basic variables (i.e., variables that either 1) have bounds but are FREE in the basis, or 2) have no bounds and are FREE in the basis at a nonzero value), then run a "push" phase to push these variables to bounds, obtaining a vertex solution. Note this situation can happen only if a starting value was specified via SetStartingVariableValuesForNextSolve().
optional bool push_to_vertex = 65 [default = true];
Definition at line 8622 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearRandomSeed | ( | ) |
At the beginning of each solve, the random number generator used in some part of the solver is reinitialized to this seed. If you change the random seed, the solver may make different choices during the solving process. Note that this may lead to a different solution, for example a different optimal basis. For some problems, the running time may vary a lot depending on small change in the solving algorithm. Running the solver with different seeds enables to have more robust benchmarks when evaluating new features. Also note that the solver is fully deterministic: two runs of the same binary, on the same machine, on the exact same data and with the same parameters will go through the exact same iterations. If they hit a time limit, they might of course yield different results because one will have advanced farther than the other.
optional int32 random_seed = 43 [default = 1];
Definition at line 7930 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearRatioTestZeroThreshold | ( | ) |
During the primal simplex (resp. dual simplex), the coefficients of the direction (resp. update row) with a magnitude lower than this threshold are not considered during the ratio test. This tolerance is related to the precision at which a Solve() involving the basis matrix can be performed. TODO(user): Automatically increase it when we detect that the precision of the Solve() is worse than this.
optional double ratio_test_zero_threshold = 12 [default = 1e-09];
Definition at line 5492 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearRecomputeEdgesNormThreshold | ( | ) |
Note that the threshold is a relative error on the actual norm (not the squared one) and that edge norms are always greater than 1. Recomputing norms is a really expensive operation and a large threshold is ok since this doesn't impact directly the solution but just the entering variable choice.
optional double recompute_edges_norm_threshold = 9 [default = 100];
Definition at line 5240 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearRecomputeReducedCostsThreshold | ( | ) |
We estimate the accuracy of the iteratively computed reduced costs. If it falls below this threshold, we reinitialize them from scratch. Note that such an operation is pretty fast, so we can use a low threshold. It is important to have a good accuracy here (better than the dual_feasibility_tolerance below) to be sure of the sign of such a cost.
optional double recompute_reduced_costs_threshold = 8 [default = 1e-08];
Definition at line 5168 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearRefactorizationThreshold | ( | ) |
We estimate the factorization accuracy of B during each pivot by using the fact that we can compute the pivot coefficient in two ways: - From direction[leaving_row]. - From update_row[entering_column]. If the two values have a relative difference above this threshold, we trigger a refactorization.
optional double refactorization_threshold = 6 [default = 1e-09];
Definition at line 5096 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearRelativeCostPerturbation | ( | ) |
The magnitude of the cost perturbation is given by RandomIn(1.0, 2.0) * ( relative_cost_perturbation * cost + relative_max_cost_perturbation * max_cost);
optional double relative_cost_perturbation = 54 [default = 1e-05];
Definition at line 8210 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearRelativeMaxCostPerturbation | ( | ) |
optional double relative_max_cost_perturbation = 55 [default = 1e-07];
Definition at line 8250 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearScalingMethod | ( | ) |
optional .operations_research.glop.GlopParameters.ScalingAlgorithm scaling_method = 57 [default = EQUILIBRATION];
Definition at line 4904 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearSmallPivotThreshold | ( | ) |
When we choose the leaving variable, we want to avoid small pivot because they are the less precise and may cause numerical instabilities. For a pivot under this threshold times the infinity norm of the direction, we try various countermeasures in order to avoid using it.
optional double small_pivot_threshold = 14 [default = 1e-06];
Definition at line 5656 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearSolutionFeasibilityTolerance | ( | ) |
When the problem status is OPTIMAL, we check the optimality using this relative tolerance and change the status to IMPRECISE if an issue is detected. The tolerance is "relative" in the sense that our thresholds are: - tolerance * max(1.0, abs(bound)) for crossing a given bound. - tolerance * max(1.0, abs(cost)) for an infeasible reduced cost. - tolerance for an infeasible dual value.
optional double solution_feasibility_tolerance = 22 [default = 1e-06];
Definition at line 6354 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearSolveDualProblem | ( | ) |
Whether or not we solve the dual of the given problem. With a value of auto, the algorithm decide which approach is probably the fastest depending on the problem dimensions (see dualizer_threshold).
optional .operations_research.glop.GlopParameters.SolverBehavior solve_dual_problem = 20 [default = LET_SOLVER_DECIDE];
Definition at line 6206 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearUseDedicatedDualFeasibilityAlgorithm | ( | ) |
We have two possible dual phase I algorithms. Both work on an LP that minimize the sum of dual infeasiblities. One use dedicated code (when this param is true), the other one use exactly the same code as the dual phase II but on an auxiliary problem where the variable bounds of the original problem are changed. TODO(user): For now we have both, but ideally the non-dedicated version will win since it is a lot less code to maintain.
optional bool use_dedicated_dual_feasibility_algorithm = 62 [default = true];
Definition at line 8142 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearUseDualSimplex | ( | ) |
Whether or not we use the dual simplex algorithm instead of the primal.
optional bool use_dual_simplex = 31 [default = false];
Definition at line 7046 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearUseImpliedFreePreprocessor | ( | ) |
If presolve runs, include the pass that detects implied free variables.
optional bool use_implied_free_preprocessor = 67 [default = true];
Definition at line 8678 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearUseMiddleProductFormUpdate | ( | ) |
Whether or not to use the middle product form update rather than the standard eta LU update. The middle form product update should be a lot more efficient (close to the Forrest-Tomlin update, a bit slower but easier to implement). See for more details: Qi Huangfu, J. A. Julian Hall, "Novel update techniques for the revised simplex method", 28 january 2013, Technical Report ERGO-13-0001 http://www.maths.ed.ac.uk/hall/HuHa12/ERGO-13-001.pdf
optional bool use_middle_product_form_update = 35 [default = true];
Definition at line 7306 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearUsePreprocessing | ( | ) |
Whether or not we use advanced preprocessing techniques.
optional bool use_preprocessing = 34 [default = true];
Definition at line 7226 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearUseScaling | ( | ) |
Whether or not we scale the matrix A so that the maximum coefficient on each line and each column is 1.0.
optional bool use_scaling = 16 [default = true];
Definition at line 5836 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.clearUseTransposedMatrix | ( | ) |
Whether or not we keep a transposed version of the matrix A to speed-up the pricing at the cost of extra memory and the initial tranposition computation.
optional bool use_transposed_matrix = 18 [default = true];
Definition at line 6004 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getAllowSimplexAlgorithmChange | ( | ) |
During incremental solve, let the solver decide if it use the primal or dual simplex algorithm depending on the current solution and on the new problem. Note that even if this is true, the value of use_dual_simplex still indicates the default algorithm that the solver will use.
optional bool allow_simplex_algorithm_change = 32 [default = false];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7081 of file GlopParameters.java.
| int com.google.ortools.glop.GlopParameters.Builder.getBasisRefactorizationPeriod | ( | ) |
Number of iterations between two basis refactorizations. Note that various conditions in the algorithm may trigger a refactorization before this period is reached. Set this to 0 if you want to refactorize at each step.
optional int32 basis_refactorization_period = 19 [default = 64];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6037 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getChangeStatusToImprecise | ( | ) |
If true, the internal API will change the return status to imprecise if the solution does not respect the internal tolerances.
optional bool change_status_to_imprecise = 58 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6509 of file GlopParameters.java.
| com.google.ortools.glop.GlopParameters.CostScalingAlgorithm com.google.ortools.glop.GlopParameters.Builder.getCostScaling | ( | ) |
optional .operations_research.glop.GlopParameters.CostScalingAlgorithm cost_scaling = 60 [default = CONTAIN_ONE_COST_SCALING];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5856 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getCrossoverBoundSnappingDistance | ( | ) |
If the starting basis contains FREE variable with bounds, we will move any such variable to their closer bounds if the distance is smaller than this parameter. The starting statuses can contains FREE variables with bounds, if a user set it like this externally. Also, any variable with an initial BASIC status that was not kept in the initial basis is marked as FREE before this step is applied. Note that by default a FREE variable is assumed to be zero unless a starting value was specified via SetStartingVariableValuesForNextSolve(). Note that, at the end of the solve, some of these FREE variable with bounds and an interior point value might still be left in the final solution. Enable push_to_vertex to clean these up.
optional double crossover_bound_snapping_distance = 64 [default = inf];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8491 of file GlopParameters.java.
| com.google.ortools.glop.GlopParameters com.google.ortools.glop.GlopParameters.Builder.getDefaultInstanceForType | ( | ) |
Definition at line 4041 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getDegenerateMinistepFactor | ( | ) |
During a degenerate iteration, the more conservative approach is to do a step of length zero (while shifting the bound of the leaving variable). That is, the variable values are unchanged for the primal simplex or the reduced cost are unchanged for the dual simplex. However, instead of doing a step of length zero, it seems to be better on degenerate problems to do a small positive step. This is what is recommended in the EXPAND procedure described in: P. E. Gill, W. Murray, M. A. Saunders, and M. H. Wright. "A practical anti- cycling procedure for linearly constrained optimization". Mathematical Programming, 45:437\u2013474, 1989. Here, during a degenerate iteration we do a small positive step of this factor times the primal (resp. dual) tolerance. In the primal simplex, this may effectively push variable values (very slightly) further out of their bounds (resp. reduced costs for the dual simplex). Setting this to zero reverts to the more conservative approach of a zero step during degenerate iterations.
optional double degenerate_ministep_factor = 42 [default = 0.01];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7757 of file GlopParameters.java.
|
static |
Definition at line 3946 of file GlopParameters.java.
| com.google.protobuf.Descriptors.Descriptor com.google.ortools.glop.GlopParameters.Builder.getDescriptorForType | ( | ) |
Definition at line 4036 of file GlopParameters.java.
| int com.google.ortools.glop.GlopParameters.Builder.getDevexWeightsResetPeriod | ( | ) |
Devex weights will be reset to 1.0 after that number of updates.
optional int32 devex_weights_reset_period = 33 [default = 150];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7143 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getDropMagnitude | ( | ) |
Value in the input LP lower than this will be ignored. This is similar to drop_tolerance but more aggressive as this is used before scaling. This is mainly here to avoid underflow and have simpler invariant in the code, like a * b == 0 iff a or b is zero and things like this.
optional double drop_magnitude = 71 [default = 1e-30];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8789 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getDropTolerance | ( | ) |
In order to increase the sparsity of the manipulated vectors, floating point values with a magnitude smaller than this parameter are set to zero (only in some places). This parameter should be positive or zero.
optional double drop_tolerance = 52 [default = 1e-14];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5745 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getDualFeasibilityTolerance | ( | ) |
Variables whose reduced costs have an absolute value smaller than this tolerance are not considered as entering candidates. That is they do not take part in deciding whether a solution is dual-feasible or not. Note that this value can temporarily increase during the execution of the algorithm if the estimated precision of the reduced costs is higher than this tolerance. Note also that we scale the costs (in the presolve step) so that the cost magnitude range contains one. This is also known as the optimality tolerance in other solvers.
optional double dual_feasibility_tolerance = 11 [default = 1e-08];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5367 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getDualizerThreshold | ( | ) |
When solve_dual_problem is LET_SOLVER_DECIDE, take the dual if the number of constraints of the problem is more than this threshold times the number of variables.
optional double dualizer_threshold = 21 [default = 1.5];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6239 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getDualPricePrioritizeNorm | ( | ) |
On some problem like stp3d or pds-100 this makes a huge difference in speed and number of iterations of the dual simplex.
optional bool dual_price_prioritize_norm = 69 [default = false];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8853 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getDualSmallPivotThreshold | ( | ) |
Like small_pivot_threshold but for the dual simplex. This is needed because the dual algorithm does not interpret this value in the same way. TODO(user): Clean this up and use the same small pivot detection.
optional double dual_small_pivot_threshold = 38 [default = 0.0001];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7459 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getDynamicallyAdjustRefactorizationPeriod | ( | ) |
If this is true, then basis_refactorization_period becomes a lower bound on the number of iterations between two refactorization (provided there is no numerical accuracy issues). Depending on the estimated time to refactorize vs the extra time spend in each solves because of the LU update, we try to balance the two times.
optional bool dynamically_adjust_refactorization_period = 63 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6105 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getExploitSingletonColumnInInitialBasis | ( | ) |
Whether or not we exploit the singleton columns already present in the problem when we create the initial basis.
optional bool exploit_singleton_column_in_initial_basis = 37 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7397 of file GlopParameters.java.
| com.google.ortools.glop.GlopParameters.PricingRule com.google.ortools.glop.GlopParameters.Builder.getFeasibilityRule | ( | ) |
PricingRule to use during the feasibility phase.
optional .operations_research.glop.GlopParameters.PricingRule feasibility_rule = 1 [default = STEEPEST_EDGE];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 4932 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getHarrisToleranceRatio | ( | ) |
This impacts the ratio test and indicates by how much we allow a basic variable value that we move to go out of bounds. The value should be in [0.0, 1.0) and should be interpreted as a ratio of the primal_feasibility_tolerance. Setting this to 0.0 basically disables the Harris ratio test while setting this too close to 1.0 will make it difficult to keep the variable values inside their bounds modulo the primal_feasibility_tolerance. Note that the same comment applies to the dual simplex ratio test. There, we allow the reduced costs to be of an infeasible sign by as much as this ratio times the dual_feasibility_tolerance.
optional double harris_tolerance_ratio = 13 [default = 0.5];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5541 of file GlopParameters.java.
| com.google.ortools.glop.GlopParameters.InitialBasisHeuristic com.google.ortools.glop.GlopParameters.Builder.getInitialBasis | ( | ) |
What heuristic is used to try to replace the fixed slack columns in the initial basis of the primal simplex.
optional .operations_research.glop.GlopParameters.InitialBasisHeuristic initial_basis = 17 [default = TRIANGULAR];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5908 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getInitialConditionNumberThreshold | ( | ) |
If our upper bound on the condition number of the initial basis (from our heurisitic or a warm start) is above this threshold, we revert to an all slack basis.
optional double initial_condition_number_threshold = 59 [default = 1e+50];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8283 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getInitializeDevexWithColumnNorms | ( | ) |
Whether we initialize devex weights to 1.0 or to the norms of the matrix columns.
optional bool initialize_devex_with_column_norms = 36 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7337 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getLogSearchProgress | ( | ) |
If true, logs the progress of a solve to LOG(INFO). Note that the same messages can also be turned on by displaying logs at level 1 for the relevant files.
optional bool log_search_progress = 61 [default = false];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8347 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getLogToStdout | ( | ) |
If true, logs will be displayed to stdout instead of using Google log info.
optional bool log_to_stdout = 66 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8407 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getLuFactorizationPivotThreshold | ( | ) |
Threshold for LU-factorization: for stability reasons, the magnitude of the chosen pivot at a given step is guaranteed to be greater than this threshold times the maximum magnitude of all the possible pivot choices in the same column. The value must be in [0,1].
optional double lu_factorization_pivot_threshold = 25 [default = 0.01];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6641 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getMarkowitzSingularityThreshold | ( | ) |
If a pivot magnitude is smaller than this during the Markowitz LU factorization, then the matrix is assumed to be singular. Note that this is an absolute threshold and is not relative to the other possible pivots on the same column (see lu_factorization_pivot_threshold).
optional double markowitz_singularity_threshold = 30 [default = 1e-15];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6957 of file GlopParameters.java.
| int com.google.ortools.glop.GlopParameters.Builder.getMarkowitzZlatevParameter | ( | ) |
How many columns do we look at in the Markowitz pivoting rule to find a good pivot. See markowitz.h.
optional int32 markowitz_zlatev_parameter = 29 [default = 3];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6893 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getMaxDeterministicTime | ( | ) |
Maximum deterministic time allowed to solve a problem. The deterministic time is more or less correlated to the running time, and its unit should be around the second (at least on a Xeon(R) CPU E5-1650 v2 @ 3.50GHz). TODO(user): Improve the correlation.
optional double max_deterministic_time = 45 [default = inf];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6767 of file GlopParameters.java.
| long com.google.ortools.glop.GlopParameters.Builder.getMaxNumberOfIterations | ( | ) |
Maximum number of simplex iterations to solve a problem. A value of -1 means no limit.
optional int64 max_number_of_iterations = 27 [default = -1];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6833 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getMaxNumberOfReoptimizations | ( | ) |
When the solution of phase II is imprecise, we re-run the phase II with the opposite algorithm from that imprecise solution (i.e., if primal or dual simplex was used, we use dual or primal simplex, respectively). We repeat such re-optimization until the solution is precise, or we hit this limit.
optional double max_number_of_reoptimizations = 56 [default = 40];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6573 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getMaxTimeInSeconds | ( | ) |
Maximum time allowed in seconds to solve a problem.
optional double max_time_in_seconds = 26 [default = inf];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6703 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getMaxValidMagnitude | ( | ) |
Any finite values in the input LP must be below this threshold, otherwise the model will be reported invalid. This is needed to avoid floating point overflow when evaluating bounds * coeff for instance. In practice, users shouldn't use super large values in an LP. With the default threshold, even evaluating large constraint with variables at their bound shouldn't cause any overflow.
optional double max_valid_magnitude = 70 [default = 1e+30];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8717 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getMinimumAcceptablePivot | ( | ) |
We never follow a basis change with a pivot under this threshold.
optional double minimum_acceptable_pivot = 15 [default = 1e-06];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5685 of file GlopParameters.java.
| int com.google.ortools.glop.GlopParameters.Builder.getNumOmpThreads | ( | ) |
Number of threads in the OMP parallel sections. If left to 1, the code will not create any OMP threads and will remain single-threaded.
optional int32 num_omp_threads = 44 [default = 1];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7961 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getObjectiveLowerLimit | ( | ) |
The solver will stop as soon as it has proven that the objective is smaller than objective_lower_limit or greater than objective_upper_limit. Depending on the simplex algorithm (primal or dual) and the optimization direction, note that only one bound will be used at the time. Important: The solver does not add any tolerances to these values, and as soon as the objective (as computed by the solver, so with some imprecision) crosses one of these bounds (strictly), the search will stop. It is up to the client to add any tolerance if needed.
optional double objective_lower_limit = 40 [default = -inf];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7611 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getObjectiveUpperLimit | ( | ) |
optional double objective_upper_limit = 41 [default = inf];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7675 of file GlopParameters.java.
| com.google.ortools.glop.GlopParameters.PricingRule com.google.ortools.glop.GlopParameters.Builder.getOptimizationRule | ( | ) |
PricingRule to use during the optimization phase.
optional .operations_research.glop.GlopParameters.PricingRule optimization_rule = 2 [default = STEEPEST_EDGE];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 4990 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getPerturbCostsInDualSimplex | ( | ) |
When this is true, then the costs are randomly perturbed before the dual simplex is even started. This has been shown to improve the dual simplex performance. For a good reference, see Huangfu Q (2013) "High performance simplex solver", Ph.D, dissertation, University of Edinburgh.
optional bool perturb_costs_in_dual_simplex = 53 [default = false];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8025 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getPreprocessorZeroTolerance | ( | ) |
A floating point tolerance used by the preprocessors. This is used for things like detecting if two columns/rows are proportional or if an interval is empty. Note that the preprocessors also use solution_feasibility_tolerance() to detect if a problem is infeasible.
optional double preprocessor_zero_tolerance = 39 [default = 1e-09];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7529 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getPrimalFeasibilityTolerance | ( | ) |
This tolerance indicates by how much we allow the variable values to go out of bounds and still consider the current solution primal-feasible. We also use the same tolerance for the error A.x - b. Note that the two errors are closely related if A is scaled in such a way that the greatest coefficient magnitude on each column is 1.0. This is also simply called feasibility tolerance in other solvers.
optional double primal_feasibility_tolerance = 10 [default = 1e-08];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5281 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getProvideStrongOptimalGuarantee | ( | ) |
If true, then when the solver returns a solution with an OPTIMAL status, we can guarantee that: - The primal variable are in their bounds. - The dual variable are in their bounds. - If we modify each component of the right-hand side a bit and each component of the objective function a bit, then the pair (primal values, dual values) is an EXACT optimal solution of the perturbed problem. - The modifications above are smaller than the associated tolerances as defined in the comment for solution_feasibility_tolerance (*). (*): This is the only place where the guarantee is not tight since we compute the upper bounds with scalar product of the primal/dual solution and the initial problem coefficients with only double precision. Note that whether or not this option is true, we still check the primal/dual infeasibility and objective gap. However if it is false, we don't move the primal/dual values within their bounds and leave them untouched.
optional bool provide_strong_optimal_guarantee = 24 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6417 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getPushToVertex | ( | ) |
If the optimization phases finishes with super-basic variables (i.e., variables that either 1) have bounds but are FREE in the basis, or 2) have no bounds and are FREE in the basis at a nonzero value), then run a "push" phase to push these variables to bounds, obtaining a vertex solution. Note this situation can happen only if a starting value was specified via SetStartingVariableValuesForNextSolve().
optional bool push_to_vertex = 65 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8585 of file GlopParameters.java.
| int com.google.ortools.glop.GlopParameters.Builder.getRandomSeed | ( | ) |
At the beginning of each solve, the random number generator used in some part of the solver is reinitialized to this seed. If you change the random seed, the solver may make different choices during the solving process. Note that this may lead to a different solution, for example a different optimal basis. For some problems, the running time may vary a lot depending on small change in the solving algorithm. Running the solver with different seeds enables to have more robust benchmarks when evaluating new features. Also note that the solver is fully deterministic: two runs of the same binary, on the same machine, on the exact same data and with the same parameters will go through the exact same iterations. If they hit a time limit, they might of course yield different results because one will have advanced farther than the other.
optional int32 random_seed = 43 [default = 1];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7875 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getRatioTestZeroThreshold | ( | ) |
During the primal simplex (resp. dual simplex), the coefficients of the direction (resp. update row) with a magnitude lower than this threshold are not considered during the ratio test. This tolerance is related to the precision at which a Solve() involving the basis matrix can be performed. TODO(user): Automatically increase it when we detect that the precision of the Solve() is worse than this.
optional double ratio_test_zero_threshold = 12 [default = 1e-09];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5453 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getRecomputeEdgesNormThreshold | ( | ) |
Note that the threshold is a relative error on the actual norm (not the squared one) and that edge norms are always greater than 1. Recomputing norms is a really expensive operation and a large threshold is ok since this doesn't impact directly the solution but just the entering variable choice.
optional double recompute_edges_norm_threshold = 9 [default = 100];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5205 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getRecomputeReducedCostsThreshold | ( | ) |
We estimate the accuracy of the iteratively computed reduced costs. If it falls below this threshold, we reinitialize them from scratch. Note that such an operation is pretty fast, so we can use a low threshold. It is important to have a good accuracy here (better than the dual_feasibility_tolerance below) to be sure of the sign of such a cost.
optional double recompute_reduced_costs_threshold = 8 [default = 1e-08];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5133 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getRefactorizationThreshold | ( | ) |
We estimate the factorization accuracy of B during each pivot by using the fact that we can compute the pivot coefficient in two ways: - From direction[leaving_row]. - From update_row[entering_column]. If the two values have a relative difference above this threshold, we trigger a refactorization.
optional double refactorization_threshold = 6 [default = 1e-09];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5059 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getRelativeCostPerturbation | ( | ) |
The magnitude of the cost perturbation is given by RandomIn(1.0, 2.0) * ( relative_cost_perturbation * cost + relative_max_cost_perturbation * max_cost);
optional double relative_cost_perturbation = 54 [default = 1e-05];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8177 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getRelativeMaxCostPerturbation | ( | ) |
optional double relative_max_cost_perturbation = 55 [default = 1e-07];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8231 of file GlopParameters.java.
| com.google.ortools.glop.GlopParameters.ScalingAlgorithm com.google.ortools.glop.GlopParameters.Builder.getScalingMethod | ( | ) |
optional .operations_research.glop.GlopParameters.ScalingAlgorithm scaling_method = 57 [default = EQUILIBRATION];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 4882 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getSmallPivotThreshold | ( | ) |
When we choose the leaving variable, we want to avoid small pivot because they are the less precise and may cause numerical instabilities. For a pivot under this threshold times the infinity norm of the direction, we try various countermeasures in order to avoid using it.
optional double small_pivot_threshold = 14 [default = 1e-06];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5623 of file GlopParameters.java.
| double com.google.ortools.glop.GlopParameters.Builder.getSolutionFeasibilityTolerance | ( | ) |
When the problem status is OPTIMAL, we check the optimality using this relative tolerance and change the status to IMPRECISE if an issue is detected. The tolerance is "relative" in the sense that our thresholds are: - tolerance * max(1.0, abs(bound)) for crossing a given bound. - tolerance * max(1.0, abs(cost)) for an infeasible reduced cost. - tolerance for an infeasible dual value.
optional double solution_feasibility_tolerance = 22 [default = 1e-06];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6313 of file GlopParameters.java.
| com.google.ortools.glop.GlopParameters.SolverBehavior com.google.ortools.glop.GlopParameters.Builder.getSolveDualProblem | ( | ) |
Whether or not we solve the dual of the given problem. With a value of auto, the algorithm decide which approach is probably the fastest depending on the problem dimensions (see dualizer_threshold).
optional .operations_research.glop.GlopParameters.SolverBehavior solve_dual_problem = 20 [default = LET_SOLVER_DECIDE];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6172 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getUseDedicatedDualFeasibilityAlgorithm | ( | ) |
We have two possible dual phase I algorithms. Both work on an LP that minimize the sum of dual infeasiblities. One use dedicated code (when this param is true), the other one use exactly the same code as the dual phase II but on an auxiliary problem where the variable bounds of the original problem are changed. TODO(user): For now we have both, but ideally the non-dedicated version will win since it is a lot less code to maintain.
optional bool use_dedicated_dual_feasibility_algorithm = 62 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8101 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getUseDualSimplex | ( | ) |
Whether or not we use the dual simplex algorithm instead of the primal.
optional bool use_dual_simplex = 31 [default = false];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7019 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getUseImpliedFreePreprocessor | ( | ) |
If presolve runs, include the pass that detects implied free variables.
optional bool use_implied_free_preprocessor = 67 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8651 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getUseMiddleProductFormUpdate | ( | ) |
Whether or not to use the middle product form update rather than the standard eta LU update. The middle form product update should be a lot more efficient (close to the Forrest-Tomlin update, a bit slower but easier to implement). See for more details: Qi Huangfu, J. A. Julian Hall, "Novel update techniques for the revised simplex method", 28 january 2013, Technical Report ERGO-13-0001 http://www.maths.ed.ac.uk/hall/HuHa12/ERGO-13-001.pdf
optional bool use_middle_product_form_update = 35 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7267 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getUsePreprocessing | ( | ) |
Whether or not we use advanced preprocessing techniques.
optional bool use_preprocessing = 34 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7199 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getUseScaling | ( | ) |
Whether or not we scale the matrix A so that the maximum coefficient on each line and each column is 1.0.
optional bool use_scaling = 16 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5807 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.getUseTransposedMatrix | ( | ) |
Whether or not we keep a transposed version of the matrix A to speed-up the pricing at the cost of extra memory and the initial tranposition computation.
optional bool use_transposed_matrix = 18 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5973 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasAllowSimplexAlgorithmChange | ( | ) |
During incremental solve, let the solver decide if it use the primal or dual simplex algorithm depending on the current solution and on the new problem. Note that even if this is true, the value of use_dual_simplex still indicates the default algorithm that the solver will use.
optional bool allow_simplex_algorithm_change = 32 [default = false];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7066 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasBasisRefactorizationPeriod | ( | ) |
Number of iterations between two basis refactorizations. Note that various conditions in the algorithm may trigger a refactorization before this period is reached. Set this to 0 if you want to refactorize at each step.
optional int32 basis_refactorization_period = 19 [default = 64];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6023 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasChangeStatusToImprecise | ( | ) |
If true, the internal API will change the return status to imprecise if the solution does not respect the internal tolerances.
optional bool change_status_to_imprecise = 58 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6496 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasCostScaling | ( | ) |
optional .operations_research.glop.GlopParameters.CostScalingAlgorithm cost_scaling = 60 [default = CONTAIN_ONE_COST_SCALING];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5848 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasCrossoverBoundSnappingDistance | ( | ) |
If the starting basis contains FREE variable with bounds, we will move any such variable to their closer bounds if the distance is smaller than this parameter. The starting statuses can contains FREE variables with bounds, if a user set it like this externally. Also, any variable with an initial BASIC status that was not kept in the initial basis is marked as FREE before this step is applied. Note that by default a FREE variable is assumed to be zero unless a starting value was specified via SetStartingVariableValuesForNextSolve(). Note that, at the end of the solve, some of these FREE variable with bounds and an interior point value might still be left in the final solution. Enable push_to_vertex to clean these up.
optional double crossover_bound_snapping_distance = 64 [default = inf];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8465 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasDegenerateMinistepFactor | ( | ) |
During a degenerate iteration, the more conservative approach is to do a step of length zero (while shifting the bound of the leaving variable). That is, the variable values are unchanged for the primal simplex or the reduced cost are unchanged for the dual simplex. However, instead of doing a step of length zero, it seems to be better on degenerate problems to do a small positive step. This is what is recommended in the EXPAND procedure described in: P. E. Gill, W. Murray, M. A. Saunders, and M. H. Wright. "A practical anti- cycling procedure for linearly constrained optimization". Mathematical Programming, 45:437\u2013474, 1989. Here, during a degenerate iteration we do a small positive step of this factor times the primal (resp. dual) tolerance. In the primal simplex, this may effectively push variable values (very slightly) further out of their bounds (resp. reduced costs for the dual simplex). Setting this to zero reverts to the more conservative approach of a zero step during degenerate iterations.
optional double degenerate_ministep_factor = 42 [default = 0.01];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7728 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasDevexWeightsResetPeriod | ( | ) |
Devex weights will be reset to 1.0 after that number of updates.
optional int32 devex_weights_reset_period = 33 [default = 150];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7131 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasDropMagnitude | ( | ) |
Value in the input LP lower than this will be ignored. This is similar to drop_tolerance but more aggressive as this is used before scaling. This is mainly here to avoid underflow and have simpler invariant in the code, like a * b == 0 iff a or b is zero and things like this.
optional double drop_magnitude = 71 [default = 1e-30];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8774 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasDropTolerance | ( | ) |
In order to increase the sparsity of the manipulated vectors, floating point values with a magnitude smaller than this parameter are set to zero (only in some places). This parameter should be positive or zero.
optional double drop_tolerance = 52 [default = 1e-14];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5731 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasDualFeasibilityTolerance | ( | ) |
Variables whose reduced costs have an absolute value smaller than this tolerance are not considered as entering candidates. That is they do not take part in deciding whether a solution is dual-feasible or not. Note that this value can temporarily increase during the execution of the algorithm if the estimated precision of the reduced costs is higher than this tolerance. Note also that we scale the costs (in the presolve step) so that the cost magnitude range contains one. This is also known as the optimality tolerance in other solvers.
optional double dual_feasibility_tolerance = 11 [default = 1e-08];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5346 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasDualizerThreshold | ( | ) |
When solve_dual_problem is LET_SOLVER_DECIDE, take the dual if the number of constraints of the problem is more than this threshold times the number of variables.
optional double dualizer_threshold = 21 [default = 1.5];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6225 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasDualPricePrioritizeNorm | ( | ) |
On some problem like stp3d or pds-100 this makes a huge difference in speed and number of iterations of the dual simplex.
optional bool dual_price_prioritize_norm = 69 [default = false];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8840 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasDualSmallPivotThreshold | ( | ) |
Like small_pivot_threshold but for the dual simplex. This is needed because the dual algorithm does not interpret this value in the same way. TODO(user): Clean this up and use the same small pivot detection.
optional double dual_small_pivot_threshold = 38 [default = 0.0001];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7445 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasDynamicallyAdjustRefactorizationPeriod | ( | ) |
If this is true, then basis_refactorization_period becomes a lower bound on the number of iterations between two refactorization (provided there is no numerical accuracy issues). Depending on the estimated time to refactorize vs the extra time spend in each solves because of the LU update, we try to balance the two times.
optional bool dynamically_adjust_refactorization_period = 63 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6089 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasExploitSingletonColumnInInitialBasis | ( | ) |
Whether or not we exploit the singleton columns already present in the problem when we create the initial basis.
optional bool exploit_singleton_column_in_initial_basis = 37 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7384 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasFeasibilityRule | ( | ) |
PricingRule to use during the feasibility phase.
optional .operations_research.glop.GlopParameters.PricingRule feasibility_rule = 1 [default = STEEPEST_EDGE];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 4920 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasHarrisToleranceRatio | ( | ) |
This impacts the ratio test and indicates by how much we allow a basic variable value that we move to go out of bounds. The value should be in [0.0, 1.0) and should be interpreted as a ratio of the primal_feasibility_tolerance. Setting this to 0.0 basically disables the Harris ratio test while setting this too close to 1.0 will make it difficult to keep the variable values inside their bounds modulo the primal_feasibility_tolerance. Note that the same comment applies to the dual simplex ratio test. There, we allow the reduced costs to be of an infeasible sign by as much as this ratio times the dual_feasibility_tolerance.
optional double harris_tolerance_ratio = 13 [default = 0.5];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5519 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasInitialBasis | ( | ) |
What heuristic is used to try to replace the fixed slack columns in the initial basis of the primal simplex.
optional .operations_research.glop.GlopParameters.InitialBasisHeuristic initial_basis = 17 [default = TRIANGULAR];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5895 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasInitialConditionNumberThreshold | ( | ) |
If our upper bound on the condition number of the initial basis (from our heurisitic or a warm start) is above this threshold, we revert to an all slack basis.
optional double initial_condition_number_threshold = 59 [default = 1e+50];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8269 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasInitializeDevexWithColumnNorms | ( | ) |
Whether we initialize devex weights to 1.0 or to the norms of the matrix columns.
optional bool initialize_devex_with_column_norms = 36 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7324 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasLogSearchProgress | ( | ) |
If true, logs the progress of a solve to LOG(INFO). Note that the same messages can also be turned on by displaying logs at level 1 for the relevant files.
optional bool log_search_progress = 61 [default = false];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8333 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasLogToStdout | ( | ) |
If true, logs will be displayed to stdout instead of using Google log info.
optional bool log_to_stdout = 66 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8395 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasLuFactorizationPivotThreshold | ( | ) |
Threshold for LU-factorization: for stability reasons, the magnitude of the chosen pivot at a given step is guaranteed to be greater than this threshold times the maximum magnitude of all the possible pivot choices in the same column. The value must be in [0,1].
optional double lu_factorization_pivot_threshold = 25 [default = 0.01];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6626 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasMarkowitzSingularityThreshold | ( | ) |
If a pivot magnitude is smaller than this during the Markowitz LU factorization, then the matrix is assumed to be singular. Note that this is an absolute threshold and is not relative to the other possible pivots on the same column (see lu_factorization_pivot_threshold).
optional double markowitz_singularity_threshold = 30 [default = 1e-15];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6942 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasMarkowitzZlatevParameter | ( | ) |
How many columns do we look at in the Markowitz pivoting rule to find a good pivot. See markowitz.h.
optional int32 markowitz_zlatev_parameter = 29 [default = 3];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6880 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasMaxDeterministicTime | ( | ) |
Maximum deterministic time allowed to solve a problem. The deterministic time is more or less correlated to the running time, and its unit should be around the second (at least on a Xeon(R) CPU E5-1650 v2 @ 3.50GHz). TODO(user): Improve the correlation.
optional double max_deterministic_time = 45 [default = inf];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6751 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasMaxNumberOfIterations | ( | ) |
Maximum number of simplex iterations to solve a problem. A value of -1 means no limit.
optional int64 max_number_of_iterations = 27 [default = -1];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6820 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasMaxNumberOfReoptimizations | ( | ) |
When the solution of phase II is imprecise, we re-run the phase II with the opposite algorithm from that imprecise solution (i.e., if primal or dual simplex was used, we use dual or primal simplex, respectively). We repeat such re-optimization until the solution is precise, or we hit this limit.
optional double max_number_of_reoptimizations = 56 [default = 40];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6558 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasMaxTimeInSeconds | ( | ) |
Maximum time allowed in seconds to solve a problem.
optional double max_time_in_seconds = 26 [default = inf];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6691 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasMaxValidMagnitude | ( | ) |
Any finite values in the input LP must be below this threshold, otherwise the model will be reported invalid. This is needed to avoid floating point overflow when evaluating bounds * coeff for instance. In practice, users shouldn't use super large values in an LP. With the default threshold, even evaluating large constraint with variables at their bound shouldn't cause any overflow.
optional double max_valid_magnitude = 70 [default = 1e+30];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8700 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasMinimumAcceptablePivot | ( | ) |
We never follow a basis change with a pivot under this threshold.
optional double minimum_acceptable_pivot = 15 [default = 1e-06];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5673 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasNumOmpThreads | ( | ) |
Number of threads in the OMP parallel sections. If left to 1, the code will not create any OMP threads and will remain single-threaded.
optional int32 num_omp_threads = 44 [default = 1];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7948 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasObjectiveLowerLimit | ( | ) |
The solver will stop as soon as it has proven that the objective is smaller than objective_lower_limit or greater than objective_upper_limit. Depending on the simplex algorithm (primal or dual) and the optimization direction, note that only one bound will be used at the time. Important: The solver does not add any tolerances to these values, and as soon as the objective (as computed by the solver, so with some imprecision) crosses one of these bounds (strictly), the search will stop. It is up to the client to add any tolerance if needed.
optional double objective_lower_limit = 40 [default = -inf];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7591 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasObjectiveUpperLimit | ( | ) |
optional double objective_upper_limit = 41 [default = inf];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7667 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasOptimizationRule | ( | ) |
PricingRule to use during the optimization phase.
optional .operations_research.glop.GlopParameters.PricingRule optimization_rule = 2 [default = STEEPEST_EDGE];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 4978 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasPerturbCostsInDualSimplex | ( | ) |
When this is true, then the costs are randomly perturbed before the dual simplex is even started. This has been shown to improve the dual simplex performance. For a good reference, see Huangfu Q (2013) "High performance simplex solver", Ph.D, dissertation, University of Edinburgh.
optional bool perturb_costs_in_dual_simplex = 53 [default = false];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8010 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasPreprocessorZeroTolerance | ( | ) |
A floating point tolerance used by the preprocessors. This is used for things like detecting if two columns/rows are proportional or if an interval is empty. Note that the preprocessors also use solution_feasibility_tolerance() to detect if a problem is infeasible.
optional double preprocessor_zero_tolerance = 39 [default = 1e-09];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7512 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasPrimalFeasibilityTolerance | ( | ) |
This tolerance indicates by how much we allow the variable values to go out of bounds and still consider the current solution primal-feasible. We also use the same tolerance for the error A.x - b. Note that the two errors are closely related if A is scaled in such a way that the greatest coefficient magnitude on each column is 1.0. This is also simply called feasibility tolerance in other solvers.
optional double primal_feasibility_tolerance = 10 [default = 1e-08];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5263 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasProvideStrongOptimalGuarantee | ( | ) |
If true, then when the solver returns a solution with an OPTIMAL status, we can guarantee that: - The primal variable are in their bounds. - The dual variable are in their bounds. - If we modify each component of the right-hand side a bit and each component of the objective function a bit, then the pair (primal values, dual values) is an EXACT optimal solution of the perturbed problem. - The modifications above are smaller than the associated tolerances as defined in the comment for solution_feasibility_tolerance (*). (*): This is the only place where the guarantee is not tight since we compute the upper bounds with scalar product of the primal/dual solution and the initial problem coefficients with only double precision. Note that whether or not this option is true, we still check the primal/dual infeasibility and objective gap. However if it is false, we don't move the primal/dual values within their bounds and leave them untouched.
optional bool provide_strong_optimal_guarantee = 24 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6388 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasPushToVertex | ( | ) |
If the optimization phases finishes with super-basic variables (i.e., variables that either 1) have bounds but are FREE in the basis, or 2) have no bounds and are FREE in the basis at a nonzero value), then run a "push" phase to push these variables to bounds, obtaining a vertex solution. Note this situation can happen only if a starting value was specified via SetStartingVariableValuesForNextSolve().
optional bool push_to_vertex = 65 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8568 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasRandomSeed | ( | ) |
At the beginning of each solve, the random number generator used in some part of the solver is reinitialized to this seed. If you change the random seed, the solver may make different choices during the solving process. Note that this may lead to a different solution, for example a different optimal basis. For some problems, the running time may vary a lot depending on small change in the solving algorithm. Running the solver with different seeds enables to have more robust benchmarks when evaluating new features. Also note that the solver is fully deterministic: two runs of the same binary, on the same machine, on the exact same data and with the same parameters will go through the exact same iterations. If they hit a time limit, they might of course yield different results because one will have advanced farther than the other.
optional int32 random_seed = 43 [default = 1];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7849 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasRatioTestZeroThreshold | ( | ) |
During the primal simplex (resp. dual simplex), the coefficients of the direction (resp. update row) with a magnitude lower than this threshold are not considered during the ratio test. This tolerance is related to the precision at which a Solve() involving the basis matrix can be performed. TODO(user): Automatically increase it when we detect that the precision of the Solve() is worse than this.
optional double ratio_test_zero_threshold = 12 [default = 1e-09];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5435 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasRecomputeEdgesNormThreshold | ( | ) |
Note that the threshold is a relative error on the actual norm (not the squared one) and that edge norms are always greater than 1. Recomputing norms is a really expensive operation and a large threshold is ok since this doesn't impact directly the solution but just the entering variable choice.
optional double recompute_edges_norm_threshold = 9 [default = 100];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5189 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasRecomputeReducedCostsThreshold | ( | ) |
We estimate the accuracy of the iteratively computed reduced costs. If it falls below this threshold, we reinitialize them from scratch. Note that such an operation is pretty fast, so we can use a low threshold. It is important to have a good accuracy here (better than the dual_feasibility_tolerance below) to be sure of the sign of such a cost.
optional double recompute_reduced_costs_threshold = 8 [default = 1e-08];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5117 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasRefactorizationThreshold | ( | ) |
We estimate the factorization accuracy of B during each pivot by using the fact that we can compute the pivot coefficient in two ways: - From direction[leaving_row]. - From update_row[entering_column]. If the two values have a relative difference above this threshold, we trigger a refactorization.
optional double refactorization_threshold = 6 [default = 1e-09];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5042 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasRelativeCostPerturbation | ( | ) |
The magnitude of the cost perturbation is given by RandomIn(1.0, 2.0) * ( relative_cost_perturbation * cost + relative_max_cost_perturbation * max_cost);
optional double relative_cost_perturbation = 54 [default = 1e-05];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8162 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasRelativeMaxCostPerturbation | ( | ) |
optional double relative_max_cost_perturbation = 55 [default = 1e-07];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8223 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasScalingMethod | ( | ) |
optional .operations_research.glop.GlopParameters.ScalingAlgorithm scaling_method = 57 [default = EQUILIBRATION];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 4874 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasSmallPivotThreshold | ( | ) |
When we choose the leaving variable, we want to avoid small pivot because they are the less precise and may cause numerical instabilities. For a pivot under this threshold times the infinity norm of the direction, we try various countermeasures in order to avoid using it.
optional double small_pivot_threshold = 14 [default = 1e-06];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5608 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasSolutionFeasibilityTolerance | ( | ) |
When the problem status is OPTIMAL, we check the optimality using this relative tolerance and change the status to IMPRECISE if an issue is detected. The tolerance is "relative" in the sense that our thresholds are: - tolerance * max(1.0, abs(bound)) for crossing a given bound. - tolerance * max(1.0, abs(cost)) for an infeasible reduced cost. - tolerance for an infeasible dual value.
optional double solution_feasibility_tolerance = 22 [default = 1e-06];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6294 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasSolveDualProblem | ( | ) |
Whether or not we solve the dual of the given problem. With a value of auto, the algorithm decide which approach is probably the fastest depending on the problem dimensions (see dualizer_threshold).
optional .operations_research.glop.GlopParameters.SolverBehavior solve_dual_problem = 20 [default = LET_SOLVER_DECIDE];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 6158 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasUseDedicatedDualFeasibilityAlgorithm | ( | ) |
We have two possible dual phase I algorithms. Both work on an LP that minimize the sum of dual infeasiblities. One use dedicated code (when this param is true), the other one use exactly the same code as the dual phase II but on an auxiliary problem where the variable bounds of the original problem are changed. TODO(user): For now we have both, but ideally the non-dedicated version will win since it is a lot less code to maintain.
optional bool use_dedicated_dual_feasibility_algorithm = 62 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8082 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasUseDualSimplex | ( | ) |
Whether or not we use the dual simplex algorithm instead of the primal.
optional bool use_dual_simplex = 31 [default = false];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7007 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasUseImpliedFreePreprocessor | ( | ) |
If presolve runs, include the pass that detects implied free variables.
optional bool use_implied_free_preprocessor = 67 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 8639 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasUseMiddleProductFormUpdate | ( | ) |
Whether or not to use the middle product form update rather than the standard eta LU update. The middle form product update should be a lot more efficient (close to the Forrest-Tomlin update, a bit slower but easier to implement). See for more details: Qi Huangfu, J. A. Julian Hall, "Novel update techniques for the revised simplex method", 28 january 2013, Technical Report ERGO-13-0001 http://www.maths.ed.ac.uk/hall/HuHa12/ERGO-13-001.pdf
optional bool use_middle_product_form_update = 35 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7249 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasUsePreprocessing | ( | ) |
Whether or not we use advanced preprocessing techniques.
optional bool use_preprocessing = 34 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 7187 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasUseScaling | ( | ) |
Whether or not we scale the matrix A so that the maximum coefficient on each line and each column is 1.0.
optional bool use_scaling = 16 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5794 of file GlopParameters.java.
| boolean com.google.ortools.glop.GlopParameters.Builder.hasUseTransposedMatrix | ( | ) |
Whether or not we keep a transposed version of the matrix A to speed-up the pricing at the cost of extra memory and the initial tranposition computation.
optional bool use_transposed_matrix = 18 [default = true];
Implements com.google.ortools.glop.GlopParametersOrBuilder.
Definition at line 5959 of file GlopParameters.java.
|
protected |
Definition at line 3952 of file GlopParameters.java.
| final boolean com.google.ortools.glop.GlopParameters.Builder.isInitialized | ( | ) |
Definition at line 4499 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.mergeFrom | ( | com.google.ortools.glop.GlopParameters | other | ) |
Definition at line 4317 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.mergeFrom | ( | com.google.protobuf.CodedInputStream | input, |
| com.google.protobuf.ExtensionRegistryLite | extensionRegistry ) throws java.io.IOException |
Definition at line 4504 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.mergeFrom | ( | com.google.protobuf.Message | other | ) |
Definition at line 4308 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setAllowSimplexAlgorithmChange | ( | boolean | value | ) |
During incremental solve, let the solver decide if it use the primal or dual simplex algorithm depending on the current solution and on the new problem. Note that even if this is true, the value of use_dual_simplex still indicates the default algorithm that the solver will use.
optional bool allow_simplex_algorithm_change = 32 [default = false];
| value | The allowSimplexAlgorithmChange to set. |
Definition at line 7096 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setBasisRefactorizationPeriod | ( | int | value | ) |
Number of iterations between two basis refactorizations. Note that various conditions in the algorithm may trigger a refactorization before this period is reached. Set this to 0 if you want to refactorize at each step.
optional int32 basis_refactorization_period = 19 [default = 64];
| value | The basisRefactorizationPeriod to set. |
Definition at line 6051 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setChangeStatusToImprecise | ( | boolean | value | ) |
If true, the internal API will change the return status to imprecise if the solution does not respect the internal tolerances.
optional bool change_status_to_imprecise = 58 [default = true];
| value | The changeStatusToImprecise to set. |
Definition at line 6522 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setCostScaling | ( | com.google.ortools.glop.GlopParameters.CostScalingAlgorithm | value | ) |
optional .operations_research.glop.GlopParameters.CostScalingAlgorithm cost_scaling = 60 [default = CONTAIN_ONE_COST_SCALING];
| value | The costScaling to set. |
Definition at line 5865 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setCrossoverBoundSnappingDistance | ( | double | value | ) |
If the starting basis contains FREE variable with bounds, we will move any such variable to their closer bounds if the distance is smaller than this parameter. The starting statuses can contains FREE variables with bounds, if a user set it like this externally. Also, any variable with an initial BASIC status that was not kept in the initial basis is marked as FREE before this step is applied. Note that by default a FREE variable is assumed to be zero unless a starting value was specified via SetStartingVariableValuesForNextSolve(). Note that, at the end of the solve, some of these FREE variable with bounds and an interior point value might still be left in the final solution. Enable push_to_vertex to clean these up.
optional double crossover_bound_snapping_distance = 64 [default = inf];
| value | The crossoverBoundSnappingDistance to set. |
Definition at line 8517 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setDegenerateMinistepFactor | ( | double | value | ) |
During a degenerate iteration, the more conservative approach is to do a step of length zero (while shifting the bound of the leaving variable). That is, the variable values are unchanged for the primal simplex or the reduced cost are unchanged for the dual simplex. However, instead of doing a step of length zero, it seems to be better on degenerate problems to do a small positive step. This is what is recommended in the EXPAND procedure described in: P. E. Gill, W. Murray, M. A. Saunders, and M. H. Wright. "A practical anti- cycling procedure for linearly constrained optimization". Mathematical Programming, 45:437\u2013474, 1989. Here, during a degenerate iteration we do a small positive step of this factor times the primal (resp. dual) tolerance. In the primal simplex, this may effectively push variable values (very slightly) further out of their bounds (resp. reduced costs for the dual simplex). Setting this to zero reverts to the more conservative approach of a zero step during degenerate iterations.
optional double degenerate_ministep_factor = 42 [default = 0.01];
| value | The degenerateMinistepFactor to set. |
Definition at line 7786 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setDevexWeightsResetPeriod | ( | int | value | ) |
Devex weights will be reset to 1.0 after that number of updates.
optional int32 devex_weights_reset_period = 33 [default = 150];
| value | The devexWeightsResetPeriod to set. |
Definition at line 7155 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setDropMagnitude | ( | double | value | ) |
Value in the input LP lower than this will be ignored. This is similar to drop_tolerance but more aggressive as this is used before scaling. This is mainly here to avoid underflow and have simpler invariant in the code, like a * b == 0 iff a or b is zero and things like this.
optional double drop_magnitude = 71 [default = 1e-30];
| value | The dropMagnitude to set. |
Definition at line 8804 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setDropTolerance | ( | double | value | ) |
In order to increase the sparsity of the manipulated vectors, floating point values with a magnitude smaller than this parameter are set to zero (only in some places). This parameter should be positive or zero.
optional double drop_tolerance = 52 [default = 1e-14];
| value | The dropTolerance to set. |
Definition at line 5759 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setDualFeasibilityTolerance | ( | double | value | ) |
Variables whose reduced costs have an absolute value smaller than this tolerance are not considered as entering candidates. That is they do not take part in deciding whether a solution is dual-feasible or not. Note that this value can temporarily increase during the execution of the algorithm if the estimated precision of the reduced costs is higher than this tolerance. Note also that we scale the costs (in the presolve step) so that the cost magnitude range contains one. This is also known as the optimality tolerance in other solvers.
optional double dual_feasibility_tolerance = 11 [default = 1e-08];
| value | The dualFeasibilityTolerance to set. |
Definition at line 5388 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setDualizerThreshold | ( | double | value | ) |
When solve_dual_problem is LET_SOLVER_DECIDE, take the dual if the number of constraints of the problem is more than this threshold times the number of variables.
optional double dualizer_threshold = 21 [default = 1.5];
| value | The dualizerThreshold to set. |
Definition at line 6253 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setDualPricePrioritizeNorm | ( | boolean | value | ) |
On some problem like stp3d or pds-100 this makes a huge difference in speed and number of iterations of the dual simplex.
optional bool dual_price_prioritize_norm = 69 [default = false];
| value | The dualPricePrioritizeNorm to set. |
Definition at line 8866 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setDualSmallPivotThreshold | ( | double | value | ) |
Like small_pivot_threshold but for the dual simplex. This is needed because the dual algorithm does not interpret this value in the same way. TODO(user): Clean this up and use the same small pivot detection.
optional double dual_small_pivot_threshold = 38 [default = 0.0001];
| value | The dualSmallPivotThreshold to set. |
Definition at line 7473 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setDynamicallyAdjustRefactorizationPeriod | ( | boolean | value | ) |
If this is true, then basis_refactorization_period becomes a lower bound on the number of iterations between two refactorization (provided there is no numerical accuracy issues). Depending on the estimated time to refactorize vs the extra time spend in each solves because of the LU update, we try to balance the two times.
optional bool dynamically_adjust_refactorization_period = 63 [default = true];
| value | The dynamicallyAdjustRefactorizationPeriod to set. |
Definition at line 6121 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setExploitSingletonColumnInInitialBasis | ( | boolean | value | ) |
Whether or not we exploit the singleton columns already present in the problem when we create the initial basis.
optional bool exploit_singleton_column_in_initial_basis = 37 [default = true];
| value | The exploitSingletonColumnInInitialBasis to set. |
Definition at line 7410 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setFeasibilityRule | ( | com.google.ortools.glop.GlopParameters.PricingRule | value | ) |
PricingRule to use during the feasibility phase.
optional .operations_research.glop.GlopParameters.PricingRule feasibility_rule = 1 [default = STEEPEST_EDGE];
| value | The feasibilityRule to set. |
Definition at line 4945 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setHarrisToleranceRatio | ( | double | value | ) |
This impacts the ratio test and indicates by how much we allow a basic variable value that we move to go out of bounds. The value should be in [0.0, 1.0) and should be interpreted as a ratio of the primal_feasibility_tolerance. Setting this to 0.0 basically disables the Harris ratio test while setting this too close to 1.0 will make it difficult to keep the variable values inside their bounds modulo the primal_feasibility_tolerance. Note that the same comment applies to the dual simplex ratio test. There, we allow the reduced costs to be of an infeasible sign by as much as this ratio times the dual_feasibility_tolerance.
optional double harris_tolerance_ratio = 13 [default = 0.5];
| value | The harrisToleranceRatio to set. |
Definition at line 5563 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setInitialBasis | ( | com.google.ortools.glop.GlopParameters.InitialBasisHeuristic | value | ) |
What heuristic is used to try to replace the fixed slack columns in the initial basis of the primal simplex.
optional .operations_research.glop.GlopParameters.InitialBasisHeuristic initial_basis = 17 [default = TRIANGULAR];
| value | The initialBasis to set. |
Definition at line 5922 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setInitialConditionNumberThreshold | ( | double | value | ) |
If our upper bound on the condition number of the initial basis (from our heurisitic or a warm start) is above this threshold, we revert to an all slack basis.
optional double initial_condition_number_threshold = 59 [default = 1e+50];
| value | The initialConditionNumberThreshold to set. |
Definition at line 8297 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setInitializeDevexWithColumnNorms | ( | boolean | value | ) |
Whether we initialize devex weights to 1.0 or to the norms of the matrix columns.
optional bool initialize_devex_with_column_norms = 36 [default = true];
| value | The initializeDevexWithColumnNorms to set. |
Definition at line 7350 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setLogSearchProgress | ( | boolean | value | ) |
If true, logs the progress of a solve to LOG(INFO). Note that the same messages can also be turned on by displaying logs at level 1 for the relevant files.
optional bool log_search_progress = 61 [default = false];
| value | The logSearchProgress to set. |
Definition at line 8361 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setLogToStdout | ( | boolean | value | ) |
If true, logs will be displayed to stdout instead of using Google log info.
optional bool log_to_stdout = 66 [default = true];
| value | The logToStdout to set. |
Definition at line 8419 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setLuFactorizationPivotThreshold | ( | double | value | ) |
Threshold for LU-factorization: for stability reasons, the magnitude of the chosen pivot at a given step is guaranteed to be greater than this threshold times the maximum magnitude of all the possible pivot choices in the same column. The value must be in [0,1].
optional double lu_factorization_pivot_threshold = 25 [default = 0.01];
| value | The luFactorizationPivotThreshold to set. |
Definition at line 6656 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setMarkowitzSingularityThreshold | ( | double | value | ) |
If a pivot magnitude is smaller than this during the Markowitz LU factorization, then the matrix is assumed to be singular. Note that this is an absolute threshold and is not relative to the other possible pivots on the same column (see lu_factorization_pivot_threshold).
optional double markowitz_singularity_threshold = 30 [default = 1e-15];
| value | The markowitzSingularityThreshold to set. |
Definition at line 6972 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setMarkowitzZlatevParameter | ( | int | value | ) |
How many columns do we look at in the Markowitz pivoting rule to find a good pivot. See markowitz.h.
optional int32 markowitz_zlatev_parameter = 29 [default = 3];
| value | The markowitzZlatevParameter to set. |
Definition at line 6906 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setMaxDeterministicTime | ( | double | value | ) |
Maximum deterministic time allowed to solve a problem. The deterministic time is more or less correlated to the running time, and its unit should be around the second (at least on a Xeon(R) CPU E5-1650 v2 @ 3.50GHz). TODO(user): Improve the correlation.
optional double max_deterministic_time = 45 [default = inf];
| value | The maxDeterministicTime to set. |
Definition at line 6783 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setMaxNumberOfIterations | ( | long | value | ) |
Maximum number of simplex iterations to solve a problem. A value of -1 means no limit.
optional int64 max_number_of_iterations = 27 [default = -1];
| value | The maxNumberOfIterations to set. |
Definition at line 6846 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setMaxNumberOfReoptimizations | ( | double | value | ) |
When the solution of phase II is imprecise, we re-run the phase II with the opposite algorithm from that imprecise solution (i.e., if primal or dual simplex was used, we use dual or primal simplex, respectively). We repeat such re-optimization until the solution is precise, or we hit this limit.
optional double max_number_of_reoptimizations = 56 [default = 40];
| value | The maxNumberOfReoptimizations to set. |
Definition at line 6588 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setMaxTimeInSeconds | ( | double | value | ) |
Maximum time allowed in seconds to solve a problem.
optional double max_time_in_seconds = 26 [default = inf];
| value | The maxTimeInSeconds to set. |
Definition at line 6715 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setMaxValidMagnitude | ( | double | value | ) |
Any finite values in the input LP must be below this threshold, otherwise the model will be reported invalid. This is needed to avoid floating point overflow when evaluating bounds * coeff for instance. In practice, users shouldn't use super large values in an LP. With the default threshold, even evaluating large constraint with variables at their bound shouldn't cause any overflow.
optional double max_valid_magnitude = 70 [default = 1e+30];
| value | The maxValidMagnitude to set. |
Definition at line 8734 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setMinimumAcceptablePivot | ( | double | value | ) |
We never follow a basis change with a pivot under this threshold.
optional double minimum_acceptable_pivot = 15 [default = 1e-06];
| value | The minimumAcceptablePivot to set. |
Definition at line 5697 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setNumOmpThreads | ( | int | value | ) |
Number of threads in the OMP parallel sections. If left to 1, the code will not create any OMP threads and will remain single-threaded.
optional int32 num_omp_threads = 44 [default = 1];
| value | The numOmpThreads to set. |
Definition at line 7974 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setObjectiveLowerLimit | ( | double | value | ) |
The solver will stop as soon as it has proven that the objective is smaller than objective_lower_limit or greater than objective_upper_limit. Depending on the simplex algorithm (primal or dual) and the optimization direction, note that only one bound will be used at the time. Important: The solver does not add any tolerances to these values, and as soon as the objective (as computed by the solver, so with some imprecision) crosses one of these bounds (strictly), the search will stop. It is up to the client to add any tolerance if needed.
optional double objective_lower_limit = 40 [default = -inf];
| value | The objectiveLowerLimit to set. |
Definition at line 7631 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setObjectiveUpperLimit | ( | double | value | ) |
optional double objective_upper_limit = 41 [default = inf];
| value | The objectiveUpperLimit to set. |
Definition at line 7683 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setOptimizationRule | ( | com.google.ortools.glop.GlopParameters.PricingRule | value | ) |
PricingRule to use during the optimization phase.
optional .operations_research.glop.GlopParameters.PricingRule optimization_rule = 2 [default = STEEPEST_EDGE];
| value | The optimizationRule to set. |
Definition at line 5003 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setPerturbCostsInDualSimplex | ( | boolean | value | ) |
When this is true, then the costs are randomly perturbed before the dual simplex is even started. This has been shown to improve the dual simplex performance. For a good reference, see Huangfu Q (2013) "High performance simplex solver", Ph.D, dissertation, University of Edinburgh.
optional bool perturb_costs_in_dual_simplex = 53 [default = false];
| value | The perturbCostsInDualSimplex to set. |
Definition at line 8040 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setPreprocessorZeroTolerance | ( | double | value | ) |
A floating point tolerance used by the preprocessors. This is used for things like detecting if two columns/rows are proportional or if an interval is empty. Note that the preprocessors also use solution_feasibility_tolerance() to detect if a problem is infeasible.
optional double preprocessor_zero_tolerance = 39 [default = 1e-09];
| value | The preprocessorZeroTolerance to set. |
Definition at line 7546 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setPrimalFeasibilityTolerance | ( | double | value | ) |
This tolerance indicates by how much we allow the variable values to go out of bounds and still consider the current solution primal-feasible. We also use the same tolerance for the error A.x - b. Note that the two errors are closely related if A is scaled in such a way that the greatest coefficient magnitude on each column is 1.0. This is also simply called feasibility tolerance in other solvers.
optional double primal_feasibility_tolerance = 10 [default = 1e-08];
| value | The primalFeasibilityTolerance to set. |
Definition at line 5299 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setProvideStrongOptimalGuarantee | ( | boolean | value | ) |
If true, then when the solver returns a solution with an OPTIMAL status, we can guarantee that: - The primal variable are in their bounds. - The dual variable are in their bounds. - If we modify each component of the right-hand side a bit and each component of the objective function a bit, then the pair (primal values, dual values) is an EXACT optimal solution of the perturbed problem. - The modifications above are smaller than the associated tolerances as defined in the comment for solution_feasibility_tolerance (*). (*): This is the only place where the guarantee is not tight since we compute the upper bounds with scalar product of the primal/dual solution and the initial problem coefficients with only double precision. Note that whether or not this option is true, we still check the primal/dual infeasibility and objective gap. However if it is false, we don't move the primal/dual values within their bounds and leave them untouched.
optional bool provide_strong_optimal_guarantee = 24 [default = true];
| value | The provideStrongOptimalGuarantee to set. |
Definition at line 6446 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setPushToVertex | ( | boolean | value | ) |
If the optimization phases finishes with super-basic variables (i.e., variables that either 1) have bounds but are FREE in the basis, or 2) have no bounds and are FREE in the basis at a nonzero value), then run a "push" phase to push these variables to bounds, obtaining a vertex solution. Note this situation can happen only if a starting value was specified via SetStartingVariableValuesForNextSolve().
optional bool push_to_vertex = 65 [default = true];
| value | The pushToVertex to set. |
Definition at line 8602 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setRandomSeed | ( | int | value | ) |
At the beginning of each solve, the random number generator used in some part of the solver is reinitialized to this seed. If you change the random seed, the solver may make different choices during the solving process. Note that this may lead to a different solution, for example a different optimal basis. For some problems, the running time may vary a lot depending on small change in the solving algorithm. Running the solver with different seeds enables to have more robust benchmarks when evaluating new features. Also note that the solver is fully deterministic: two runs of the same binary, on the same machine, on the exact same data and with the same parameters will go through the exact same iterations. If they hit a time limit, they might of course yield different results because one will have advanced farther than the other.
optional int32 random_seed = 43 [default = 1];
| value | The randomSeed to set. |
Definition at line 7901 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setRatioTestZeroThreshold | ( | double | value | ) |
During the primal simplex (resp. dual simplex), the coefficients of the direction (resp. update row) with a magnitude lower than this threshold are not considered during the ratio test. This tolerance is related to the precision at which a Solve() involving the basis matrix can be performed. TODO(user): Automatically increase it when we detect that the precision of the Solve() is worse than this.
optional double ratio_test_zero_threshold = 12 [default = 1e-09];
| value | The ratioTestZeroThreshold to set. |
Definition at line 5471 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setRecomputeEdgesNormThreshold | ( | double | value | ) |
Note that the threshold is a relative error on the actual norm (not the squared one) and that edge norms are always greater than 1. Recomputing norms is a really expensive operation and a large threshold is ok since this doesn't impact directly the solution but just the entering variable choice.
optional double recompute_edges_norm_threshold = 9 [default = 100];
| value | The recomputeEdgesNormThreshold to set. |
Definition at line 5221 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setRecomputeReducedCostsThreshold | ( | double | value | ) |
We estimate the accuracy of the iteratively computed reduced costs. If it falls below this threshold, we reinitialize them from scratch. Note that such an operation is pretty fast, so we can use a low threshold. It is important to have a good accuracy here (better than the dual_feasibility_tolerance below) to be sure of the sign of such a cost.
optional double recompute_reduced_costs_threshold = 8 [default = 1e-08];
| value | The recomputeReducedCostsThreshold to set. |
Definition at line 5149 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setRefactorizationThreshold | ( | double | value | ) |
We estimate the factorization accuracy of B during each pivot by using the fact that we can compute the pivot coefficient in two ways: - From direction[leaving_row]. - From update_row[entering_column]. If the two values have a relative difference above this threshold, we trigger a refactorization.
optional double refactorization_threshold = 6 [default = 1e-09];
| value | The refactorizationThreshold to set. |
Definition at line 5076 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setRelativeCostPerturbation | ( | double | value | ) |
The magnitude of the cost perturbation is given by RandomIn(1.0, 2.0) * ( relative_cost_perturbation * cost + relative_max_cost_perturbation * max_cost);
optional double relative_cost_perturbation = 54 [default = 1e-05];
| value | The relativeCostPerturbation to set. |
Definition at line 8192 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setRelativeMaxCostPerturbation | ( | double | value | ) |
optional double relative_max_cost_perturbation = 55 [default = 1e-07];
| value | The relativeMaxCostPerturbation to set. |
Definition at line 8239 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setScalingMethod | ( | com.google.ortools.glop.GlopParameters.ScalingAlgorithm | value | ) |
optional .operations_research.glop.GlopParameters.ScalingAlgorithm scaling_method = 57 [default = EQUILIBRATION];
| value | The scalingMethod to set. |
Definition at line 4891 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setSmallPivotThreshold | ( | double | value | ) |
When we choose the leaving variable, we want to avoid small pivot because they are the less precise and may cause numerical instabilities. For a pivot under this threshold times the infinity norm of the direction, we try various countermeasures in order to avoid using it.
optional double small_pivot_threshold = 14 [default = 1e-06];
| value | The smallPivotThreshold to set. |
Definition at line 5638 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setSolutionFeasibilityTolerance | ( | double | value | ) |
When the problem status is OPTIMAL, we check the optimality using this relative tolerance and change the status to IMPRECISE if an issue is detected. The tolerance is "relative" in the sense that our thresholds are: - tolerance * max(1.0, abs(bound)) for crossing a given bound. - tolerance * max(1.0, abs(cost)) for an infeasible reduced cost. - tolerance for an infeasible dual value.
optional double solution_feasibility_tolerance = 22 [default = 1e-06];
| value | The solutionFeasibilityTolerance to set. |
Definition at line 6332 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setSolveDualProblem | ( | com.google.ortools.glop.GlopParameters.SolverBehavior | value | ) |
Whether or not we solve the dual of the given problem. With a value of auto, the algorithm decide which approach is probably the fastest depending on the problem dimensions (see dualizer_threshold).
optional .operations_research.glop.GlopParameters.SolverBehavior solve_dual_problem = 20 [default = LET_SOLVER_DECIDE];
| value | The solveDualProblem to set. |
Definition at line 6187 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setUseDedicatedDualFeasibilityAlgorithm | ( | boolean | value | ) |
We have two possible dual phase I algorithms. Both work on an LP that minimize the sum of dual infeasiblities. One use dedicated code (when this param is true), the other one use exactly the same code as the dual phase II but on an auxiliary problem where the variable bounds of the original problem are changed. TODO(user): For now we have both, but ideally the non-dedicated version will win since it is a lot less code to maintain.
optional bool use_dedicated_dual_feasibility_algorithm = 62 [default = true];
| value | The useDedicatedDualFeasibilityAlgorithm to set. |
Definition at line 8120 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setUseDualSimplex | ( | boolean | value | ) |
Whether or not we use the dual simplex algorithm instead of the primal.
optional bool use_dual_simplex = 31 [default = false];
| value | The useDualSimplex to set. |
Definition at line 7031 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setUseImpliedFreePreprocessor | ( | boolean | value | ) |
If presolve runs, include the pass that detects implied free variables.
optional bool use_implied_free_preprocessor = 67 [default = true];
| value | The useImpliedFreePreprocessor to set. |
Definition at line 8663 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setUseMiddleProductFormUpdate | ( | boolean | value | ) |
Whether or not to use the middle product form update rather than the standard eta LU update. The middle form product update should be a lot more efficient (close to the Forrest-Tomlin update, a bit slower but easier to implement). See for more details: Qi Huangfu, J. A. Julian Hall, "Novel update techniques for the revised simplex method", 28 january 2013, Technical Report ERGO-13-0001 http://www.maths.ed.ac.uk/hall/HuHa12/ERGO-13-001.pdf
optional bool use_middle_product_form_update = 35 [default = true];
| value | The useMiddleProductFormUpdate to set. |
Definition at line 7285 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setUsePreprocessing | ( | boolean | value | ) |
Whether or not we use advanced preprocessing techniques.
optional bool use_preprocessing = 34 [default = true];
| value | The usePreprocessing to set. |
Definition at line 7211 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setUseScaling | ( | boolean | value | ) |
Whether or not we scale the matrix A so that the maximum coefficient on each line and each column is 1.0.
optional bool use_scaling = 16 [default = true];
| value | The useScaling to set. |
Definition at line 5820 of file GlopParameters.java.
| Builder com.google.ortools.glop.GlopParameters.Builder.setUseTransposedMatrix | ( | boolean | value | ) |
Whether or not we keep a transposed version of the matrix A to speed-up the pricing at the cost of extra memory and the initial tranposition computation.
optional bool use_transposed_matrix = 18 [default = true];
| value | The useTransposedMatrix to set. |
Definition at line 5987 of file GlopParameters.java.
1.12.0 
Public Member Functions inherited from