MAiNGO
lbp.h
Go to the documentation of this file.
1 /**********************************************************************************
2  * Copyright (c) 2019 Process Systems Engineering (AVT.SVT), RWTH Aachen University
3  *
4  * This program and the accompanying materials are made available under the
5  * terms of the Eclipse Public License 2.0 which is available at
6  * http://www.eclipse.org/legal/epl-2.0.
7  *
8  * SPDX-License-Identifier: EPL-2.0
9  *
10  * @file lbp.h
11  *
12  * @brief File containing declaration of LowerBoundingSolver class used for
13  * constructing and solving the lower bounding problems and OBBT.
14  *
15  **********************************************************************************/
16 
17 #pragma once
18 
19 #include "MAiNGOdebug.h"
20 #include "constraint.h"
21 #include "intervalLibrary.h"
22 #include "lbpDagObj.h"
23 #include "logger.h"
24 #include "returnCodes.h"
25 #include "settings.h"
26 
27 #include "babNode.h"
28 #include "babUtils.h"
29 
30 #include <list>
31 #include <memory>
32 #include <string>
33 #include <vector>
34 
35 
36 namespace maingo {
37 
38 
39 namespace lbp {
40 
41 
47 struct LbpDualInfo {
48  std::vector<double> multipliers;
49  double lpLowerBound;
50 };
51 
52 
61  public:
78  LowerBoundingSolver(mc::FFGraph &DAG, const std::vector<mc::FFVar> &DAGvars, const std::vector<mc::FFVar> &DAGfunctions,
79  const std::vector<babBase::OptimizationVariable> &variables, const unsigned nineqIn, const unsigned neqIn,
80  const unsigned nineqRelaxationOnlyIn, const unsigned neqRelaxationOnlyIn, const unsigned nineqSquashIn,
81  Settings *settingsIn, Logger *loggerIn, std::vector<Constraint> *constraintPropertiesIn);
82 
86  virtual ~LowerBoundingSolver(){};
87 
97  SUBSOLVER_RETCODE solve_LBP(const babBase::BabNode &currentNode, double &lowerBound, std::vector<double> &solutionPoint, LbpDualInfo &dualInfo);
98 
107  TIGHTENING_RETCODE solve_OBBT(babBase::BabNode &currentNode, const double currentUBD, const OBBT reductionType);
108 
118  virtual TIGHTENING_RETCODE do_constraint_propagation(babBase::BabNode &currentNode, const double currentUBD, const unsigned pass = 3);
119 
129  TIGHTENING_RETCODE do_dbbt_and_probing(babBase::BabNode &currentNode, const std::vector<double> &lbpSolutionPoint, const LbpDualInfo &dualInfo, const double currentUBD);
130 
136  void update_incumbent_LBP(const std::vector<double> &incumbentBAB);
137 
141  virtual void activate_more_scaling();
142 
148  void preprocessor_check_options(const babBase::BabNode &rootNode);
149 
150  protected:
158  virtual LINEARIZATION_RETCODE _update_LP(const babBase::BabNode &currentNode);
159 
166  virtual void _set_variable_bounds(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
167 
178  virtual void _update_LP_obj(const MC &resultRelaxation, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
179  const std::vector<double> &upperVarBounds, unsigned const &iLin, unsigned const &iObj);
180 
191  virtual void _update_LP_ineq(const MC &resultRelaxation, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
192  const std::vector<double> &upperVarBounds, unsigned const &iLin, unsigned const &iIneq);
193 
205  virtual void _update_LP_eq(const MC &resultRelaxationCv, const MC &resultRelaxationCc, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
206  const std::vector<double> &upperVarBounds, unsigned const &iLin, unsigned const &iEq);
207 
218  virtual void _update_LP_ineqRelaxationOnly(const MC &resultRelaxation, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
219  const std::vector<double> &upperVarBounds, unsigned const &iLin, unsigned const &iIneqRelaxationOnly);
220 
232  virtual void _update_LP_eqRelaxationOnly(const MC &resultRelaxationCv, const MC &resultRelaxationCc, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
233  const std::vector<double> &upperVarBounds, unsigned const &iLin, unsigned const &iEqRelaxationOnly);
234 
235 
247  virtual void _update_LP_ineq_squash(const MC &resultRelaxation, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
248  const std::vector<double> &upperVarBounds, unsigned const &iLin, unsigned const &iIneqSquash);
258  void _update_whole_LP_at_linpoint(const std::vector<MC> &resultRelaxation, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
259  const std::vector<double> &upperVarBounds, unsigned const &iLin);
260 
270  virtual void _update_LP_obj(const vMC &resultRelaxationVMC, const std::vector<std::vector<double>> &linearizationPoint, const std::vector<double> &lowerVarBounds,
271  const std::vector<double> &upperVarBounds, unsigned const &iObj);
272 
282  virtual void _update_LP_ineq(const vMC &resultRelaxationVMC, const std::vector<std::vector<double>> &linearizationPoint, const std::vector<double> &lowerVarBounds,
283  const std::vector<double> &upperVarBounds, unsigned const &iIneq);
284 
295  virtual void _update_LP_eq(const vMC &resultRelaxationCvVMC, const vMC &resultRelaxationCcVMC, const std::vector<std::vector<double>> &linearizationPoint, const std::vector<double> &lowerVarBounds,
296  const std::vector<double> &upperVarBounds, unsigned const &iEq);
297 
307  virtual void _update_LP_ineqRelaxationOnly(const vMC &resultRelaxationVMC, const std::vector<std::vector<double>> &linearizationPoint, const std::vector<double> &lowerVarBounds,
308  const std::vector<double> &upperVarBounds, unsigned const &iIneqRelaxationOnly);
309 
320  virtual void _update_LP_eqRelaxationOnly(const vMC &resultRelaxationCvVMC, const vMC &resultRelaxationCcVMC, const std::vector<std::vector<double>> &linearizationPoint, const std::vector<double> &lowerVarBounds,
321  const std::vector<double> &upperVarBounds, unsigned const &iEqRelaxationOnly);
322 
323 
334  virtual void _update_LP_ineq_squash(const vMC &resultRelaxationVMC, const std::vector<std::vector<double>> &linearizationPoint, const std::vector<double> &lowerVarBounds,
335  const std::vector<double> &upperVarBounds, unsigned const &iIneqSquash);
336 
345  void _update_whole_LP_at_vector_linpoints(const std::vector<vMC> &resultRelaxationVMC, const std::vector<std::vector<double>> &linearizationPoints, const std::vector<double> &lowerVarBounds,
346  const std::vector<double> &upperVarBounds);
347 
357  double _equilibrate_and_relax(std::vector<double> &coefficients, double &rhs, const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
358 
365  virtual void _solve_LP(const babBase::BabNode &currentNode);
366 
372  virtual LP_RETCODE _get_LP_status();
373 
380  virtual void _get_solution_point(std::vector<double> &solution, double &etaVal);
381 
387  double _get_objective_value();
388 
394  virtual double _get_objective_value_solver();
395 
401  virtual void _get_multipliers(std::vector<double> &multipliers);
402 
407 
415  virtual void _modify_LP_for_feasopt_OBBT(const double &currentUBD, std::list<unsigned> &toTreatMax, std::list<unsigned> &toTreatMin);
416 
423  virtual void _set_optimization_sense_of_variable(const unsigned &iVar, const int &optimizationSense);
424 
429 
436  virtual void _fix_variable(const unsigned &iVar, const bool fixToLowerBound);
437 
443  virtual bool _check_if_LP_really_infeasible();
444 
455  void _linearize_functions_at_linpoint(std::vector<MC> &resultRelaxation, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds,
456  mc::FFSubgraph &subgraph, std::vector<mc::FFVar> &functions);
457 
469  void _linearize_functions_at_preset_vector_linpoint(std::vector<vMC> &resultRelaxationVMC, const std::vector<std::vector<double>> &linearizationPoints,
470  const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds,
471  mc::FFSubgraph &subgraph, std::vector<mc::FFVar> &functions);
472 
473 
481  LINEARIZATION_RETCODE _linearize_model_at_midpoint(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
482 
492  LINEARIZATION_RETCODE _linearize_model_at_incumbent(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds, const bool holdsIncumbent);
493 
507 
516  LINEARIZATION_RETCODE _linearization_points_Simplex(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
517 
525  LINEARIZATION_RETCODE _linearization_points_random(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
526 
540 
551  void _update_LP_nonlinear_linear(const std::vector<vMC> &resultRelaxationVMCNonlinear, const std::vector<MC> &resultRelaxationLinear, const std::vector<double> &linearizationPoint,
552  const std::vector<std::vector<double>> &scaledPoints, const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
553 
563  void _update_LP_nonlinear(const std::vector<MC> &resultRelaxationNonlinear, const std::vector<double> &linearizationPoint,
564  const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds, const unsigned iLin);
565 
573  void _reset_LP(const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
574 
583  void _compute_and_rotate_simplex(const unsigned int dim, const double angleIn, const double sphereRadius, std::vector<std::vector<double>> &simplexPoints);
584 
588  void _choose_good_lin_points(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds, bool firstTime = true);
589 
597  virtual SUBSOLVER_RETCODE _fallback_to_intervals(double &newLBD);
598 
602  virtual void _turn_off_specific_options();
603 
610  void _truncate_value(double &value, const double tolerance) { value = std::trunc(value * (tolerance)) / (tolerance); }
611 
612 #ifdef LP__OPTIMALITY_CHECK
613 
619  virtual SUBSOLVER_RETCODE _check_infeasibility(const babBase::BabNode &currentNode);
620 
627  virtual SUBSOLVER_RETCODE _check_feasibility(const std::vector<double> &solution);
628 
639  virtual SUBSOLVER_RETCODE _check_optimality(const babBase::BabNode &currentNode, const double newLBD, const std::vector<double> &solution,
640  const double etaVal, const std::vector<double> &multipliers);
641 
648  void _print_LP(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
649 
650 #endif
651 
652 #ifdef LP__WRITE_CHECK_FILES
653 
658  virtual void _write_LP_to_file(std::string &fileName);
659 #endif
660 
665  std::vector<std::vector<std::vector<double>>> _matrixObj;
666  std::vector<std::vector<std::vector<double>>> _matrixIneq;
667  std::vector<std::vector<std::vector<double>>> _matrixEq1;
668  std::vector<std::vector<std::vector<double>>> _matrixEq2;
669  std::vector<std::vector<std::vector<double>>> _matrixIneqRelaxationOnly;
670  std::vector<std::vector<std::vector<double>>> _matrixEqRelaxationOnly1;
671  std::vector<std::vector<std::vector<double>>> _matrixEqRelaxationOnly2;
672  std::vector<std::vector<std::vector<double>>> _matrixIneqSquash;
673  std::vector<std::vector<double>> _rhsObj;
674  std::vector<std::vector<double>> _rhsIneq;
675  std::vector<std::vector<double>> _rhsEq1;
676  std::vector<std::vector<double>> _rhsEq2;
677  std::vector<std::vector<double>> _rhsIneqRelaxationOnly;
678  std::vector<std::vector<double>> _rhsEqRelaxationOnly1;
679  std::vector<std::vector<double>> _rhsEqRelaxationOnly2;
680  std::vector<std::vector<double>> _rhsIneqSquash;
683  std::vector<double> _incumbent;
684  std::vector<std::vector<double>> _objectiveScalingFactors;
690  std::shared_ptr<DagObj> _DAGobj;
693  std::vector<Constraint> *_constraintProperties;
700  std::vector<unsigned> _nLinObj;
701  std::vector<unsigned> _nLinIneq;
702  std::vector<unsigned> _nLinEq;
703  std::vector<unsigned> _nLinIneqRelaxationOnly;
704  std::vector<unsigned> _nLinEqRelaxationOnly;
705  std::vector<unsigned> _nLinIneqSquash;
707  const unsigned _nvar;
708  const unsigned _nineq;
709  const unsigned _neq;
710  const unsigned _nineqRelaxationOnly;
711  const unsigned _neqRelaxationOnly;
712  const unsigned _nineqSquash;
713  std::vector<babBase::OptimizationVariable> _originalVariables;
715  std::vector<double> _solutionPoint;
716  std::vector<double> _multipliers;
717  std::vector<double> _lowerVarBounds;
718  std::vector<double> _upperVarBounds;
721  bool _differentNumberOfLins = false;
725  private:
736  const unsigned int iVar, const bool fixToLowerBound);
737 
743  void _set_number_of_linpoints(const unsigned int LBP_linPoints);
744 
745 
746  // Prevent use of default copy constructor and copy assignment operator by declaring them private:
749 };
750 
767 std::shared_ptr<LowerBoundingSolver> make_lbp_solver(mc::FFGraph &DAG, const std::vector<mc::FFVar> &DAGvars, const std::vector<mc::FFVar> &DAGfunctions,
768  const std::vector<babBase::OptimizationVariable> &variables, const unsigned nineqIn, const unsigned neqIn,
769  const unsigned nineqRelaxationOnlyIn, const unsigned neqRelaxationOnlyIn, const unsigned nineqSquashIn,
770  Settings *settingsIn, Logger *loggerIn, std::vector<Constraint> *constraintPropertiesIn);
771 
772 
773 } // end namespace lbp
774 
775 
776 } // end namespace maingo
Wrapper for handling the lower bounding problems as well as optimization-based bounds tightening (OBB...
Definition: lbp.h:60
virtual void _turn_off_specific_options()
Virtual function for checking if a specific option has to be turned off for a given lower bounding so...
Definition: lbp.cpp:2103
std::vector< unsigned > _nLinIneq
Definition: lbp.h:701
std::vector< std::vector< double > > _rhsEqRelaxationOnly2
Definition: lbp.h:679
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 in...
Definition: lbp.cpp:1581
Logger * _logger
Definition: lbp.h:692
std::vector< Constraint > * _constraintProperties
Definition: lbp.h:693
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...
Definition: lbp.cpp:1289
std::vector< babBase::OptimizationVariable > _originalVariables
Definition: lbp.h:713
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.
Definition: lbpLinearizationStrats.cpp:31
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 no...
Definition: lbpLinearizationStrats.cpp:695
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.
OBBT
Enum for communicating whether Optimization-Based Bound Tightening should consider only feasibility o...
Definition: settings.h:89
std::vector< unsigned > _nLinEqRelaxationOnly
Definition: lbp.h:704
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.
Definition: lbp.cpp:1977
virtual void _solve_LP(const babBase::BabNode &currentNode)
Virtual function for solving the currently constructed linear program. This function also internally ...
Definition: lbp.cpp:1846
std::vector< std::vector< double > > _rhsEqRelaxationOnly1
Definition: lbp.h:678
const unsigned _nvar
Definition: lbp.h:707
void _set_number_of_linpoints(const unsigned int LBP_linPoints)
Function for setting the correct number of linearization points depending on the LBP_linpoints settin...
Definition: lbp.cpp:233
Class representing a node in the Branch-and-Bound tree.
Definition: babNode.h:35
std::vector< unsigned > _nLinIneqSquash
Definition: lbp.h:705
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 objec...
Definition: lbp.cpp:1565
double _computationTol
Definition: lbp.h:720
const unsigned _neqRelaxationOnly
Definition: lbp.h:711
Struct for storing settings for MAiNGO.
Definition: settings.h:143
double _objectiveValue
Definition: lbp.h:714
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....
Definition: lbpLinearizationStrats.cpp:199
virtual double _get_objective_value_solver()
Virtual function returning the objective value of the lastly solved LP for a specific solver.
Definition: lbp.cpp:1941
mc::vMcCormick< I > vMC
A type definition for a vector McCormick variable.
Definition: intervalLibrary.h:64
std::vector< std::vector< std::vector< double > > > _matrixObj
Definition: lbp.h:665
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.
Definition: lbp.cpp:1531
virtual LP_RETCODE _get_LP_status()
Virtual function returning the current status of the last solved linear program.
Definition: lbp.cpp:1912
virtual void _deactivate_objective_function_for_OBBT()
Virtual function deactivating all objective rows in the LP for feasibility OBBT.
Definition: lbp.cpp:1968
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.
Definition: lbp.cpp:1986
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,...
Definition: lbp.cpp:2020
std::vector< unsigned > _nLinEq
Definition: lbp.h:702
double lpLowerBound
Definition: lbp.h:49
LowerBoundingSolver & operator=(const LowerBoundingSolver &)
std::vector< std::vector< double > > _rhsEq2
Definition: lbp.h:676
virtual LINEARIZATION_RETCODE _update_LP(const babBase::BabNode &currentNode)
Calls the proper function for computing linearization points and modifying the coefficients of the LP...
Definition: lbp.cpp:1457
LINEARIZATION_RETCODE
Enum for representing the return codes returned by the different linearization techniques.
Definition: returnCodes.h:63
std::vector< unsigned > _nLinObj
Definition: lbp.h:700
std::vector< double > _incumbent
Definition: lbp.h:683
This class contains all logging and output information.
Definition: logger.h:100
std::vector< std::vector< std::vector< double > > > _matrixEqRelaxationOnly2
Definition: lbp.h:671
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 solu...
Definition: lbp.cpp:1151
std::vector< std::vector< double > > _rhsEq1
Definition: lbp.h:675
virtual void _get_multipliers(std::vector< double > &multipliers)
Virtual function for setting the multipliers of the lastly solved LP.
Definition: lbp.cpp:1950
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...
Definition: lbpLinearizationStrats.cpp:403
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 curr...
Definition: lbp.cpp:1308
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 lineari...
Definition: lbp.cpp:1613
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 lineariza...
Definition: lbp.cpp:1629
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 poi...
Definition: lbpLinearizationStrats.cpp:69
virtual void _restore_LP_coefficients_after_OBBT()
Virtual function for restoring proper coefficients and options in the LP after OBBT.
Definition: lbp.cpp:1959
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....
Definition: lbpLinearizationStrats.cpp:477
const unsigned _nineqSquash
Definition: lbp.h:712
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 line...
Definition: lbpLinearizationStrats.cpp:438
std::shared_ptr< DagObj > _DAGobj
Definition: lbp.h:690
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 linea...
Definition: lbpLinearizationStrats.cpp:136
std::vector< double > _lowerVarBounds
Definition: lbp.h:717
std::vector< double > multipliers
Definition: lbp.h:48
std::vector< unsigned > _nLinIneqRelaxationOnly
Definition: lbp.h:703
double _get_objective_value()
Virtual function returning the objective value of the lastly solved LP.
Definition: lbp.cpp:1931
virtual ~LowerBoundingSolver()
Virtual destructor, only needed to make sure the correct destructor of the derived classes is called.
Definition: lbp.h:86
std::vector< std::vector< double > > _rhsIneqSquash
Definition: lbp.h:680
TIGHTENING_RETCODE
Enum for representing the return codes returned by LowerBoundingSolvers when solving OBBT or constrai...
Definition: returnCodes.h:49
virtual void _fix_variable(const unsigned &iVar, const bool fixToLowerBound)
Virtual function for fixing a variable to one of its bounds.
Definition: lbp.cpp:1995
SUBSOLVER_RETCODE
Enum for representing the return codes returned by the different sub-solvers (UpperBoundingSolver,...
Definition: returnCodes.h:40
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 equa...
Definition: lbp.cpp:1597
bool _differentNumberOfLins
Definition: lbp.h:721
Settings * _maingoSettings
Definition: lbp.h:691
namespace holding all essentials of MAiNGO
Definition: aleModel.h:31
unsigned _maxnParticipatingVariables
Definition: lbp.h:706
mc::McCormick< I > MC
A type definition for a McCormick variable.
Definition: intervalLibrary.h:57
std::vector< std::vector< std::vector< double > > > _matrixIneq
Definition: lbp.h:666
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.
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...
Definition: lbp.cpp:1645
const unsigned _neq
Definition: lbp.h:709
std::vector< std::vector< std::vector< double > > > _matrixEq1
Definition: lbp.h:667
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.
Definition: lbp.cpp:1808
std::shared_ptr< LowerBoundingSolver > make_lbp_solver(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)
Factory function for initializing different lower bounding solver wrappers.
Definition: lbpFactory.cpp:34
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.
std::vector< std::vector< double > > _rhsIneq
Definition: lbp.h:674
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 overw...
Definition: lbp.cpp:990
std::vector< std::vector< std::vector< double > > > _matrixIneqSquash
Definition: lbp.h:672
std::vector< std::vector< std::vector< double > > > _matrixEq2
Definition: lbp.h:668
std::vector< double > _multipliers
Definition: lbp.h:716
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.
Definition: lbp.cpp:392
std::vector< std::vector< double > > _objectiveScalingFactors
Definition: lbp.h:684
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....
Definition: lbp.cpp:552
std::vector< double > _solutionPoint
Definition: lbp.h:715
virtual SUBSOLVER_RETCODE _fallback_to_intervals(double &newLBD)
Virtual function for checking if a given node is feasible with the use of interval arithmetics....
Definition: lbp.cpp:2129
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.
Definition: lbp.cpp:1661
virtual bool _check_if_LP_really_infeasible()
Virtual function for checking if the current linear program is really infeasible by,...
Definition: lbp.cpp:2009
void _truncate_value(double &value, const double tolerance)
Function used for truncation of value digits which are not guaranteed to be correct.
Definition: lbp.h:610
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....
Definition: lbpLinearizationStrats.cpp:273
std::vector< std::vector< std::vector< double > > > _matrixEqRelaxationOnly1
Definition: lbp.h:670
const unsigned _nineq
Definition: lbp.h:708
virtual void _set_variable_bounds(const std::vector< double > &lowerVarBounds, const std::vector< double > &upperVarBounds)
Virtual function for setting the bounds of variables.
Definition: lbp.cpp:1519
std::vector< std::vector< std::vector< double > > > _matrixIneqRelaxationOnly
Definition: lbp.h:669
std::vector< double > _upperVarBounds
Definition: lbp.h:718
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 gra...
Definition: lbp.cpp:34
LP_RETCODE
Enum for representing the return codes returned when a linear program is solved.
Definition: returnCodes.h:73
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 ...
Definition: lbpLinearizationStrats.cpp:321
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 curren...
Definition: lbpLinearizationStrats.cpp:50
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.
Definition: lbpLinearizationStrats.cpp:642
virtual void activate_more_scaling()
Function called by the B&B solver to heuristically activate more scaling in the LBS.
Definition: lbp.cpp:1298
std::vector< std::vector< double > > _rhsObj
Definition: lbp.h:673
Container for information from the LBP that is needed in DBBT and probing, used for communicating the...
Definition: lbp.h:47
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.
Definition: lbp.cpp:1921
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.
LP_RETCODE _LPstatus
Definition: lbp.h:719
std::vector< std::vector< double > > _rhsIneqRelaxationOnly
Definition: lbp.h:677
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.
Definition: lbpLinearizationStrats.cpp:562
const unsigned _nineqRelaxationOnly
Definition: lbp.h:710