MAiNGO
maingo::ubp::UpperBoundingSolver Class Reference

Base class for wrappers for handling the upper bounding problems. More...

#include <ubp.h>

Inheritance diagram for maingo::ubp::UpperBoundingSolver:
maingo::ubp::UbpClp maingo::ubp::UbpCplex maingo::ubp::UbpIpopt maingo::ubp::UbpKnitro maingo::ubp::UbpNLopt

Public Types

enum  UBS_USE { USE_PRE = 0, USE_BAB }
 Enum for communicating what the intended purpose of the solver is. This determines which settings are used. More...
 

Public Member Functions

 UpperBoundingSolver (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 nineqSquashIn, Settings *settingsIn, Logger *loggerIn, std::vector< Constraint > *constraintPropertiesIn, UBS_USE useIn)
 Constructor, stores information on the problem and constructs an own copy of the directed acyclic graph. More...
 
virtual ~UpperBoundingSolver ()
 Virtual destructor, only needed to make sure the correct destructor of the derived classes is called. More...
 
virtual SUBSOLVER_RETCODE solve (babBase::BabNode const &currentNode, double &objectiveValue, std::vector< double > &solutionPoint)
 Function called by B&B solver for solving the upper bounding problem on the current node. This calls the internal (protected) function solve_nlp that needs to be re-implemented by the derived classes. More...
 
SUBSOLVER_RETCODE multistart (babBase::BabNode const &currentNode, double &objectiveValue, std::vector< double > &solutionPoint, std::vector< SUBSOLVER_RETCODE > &feasible, std::vector< double > &optimalObjectives, bool &initialPointFeasible)
 Multistart heuristic for automatically solving the UBP from multiple starting points. More...
 
SUBSOLVER_RETCODE check_feasibility (const std::vector< double > &currentPoint, double &objectiveValue) const
 Function for checking feasibility of a point. More...
 

Protected Member Functions

virtual SUBSOLVER_RETCODE _solve_nlp (const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds, double &objectiveValue, std::vector< double > &solutionPoint)
 Function for actually solving the NLP sub-problem. This needs to be re-defined in derived classes to call specific sub-solvers. More...
 
void _determine_structure ()
 Function for determining the number of variables participating in each function and the type of a function (linear, bilinear, quadratic, non-linear) More...
 
void _determine_sparsity_jacobian ()
 Function for setting the information about the sparsity structure in the Jacobian. More...
 
void _determine_sparsity_hessian ()
 Function for determining the non-zero entries in the Hessian of the Lagrangian function. More...
 
std::vector< double > _generate_multistart_point (bool &usedCenter, const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds)
 Function for generating a point used in multistart. More...
 
Functions for checking feasibility of a given point
SUBSOLVER_RETCODE _check_ineq (const std::vector< double > &modelOutput) const
 Function checking if inequality constraints are fulfilled. More...
 
SUBSOLVER_RETCODE _check_ineq_squash (const std::vector< double > &modelOutput) const
 Function checking if squash inequality constraints are fulfilled (no tolerance allowed) More...
 
SUBSOLVER_RETCODE _check_eq (const std::vector< double > &modelOutput) const
 Function checking if equality constraints are fulfilled. More...
 
SUBSOLVER_RETCODE _check_bounds (const std::vector< double > &currentPoint) const
 Function checking if bounds are fulfilled. More...
 
SUBSOLVER_RETCODE _check_integrality (const std::vector< double > &currentPoint) const
 Function checking if discrete variables are indeed discrete. More...
 

Protected Attributes

Pointers to several objects. Note that these are NOT const, since if we want to resolve with MAiNGO, the pointers have to change
Settings_maingoSettings
 
Logger_logger
 
std::shared_ptr< DagObj_DAGobj
 
UBS_USE _intendedUse
 
std::vector< Constraint > * _constraintProperties
 
Internal variables for storing information on the problem
unsigned _nvar
 
unsigned _nineq
 
unsigned _nineqSquash
 
unsigned _neq
 
std::vector< babBase::OptimizationVariable_originalVariables
 
std::vector< double > _originalUpperBounds
 
std::vector< double > _originalLowerBounds
 
UbpStructure _structure
 

Private Member Functions

 UpperBoundingSolver ()
 
 UpperBoundingSolver (const UpperBoundingSolver &)
 
UpperBoundingSolveroperator= (const UpperBoundingSolver &)
 

Detailed Description

Base class for wrappers for handling the upper bounding problems.

This is the base class for the upper bounding solvers that construct and solve upper bounding problems. The base class simply checks feasibility of the initial point (or midpoint if none is given). The derived classes mainly need to implement the solve method for solving the upper bounding problem, as well as the set_effort method for choosing between a high and low solution effort.

Member Enumeration Documentation

◆ UBS_USE

Enum for communicating what the intended purpose of the solver is. This determines which settings are used.

Enumerator
USE_PRE 

(=0): used during pre-processing

USE_BAB 

(=1): used in Branch-and-Bound

Constructor & Destructor Documentation

◆ UpperBoundingSolver() [1/3]

UpperBoundingSolver::UpperBoundingSolver ( 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  nineqSquashIn,
Settings settingsIn,
Logger loggerIn,
std::vector< Constraint > *  constraintPropertiesIn,
UBS_USE  useIn 
)

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 constraints
[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
[in]useIncommunicates what the solver is to be used for

◆ ~UpperBoundingSolver()

virtual maingo::ubp::UpperBoundingSolver::~UpperBoundingSolver ( )
inlinevirtual

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

◆ UpperBoundingSolver() [2/3]

maingo::ubp::UpperBoundingSolver::UpperBoundingSolver ( )
private

Standard constructor prohibited

◆ UpperBoundingSolver() [3/3]

maingo::ubp::UpperBoundingSolver::UpperBoundingSolver ( const UpperBoundingSolver )
private

default copy constructor declared private to prevent use

Member Function Documentation

◆ _check_bounds()

SUBSOLVER_RETCODE UpperBoundingSolver::_check_bounds ( const std::vector< double > &  currentPoint) const
protected

Function checking if bounds are fulfilled.

Parameters
[in]currentPointholds the values of the current point

◆ _check_eq()

SUBSOLVER_RETCODE UpperBoundingSolver::_check_eq ( const std::vector< double > &  modelOutput) const
protected

Function checking if equality constraints are fulfilled.

Parameters
[in]modelOutputholds the values of all constraints of the model

◆ _check_ineq()

SUBSOLVER_RETCODE UpperBoundingSolver::_check_ineq ( const std::vector< double > &  modelOutput) const
protected

Function checking if inequality constraints are fulfilled.

Parameters
[in]modelOutputholds the values of all constraints of the model

◆ _check_ineq_squash()

SUBSOLVER_RETCODE UpperBoundingSolver::_check_ineq_squash ( const std::vector< double > &  modelOutput) const
protected

Function checking if squash inequality constraints are fulfilled (no tolerance allowed)

Parameters
[in]modelOutputholds the values of all constraints of the model

◆ _check_integrality()

SUBSOLVER_RETCODE UpperBoundingSolver::_check_integrality ( const std::vector< double > &  currentPoint) const
protected

Function checking if discrete variables are indeed discrete.

Parameters
[in]currentPointholds the values of the current point

◆ _determine_sparsity_hessian()

void UpperBoundingSolver::_determine_sparsity_hessian ( )
protected

Function for determining the non-zero entries in the Hessian of the Lagrangian function.

◆ _determine_sparsity_jacobian()

void UpperBoundingSolver::_determine_sparsity_jacobian ( )
protected

Function for setting the information about the sparsity structure in the Jacobian.

◆ _determine_structure()

void UpperBoundingSolver::_determine_structure ( )
protected

Function for determining the number of variables participating in each function and the type of a function (linear, bilinear, quadratic, non-linear)

◆ _generate_multistart_point()

std::vector< double > UpperBoundingSolver::_generate_multistart_point ( bool &  usedCenter,
const std::vector< double > &  lowerVarBounds,
const std::vector< double > &  upperVarBounds 
)
protected

Function for generating a point used in multistart.

Parameters
[in]usedCenteris a flag indicating whether the mid point has already been used
[in]lowerVarBoundsholds lower bounds of variables
[in]upperVarBoundsholds upper bounds of variables

◆ _solve_nlp()

SUBSOLVER_RETCODE UpperBoundingSolver::_solve_nlp ( const std::vector< double > &  lowerVarBounds,
const std::vector< double > &  upperVarBounds,
double &  objectiveValue,
std::vector< double > &  solutionPoint 
)
protectedvirtual

Function for actually solving the NLP sub-problem. This needs to be re-defined in derived classes to call specific sub-solvers.

Parameters
[in]lowerVarBoundsis the vector containing the lower bounds on the variables within the current node
[in]upperVarBoundsis the vector containing the upper bounds on the variables within the current node
[out]objectiveValueis the objective value obtained for the solution point of the upper bounding problem (need not be a local optimum!)
[in,out]solutionPointis the point at which objectiveValue was achieved (can in principle be any point within the current node!); it is also used for communicating the initial point (usually the LBP solution point)
Returns
Return code, either SUBSOLVER_FEASIBLE or SUBSOLVER_INFEASIBLE, indicating whether the returned solutionPoint (!!) is feasible or not

Reimplemented in maingo::ubp::UbpCplex, maingo::ubp::UbpClp, maingo::ubp::UbpKnitro, maingo::ubp::UbpIpopt, and maingo::ubp::UbpNLopt.

◆ check_feasibility()

SUBSOLVER_RETCODE UpperBoundingSolver::check_feasibility ( const std::vector< double > &  currentPoint,
double &  objectiveValue 
) const

Function for checking feasibility of a point.

Parameters
[in]currentPointis the point to be checked
[in]objectiveValueis the objective value of the current point

◆ multistart()

SUBSOLVER_RETCODE UpperBoundingSolver::multistart ( babBase::BabNode const &  currentNode,
double &  objectiveValue,
std::vector< double > &  solutionPoint,
std::vector< SUBSOLVER_RETCODE > &  feasible,
std::vector< double > &  optimalObjectives,
bool &  initialPointFeasible 
)

Multistart heuristic for automatically solving the UBP from multiple starting points.

Parameters
[in]currentNodeis the B&B node for which the lower bounding problem should be solved
[out]objectiveValueis the objective value obtained for the solution point of the upper bounding problem (need not be a local optimum!)
[in,out]solutionPointis the point at which objectiveValue was achieved (can in principle be any point within the current node!); it is also used for communicating the user-defined initial point (if any)
[out]feasibleis a vector containing information about which multistart runs were successful in finding a feasible point (only used if corresponding setting PRE_printEveryLocalSerach is on)
[out]optimalObjectivesis a vector containing the optimal objectives found (either all of them if PRE_printEveryLocalSerach is enabled, or only the ones with significant improvements)
[out]initialPointFeasiblestates whether or not the user-specified point was found to be feasible
Returns
Return code, either RETCODE_FEASIBLE or RETCODE_INFEASIBLE, indicating whether a feasible solution has been found

◆ operator=()

UpperBoundingSolver& maingo::ubp::UpperBoundingSolver::operator= ( const UpperBoundingSolver )
private

default assignment operator declared private to prevent use

◆ solve()

SUBSOLVER_RETCODE UpperBoundingSolver::solve ( babBase::BabNode const &  currentNode,
double &  objectiveValue,
std::vector< double > &  solutionPoint 
)
virtual

Function called by B&B solver for solving the upper bounding problem on the current node. This calls the internal (protected) function solve_nlp that needs to be re-implemented by the derived classes.

Parameters
[in]currentNodeis the B&B node for which the lower bounding problem should be solved
[out]objectiveValueis the objective value obtained for the solution point of the upper bounding problem (need not be a local optimum!)
[in,out]solutionPointis the point at which objectiveValue was achieved (can in principle be any point within the current node!); it is also used for communicating the initial point (usually the LBP solution point)
Returns
Return code, either SUBSOLVER_FEASIBLE or SUBSOLVER_INFEASIBLE, indicating whether the returned solutionPoint (!!) is feasible or not

Member Data Documentation

◆ _constraintProperties

std::vector<Constraint>* maingo::ubp::UpperBoundingSolver::_constraintProperties
protected

pointer to constraint properties determined by MAiNGO

◆ _DAGobj

std::shared_ptr<DagObj> maingo::ubp::UpperBoundingSolver::_DAGobj
protected

pointer to object containing DAG for upper bounding

◆ _intendedUse

UBS_USE maingo::ubp::UpperBoundingSolver::_intendedUse
protected

object storing information about the intended use of this UpperBoundingSolver object

◆ _logger

Logger* maingo::ubp::UpperBoundingSolver::_logger
protected

pointer to MAiNGO logger

◆ _maingoSettings

Settings* maingo::ubp::UpperBoundingSolver::_maingoSettings
protected

pointer to object holding MAiNGO settings

◆ _neq

unsigned maingo::ubp::UpperBoundingSolver::_neq
protected

number of equalities

◆ _nineq

unsigned maingo::ubp::UpperBoundingSolver::_nineq
protected

number of inequalities

◆ _nineqSquash

unsigned maingo::ubp::UpperBoundingSolver::_nineqSquash
protected

number of squash inequalities

◆ _nvar

unsigned maingo::ubp::UpperBoundingSolver::_nvar
protected

number of variables

◆ _originalLowerBounds

std::vector<double> maingo::ubp::UpperBoundingSolver::_originalLowerBounds
protected

vector of upper bounds for variables as specified in the problem definition

◆ _originalUpperBounds

std::vector<double> maingo::ubp::UpperBoundingSolver::_originalUpperBounds
protected

vector of upper bounds for variables as specified in the problem definition

◆ _originalVariables

std::vector<babBase::OptimizationVariable> maingo::ubp::UpperBoundingSolver::_originalVariables
protected

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

◆ _structure

UbpStructure maingo::ubp::UpperBoundingSolver::_structure
protected

struct storing information on the problem structure


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