MAiNGO
maingo::lbp::LowerBoundingSolver Class Reference

Wrapper for handling the lower bounding problems as well as optimization-based bounds tightening (OBBT) More...

#include <lbp.h>

Inheritance diagram for maingo::lbp::LowerBoundingSolver:
maingo::lbp::LbpClp maingo::lbp::LbpCplex maingo::lbp::LbpInterval

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 &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. More...
 
TIGHTENING_RETCODE 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) More...
 
virtual TIGHTENING_RETCODE do_constraint_propagation (babBase::BabNode &currentNode, 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 &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) 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 &currentNode)
 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 &currentNode)
 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 &currentUBD, 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 &currentNode)
 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 &currentNode)
 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 &currentNode)
 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 &currentNode, 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 &currentNode, 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 &)
 
LowerBoundingSolveroperator= (const LowerBoundingSolver &)
 

Detailed Description

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.

Constructor & Destructor Documentation

◆ LowerBoundingSolver() [1/2]

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.

Parameters
[in]DAGis the directed acyclic graph constructed in MAiNGO.cpp needed to construct an own DAG for the lower bounding solver
[in]DAGvarsare the variables corresponding to the DAG
[in]DAGfunctionsare the functions corresponding to the DAG
[in]variablesis a vector containing the initial optimization variables defined in problem.h
[in]nineqInis the number of inequality constraints
[in]neqInis the number of equality
[in]nineqRelaxationOnlyInis the number of inequality for use only in the relaxed problem
[in]neqRelaxationOnlyInis the number of equality constraints for use only in the relaxed problem
[in]nineqSquashInis the number of squash inequality constraints which are to be used only if the squash node has been used
[in]settingsInis a pointer to the MAiNGO settings
[in]loggerInis a pointer to the MAiNGO logger object
[in]constraintPropertiesInis a pointer to the constraint properties determined by MAiNGO

◆ ~LowerBoundingSolver()

virtual maingo::lbp::LowerBoundingSolver::~LowerBoundingSolver ( )
inlinevirtual

Virtual destructor, only needed to make sure the correct destructor of the derived classes is called.

◆ LowerBoundingSolver() [2/2]

maingo::lbp::LowerBoundingSolver::LowerBoundingSolver ( const LowerBoundingSolver )
private

default copy constructor declared private to prevent use

Member Function Documentation

◆ _check_feasibility()

virtual SUBSOLVER_RETCODE maingo::lbp::LowerBoundingSolver::_check_feasibility ( const std::vector< double > &  solution)
protectedvirtual

Virtual function for checking if the solution point returned by the LP solver is really feasible.

Parameters
[in]solutionis holding the solution point to check
Returns
Returns whether the given solution was confirmed to be feasible or not

Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.

◆ _check_if_LP_really_infeasible()

bool LowerBoundingSolver::_check_if_LP_really_infeasible ( )
protectedvirtual

Virtual function for checking if the current linear program is really infeasible by, e.g., resolving it with different algorithms.

Returns
Returns true if the linear program is indeed infeasible, false if and optimal solution was found

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _check_infeasibility()

virtual SUBSOLVER_RETCODE maingo::lbp::LowerBoundingSolver::_check_infeasibility ( const babBase::BabNode currentNode)
protectedvirtual

Virtual function for checking if the solution point returned by the LP solver is really infeasible.

Parameters
[in]currentNodeis holding the current node in the branch-and-bound tree
Returns
Returns whether the problem was confirmed to be infeasible or not

Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.

◆ _check_optimality()

virtual SUBSOLVER_RETCODE maingo::lbp::LowerBoundingSolver::_check_optimality ( const babBase::BabNode currentNode,
const double  newLBD,
const std::vector< double > &  solution,
const double  etaVal,
const std::vector< double > &  multipliers 
)
protectedvirtual

Virtual function for checking if the solution point returned by the LP solver is really optimal.

Parameters
[in]currentNodeis holding the current node in the branch-and-bound tree
[in]newLBDis the value of the solution point to check
[in]solutionis holding the solution point to check
[in]etaValis holding the value of eta at the solution point
[in]multipliersis holding the dual multipliers of the solution
Returns
Returns whether the given solution was confirmed to be optimal or not

Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.

◆ _choose_good_lin_points()

void LowerBoundingSolver::_choose_good_lin_points ( const std::vector< double > &  lowerVarBounds,
const std::vector< double > &  upperVarBounds,
bool  firstTime = true 
)
protected

Heuristical determination of good linearization points. This function is in testing phasing and is not used.

◆ _compute_and_rotate_simplex()

void LowerBoundingSolver::_compute_and_rotate_simplex ( const unsigned int  dim,
const double  angleIn,
const double  sphereRadius,
std::vector< std::vector< double >> &  simplexPoints 
)
protected

Function for the computation of simplex points lying on a sphere with radius sphereRadius rotated by angleIn.

Parameters
[in]dimdenotes the dimension of the current optimization problem
[in]angleInis the rotation angle of the simplex, the simplex will be rotated alternating by angleIn and 180°+angleIn
[in]sphereRadiusis the radius of the dim-dimensional ball on which the simplex vertices lie
[in]simplexPointsholds the computed points of the simplex

◆ _deactivate_objective_function_for_OBBT()

void LowerBoundingSolver::_deactivate_objective_function_for_OBBT ( )
protectedvirtual

Virtual function deactivating all objective rows in the LP for feasibility OBBT.

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _equilibrate_and_relax()

double LowerBoundingSolver::_equilibrate_and_relax ( std::vector< double > &  coefficients,
double &  rhs,
const std::vector< double > &  lowerVarBounds,
const std::vector< double > &  upperVarBounds 
)
protected

Function for equilibrating a line in an LP.

Parameters
[in,out]coefficientsis the vector holding the coefficients aij in the corresponding LP line j: sum_i a_ji xi <= bj
[in,out]rhsis the right-hand side bj in the corresponding LP line j: sum_i a_ji xi <= bj
[in]lowerVarBoundsis the vector of lower bounds on your variables
[in]upperVarBoundsis the vector of upper bounds on your variables
Returns
Returns the scaling factor used for the present LP line

◆ _fallback_to_intervals()

SUBSOLVER_RETCODE LowerBoundingSolver::_fallback_to_intervals ( double &  newLBD)
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.

Parameters
[in,out]newLBDist the lower bound obtained through intervals by the fallback function
Returns
Returns whether the node is feasible in interval arithmetic or not

◆ _fix_variable()

void LowerBoundingSolver::_fix_variable ( const unsigned &  iVar,
const bool  fixToLowerBound 
)
protectedvirtual

Virtual function for fixing a variable to one of its bounds.

Parameters
[in]iVaris the number of variable which will be fixed.
[in]fixToLowerBounddescribes whether the variable shall be fixed to its lower or upper bound.

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _get_LP_status()

LP_RETCODE LowerBoundingSolver::_get_LP_status ( )
protectedvirtual

Virtual function returning the current status of the last solved linear program.

Returns
Returns the current status of the last solved linear program.

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _get_multipliers()

void LowerBoundingSolver::_get_multipliers ( std::vector< double > &  multipliers)
protectedvirtual

Virtual function for setting the multipliers of the lastly solved LP.

Parameters
[in]multipliersis modified to hold the reduced costs of the lastly solved LP

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _get_objective_value()

double LowerBoundingSolver::_get_objective_value ( )
protected

Virtual function returning the objective value of the lastly solved LP.

Returns
Returns the objective value of the lastly solved LP.

◆ _get_objective_value_solver()

double LowerBoundingSolver::_get_objective_value_solver ( )
protectedvirtual

Virtual function returning the objective value of the lastly solved LP for a specific solver.

Returns
Returns the objective value of the lastly solved LP.

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _get_solution_point()

void LowerBoundingSolver::_get_solution_point ( std::vector< double > &  solution,
double &  etaVal 
)
protectedvirtual

Virtual function for setting the solution to the solution point of the lastly solved LP.

Parameters
[in,out]solutionis modified to hold the solution point of the lastly solved LP
[in,out]etaValis modified to hold the value of eta variable of the lastly solved LP

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _linearization_points_Kelley()

LINEARIZATION_RETCODE LowerBoundingSolver::_linearization_points_Kelley ( const babBase::BabNode currentNode)
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.

Parameters
[in]currentNodeis the current node in the B&B
Returns
Returns LINEARIZATION_UNKNOWN if the problem was not solved completely during linearization, returns LINEARIZATION_INFEASIBLE if the problem was found to be infeasible, returns LINEARIZATION_FEASIBLE if the problem was solved during linearization

◆ _linearization_points_Kelley_Simplex()

LINEARIZATION_RETCODE LowerBoundingSolver::_linearization_points_Kelley_Simplex ( const babBase::BabNode currentNode)
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.

Parameters
[in]currentNodeis the current node in the B&B
Returns
Returns LINEARIZATION_UNKNOWN if the problem was not solved completely during linearization, returns LINEARIZATION_INFEASIBLE if the problem was found to be infeasible, returns LINEARIZATION_FEASIBLE if the problem was solved during linearization

◆ _linearization_points_random()

LINEARIZATION_RETCODE LowerBoundingSolver::_linearization_points_random ( const std::vector< double > &  lowerVarBounds,
const std::vector< double > &  upperVarBounds 
)
protected

This function linearizes each function of the model at (_nvar+2)/2 random points (except for the linear ones)

Parameters
[in]lowerVarBoundsis the vector of lower bounds on your variables
[in]upperVarBoundsis the vector of upper bounds on your variables
Returns
Returns LINEARIZATION_UNKNOWN, since the problem is not solved in this function

◆ _linearization_points_Simplex()

LINEARIZATION_RETCODE LowerBoundingSolver::_linearization_points_Simplex ( const std::vector< double > &  lowerVarBounds,
const std::vector< double > &  upperVarBounds 
)
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.

Parameters
[in]lowerVarBoundsis the vector of lower bounds on your variables
[in]upperVarBoundsis the vector of upper bounds on your variables
Returns
Returns LINEARIZATION_UNKNOWN, since the problem is not solved in this function

◆ _linearize_functions_at_linpoint()

void LowerBoundingSolver::_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 
)
protected

Auxiliary function for calling the proper function to linearize functions at chosen linearization point.

Parameters
[out]resultRelaxationis the vector holding McCormick relaxation after they have been evaluated at the linearization point
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]subgraphis the subgraph holding the list of operations of the underlying function(s) to be evaluated
[in]functionsis the vector holding the FFVar pointers to function(s) to be evaluated

◆ _linearize_functions_at_preset_vector_linpoint()

void LowerBoundingSolver::_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 
)
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.

Parameters
[out]resultRelaxationVMCis the vector holding vector McCormick relaxation after they have been evaluated at the vector linearization point
[in]linearizationPointsis the vector holding linearization points used for subgradient heuristic
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]subgraphis the subgraph holding the list of operations of the underlying function(s) to be evaluated
[in]functionsis the vector holding the FFVar pointers to function(s) to be evaluated

◆ _linearize_model_at_incumbent()

LINEARIZATION_RETCODE LowerBoundingSolver::_linearize_model_at_incumbent ( const std::vector< double > &  lowerVarBounds,
const std::vector< double > &  upperVarBounds,
const bool  holdsIncumbent 
)
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.

Parameters
[in]lowerVarBoundsis the vector of lower bounds on your variables
[in]upperVarBoundsis the vector of upper bounds on your variables
[in]holdsIncumbenttells whether the current node holds the incumbent
Returns
Returns LINEARIZATION_UNKNOWN, since the problem is not solved in this function

◆ _linearize_model_at_midpoint()

LINEARIZATION_RETCODE LowerBoundingSolver::_linearize_model_at_midpoint ( const std::vector< double > &  lowerVarBounds,
const std::vector< double > &  upperVarBounds 
)
protected

This function linearizes each function of the model at the middle point of the underlying box.

Parameters
[in]lowerVarBoundsis the vector of lower bounds on your variables
[in]upperVarBoundsis the vector of upper bounds on your variables
Returns
Returns LINEARIZATION_UNKNOWN, since the problem is not solved in this function

◆ _modify_LP_for_feasopt_OBBT()

void LowerBoundingSolver::_modify_LP_for_feasopt_OBBT ( const double &  currentUBD,
std::list< unsigned > &  toTreatMax,
std::list< unsigned > &  toTreatMin 
)
protectedvirtual

Virtual function modifying the LP for feasibility-optimality OBBT.

Parameters
[in]currentUBDis the current upper bound
[in,out]toTreatMaxis the list holding variables indices for maximization
[in,out]toTreatMinis the list holding variables indices for minimization

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _print_LP()

void maingo::lbp::LowerBoundingSolver::_print_LP ( const std::vector< double > &  lowerVarBounds,
const std::vector< double > &  upperVarBounds 
)
protected

Function for printing the current LP stored in _MatrixA, _MatrixA_eqs, _rhsB, _rhsB_eqs.

Parameters
[in]lowerVarBoundsis the vector of lower bounds on your variables
[in]upperVarBoundsis the vector of upper bounds on your variables

◆ _reset_LP()

void LowerBoundingSolver::_reset_LP ( const std::vector< double > &  linearizationPoint,
const std::vector< double > &  lowerVarBounds,
const std::vector< double > &  upperVarBounds 
)
protected

The function resets the LP, meaning it sets all rhs to 1e19 and coefficients to 0. Eta coefficients are -1.

Parameters
[in]linearizationPointis a dummy point to save computation time
[in]lowerVarBoundsis the vector of lower bounds on your variables
[in]upperVarBoundsis the vector of upper bounds on your variables

◆ _restore_LP_coefficients_after_OBBT()

void LowerBoundingSolver::_restore_LP_coefficients_after_OBBT ( )
protectedvirtual

Virtual function for restoring proper coefficients and options in the LP after OBBT.

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _set_number_of_linpoints()

void LowerBoundingSolver::_set_number_of_linpoints ( const unsigned int  LBP_linPoints)
private

Function for setting the correct number of linearization points depending on the LBP_linpoints setting.

Parameters
[in]LBP_linPointsis the corresponding setting

◆ _set_optimization_sense_of_variable()

void LowerBoundingSolver::_set_optimization_sense_of_variable ( const unsigned &  iVar,
const int &  optimizationSense 
)
protectedvirtual

Virtual function for setting the optimization sense of variable iVar in OBBT.

Parameters
[in]iVaris the number of variable of which the optimization sense will be changed.
[in]optimizationSensedescribes whether the variable shall be maximized or minimized 1: minimize, 0: ignore, -1: maximize.

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _set_variable_bounds()

void LowerBoundingSolver::_set_variable_bounds ( const std::vector< double > &  lowerVarBounds,
const std::vector< double > &  upperVarBounds 
)
protectedvirtual

Virtual function for setting the bounds of variables.

Parameters
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables

Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.

◆ _solve_LP()

void LowerBoundingSolver::_solve_LP ( const babBase::BabNode currentNode)
protectedvirtual

Virtual function for solving the currently constructed linear program. This function also internally sets the _solutionPoint, _multipliers, and the _LPstatus.

Parameters
[in]currentNodeis the currentNode, needed for throwing exceptions or similar

Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.

◆ _solve_probing_LBP()

SUBSOLVER_RETCODE LowerBoundingSolver::_solve_probing_LBP ( babBase::BabNode currentNode,
LbpDualInfo dualInfo,
const unsigned int  iVar,
const bool  fixToLowerBound 
)
private

Function called by do_dbbt_and_probing for solving the lower bounding problem for probing on the current node.

Parameters
[in,out]currentNodeis the B&B node for which the lower bounding problem should be solved
[out]dualInfois a struct containing information from the LP solved during probing
[in]iVaris the variable to be fixed to its bound
[in]fixToLowerBounddenotes whether the variable shall be fixed to its lower bound
Returns
Return code, either RETCODE_FEASIBLE or RETCODE_INFEASIBLE

◆ _truncate_value()

void maingo::lbp::LowerBoundingSolver::_truncate_value ( double &  value,
const double  tolerance 
)
inlineprotected

Function used for truncation of value digits which are not guaranteed to be correct.

Parameters
[in]valueist the double to be truncated
[in]toleranceis a given tolerance up to which the value will be truncated, e.g., 10e9 means that 9 digits after comma will be cut off

◆ _turn_off_specific_options()

void LowerBoundingSolver::_turn_off_specific_options ( )
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.

◆ _update_LP()

LINEARIZATION_RETCODE LowerBoundingSolver::_update_LP ( const babBase::BabNode currentNode)
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.

Parameters
[in]currentNodeis current node of the branch-and-bound tree
Returns
returns a LINEARIZATION_RETCODE defining whether the final problem was already solved/proven infeasible during linearization

Reimplemented in maingo::lbp::LbpInterval.

◆ _update_LP_eq() [1/2]

void LowerBoundingSolver::_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 
)
protectedvirtual

Virtual auxiliary function for updating LP equalities, i.e., processing the linearization of the equality.

Parameters
[in]resultRelaxationCvis the McCormick object holding relaxation of equality iEq at linearizationPoint used for the convex part
[in]resultRelaxationCcis the McCormick object holding relaxation of equality iEq at linearizationPoint used for the concave part
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iLinis the number of the linearization point
[in]iEqis the number of the equality function

Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.

◆ _update_LP_eq() [2/2]

void LowerBoundingSolver::_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 
)
protectedvirtual

Virtual auxiliary function for updating LP equalities, i.e., processing the linearization of the equality for vector McCormick relaxations.

Parameters
[in]resultRelaxationCvVMCis the vector McCormick object holding relaxation of equality iEq at linearizationPoint used for the convex part
[in]resultRelaxationCcVMCis the vector McCormick object holding relaxation of equality iEq at linearizationPoint used for the concave part
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iEqis the number of the equality function

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _update_LP_eqRelaxationOnly() [1/2]

void LowerBoundingSolver::_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 
)
protectedvirtual

Virtual auxiliary function for updating LP relaxation only equalities, i.e., processing the linearization of the relaxation only equality.

Parameters
[in]resultRelaxationCvis the McCormick object holding relaxation of relaxation only equality iEqRelaxationOnly at linearizationPoint used for the convex part
[in]resultRelaxationCcis the McCormick object holding relaxation of relaxation only equality iEqRelaxationOnly at linearizationPoint used for the concave part
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iLinis the number of the linearization point
[in]iEqRelaxationOnlyis the number of the relaxation only equality function

Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.

◆ _update_LP_eqRelaxationOnly() [2/2]

void LowerBoundingSolver::_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 
)
protectedvirtual

Virtual auxiliary function for updating LP relaxation only equalities, i.e., processing the linearization of the relaxation only equality for vector McCormick relaxations.

Parameters
[in]resultRelaxationCvVMCis the vector McCormick object holding relaxation of relaxation only equality iEqRelaxationOnly at linearizationPoint used for the convex part
[in]resultRelaxationCcVMCis the vector McCormick object holding relaxation of relaxation only equality iEqRelaxationOnly at linearizationPoint used for the concave part
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iEqRelaxationOnlyis the number of the relaxation only equality function

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _update_LP_ineq() [1/2]

void LowerBoundingSolver::_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 
)
protectedvirtual

Virtual auxiliary function for updating LP inequalities, i.e., processing the linearization of the inequality.

Parameters
[in]resultRelaxationis the McCormick object holding relaxation of inequality iIneq at linearizationPoint
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iLinis the number of the linearization point
[in]iIneqis the number of the inequality function

Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.

◆ _update_LP_ineq() [2/2]

void LowerBoundingSolver::_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 
)
protectedvirtual

Virtual auxiliary function for updating LP inequalities, i.e., processing the linearization of the inequality for vector McCormick relaxations.

Parameters
[in]resultRelaxationVMCis the vector McCormick object holding relaxation of inequality iIneq at linearizationPoint
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iIneqis the number of the inequality function

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _update_LP_ineq_squash() [1/2]

void LowerBoundingSolver::_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 
)
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!

Parameters
[in]resultRelaxationis the McCormick object holding relaxation of inequality iIneqSquash at linearizationPoint
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iLinis the number of the linearization point
[in]iIneqSquashis the number of the inequality function

Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.

◆ _update_LP_ineq_squash() [2/2]

void LowerBoundingSolver::_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 
)
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!

Parameters
[in]resultRelaxationVMCis the vector McCormick object holding relaxation of inequality iIneqSquash at linearizationPoint
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iIneqSquashis the number of the inequality function

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _update_LP_ineqRelaxationOnly() [1/2]

void LowerBoundingSolver::_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 
)
protectedvirtual

Virtual auxiliary function for updating LP relaxation only inequalities, i.e., processing the linearization of the relaxation only inequality.

Parameters
[in]resultRelaxationis the McCormick object holding relaxation of relaxation only inequality iIneqRelaxationOnly at linearizationPoint
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iLinis the number of the linearization point
[in]iIneqRelaxationOnlyis the number of the relaxation only inequality function

Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.

◆ _update_LP_ineqRelaxationOnly() [2/2]

void LowerBoundingSolver::_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 
)
protectedvirtual

Virtual auxiliary function for updating LP relaxation only inequalities, i.e., processing the linearization of the relaxation only inequality for vector McCormick relaxations.

Parameters
[in]resultRelaxationVMCis the vector McCormick object holding relaxation of relaxation only inequality iIneqRelaxationOnly at linearizationPoint
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iIneqRelaxationOnlyis the number of the relaxation only inequality function

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _update_LP_nonlinear()

void LowerBoundingSolver::_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 
)
protected

This function properly builds the LP using previously determined nonlinear functions.

Parameters
[in]resultRelaxationNonlinearis the vector of MC objects holding relaxations of nonlinear functions
[in]linearizationPointis the point where the subgradient heuristic was performed
[in]lowerVarBoundsis the vector of lower bounds on your variables
[in]upperVarBoundsis the vector of upper bounds on your variables
[in]iLinis the number of linearization

◆ _update_LP_nonlinear_linear()

void LowerBoundingSolver::_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 
)
protected

This function properly builds the LP using previously determined nonlinear and linear functions.

Parameters
[in]resultRelaxationVMCNonlinearis the vector of VMC objects holding relaxations of nonlinear functions
[in]resultRelaxationLinearis the vector of MC objects holding relaxations of linear functions
[in]linearizationPointis the point where the subgradient heuristic was performed and acts as a reference point for linear functions
[in]scaledPointsare the simplex/random points scaled back to its original domain
[in]lowerVarBoundsis the vector of lower bounds on your variables
[in]upperVarBoundsis the vector of upper bounds on your variables

◆ _update_LP_obj() [1/2]

void LowerBoundingSolver::_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 
)
protectedvirtual

Virtual auxiliary function for updating LP objective, i.e., processing the linearization of the objective function.

Parameters
[in]resultRelaxationis the McCormick object holding relaxation of objective iObj at linearizationPoint
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iLinis the number of the linearization point
[in]iObjis the number of the objective function

Reimplemented in maingo::lbp::LbpClp, maingo::lbp::LbpCplex, and maingo::lbp::LbpInterval.

◆ _update_LP_obj() [2/2]

void LowerBoundingSolver::_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 
)
protectedvirtual

Virtual auxiliary function for updating LP objective, i.e., processing the linearization of the objective function for vector McCormick relaxations.

Parameters
[in]resultRelaxationVMCis the vector McCormick object holding relaxation of objective iObj at linearizationPoint
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iObjis the number of the objective function

Reimplemented in maingo::lbp::LbpClp, and maingo::lbp::LbpCplex.

◆ _update_whole_LP_at_linpoint()

void LowerBoundingSolver::_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 
)
protected

Virtual auxiliary function for updating whole LP at once.

Parameters
[in]resultRelaxationis the vector holding McCormick relaxations at linearizationPoint
[in]linearizationPointis the vector holding the linearization point
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables
[in]iLinis the number of the linearization point

◆ _update_whole_LP_at_vector_linpoints()

void LowerBoundingSolver::_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 
)
protected

Virtual auxiliary function for updating whole LP at once.

Parameters
[in]resultRelaxationVMCis the vector holding vector McCormick relaxations at linearizationPoints
[in]linearizationPointsis the vector holding the linearization points
[in]lowerVarBoundsis the vector holding the lower bounds of the variables
[in]upperVarBoundsis the vector holding the upper bounds of the variables

◆ activate_more_scaling()

void LowerBoundingSolver::activate_more_scaling ( )
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.

◆ do_constraint_propagation()

TIGHTENING_RETCODE LowerBoundingSolver::do_constraint_propagation ( babBase::BabNode currentNode,
const double  currentUBD,
const unsigned  pass = 3 
)
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.

Parameters
[in,out]currentNodeis 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]currentUBDis the current upper bounds (i.e., incumbent objective value); it is used for the upper bound of the objective constraint interval
[in]passis the maximum number of consecutive propagation runs
Returns
Return code, see enum TIGHTENING_RETCODE

◆ do_dbbt_and_probing()

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)

Parameters
[in,out]currentNodeis 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]lbpSolutionPointis a vector containing the solution point of the LBP for currentNode
[in]dualInfois a struct containing information from the LP solved during LBP
[in]currentUBDis the current upper bounds (i.e., incumbent objective value); it is used for the upper bound in DBBT / probing
Returns
Return code, see enum TIGHTENING_RETCODE

◆ operator=()

LowerBoundingSolver& maingo::lbp::LowerBoundingSolver::operator= ( const LowerBoundingSolver )
private

default assignment operator declared private to prevent use

◆ preprocessor_check_options()

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.

Parameters
[in]rootNodeis the rootNode on which some options are checked

◆ solve_LBP()

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.

Parameters
[in]currentNodeis the B&B node for which the lower bounding problem should be solved
[out]lowerBoundis the lower bound on the optimal objective value obtained for the current node
[out]solutionPointis the point at which lowerBound was achieved
[out]dualInfois a struct containing information from the LP solver needed for DBBT and probing
Returns
Return code, either RETCODE_FEASIBLE or RETCODE_INFEASIBLE

◆ solve_OBBT()

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)

Parameters
[in,out]currentNodeis 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]currentUBDis the current upper bounds (i.e., incumbent objective value); It is used for the objective function cut if reductionType==OBBT_FEASOPT
[in]reductionTypedetermines whether OBBT should include only feasibility or also optimality (i.e., an objective function cut f_cv<=currentUBD)
Returns
Return code, see enum TIGHTENING_RETCODE

◆ update_incumbent_LBP()

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.

Parameters
[in]incumbentBABis a vector containing the current incumbent

Member Data Documentation

◆ _computationTol

double maingo::lbp::LowerBoundingSolver::_computationTol
protected

variable holding the computational tolerance given as max(deltaIneq,deltaEq)

◆ _constraintProperties

std::vector<Constraint>* maingo::lbp::LowerBoundingSolver::_constraintProperties
protected

pointer to constraint properties determined by MAiNGO

◆ _DAGobj

std::shared_ptr<DagObj> maingo::lbp::LowerBoundingSolver::_DAGobj
protected

object holding the DAG

◆ _differentNumberOfLins

bool maingo::lbp::LowerBoundingSolver::_differentNumberOfLins = false
protected

flag indicating whether the number of linearizations set in CPLEX and CLP equals the number of linearization points in vmccormick

◆ _incumbent

std::vector<double> maingo::lbp::LowerBoundingSolver::_incumbent
protected

incumbent point, needed for some heuristics and checks

◆ _logger

Logger* maingo::lbp::LowerBoundingSolver::_logger
protected

pointer to MAiNGO logger

◆ _lowerVarBounds

std::vector<double> maingo::lbp::LowerBoundingSolver::_lowerVarBounds
protected

vector storing the lower variable bounds for MAiNGO solver and Interval solver

◆ _LPstatus

LP_RETCODE maingo::lbp::LowerBoundingSolver::_LPstatus
protected

variable holding the current LP status for MAiNGO solver and Interval solver

◆ _maingoSettings

Settings* maingo::lbp::LowerBoundingSolver::_maingoSettings
protected

pointer to object holding the settings

◆ _matrixEq1

std::vector<std::vector<std::vector<double> > > maingo::lbp::LowerBoundingSolver::_matrixEq1
protected

equalities convex times _nLinEq variables

◆ _matrixEq2

std::vector<std::vector<std::vector<double> > > maingo::lbp::LowerBoundingSolver::_matrixEq2
protected

equalities concave times _nLinEq variables

◆ _matrixEqRelaxationOnly1

std::vector<std::vector<std::vector<double> > > maingo::lbp::LowerBoundingSolver::_matrixEqRelaxationOnly1
protected

equalities relaxation only convex times _nLinEqRelaxationOnly variables

◆ _matrixEqRelaxationOnly2

std::vector<std::vector<std::vector<double> > > maingo::lbp::LowerBoundingSolver::_matrixEqRelaxationOnly2
protected

equalities relaxation only concave times _nLinEqRelaxationOnly variables

◆ _matrixIneq

std::vector<std::vector<std::vector<double> > > maingo::lbp::LowerBoundingSolver::_matrixIneq
protected

inequalities times _nLinIneq times variables

◆ _matrixIneqRelaxationOnly

std::vector<std::vector<std::vector<double> > > maingo::lbp::LowerBoundingSolver::_matrixIneqRelaxationOnly
protected

inequalities relaxation only times _nLinIneqRelaxationOnly times variables

◆ _matrixIneqSquash

std::vector<std::vector<std::vector<double> > > maingo::lbp::LowerBoundingSolver::_matrixIneqSquash
protected

inequalities squash times _nLinIneqSquash times variables

◆ _matrixObj

std::vector<std::vector<std::vector<double> > > maingo::lbp::LowerBoundingSolver::_matrixObj
protected

objective(s) times _nLinObj times variables

◆ _maxnParticipatingVariables

unsigned maingo::lbp::LowerBoundingSolver::_maxnParticipatingVariables
protected

maximal number of participating variables over all functions

◆ _multipliers

std::vector<double> maingo::lbp::LowerBoundingSolver::_multipliers
protected

vector storing the multipliers for MAiNGO solver and Interval solver

◆ _neq

const unsigned maingo::lbp::LowerBoundingSolver::_neq
protected

number of non-constant equalities in the original (not relaxed) problem

◆ _neqRelaxationOnly

const unsigned maingo::lbp::LowerBoundingSolver::_neqRelaxationOnly
protected

number of non-constant equalities for use only in the relaxed problem

◆ _nineq

const unsigned maingo::lbp::LowerBoundingSolver::_nineq
protected

number of non-constant inequalities in the original (not relaxed) problem

◆ _nineqRelaxationOnly

const unsigned maingo::lbp::LowerBoundingSolver::_nineqRelaxationOnly
protected

number of non-constant inequalities for use only in the relaxed problem

◆ _nineqSquash

const unsigned maingo::lbp::LowerBoundingSolver::_nineqSquash
protected

number of non-constant squash inequalities in the original (not relaxed) problem

◆ _nLinEq

std::vector<unsigned> maingo::lbp::LowerBoundingSolver::_nLinEq
protected

vector holding the number of linearization points of each equality constraint

◆ _nLinEqRelaxationOnly

std::vector<unsigned> maingo::lbp::LowerBoundingSolver::_nLinEqRelaxationOnly
protected

vector holding the number of linearization points of each equality relaxation only constraint

◆ _nLinIneq

std::vector<unsigned> maingo::lbp::LowerBoundingSolver::_nLinIneq
protected

vector holding the number of linearization points of each inequality constraint

◆ _nLinIneqRelaxationOnly

std::vector<unsigned> maingo::lbp::LowerBoundingSolver::_nLinIneqRelaxationOnly
protected

vector holding the number of linearization points of each inequality relaxation only constraint

◆ _nLinIneqSquash

std::vector<unsigned> maingo::lbp::LowerBoundingSolver::_nLinIneqSquash
protected

vector holding the number of linearization points of each squash inequality constraint

◆ _nLinObj

std::vector<unsigned> maingo::lbp::LowerBoundingSolver::_nLinObj
protected

vector holding the number of linearization points of the objective function(s)

◆ _nvar

const unsigned maingo::lbp::LowerBoundingSolver::_nvar
protected

number of variables in the original (not relaxed) problem

◆ _objectiveScalingFactors

std::vector<std::vector<double> > maingo::lbp::LowerBoundingSolver::_objectiveScalingFactors
protected

scaling factors used in the linearizations of the objective function(s)

◆ _objectiveValue

double maingo::lbp::LowerBoundingSolver::_objectiveValue
protected

variable holding the objective value of the linear program for MAiNGO solver and Interval solver

◆ _originalVariables

std::vector<babBase::OptimizationVariable> maingo::lbp::LowerBoundingSolver::_originalVariables
protected

original variables (i.e., original upper and lower bounds, info on which variables are binary etc., cf. structs.h)

◆ _rhsEq1

std::vector<std::vector<double> > maingo::lbp::LowerBoundingSolver::_rhsEq1
protected

right-hand side of the equalities (convex) of the lower bounding linear program

◆ _rhsEq2

std::vector<std::vector<double> > maingo::lbp::LowerBoundingSolver::_rhsEq2
protected

right-hand side of the equalities (concave) of the lower bounding linear program

◆ _rhsEqRelaxationOnly1

std::vector<std::vector<double> > maingo::lbp::LowerBoundingSolver::_rhsEqRelaxationOnly1
protected

right-hand side of the relaxation only equalities (convex) of the lower bounding linear program

◆ _rhsEqRelaxationOnly2

std::vector<std::vector<double> > maingo::lbp::LowerBoundingSolver::_rhsEqRelaxationOnly2
protected

right-hand side of the relaxation only equalities (concave) of the lower bounding linear program

◆ _rhsIneq

std::vector<std::vector<double> > maingo::lbp::LowerBoundingSolver::_rhsIneq
protected

right-hand side of the inequalities of the lower bounding linear program

◆ _rhsIneqRelaxationOnly

std::vector<std::vector<double> > maingo::lbp::LowerBoundingSolver::_rhsIneqRelaxationOnly
protected

right-hand side of the relaxation only inequalities of the lower bounding linear program

◆ _rhsIneqSquash

std::vector<std::vector<double> > maingo::lbp::LowerBoundingSolver::_rhsIneqSquash
protected

right-hand side of the squash inequalities of the lower bounding linear program

◆ _rhsObj

std::vector<std::vector<double> > maingo::lbp::LowerBoundingSolver::_rhsObj
protected

right-hand side of the objective(s) of the lower bounding linear program

◆ _solutionPoint

std::vector<double> maingo::lbp::LowerBoundingSolver::_solutionPoint
protected

vector storing the solution point for MAiNGO solver and Interval solver

◆ _upperVarBounds

std::vector<double> maingo::lbp::LowerBoundingSolver::_upperVarBounds
protected

vector storing the upper variable bounds for MAiNGO solver and Interval solver


The documentation for this class was generated from the following files: