Wrapper for handling the lower bounding problems by using interval arithmetics. We currently do a bit too much work, if the subgradient interval heuristic is not used, since we additionally compute the McCormick relaxations.
More...
|
| LbpInterval (mc::FFGraph &DAG, const std::vector< mc::FFVar > &DAGvars, const std::vector< mc::FFVar > &DAGfunctions, const std::vector< babBase::OptimizationVariable > &variables, const unsigned nineqIn, const unsigned neqIn, const unsigned nineqRelaxationOnlyIn, const unsigned neqRelaxationOnlyIn, const unsigned nineqSquashIn, Settings *settingsIn, Logger *loggerIn, std::vector< Constraint > *constraintPropertiesIn) |
| Constructor, stores information on the problem. More...
|
|
void | activate_more_scaling () |
| Function called by the B&B solver to heuristically activate more scaling in the LBS. More...
|
|
Public Member Functions inherited from maingo::lbp::LowerBoundingSolver |
| LowerBoundingSolver (mc::FFGraph &DAG, const std::vector< mc::FFVar > &DAGvars, const std::vector< mc::FFVar > &DAGfunctions, const std::vector< babBase::OptimizationVariable > &variables, const unsigned nineqIn, const unsigned neqIn, const unsigned nineqRelaxationOnlyIn, const unsigned neqRelaxationOnlyIn, const unsigned nineqSquashIn, Settings *settingsIn, Logger *loggerIn, std::vector< Constraint > *constraintPropertiesIn) |
| Constructor, stores information on the problem and constructs an own copy of the directed acyclic graph. More...
|
|
virtual | ~LowerBoundingSolver () |
| Virtual destructor, only needed to make sure the correct destructor of the derived classes is called. More...
|
|
SUBSOLVER_RETCODE | solve_LBP (const babBase::BabNode ¤tNode, double &lowerBound, std::vector< double > &solutionPoint, LbpDualInfo &dualInfo) |
| Function called by B&B solver for solving the lower bounding problem on the current node. More...
|
|
TIGHTENING_RETCODE | solve_OBBT (babBase::BabNode ¤tNode, const double currentUBD, const OBBT reductionType) |
| Function called by B&B solver for optimality-based range reduction (cf., e.g., Gleixner et al., J. Glob. Optim. 67 (2017) 731) More...
|
|
virtual TIGHTENING_RETCODE | do_constraint_propagation (babBase::BabNode ¤tNode, const double currentUBD, const unsigned pass=3) |
| Function called by B&B solver for constraint propagation. This function is virtual as it may be overwritten for certain LBD solvers. The defaults for constraint propagation are 10 rounds and at least 1% improvement. More...
|
|
TIGHTENING_RETCODE | do_dbbt_and_probing (babBase::BabNode ¤tNode, const std::vector< double > &lbpSolutionPoint, const LbpDualInfo &dualInfo, const double currentUBD) |
| Function called by B&B solver for DBBT and probing (for each variable depending on where the LBD solution lies) More...
|
|
void | update_incumbent_LBP (const std::vector< double > &incumbentBAB) |
| Function called by the B&B solver to update the incumbent and the ID of the node currently holding it, which is needed by some linearization heuristics. More...
|
|
void | preprocessor_check_options (const babBase::BabNode &rootNode) |
| Function called by the B&B in preprocessing in order to check the need for specific options, currently for subgradient intervals & CPLEX no large values. More...
|
|
|
void | _set_variable_bounds (const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds) |
| Function for setting the interval bounds. More...
|
|
LINEARIZATION_RETCODE | _update_LP (const babBase::BabNode ¤tNode) |
| Calls the proper function for computing Intervals. More...
|
|
void | _update_LP_obj (const MC &resultRelaxation, const std::vector< double > &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iLin, unsigned const &iObj) |
| Auxiliary function for updating LP objective, i.e., processing the linearization of the objective function ( CPLEX cannot work with coefficients >+1e19 or -1e19> ) More...
|
|
void | _update_LP_ineq (const MC &resultRelaxation, const std::vector< double > &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iLin, unsigned const &iIneq) |
| Auxiliary function for updating LP inequalities, i.e., processing the linearization of the inequality. More...
|
|
void | _update_LP_eq (const MC &resultRelaxationCv, const MC &resultRelaxationCc, const std::vector< double > &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iLin, unsigned const &iEq) |
| Auxiliary function for updating LP equalities, i.e., processing the linearization of the equality. More...
|
|
void | _update_LP_ineqRelaxationOnly (const MC &resultRelaxation, const std::vector< double > &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iLin, unsigned const &iIneqRelaxationOnly) |
| Auxiliary function for updating LP relaxation only inequalities, i.e., processing the linearization of the relaxation only inequality. More...
|
|
void | _update_LP_eqRelaxationOnly (const MC &resultRelaxationCv, const MC &resultRelaxationCc, const std::vector< double > &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iLin, unsigned const &iEqRelaxationOnly) |
| Auxiliary function for updating LP relaxation only equalities, i.e., processing the linearization of the relaxation only equality. More...
|
|
void | _update_LP_ineq_squash (const MC &resultRelaxation, const std::vector< double > &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iLin, unsigned const &iIneqSquash) |
| Auxiliary function for updating LP squash inequalities, i.e., processing the linearization of the squash inequality No tolerances are allowed for squash inequalities! More...
|
|
void | _solve_LP (const babBase::BabNode ¤tNode) |
| Function for solving the currently constructed linear program. This function also internally sets the _solutionPoint, _multipliers, and the _LPstatus. More...
|
|
void | _turn_off_specific_options () |
| Function for checking if a specific option has to be turned off for a given lower bounding solver. More...
|
|
SUBSOLVER_RETCODE | _check_infeasibility (const babBase::BabNode ¤tNode) |
| Function for checking if the solution point returned is really infeasible. Not available in this solver. More...
|
|
SUBSOLVER_RETCODE | _check_feasibility (const std::vector< double > &solution) |
| Function for checking if the solution point returned is really feasible. Not available in this solver. More...
|
|
SUBSOLVER_RETCODE | _check_optimality (const babBase::BabNode ¤tNode, const double newLBD, const std::vector< double > &solution, const double etaVal, const std::vector< double > &multipliers) |
| Function for checking if the solution point returned is really optimal. Not available in this solver. More...
|
|
Protected Member Functions inherited from maingo::lbp::LowerBoundingSolver |
void | _update_whole_LP_at_linpoint (const std::vector< MC > &resultRelaxation, const std::vector< double > &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iLin) |
| Virtual auxiliary function for updating whole LP at once. More...
|
|
virtual void | _update_LP_obj (const vMC &resultRelaxationVMC, const std::vector< std::vector< double >> &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iObj) |
| Virtual auxiliary function for updating LP objective, i.e., processing the linearization of the objective function for vector McCormick relaxations. More...
|
|
virtual void | _update_LP_ineq (const vMC &resultRelaxationVMC, const std::vector< std::vector< double >> &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iIneq) |
| Virtual auxiliary function for updating LP inequalities, i.e., processing the linearization of the inequality for vector McCormick relaxations. More...
|
|
virtual void | _update_LP_eq (const vMC &resultRelaxationCvVMC, const vMC &resultRelaxationCcVMC, const std::vector< std::vector< double >> &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iEq) |
| Virtual auxiliary function for updating LP equalities, i.e., processing the linearization of the equality for vector McCormick relaxations. More...
|
|
virtual void | _update_LP_ineqRelaxationOnly (const vMC &resultRelaxationVMC, const std::vector< std::vector< double >> &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iIneqRelaxationOnly) |
| Virtual auxiliary function for updating LP relaxation only inequalities, i.e., processing the linearization of the relaxation only inequality for vector McCormick relaxations. More...
|
|
virtual void | _update_LP_eqRelaxationOnly (const vMC &resultRelaxationCvVMC, const vMC &resultRelaxationCcVMC, const std::vector< std::vector< double >> &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iEqRelaxationOnly) |
| Virtual auxiliary function for updating LP relaxation only equalities, i.e., processing the linearization of the relaxation only equality for vector McCormick relaxations. More...
|
|
virtual void | _update_LP_ineq_squash (const vMC &resultRelaxationVMC, const std::vector< std::vector< double >> &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, unsigned const &iIneqSquash) |
| Virtual auxiliary function for updating LP squash inequalities, i.e., processing the linearization of the squash inequality for vector McCormick relaxations No tolerances are allowed for squash inequalities! More...
|
|
void | _update_whole_LP_at_vector_linpoints (const std::vector< vMC > &resultRelaxationVMC, const std::vector< std::vector< double >> &linearizationPoints, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds) |
| Virtual auxiliary function for updating whole LP at once. More...
|
|
double | _equilibrate_and_relax (std::vector< double > &coefficients, double &rhs, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds) |
| Function for equilibrating a line in an LP. More...
|
|
virtual LP_RETCODE | _get_LP_status () |
| Virtual function returning the current status of the last solved linear program. More...
|
|
virtual void | _get_solution_point (std::vector< double > &solution, double &etaVal) |
| Virtual function for setting the solution to the solution point of the lastly solved LP. More...
|
|
double | _get_objective_value () |
| Virtual function returning the objective value of the lastly solved LP. More...
|
|
virtual double | _get_objective_value_solver () |
| Virtual function returning the objective value of the lastly solved LP for a specific solver. More...
|
|
virtual void | _get_multipliers (std::vector< double > &multipliers) |
| Virtual function for setting the multipliers of the lastly solved LP. More...
|
|
virtual void | _deactivate_objective_function_for_OBBT () |
| Virtual function deactivating all objective rows in the LP for feasibility OBBT. More...
|
|
virtual void | _modify_LP_for_feasopt_OBBT (const double ¤tUBD, std::list< unsigned > &toTreatMax, std::list< unsigned > &toTreatMin) |
| Virtual function modifying the LP for feasibility-optimality OBBT. More...
|
|
virtual void | _set_optimization_sense_of_variable (const unsigned &iVar, const int &optimizationSense) |
| Virtual function for setting the optimization sense of variable iVar in OBBT. More...
|
|
virtual void | _restore_LP_coefficients_after_OBBT () |
| Virtual function for restoring proper coefficients and options in the LP after OBBT. More...
|
|
virtual void | _fix_variable (const unsigned &iVar, const bool fixToLowerBound) |
| Virtual function for fixing a variable to one of its bounds. More...
|
|
virtual bool | _check_if_LP_really_infeasible () |
| Virtual function for checking if the current linear program is really infeasible by, e.g., resolving it with different algorithms. More...
|
|
void | _linearize_functions_at_linpoint (std::vector< MC > &resultRelaxation, const std::vector< double > &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, mc::FFSubgraph &subgraph, std::vector< mc::FFVar > &functions) |
| Auxiliary function for calling the proper function to linearize functions at chosen linearization point. More...
|
|
void | _linearize_functions_at_preset_vector_linpoint (std::vector< vMC > &resultRelaxationVMC, const std::vector< std::vector< double >> &linearizationPoints, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, mc::FFSubgraph &subgraph, std::vector< mc::FFVar > &functions) |
| Auxiliary function for calling the proper function to linearize functions at precomputed vector linearization point. The precomputed vector linearization point has to be saved in _DAGobj.vMcPoint. More...
|
|
LINEARIZATION_RETCODE | _linearize_model_at_midpoint (const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds) |
| This function linearizes each function of the model at the middle point of the underlying box. More...
|
|
LINEARIZATION_RETCODE | _linearize_model_at_incumbent (const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, const bool holdsIncumbent) |
| This function linearizes each function of the model at the incumbent if it is contained in the current node. Otherwise each function is linearized at the middle point of the underlying box. More...
|
|
LINEARIZATION_RETCODE | _linearization_points_Kelley (const babBase::BabNode ¤tNode) |
| This function adds linearizations to LP with the use of an adapted version of Kelley's algorithm. The number of points equals at most _nvar+2. This function requires the solution of auxiliary LPs. Linear functions will be computed only once, since McCormick returns envelopes. Superfluous rows in the resulting LP will be set to 0. More...
|
|
LINEARIZATION_RETCODE | _linearization_points_Simplex (const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds) |
| This function linearizes each function of the model at (_nvar+2)/2 points (except for the linear ones). The points are computed by using the precomputed simplex vertices from _compute_and_rotate_simplex. More...
|
|
LINEARIZATION_RETCODE | _linearization_points_random (const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds) |
| This function linearizes each function of the model at (_nvar+2)/2 random points (except for the linear ones) More...
|
|
LINEARIZATION_RETCODE | _linearization_points_Kelley_Simplex (const babBase::BabNode ¤tNode) |
| This function adds linearizations to LP with the use of an adapted version of Kelley's algorithm. The number of points equals at most the size of the chosen linpoints vector +3. This function requires the solution of auxiliary LPs. Linear functions will be computed only once, since McCormick returns envelopes. Superfluous rows in the resulting LP will be set to 0. More...
|
|
void | _update_LP_nonlinear_linear (const std::vector< vMC > &resultRelaxationVMCNonlinear, const std::vector< MC > &resultRelaxationLinear, const std::vector< double > &linearizationPoint, const std::vector< std::vector< double >> &scaledPoints, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds) |
| This function properly builds the LP using previously determined nonlinear and linear functions. More...
|
|
void | _update_LP_nonlinear (const std::vector< MC > &resultRelaxationNonlinear, const std::vector< double > &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, const unsigned iLin) |
| This function properly builds the LP using previously determined nonlinear functions. More...
|
|
void | _reset_LP (const std::vector< double > &linearizationPoint, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds) |
| The function resets the LP, meaning it sets all rhs to 1e19 and coefficients to 0. Eta coefficients are -1. More...
|
|
void | _compute_and_rotate_simplex (const unsigned int dim, const double angleIn, const double sphereRadius, std::vector< std::vector< double >> &simplexPoints) |
| Function for the computation of simplex points lying on a sphere with radius sphereRadius rotated by angleIn. More...
|
|
void | _choose_good_lin_points (const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, bool firstTime=true) |
| Heuristical determination of good linearization points. This function is in testing phasing and is not used. More...
|
|
virtual SUBSOLVER_RETCODE | _fallback_to_intervals (double &newLBD) |
| Virtual function for checking if a given node is feasible with the use of interval arithmetics. It is needed in cases where the LBD solver may return something misleading, e.g., says sth is optimal but it can't be verified. More...
|
|
void | _truncate_value (double &value, const double tolerance) |
| Function used for truncation of value digits which are not guaranteed to be correct. More...
|
|
void | _print_LP (const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds) |
| Function for printing the current LP stored in _MatrixA, _MatrixA_eqs, _rhsB, _rhsB_eqs. More...
|
|