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  **********************************************************************************/
11 
12 #pragma once
13 
14 #include "MAiNGOdebug.h"
15 #include "constraint.h"
16 #include "intervalLibrary.h"
17 #include "lbpDagObj.h"
18 #include "logger.h"
19 #include "returnCodes.h"
20 #include "settings.h"
21 
22 #include "babNode.h"
23 #include "babUtils.h"
24 
25 #include <list>
26 #include <memory>
27 #include <string>
28 #include <vector>
29 
30 
31 namespace maingo {
32 
33 
34 namespace lbp {
35 
36 
41 enum OBBT {
42  OBBT_FEAS = 0,
44 };
45 
46 
52 struct LbpDualInfo {
53  std::vector<double> multipliers;
54  double lpLowerBound;
55 };
56 
57 
66  public:
83  LowerBoundingSolver(mc::FFGraph &DAG, const std::vector<mc::FFVar> &DAGvars, const std::vector<mc::FFVar> &DAGfunctions,
84  const std::vector<babBase::OptimizationVariable> &variables, const unsigned nineqIn, const unsigned neqIn,
85  const unsigned nineqRelaxationOnlyIn, const unsigned neqRelaxationOnlyIn, const unsigned nineqSquashIn,
86  std::shared_ptr<Settings> settingsIn, std::shared_ptr<Logger> loggerIn, std::shared_ptr<std::vector<Constraint>> constraintPropertiesIn);
87 
91  virtual ~LowerBoundingSolver(){};
92 
102  SUBSOLVER_RETCODE solve_LBP(const babBase::BabNode &currentNode, double &lowerBound, std::vector<double> &solutionPoint, LbpDualInfo &dualInfo);
103 
112  TIGHTENING_RETCODE solve_OBBT(babBase::BabNode &currentNode, const double currentUBD, const OBBT reductionType);
113 
123  virtual TIGHTENING_RETCODE do_constraint_propagation(babBase::BabNode &currentNode, const double currentUBD, const unsigned pass = 3);
124 
134  TIGHTENING_RETCODE do_dbbt_and_probing(babBase::BabNode &currentNode, const std::vector<double> &lbpSolutionPoint, const LbpDualInfo &dualInfo, const double currentUBD);
135 
141  void update_incumbent_LBP(const std::vector<double> &incumbentBAB);
142 
146  virtual void activate_more_scaling();
147 
153  void preprocessor_check_options(const babBase::BabNode &rootNode);
154 
155  protected:
163  virtual LINEARIZATION_RETCODE _update_LP(const babBase::BabNode &currentNode);
164 
171  virtual void _set_variable_bounds(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
172 
183  virtual void _update_LP_obj(const MC &resultRelaxation, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
184  const std::vector<double> &upperVarBounds, unsigned const &iLin, unsigned const &iObj);
185 
196  virtual void _update_LP_ineq(const MC &resultRelaxation, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
197  const std::vector<double> &upperVarBounds, unsigned const &iLin, unsigned const &iIneq);
198 
210  virtual void _update_LP_eq(const MC &resultRelaxationCv, const MC &resultRelaxationCc, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
211  const std::vector<double> &upperVarBounds, unsigned const &iLin, unsigned const &iEq);
212 
223  virtual void _update_LP_ineqRelaxationOnly(const MC &resultRelaxation, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
224  const std::vector<double> &upperVarBounds, unsigned const &iLin, unsigned const &iIneqRelaxationOnly);
225 
237  virtual void _update_LP_eqRelaxationOnly(const MC &resultRelaxationCv, const MC &resultRelaxationCc, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
238  const std::vector<double> &upperVarBounds, unsigned const &iLin, unsigned const &iEqRelaxationOnly);
239 
240 
252  virtual void _update_LP_ineq_squash(const MC &resultRelaxation, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
253  const std::vector<double> &upperVarBounds, unsigned const &iLin, unsigned const &iIneqSquash);
263  void _update_whole_LP_at_linpoint(const std::vector<MC> &resultRelaxation, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds,
264  const std::vector<double> &upperVarBounds, unsigned const &iLin);
265 
275  virtual void _update_LP_obj(const vMC &resultRelaxationVMC, const std::vector<std::vector<double>> &linearizationPoint, const std::vector<double> &lowerVarBounds,
276  const std::vector<double> &upperVarBounds, unsigned const &iObj);
277 
287  virtual void _update_LP_ineq(const vMC &resultRelaxationVMC, const std::vector<std::vector<double>> &linearizationPoint, const std::vector<double> &lowerVarBounds,
288  const std::vector<double> &upperVarBounds, unsigned const &iIneq);
289 
300  virtual void _update_LP_eq(const vMC &resultRelaxationCvVMC, const vMC &resultRelaxationCcVMC, const std::vector<std::vector<double>> &linearizationPoint, const std::vector<double> &lowerVarBounds,
301  const std::vector<double> &upperVarBounds, unsigned const &iEq);
302 
312  virtual void _update_LP_ineqRelaxationOnly(const vMC &resultRelaxationVMC, const std::vector<std::vector<double>> &linearizationPoint, const std::vector<double> &lowerVarBounds,
313  const std::vector<double> &upperVarBounds, unsigned const &iIneqRelaxationOnly);
314 
325  virtual void _update_LP_eqRelaxationOnly(const vMC &resultRelaxationCvVMC, const vMC &resultRelaxationCcVMC, const std::vector<std::vector<double>> &linearizationPoint, const std::vector<double> &lowerVarBounds,
326  const std::vector<double> &upperVarBounds, unsigned const &iEqRelaxationOnly);
327 
328 
339  virtual void _update_LP_ineq_squash(const vMC &resultRelaxationVMC, const std::vector<std::vector<double>> &linearizationPoint, const std::vector<double> &lowerVarBounds,
340  const std::vector<double> &upperVarBounds, unsigned const &iIneqSquash);
341 
350  void _update_whole_LP_at_vector_linpoints(const std::vector<vMC> &resultRelaxationVMC, const std::vector<std::vector<double>> &linearizationPoints, const std::vector<double> &lowerVarBounds,
351  const std::vector<double> &upperVarBounds);
352 
362  double _equilibrate_and_relax(std::vector<double> &coefficients, double &rhs, const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
363 
370  virtual void _solve_LP(const babBase::BabNode &currentNode);
371 
377  virtual LP_RETCODE _get_LP_status();
378 
385  virtual void _get_solution_point(std::vector<double> &solution, double &etaVal);
386 
392  double _get_objective_value();
393 
399  virtual double _get_objective_value_solver();
400 
406  virtual void _get_multipliers(std::vector<double> &multipliers);
407 
412 
420  virtual void _modify_LP_for_feasopt_OBBT(const double &currentUBD, std::list<unsigned> &toTreatMax, std::list<unsigned> &toTreatMin);
421 
428  virtual void _set_optimization_sense_of_variable(const unsigned &iVar, const int &optimizationSense);
429 
434 
441  virtual void _fix_variable(const unsigned &iVar, const bool fixToLowerBound);
442 
448  virtual bool _check_if_LP_really_infeasible();
449 
460  void _linearize_functions_at_linpoint(std::vector<MC> &resultRelaxation, const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds,
461  mc::FFSubgraph &subgraph, std::vector<mc::FFVar> &functions);
462 
474  void _linearize_functions_at_preset_vector_linpoint(std::vector<vMC> &resultRelaxationVMC, const std::vector<std::vector<double>> &linearizationPoints,
475  const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds,
476  mc::FFSubgraph &subgraph, std::vector<mc::FFVar> &functions);
477 
478 
486  LINEARIZATION_RETCODE _linearize_model_at_midpoint(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
487 
497  LINEARIZATION_RETCODE _linearize_model_at_incumbent(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds, const bool holdsIncumbent);
498 
512 
521  LINEARIZATION_RETCODE _linearization_points_Simplex(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
522 
530  LINEARIZATION_RETCODE _linearization_points_random(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
531 
545 
556  void _update_LP_nonlinear_linear(const std::vector<vMC> &resultRelaxationVMCNonlinear, const std::vector<MC> &resultRelaxationLinear, const std::vector<double> &linearizationPoint,
557  const std::vector<std::vector<double>> &scaledPoints, const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
558 
568  void _update_LP_nonlinear(const std::vector<MC> &resultRelaxationNonlinear, const std::vector<double> &linearizationPoint,
569  const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds, const unsigned iLin);
570 
578  void _reset_LP(const std::vector<double> &linearizationPoint, const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
579 
588  void _compute_and_rotate_simplex(const unsigned int dim, const double angleIn, const double sphereRadius, std::vector<std::vector<double>> &simplexPoints);
589 
593  void _choose_good_lin_points(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds, bool firstTime = true);
594 
602  virtual SUBSOLVER_RETCODE _fallback_to_intervals(double &newLBD);
603 
607  virtual void _turn_off_specific_options();
608 
615  void _truncate_value(double &value, const double tolerance) { value = std::trunc(value * (tolerance)) / (tolerance); }
616 
617 #ifdef LP__OPTIMALITY_CHECK
618 
624  virtual SUBSOLVER_RETCODE _check_infeasibility(const babBase::BabNode &currentNode);
625 
632  virtual SUBSOLVER_RETCODE _check_feasibility(const std::vector<double> &solution);
633 
644  virtual SUBSOLVER_RETCODE _check_optimality(const babBase::BabNode &currentNode, const double newLBD, const std::vector<double> &solution,
645  const double etaVal, const std::vector<double> &multipliers);
646 
653  void _print_LP(const std::vector<double> &lowerVarBounds, const std::vector<double> &upperVarBounds);
654 
655 #endif
656 
657 #ifdef LP__WRITE_CHECK_FILES
658 
663  virtual void _write_LP_to_file(std::string &fileName);
664 #endif
665 
670  std::vector<std::vector<std::vector<double>>> _matrixObj;
671  std::vector<std::vector<std::vector<double>>> _matrixIneq;
672  std::vector<std::vector<std::vector<double>>> _matrixEq1;
673  std::vector<std::vector<std::vector<double>>> _matrixEq2;
674  std::vector<std::vector<std::vector<double>>> _matrixIneqRelaxationOnly;
675  std::vector<std::vector<std::vector<double>>> _matrixEqRelaxationOnly1;
676  std::vector<std::vector<std::vector<double>>> _matrixEqRelaxationOnly2;
677  std::vector<std::vector<std::vector<double>>> _matrixIneqSquash;
678  std::vector<std::vector<double>> _rhsObj;
679  std::vector<std::vector<double>> _rhsIneq;
680  std::vector<std::vector<double>> _rhsEq1;
681  std::vector<std::vector<double>> _rhsEq2;
682  std::vector<std::vector<double>> _rhsIneqRelaxationOnly;
683  std::vector<std::vector<double>> _rhsEqRelaxationOnly1;
684  std::vector<std::vector<double>> _rhsEqRelaxationOnly2;
685  std::vector<std::vector<double>> _rhsIneqSquash;
688  std::vector<double> _incumbent;
689  std::vector<std::vector<double>> _objectiveScalingFactors;
695  std::shared_ptr<DagObj> _DAGobj;
696  std::shared_ptr<Settings> _maingoSettings;
697  std::shared_ptr<Logger> _logger;
698  std::shared_ptr<std::vector<Constraint>> _constraintProperties;
705  std::vector<unsigned> _nLinObj;
706  std::vector<unsigned> _nLinIneq;
707  std::vector<unsigned> _nLinEq;
708  std::vector<unsigned> _nLinIneqRelaxationOnly;
709  std::vector<unsigned> _nLinEqRelaxationOnly;
710  std::vector<unsigned> _nLinIneqSquash;
712  const unsigned _nvar;
713  const unsigned _nineq;
714  const unsigned _neq;
715  const unsigned _nineqRelaxationOnly;
716  const unsigned _neqRelaxationOnly;
717  const unsigned _nineqSquash;
719  std::vector<babBase::OptimizationVariable> _originalVariables;
721  std::vector<double> _solutionPoint;
722  std::vector<double> _multipliers;
723  std::vector<double> _lowerVarBounds;
724  std::vector<double> _upperVarBounds;
727  bool _differentNumberOfLins = false;
731  private:
742  const unsigned int iVar, const bool fixToLowerBound);
743 
749  void _set_number_of_linpoints(const unsigned int LBP_linPoints);
750 
751 
752  // Prevent use of default copy constructor and copy assignment operator by declaring them private:
755 };
756 
773 std::shared_ptr<LowerBoundingSolver> make_lbp_solver(mc::FFGraph &DAG, const std::vector<mc::FFVar> &DAGvars, const std::vector<mc::FFVar> &DAGfunctions,
774  const std::vector<babBase::OptimizationVariable> &variables, const unsigned nineqIn, const unsigned neqIn,
775  const unsigned nineqRelaxationOnlyIn, const unsigned neqRelaxationOnlyIn, const unsigned nineqSquashIn,
776  std::shared_ptr<Settings> settingsIn, std::shared_ptr<Logger> loggerIn, std::shared_ptr<std::vector<Constraint>> constraintPropertiesIn);
777 
778 
779 } // end namespace lbp
780 
781 
782 } // end namespace maingo
Wrapper for handling the lower bounding problems as well as optimization-based bounds tightening (OBB...
Definition: lbp.h:65
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:2078
std::vector< unsigned > _nLinIneq
Definition: lbp.h:706
std::vector< std::vector< double > > _rhsEqRelaxationOnly2
Definition: lbp.h:684
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:1575
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:1283
std::vector< babBase::OptimizationVariable > _originalVariables
Definition: lbp.h:719
Definition: lbp.h:42
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:25
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:651
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: lbp.h:41
std::vector< unsigned > _nLinEqRelaxationOnly
Definition: lbp.h:709
bool _onlyBoxConstraints
Definition: lbp.h:718
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:1971
virtual void _solve_LP(const babBase::BabNode &currentNode)
Virtual function for solving the currently constructed linear program. This function also internally ...
Definition: lbp.cpp:1840
std::vector< std::vector< double > > _rhsEqRelaxationOnly1
Definition: lbp.h:683
const unsigned _nvar
Definition: lbp.h:712
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:228
Class representing a node in the Branch-and-Bound tree.
Definition: babNode.h:35
std::vector< unsigned > _nLinIneqSquash
Definition: lbp.h:710
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:1559
double _computationTol
Definition: lbp.h:726
const unsigned _neqRelaxationOnly
Definition: lbp.h:716
double _objectiveValue
Definition: lbp.h:720
LINEARIZATION_RETCODE _linearization_points_Kelley(const babBase::BabNode &currentNode)
This function adds linearizations to LP with the use of an adapted version of Kelley&#39;s algorithm...
Definition: lbpLinearizationStrats.cpp:155
virtual double _get_objective_value_solver()
Virtual function returning the objective value of the lastly solved LP for a specific solver...
Definition: lbp.cpp:1935
mc::vMcCormick< I > vMC
A type definition for a vector McCormick variable.
Definition: intervalLibrary.h:41
std::vector< std::vector< std::vector< double > > > _matrixObj
Definition: lbp.h:670
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:1525
virtual LP_RETCODE _get_LP_status()
Virtual function returning the current status of the last solved linear program.
Definition: lbp.cpp:1906
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, std::shared_ptr< Settings > settingsIn, std::shared_ptr< Logger > loggerIn, std::shared_ptr< std::vector< Constraint >> constraintPropertiesIn)
Constructor, stores information on the problem and constructs an own copy of the directed acyclic gra...
Definition: lbp.cpp:26
virtual void _deactivate_objective_function_for_OBBT()
Virtual function deactivating all objective rows in the LP for feasibility OBBT.
Definition: lbp.cpp:1962
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:1980
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:2014
std::vector< unsigned > _nLinEq
Definition: lbp.h:707
double lpLowerBound
Definition: lbp.h:54
LowerBoundingSolver & operator=(const LowerBoundingSolver &)
std::vector< std::vector< double > > _rhsEq2
Definition: lbp.h:681
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:1451
LINEARIZATION_RETCODE
Enum for representing the return codes returned by the different linearization techniques.
Definition: returnCodes.h:59
std::vector< unsigned > _nLinObj
Definition: lbp.h:705
std::vector< double > _incumbent
Definition: lbp.h:688
std::vector< std::vector< std::vector< double > > > _matrixEqRelaxationOnly2
Definition: lbp.h:676
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:1153
std::vector< std::vector< double > > _rhsEq1
Definition: lbp.h:680
virtual void _get_multipliers(std::vector< double > &multipliers)
Virtual function for setting the multipliers of the lastly solved LP.
Definition: lbp.cpp:1944
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:359
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:1302
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:1607
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:1623
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:63
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, std::shared_ptr< Settings > settingsIn, std::shared_ptr< Logger > loggerIn, std::shared_ptr< std::vector< Constraint >> constraintPropertiesIn)
Factory function for initializing different lower bounding solver wrappers.
Definition: lbpFactory.cpp:30
virtual void _restore_LP_coefficients_after_OBBT()
Virtual function for restoring proper coefficients and options in the LP after OBBT.
Definition: lbp.cpp:1953
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&#39;s algorithm...
Definition: lbpLinearizationStrats.cpp:433
const unsigned _nineqSquash
Definition: lbp.h:717
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:394
std::shared_ptr< DagObj > _DAGobj
Definition: lbp.h:695
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:111
std::shared_ptr< Logger > _logger
Definition: lbp.h:697
std::vector< double > _lowerVarBounds
Definition: lbp.h:723
std::vector< double > multipliers
Definition: lbp.h:53
std::vector< unsigned > _nLinIneqRelaxationOnly
Definition: lbp.h:708
double _get_objective_value()
Virtual function returning the objective value of the lastly solved LP.
Definition: lbp.cpp:1925
virtual ~LowerBoundingSolver()
Virtual destructor, only needed to make sure the correct destructor of the derived classes is called...
Definition: lbp.h:91
std::vector< std::vector< double > > _rhsIneqSquash
Definition: lbp.h:685
TIGHTENING_RETCODE
Enum for representing the return codes returned by LowerBoundingSolvers when solving OBBT or constrai...
Definition: returnCodes.h:45
virtual void _fix_variable(const unsigned &iVar, const bool fixToLowerBound)
Virtual function for fixing a variable to one of its bounds.
Definition: lbp.cpp:1989
SUBSOLVER_RETCODE
Enum for representing the return codes returned by the different sub-solvers (UpperBoundingSolver, LowerBoundingSolver).
Definition: returnCodes.h:36
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:1591
bool _differentNumberOfLins
Definition: lbp.h:727
namespace holding all essentials of MAiNGO
Definition: aleModel.h:25
unsigned _maxnParticipatingVariables
Definition: lbp.h:711
mc::McCormick< I > MC
A type definition for a McCormick variable.
Definition: intervalLibrary.h:34
std::vector< std::vector< std::vector< double > > > _matrixIneq
Definition: lbp.h:671
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:1639
const unsigned _neq
Definition: lbp.h:714
std::vector< std::vector< std::vector< double > > > _matrixEq1
Definition: lbp.h:672
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:1802
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:679
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:987
std::vector< std::vector< std::vector< double > > > _matrixIneqSquash
Definition: lbp.h:677
std::shared_ptr< Settings > _maingoSettings
Definition: lbp.h:696
std::vector< std::vector< std::vector< double > > > _matrixEq2
Definition: lbp.h:673
std::vector< double > _multipliers
Definition: lbp.h:722
std::shared_ptr< std::vector< Constraint > > _constraintProperties
Definition: lbp.h:698
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:386
std::vector< std::vector< double > > _objectiveScalingFactors
Definition: lbp.h:689
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:546
std::vector< double > _solutionPoint
Definition: lbp.h:721
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:2104
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:1655
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.
Definition: lbp.cpp:2003
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:615
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.
Definition: lbpLinearizationStrats.cpp:229
std::vector< std::vector< std::vector< double > > > _matrixEqRelaxationOnly1
Definition: lbp.h:675
const unsigned _nineq
Definition: lbp.h:713
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:1513
std::vector< std::vector< std::vector< double > > > _matrixIneqRelaxationOnly
Definition: lbp.h:674
std::vector< double > _upperVarBounds
Definition: lbp.h:724
LP_RETCODE
Enum for representing the return codes returned when a linear program is solved.
Definition: returnCodes.h:69
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:277
Definition: lbp.h:43
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:44
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:598
virtual void activate_more_scaling()
Function called by the B&B solver to heuristically activate more scaling in the LBS.
Definition: lbp.cpp:1292
std::vector< std::vector< double > > _rhsObj
Definition: lbp.h:678
Container for information from the LBP that is needed in DBBT and probing, used for communicating the...
Definition: lbp.h:52
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:1915
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:725
std::vector< std::vector< double > > _rhsIneqRelaxationOnly
Definition: lbp.h:682
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:518
const unsigned _nineqRelaxationOnly
Definition: lbp.h:715