![]() |
MAiNGO
|
Wrapper for handling the lower bounding problems as well as optimization-based bounds tightening (OBBT) More...
#include <lbp.h>
Public Member Functions | |
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... | |
virtual void | activate_more_scaling () |
Function called by the B&B solver to heuristically activate more scaling in the LBS. 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... | |
Protected Member Functions | |
virtual LINEARIZATION_RETCODE | _update_LP (const babBase::BabNode ¤tNode) |
Calls the proper function for computing linearization points and modifying the coefficients of the LP problem The function is virtual, since other solver types, e.g., an interval solver does not need to always compute McCormick relaxations. More... | |
virtual void | _set_variable_bounds (const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds) |
Virtual function for setting the bounds of variables. More... | |
virtual 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) |
Virtual auxiliary function for updating LP objective, i.e., processing the linearization of the objective function. More... | |
virtual 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) |
Virtual auxiliary function for updating LP inequalities, i.e., processing the linearization of the inequality. More... | |
virtual 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) |
Virtual auxiliary function for updating LP equalities, i.e., processing the linearization of the equality. More... | |
virtual 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) |
Virtual auxiliary function for updating LP relaxation only inequalities, i.e., processing the linearization of the relaxation only inequality. More... | |
virtual 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) |
Virtual auxiliary function for updating LP relaxation only equalities, i.e., processing the linearization of the relaxation only equality. More... | |
virtual 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) |
Virtual 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 | _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 void | _solve_LP (const babBase::BabNode ¤tNode) |
Virtual function for solving the currently constructed linear program. This function also internally sets the _solutionPoint, _multipliers, and the _LPstatus. 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... | |
virtual void | _turn_off_specific_options () |
Virtual function for checking if a specific option has to be turned off for a given lower bounding solver, e.g., interval-based solvers can't use OBBT. More... | |
void | _truncate_value (double &value, const double tolerance) |
Function used for truncation of value digits which are not guaranteed to be correct. More... | |
virtual SUBSOLVER_RETCODE | _check_infeasibility (const babBase::BabNode ¤tNode) |
Virtual function for checking if the solution point returned by the LP solver is really infeasible. More... | |
virtual SUBSOLVER_RETCODE | _check_feasibility (const std::vector< double > &solution) |
Virtual function for checking if the solution point returned by the LP solver is really feasible. More... | |
virtual SUBSOLVER_RETCODE | _check_optimality (const babBase::BabNode ¤tNode, const double newLBD, const std::vector< double > &solution, const double etaVal, const std::vector< double > &multipliers) |
Virtual function for checking if the solution point returned by the LP solver is really optimal. 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... | |
Protected Attributes | |
std::vector< double > | _incumbent |
std::vector< std::vector< double > > | _objectiveScalingFactors |
Objects for dual optimality condition check, i.e., c^T * x = y^T * b | |
std::vector< std::vector< std::vector< double > > > | _matrixObj |
std::vector< std::vector< std::vector< double > > > | _matrixIneq |
std::vector< std::vector< std::vector< double > > > | _matrixEq1 |
std::vector< std::vector< std::vector< double > > > | _matrixEq2 |
std::vector< std::vector< std::vector< double > > > | _matrixIneqRelaxationOnly |
std::vector< std::vector< std::vector< double > > > | _matrixEqRelaxationOnly1 |
std::vector< std::vector< std::vector< double > > > | _matrixEqRelaxationOnly2 |
std::vector< std::vector< std::vector< double > > > | _matrixIneqSquash |
std::vector< std::vector< double > > | _rhsObj |
std::vector< std::vector< double > > | _rhsIneq |
std::vector< std::vector< double > > | _rhsEq1 |
std::vector< std::vector< double > > | _rhsEq2 |
std::vector< std::vector< double > > | _rhsIneqRelaxationOnly |
std::vector< std::vector< double > > | _rhsEqRelaxationOnly1 |
std::vector< std::vector< double > > | _rhsEqRelaxationOnly2 |
std::vector< std::vector< double > > | _rhsIneqSquash |
Pointers to several objects. Note that these are NOT const, since if we want to resolve with MAiNGO, the pointers have to change | |
std::shared_ptr< DagObj > | _DAGobj |
Settings * | _maingoSettings |
Logger * | _logger |
std::vector< Constraint > * | _constraintProperties |
Internal variables for storing information on the problem | |
std::vector< unsigned > | _nLinObj |
std::vector< unsigned > | _nLinIneq |
std::vector< unsigned > | _nLinEq |
std::vector< unsigned > | _nLinIneqRelaxationOnly |
std::vector< unsigned > | _nLinEqRelaxationOnly |
std::vector< unsigned > | _nLinIneqSquash |
unsigned | _maxnParticipatingVariables |
const unsigned | _nvar |
const unsigned | _nineq |
const unsigned | _neq |
const unsigned | _nineqRelaxationOnly |
const unsigned | _neqRelaxationOnly |
const unsigned | _nineqSquash |
std::vector< babBase::OptimizationVariable > | _originalVariables |
double | _objectiveValue |
std::vector< double > | _solutionPoint |
std::vector< double > | _multipliers |
std::vector< double > | _lowerVarBounds |
std::vector< double > | _upperVarBounds |
LP_RETCODE | _LPstatus |
double | _computationTol |
bool | _differentNumberOfLins = false |
Private Member Functions | |
SUBSOLVER_RETCODE | _solve_probing_LBP (babBase::BabNode ¤tNode, LbpDualInfo &dualInfo, const unsigned int iVar, const bool fixToLowerBound) |
Function called by do_dbbt_and_probing for solving the lower bounding problem for probing on the current node. More... | |
void | _set_number_of_linpoints (const unsigned int LBP_linPoints) |
Function for setting the correct number of linearization points depending on the LBP_linpoints setting. More... | |
LowerBoundingSolver (const LowerBoundingSolver &) | |
LowerBoundingSolver & | operator= (const LowerBoundingSolver &) |
Wrapper for handling the lower bounding problems as well as optimization-based bounds tightening (OBBT)
This class provides an interface between the Branch-and-Bound solver, the problem definition used by BigMC, and the actual sub-solver used for lower bounding (currently CPLEX). It manages the CPLEX problem and solver instance(s), evaluates the Model using MC++ to obtain relaxations and subgradients, constructs the respective LP relaxations, and calls CPLEX to solve either the lower bounding problems (LBP) or OBBT as queried by the B&B solver.
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.
[in] | DAG | is the directed acyclic graph constructed in MAiNGO.cpp needed to construct an own DAG for the lower bounding solver |
[in] | DAGvars | are the variables corresponding to the DAG |
[in] | DAGfunctions | are the functions corresponding to the DAG |
[in] | variables | is a vector containing the initial optimization variables defined in problem.h |
[in] | nineqIn | is the number of inequality constraints |
[in] | neqIn | is the number of equality |
[in] | nineqRelaxationOnlyIn | is the number of inequality for use only in the relaxed problem |
[in] | neqRelaxationOnlyIn | is the number of equality constraints for use only in the relaxed problem |
[in] | nineqSquashIn | is the number of squash inequality constraints which are to be used only if the squash node has been used |
[in] | settingsIn | is a pointer to the MAiNGO settings |
[in] | loggerIn | is a pointer to the MAiNGO logger object |
[in] | constraintPropertiesIn | is a pointer to the constraint properties determined by MAiNGO |
|
inlinevirtual |
Virtual destructor, only needed to make sure the correct destructor of the derived classes is called.
|
private |
default copy constructor declared private to prevent use
|
protectedvirtual |
Virtual function for checking if the solution point returned by the LP solver is really feasible.
[in] | solution | is holding the solution point to check |
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
protectedvirtual |
Virtual function for checking if the current linear program is really infeasible by, e.g., resolving it with different algorithms.
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protectedvirtual |
Virtual function for checking if the solution point returned by the LP solver is really infeasible.
[in] | currentNode | is holding the current node in the branch-and-bound tree |
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
protectedvirtual |
Virtual function for checking if the solution point returned by the LP solver is really optimal.
[in] | currentNode | is holding the current node in the branch-and-bound tree |
[in] | newLBD | is the value of the solution point to check |
[in] | solution | is holding the solution point to check |
[in] | etaVal | is holding the value of eta at the solution point |
[in] | multipliers | is holding the dual multipliers of the solution |
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
protected |
Heuristical determination of good linearization points. This function is in testing phasing and is not used.
|
protected |
Function for the computation of simplex points lying on a sphere with radius sphereRadius rotated by angleIn.
[in] | dim | denotes the dimension of the current optimization problem |
[in] | angleIn | is the rotation angle of the simplex, the simplex will be rotated alternating by angleIn and 180°+angleIn |
[in] | sphereRadius | is the radius of the dim-dimensional ball on which the simplex vertices lie |
[in] | simplexPoints | holds the computed points of the simplex |
|
protectedvirtual |
Virtual function deactivating all objective rows in the LP for feasibility OBBT.
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protected |
Function for equilibrating a line in an LP.
[in,out] | coefficients | is the vector holding the coefficients aij in the corresponding LP line j: sum_i a_ji xi <= bj |
[in,out] | rhs | is the right-hand side bj in the corresponding LP line j: sum_i a_ji xi <= bj |
[in] | lowerVarBounds | is the vector of lower bounds on your variables |
[in] | upperVarBounds | is the vector of upper bounds on your variables |
|
protectedvirtual |
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.
[in,out] | newLBD | ist the lower bound obtained through intervals by the fallback function |
|
protectedvirtual |
Virtual function for fixing a variable to one of its bounds.
[in] | iVar | is the number of variable which will be fixed. |
[in] | fixToLowerBound | describes whether the variable shall be fixed to its lower or upper bound. |
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protectedvirtual |
Virtual function returning the current status of the last solved linear program.
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protectedvirtual |
Virtual function for setting the multipliers of the lastly solved LP.
[in] | multipliers | is modified to hold the reduced costs of the lastly solved LP |
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protected |
Virtual function returning the objective value of the lastly solved LP.
|
protectedvirtual |
Virtual function returning the objective value of the lastly solved LP for a specific solver.
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protectedvirtual |
Virtual function for setting the solution to the solution point of the lastly solved LP.
[in,out] | solution | is modified to hold the solution point of the lastly solved LP |
[in,out] | etaVal | is modified to hold the value of eta variable of the lastly solved LP |
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protected |
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.
[in] | currentNode | is the current node in the B&B |
|
protected |
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.
[in] | currentNode | is the current node in the B&B |
|
protected |
This function linearizes each function of the model at (_nvar+2)/2 random points (except for the linear ones)
[in] | lowerVarBounds | is the vector of lower bounds on your variables |
[in] | upperVarBounds | is the vector of upper bounds on your variables |
|
protected |
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.
[in] | lowerVarBounds | is the vector of lower bounds on your variables |
[in] | upperVarBounds | is the vector of upper bounds on your variables |
|
protected |
Auxiliary function for calling the proper function to linearize functions at chosen linearization point.
[out] | resultRelaxation | is the vector holding McCormick relaxation after they have been evaluated at the linearization point |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | subgraph | is the subgraph holding the list of operations of the underlying function(s) to be evaluated |
[in] | functions | is the vector holding the FFVar pointers to function(s) to be evaluated |
|
protected |
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.
[out] | resultRelaxationVMC | is the vector holding vector McCormick relaxation after they have been evaluated at the vector linearization point |
[in] | linearizationPoints | is the vector holding linearization points used for subgradient heuristic |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | subgraph | is the subgraph holding the list of operations of the underlying function(s) to be evaluated |
[in] | functions | is the vector holding the FFVar pointers to function(s) to be evaluated |
|
protected |
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.
[in] | lowerVarBounds | is the vector of lower bounds on your variables |
[in] | upperVarBounds | is the vector of upper bounds on your variables |
[in] | holdsIncumbent | tells whether the current node holds the incumbent |
|
protected |
This function linearizes each function of the model at the middle point of the underlying box.
[in] | lowerVarBounds | is the vector of lower bounds on your variables |
[in] | upperVarBounds | is the vector of upper bounds on your variables |
|
protectedvirtual |
Virtual function modifying the LP for feasibility-optimality OBBT.
[in] | currentUBD | is the current upper bound |
[in,out] | toTreatMax | is the list holding variables indices for maximization |
[in,out] | toTreatMin | is the list holding variables indices for minimization |
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protected |
Function for printing the current LP stored in _MatrixA, _MatrixA_eqs, _rhsB, _rhsB_eqs.
[in] | lowerVarBounds | is the vector of lower bounds on your variables |
[in] | upperVarBounds | is the vector of upper bounds on your variables |
|
protected |
The function resets the LP, meaning it sets all rhs to 1e19 and coefficients to 0. Eta coefficients are -1.
[in] | linearizationPoint | is a dummy point to save computation time |
[in] | lowerVarBounds | is the vector of lower bounds on your variables |
[in] | upperVarBounds | is the vector of upper bounds on your variables |
|
protectedvirtual |
Virtual function for restoring proper coefficients and options in the LP after OBBT.
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
private |
Function for setting the correct number of linearization points depending on the LBP_linpoints setting.
[in] | LBP_linPoints | is the corresponding setting |
|
protectedvirtual |
Virtual function for setting the optimization sense of variable iVar in OBBT.
[in] | iVar | is the number of variable of which the optimization sense will be changed. |
[in] | optimizationSense | describes whether the variable shall be maximized or minimized 1: minimize, 0: ignore, -1: maximize. |
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protectedvirtual |
Virtual function for setting the bounds of variables.
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
protectedvirtual |
Virtual function for solving the currently constructed linear program. This function also internally sets the _solutionPoint, _multipliers, and the _LPstatus.
[in] | currentNode | is the currentNode, needed for throwing exceptions or similar |
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
private |
Function called by do_dbbt_and_probing for solving the lower bounding problem for probing on the current node.
[in,out] | currentNode | is the B&B node for which the lower bounding problem should be solved |
[out] | dualInfo | is a struct containing information from the LP solved during probing |
[in] | iVar | is the variable to be fixed to its bound |
[in] | fixToLowerBound | denotes whether the variable shall be fixed to its lower bound |
|
inlineprotected |
Function used for truncation of value digits which are not guaranteed to be correct.
[in] | value | ist the double to be truncated |
[in] | tolerance | is a given tolerance up to which the value will be truncated, e.g., 10e9 means that 9 digits after comma will be cut off |
|
protectedvirtual |
Virtual function for checking if a specific option has to be turned off for a given lower bounding solver, e.g., interval-based solvers can't use OBBT.
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
protectedvirtual |
Calls the proper function for computing linearization points and modifying the coefficients of the LP problem The function is virtual, since other solver types, e.g., an interval solver does not need to always compute McCormick relaxations.
[in] | currentNode | is current node of the branch-and-bound tree |
Reimplemented in maingo::lbp::LbpInterval.
|
protectedvirtual |
Virtual auxiliary function for updating LP equalities, i.e., processing the linearization of the equality.
[in] | resultRelaxationCv | is the McCormick object holding relaxation of equality iEq at linearizationPoint used for the convex part |
[in] | resultRelaxationCc | is the McCormick object holding relaxation of equality iEq at linearizationPoint used for the concave part |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iLin | is the number of the linearization point |
[in] | iEq | is the number of the equality function |
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
protectedvirtual |
Virtual auxiliary function for updating LP equalities, i.e., processing the linearization of the equality for vector McCormick relaxations.
[in] | resultRelaxationCvVMC | is the vector McCormick object holding relaxation of equality iEq at linearizationPoint used for the convex part |
[in] | resultRelaxationCcVMC | is the vector McCormick object holding relaxation of equality iEq at linearizationPoint used for the concave part |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iEq | is the number of the equality function |
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protectedvirtual |
Virtual auxiliary function for updating LP relaxation only equalities, i.e., processing the linearization of the relaxation only equality.
[in] | resultRelaxationCv | is the McCormick object holding relaxation of relaxation only equality iEqRelaxationOnly at linearizationPoint used for the convex part |
[in] | resultRelaxationCc | is the McCormick object holding relaxation of relaxation only equality iEqRelaxationOnly at linearizationPoint used for the concave part |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iLin | is the number of the linearization point |
[in] | iEqRelaxationOnly | is the number of the relaxation only equality function |
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
protectedvirtual |
Virtual auxiliary function for updating LP relaxation only equalities, i.e., processing the linearization of the relaxation only equality for vector McCormick relaxations.
[in] | resultRelaxationCvVMC | is the vector McCormick object holding relaxation of relaxation only equality iEqRelaxationOnly at linearizationPoint used for the convex part |
[in] | resultRelaxationCcVMC | is the vector McCormick object holding relaxation of relaxation only equality iEqRelaxationOnly at linearizationPoint used for the concave part |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iEqRelaxationOnly | is the number of the relaxation only equality function |
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protectedvirtual |
Virtual auxiliary function for updating LP inequalities, i.e., processing the linearization of the inequality.
[in] | resultRelaxation | is the McCormick object holding relaxation of inequality iIneq at linearizationPoint |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iLin | is the number of the linearization point |
[in] | iIneq | is the number of the inequality function |
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
protectedvirtual |
Virtual auxiliary function for updating LP inequalities, i.e., processing the linearization of the inequality for vector McCormick relaxations.
[in] | resultRelaxationVMC | is the vector McCormick object holding relaxation of inequality iIneq at linearizationPoint |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iIneq | is the number of the inequality function |
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protectedvirtual |
Virtual auxiliary function for updating LP squash inequalities, i.e., processing the linearization of the squash inequality No tolerances are allowed for squash inequalities!
[in] | resultRelaxation | is the McCormick object holding relaxation of inequality iIneqSquash at linearizationPoint |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iLin | is the number of the linearization point |
[in] | iIneqSquash | is the number of the inequality function |
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
protectedvirtual |
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!
[in] | resultRelaxationVMC | is the vector McCormick object holding relaxation of inequality iIneqSquash at linearizationPoint |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iIneqSquash | is the number of the inequality function |
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protectedvirtual |
Virtual auxiliary function for updating LP relaxation only inequalities, i.e., processing the linearization of the relaxation only inequality.
[in] | resultRelaxation | is the McCormick object holding relaxation of relaxation only inequality iIneqRelaxationOnly at linearizationPoint |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iLin | is the number of the linearization point |
[in] | iIneqRelaxationOnly | is the number of the relaxation only inequality function |
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
protectedvirtual |
Virtual auxiliary function for updating LP relaxation only inequalities, i.e., processing the linearization of the relaxation only inequality for vector McCormick relaxations.
[in] | resultRelaxationVMC | is the vector McCormick object holding relaxation of relaxation only inequality iIneqRelaxationOnly at linearizationPoint |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iIneqRelaxationOnly | is the number of the relaxation only inequality function |
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protected |
This function properly builds the LP using previously determined nonlinear functions.
[in] | resultRelaxationNonlinear | is the vector of MC objects holding relaxations of nonlinear functions |
[in] | linearizationPoint | is the point where the subgradient heuristic was performed |
[in] | lowerVarBounds | is the vector of lower bounds on your variables |
[in] | upperVarBounds | is the vector of upper bounds on your variables |
[in] | iLin | is the number of linearization |
|
protected |
This function properly builds the LP using previously determined nonlinear and linear functions.
[in] | resultRelaxationVMCNonlinear | is the vector of VMC objects holding relaxations of nonlinear functions |
[in] | resultRelaxationLinear | is the vector of MC objects holding relaxations of linear functions |
[in] | linearizationPoint | is the point where the subgradient heuristic was performed and acts as a reference point for linear functions |
[in] | scaledPoints | are the simplex/random points scaled back to its original domain |
[in] | lowerVarBounds | is the vector of lower bounds on your variables |
[in] | upperVarBounds | is the vector of upper bounds on your variables |
|
protectedvirtual |
Virtual auxiliary function for updating LP objective, i.e., processing the linearization of the objective function.
[in] | resultRelaxation | is the McCormick object holding relaxation of objective iObj at linearizationPoint |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iLin | is the number of the linearization point |
[in] | iObj | is the number of the objective function |
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
protectedvirtual |
Virtual auxiliary function for updating LP objective, i.e., processing the linearization of the objective function for vector McCormick relaxations.
[in] | resultRelaxationVMC | is the vector McCormick object holding relaxation of objective iObj at linearizationPoint |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iObj | is the number of the objective function |
Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.
|
protected |
Virtual auxiliary function for updating whole LP at once.
[in] | resultRelaxation | is the vector holding McCormick relaxations at linearizationPoint |
[in] | linearizationPoint | is the vector holding the linearization point |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
[in] | iLin | is the number of the linearization point |
|
protected |
Virtual auxiliary function for updating whole LP at once.
[in] | resultRelaxationVMC | is the vector holding vector McCormick relaxations at linearizationPoints |
[in] | linearizationPoints | is the vector holding the linearization points |
[in] | lowerVarBounds | is the vector holding the lower bounds of the variables |
[in] | upperVarBounds | is the vector holding the upper bounds of the variables |
|
virtual |
Function called by the B&B solver to heuristically activate more scaling in the LBS.
Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.
|
virtual |
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.
[in,out] | currentNode | is the B&B node for which constraint propagation should be executed; if constraint propagation is successful in tightening bounds, currentNode will be modified accordingly |
[in] | currentUBD | is the current upper bounds (i.e., incumbent objective value); it is used for the upper bound of the objective constraint interval |
[in] | pass | is the maximum number of consecutive propagation runs |
TIGHTENING_RETCODE LowerBoundingSolver::do_dbbt_and_probing | ( | babBase::BabNode & | currentNode, |
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)
[in,out] | currentNode | is the B&B node for which constraint propagation should be executed; if DBBT or probing are successful in tightening bounds, currentNode will be modified accordingly |
[in] | lbpSolutionPoint | is a vector containing the solution point of the LBP for currentNode |
[in] | dualInfo | is a struct containing information from the LP solved during LBP |
[in] | currentUBD | is the current upper bounds (i.e., incumbent objective value); it is used for the upper bound in DBBT / probing |
|
private |
default assignment operator declared private to prevent use
void LowerBoundingSolver::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.
[in] | rootNode | is the rootNode on which some options are checked |
SUBSOLVER_RETCODE LowerBoundingSolver::solve_LBP | ( | const babBase::BabNode & | currentNode, |
double & | lowerBound, | ||
std::vector< double > & | solutionPoint, | ||
LbpDualInfo & | dualInfo | ||
) |
Function called by B&B solver for solving the lower bounding problem on the current node.
[in] | currentNode | is the B&B node for which the lower bounding problem should be solved |
[out] | lowerBound | is the lower bound on the optimal objective value obtained for the current node |
[out] | solutionPoint | is the point at which lowerBound was achieved |
[out] | dualInfo | is a struct containing information from the LP solver needed for DBBT and probing |
TIGHTENING_RETCODE LowerBoundingSolver::solve_OBBT | ( | babBase::BabNode & | currentNode, |
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)
[in,out] | currentNode | is the B&B node for which the lower bounding problem should be solved; if OBBT is successful in tightening bounds, currentNode will be modified accordingly |
[in] | currentUBD | is the current upper bounds (i.e., incumbent objective value); It is used for the objective function cut if reductionType==OBBT_FEASOPT |
[in] | reductionType | determines whether OBBT should include only feasibility or also optimality (i.e., an objective function cut f_cv<=currentUBD) |
void LowerBoundingSolver::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.
[in] | incumbentBAB | is a vector containing the current incumbent |
|
protected |
variable holding the computational tolerance given as max(deltaIneq,deltaEq)
|
protected |
pointer to constraint properties determined by MAiNGO
|
protected |
object holding the DAG
|
protected |
flag indicating whether the number of linearizations set in CPLEX and CLP equals the number of linearization points in vmccormick
|
protected |
incumbent point, needed for some heuristics and checks
|
protected |
vector storing the lower variable bounds for MAiNGO solver and Interval solver
|
protected |
variable holding the current LP status for MAiNGO solver and Interval solver
|
protected |
pointer to object holding the settings
|
protected |
equalities convex times _nLinEq variables
|
protected |
equalities concave times _nLinEq variables
|
protected |
equalities relaxation only convex times _nLinEqRelaxationOnly variables
|
protected |
equalities relaxation only concave times _nLinEqRelaxationOnly variables
|
protected |
inequalities times _nLinIneq times variables
|
protected |
inequalities relaxation only times _nLinIneqRelaxationOnly times variables
|
protected |
inequalities squash times _nLinIneqSquash times variables
|
protected |
objective(s) times _nLinObj times variables
|
protected |
maximal number of participating variables over all functions
|
protected |
vector storing the multipliers for MAiNGO solver and Interval solver
|
protected |
number of non-constant equalities in the original (not relaxed) problem
|
protected |
number of non-constant equalities for use only in the relaxed problem
|
protected |
number of non-constant inequalities in the original (not relaxed) problem
|
protected |
number of non-constant inequalities for use only in the relaxed problem
|
protected |
number of non-constant squash inequalities in the original (not relaxed) problem
|
protected |
vector holding the number of linearization points of each equality constraint
|
protected |
vector holding the number of linearization points of each equality relaxation only constraint
|
protected |
vector holding the number of linearization points of each inequality constraint
|
protected |
vector holding the number of linearization points of each inequality relaxation only constraint
|
protected |
vector holding the number of linearization points of each squash inequality constraint
|
protected |
vector holding the number of linearization points of the objective function(s)
|
protected |
number of variables in the original (not relaxed) problem
|
protected |
scaling factors used in the linearizations of the objective function(s)
|
protected |
variable holding the objective value of the linear program for MAiNGO solver and Interval solver
|
protected |
original variables (i.e., original upper and lower bounds, info on which variables are binary etc., cf. structs.h)
|
protected |
right-hand side of the equalities (convex) of the lower bounding linear program
|
protected |
right-hand side of the equalities (concave) of the lower bounding linear program
|
protected |
right-hand side of the relaxation only equalities (convex) of the lower bounding linear program
|
protected |
right-hand side of the relaxation only equalities (concave) of the lower bounding linear program
|
protected |
right-hand side of the inequalities of the lower bounding linear program
|
protected |
right-hand side of the relaxation only inequalities of the lower bounding linear program
|
protected |
right-hand side of the squash inequalities of the lower bounding linear program
|
protected |
right-hand side of the objective(s) of the lower bounding linear program
|
protected |
vector storing the solution point for MAiNGO solver and Interval solver
|
protected |
vector storing the upper variable bounds for MAiNGO solver and Interval solver