Go to the documentation of this file.
12 #ifndef COUENNE_PROBLEM_HPP
13 #define COUENNE_PROBLEM_HPP
15 #define FM_TRACE_OPTSOL
31 template <
class T>
class SmartPtr;
37 class RegisteredOptions;
39 class OsiTMINLPInterface;
62 void node(
int,
double,
double,
double,
int,
int);
66 inline double get_lb ()
const {
return lb;}
67 inline double get_ub ()
const {
return ub;}
71 inline void bounds(
register double a,
register double b){ lb = a; ub = b;}
74 #define COUENNE_EPS_SYMM 1e-8
129 inline bool operator() (
register const char *a,
register const char *b)
const
130 {
return strcmp (a, b) < 0;}
142 class CouenneCutGenerator;
146 class CouenneConstraint;
147 class CouenneObjective;
149 class CouenneBTPerfIndicator;
150 class CouenneRecordBestSol;
151 class CouenneSdpCuts;
174 enum fixType {UNFIXED, FIXED, CONTINUOUS};
427 inline std::set <exprAux *, compExpr> *&
AuxSet ()
491 void print (std::ostream & = std::cout);
494 int readnl (
const struct ASL *);
498 expression *nl2e (
struct expr *,
const ASL *asl);
608 bool checkNLP (
const double *solution,
double &obj,
bool recompute =
false)
const;
633 std::vector <std::pair <exprVar *, CouNumber> > &lcoeff);
639 std::vector <quadElem> &qcoeff);
669 const std::vector <CouenneObject *> &
Objects ()
const
791 std::map <int, CouNumber> &indices);
834 const int from,
const int upto,
835 const std::vector<int> listInt,
836 const bool origVarOnly,
837 const bool stopAtFirstViol,
838 const double precision,
double &maxViol)
const;
842 const bool stopAtFirstViol,
843 const double precision,
double &maxViol)
const;
847 const bool stopAtFirstViol,
848 const double precision,
double &maxViol)
const;
852 const bool stopAtFirstViol,
853 const double precision,
double &maxViol)
const;
881 const bool careAboutObj,
882 const bool stopAtFirstViol,
884 const double precision)
const;
889 bool recompute_obj =
false,
890 const bool careAboutObj =
false,
891 const bool stopAtFirstViol =
true,
892 const bool checkAll =
false,
893 const double precision = -1)
const;
CouNumber * getCutOffSol() const
Get cutoff solution.
void Compute_Symmetry() const
void print(std::ostream &=std::cout)
Display current representation of problem: objective, linear and nonlinear constraints,...
status of lower/upper bound of a variable, to be checked/modified in bound tightening
const CouNumber feas_tolerance_default
CouNumber getCutOff() const
Get cutoff.
int logAbtLev() const
How often shall we do ABT?
int nUnusedOriginals_
number of unused originals
enum multiSep multilinSep_
Type of Multilinear separation.
Domain domain_
current point and bounds;
std::vector< expression * > commonexprs_
AMPL's common expressions (read from AMPL through structures cexps and cexps1)
int * unusedOriginalsIndices()
return indices of neglected redundant variables
CouNumber & Lb(int i) const
lower bound on
int nUnusedOriginals()
number of unused originals
class for multiplications,
GlobalCutOff * pcutoff_
Pointer to a global cutoff object.
CouenneSdpCuts * sdpCutGen_
Temporary pointer to SDP cut generator.
bool doFBBT() const
shall we do Feasibility Based Bound Tightening?
void initAuxs() const
Initialize auxiliary variables and their bounds from original variables.
CouNumber *& bestSol() const
Best known solution (read from file)
bool fbbtReachedIterLimit() const
true if latest call to FBBT terminated due to iteration limit reached
void getAuxs(CouNumber *) const
Get auxiliary variables from original variables.
multiSep
Type of multilinear separation.
int nObjs() const
Get number of objectives.
CouenneSdpCuts * getSdpCutGen()
Returns pointer to sdp cut generator.
double getMaxCpuTime() const
return maximum CPU time
void auxiliarize(exprVar *, exprVar *=NULL)
Replace all occurrences of original variable with new aux given as argument.
int logAbtLev_
frequency of Aggressive bound tightening
int obbt(const CouenneCutGenerator *cg, const OsiSolverInterface &csi, OsiCuts &cs, const CglTreeInfo &info, Bonmin::BabInfo *babInfo, t_chg_bounds *chg_bds)
Optimality Based Bound Tightening.
void reformulate(CouenneCutGenerator *=NULL)
preprocess problem in order to extract linear relaxations etc.
bool btCore(t_chg_bounds *chg_bds) const
core of the bound tightening procedure
void fillIntegerRank() const
fill freeIntegers_ array
int redCostBT(const OsiSolverInterface *psi, t_chg_bounds *chg_bds) const
procedure to strengthen variable bounds.
int evalOrder(int i) const
get evaluation order index
exprAux * addAuxiliary(expression *)
Add auxiliary variable and associate it with expression given as argument (used in standardization)
std::vector< CouenneConstraint * > constraints_
Constraints.
CouenneRecordBestSol * recBSol
Ipopt::SmartPtr< const Ipopt::Journalist > ConstJnlstPtr
std::vector< int > numberInRank_
numberInRank_ [i] is the number of integer variables in rank i
bool checkBounds(const CouNumber *sol, const bool stopAtFirstViol, const double precision, double &maxViol) const
Check bounds; returns true iff feasible for given precision.
CouenneBTPerfIndicator * OBBTperfIndicator_
Performance indicator for OBBT – to be moved away from CouenneProblem.
CouNumber & ub(register int index)
current upper bound
bool aggressiveBT(Bonmin::OsiTMINLPInterface *nlp, t_chg_bounds *, const CglTreeInfo &info, Bonmin::BabInfo *=NULL) const
aggressive bound tightening.
~CouenneProblem()
Destructor.
int nDefVars() const
Number of def'd variables.
int logObbtLev() const
How often shall we do OBBT?
std::vector< std::set< int > > dependence_
inverse dependence structure: for each variable x give set of auxiliary variables (or better,...
expression * addVariable(bool isint=false, Domain *d=NULL)
Add original variable.
Domain * domain() const
return current point & bounds
int logObbtLev_
frequency of Optimality-based bound tightening
exprAux * linStandardize(bool addAux, CouNumber c0, LinMap &lmap, QuadMap &qmap)
standardization of linear exprOp's
bool created_pcutoff_
flag indicating if this class is creator of global cutoff object
Cut Generator for linear convexifications.
int nOrigIntVars() const
Number of original integers.
std::map< const char *, std::vector< CouenneConstraint * > *, less_than_str > ConstraintClass_
Return particular constraint class.
bool checkAux(const CouNumber *sol, const bool stopAtFirstViol, const double precision, double &maxViol) const
returns true iff value of all auxiliaries are within bounds
bool * commuted_
Variables that have commuted to auxiliary.
std::vector< CouenneObjective * > objectives_
Objectives.
CouenneProblem(ASL *=NULL, Bonmin::BabSetupBase *base=NULL, JnlstPtr jnlst=NULL)
Constructor.
int nOrigCons() const
Get number of original constraints.
void writeLP(const std::string &fname)
Write nonlinear problem to a .lp file.
DepGraph * graph_
Dependence (acyclic) graph: shows dependence of all auxiliary variables on one another and on origina...
bool operator()(register const Node &a, register const Node &b)
bool operator()(register const Node &a, register const Node &b)
JnlstPtr jnlst_
SmartPointer to the Journalist.
void addObjective(expression *, const std::string &="min")
Add (non linear) objective function.
int obbt_iter(OsiSolverInterface *csi, t_chg_bounds *chg_bds, const CoinWarmStart *warmstart, Bonmin::BabInfo *babInfo, double *objcoe, int sense, int index) const
void fillQuadIndices()
Look for quadratic terms to be used with SDP cuts.
CouNumber bestObj() const
Objective of best known solution.
void setCutOff(CouNumber cutoff, const CouNumber *sol=NULL) const
Set cutoff.
general include file for different compilers
int getIntegerCandidate(const double *xFrac, double *xInt, double *lb, double *ub) const
generate integer NLP point Y starting from fractional solution using bound tightening
std::vector< CouenneConstraint * > * ConstraintClass(const char *str)
return particular constraint class.
CouenneProblem(const CouenneProblem &)
Copy constructor.
int * unusedOriginalsIndices_
some originals may be unused due to their zero multiplicity (that happens when they are duplicates).
enum TrilinDecompType trilinDecompType_
return type of decomposition of quadrilinear terms
void analyzeSparsity(CouNumber, LinMap &, QuadMap &)
analyze sparsity of potential exprQuad/exprGroup and change linear/quadratic maps accordingly,...
int nOrigVars_
Number of original variables.
void setupSymmetry()
empty if no NTY, symmetry data structure setup otherwise
CouenneObjective * Obj(int i) const
i-th objective
CouNumber feas_tolerance_
feasibility tolerance (to be used in checkNLP)
void resetCutOff(CouNumber value=COUENNE_INFINITY) const
Reset cutoff.
bool standardize()
Break problem's nonlinear constraints in simple expressions to be convexified later.
void color_vertex(register int k)
ConstJnlstPtr Jnlst() const
Provide Journalist.
std::vector< CouenneObject * > objects_
vector of pointer to CouenneObjects.
void indcoe2vector(int *indexL, CouNumber *coeff, std::vector< std::pair< exprVar *, CouNumber > > &lcoeff)
translates pair (indices, coefficients) into vector with pointers to variables
void writeGAMS(const std::string &fname)
Write nonlinear problem to a .gms file.
void ChangeBounds(const double *, const double *, int) const
int max_fbbt_iter_
number of FBBT iterations
void bounds(register double a, register double b)
DepGraph * getDepGraph()
Return pointer to dependence graph.
const std::vector< std::set< int > > & Dependence() const
return inverse dependence structure
void realign()
clear all spurious variables pointers not referring to the variables_ vector
bool *& Commuted()
Get vector of commuted variables.
CouNumber * optimum_
Best solution known to be loaded from file – for testing purposes.
bool doOBBT() const
shall we do Optimality Based Bound Tightening?
bool readOptimum(std::string *fname=NULL)
Read best known solution from file given in argument.
bool doFBBT_
do Feasibility-based bound tightening
bool checkAuxBounds_
check bounds on auxiliary variables when verifying MINLP feasibility of a solution.
bool checkCons(const CouNumber *sol, const bool stopAtFirstViol, const double precision, double &maxViol) const
returns true iff value of all auxiliaries are within bounds
CouenneBTPerfIndicator * FBBTperfIndicator_
Performance indicator for FBBT – to be moved away from CouenneProblem when we do it with FBBT.
int * numbering_
numbering of variables.
CouNumber * Ub() const
Return vector of upper bounds.
int getLastPrioSort() const
double CouNumber
main number type in Couenne
bool doOBBT_
do Optimality-based bound tightening
void addLEConstraint(expression *, expression *=NULL)
Add constraint, .
bool doRCBT() const
shall we do reduced cost Bound Tightening?
void fillDependence(Bonmin::BabSetupBase *base, CouenneCutGenerator *=NULL)
fill dependence_ structure
Bonmin::BabSetupBase * bonBase_
options
void restoreUnusedOriginals(CouNumber *=NULL) const
Some originals may be unused due to their zero multiplicity (that happens when they are duplicates).
exprVar * Var(int i) const
Return pointer to i-th variable.
int impliedBounds(t_chg_bounds *) const
"Backward" bound tightening, aka implied bounds.
CouNumber & lb(register int index)
current lower bound
CouenneRecordBestSol * getRecordBestSol() const
returns recorded best solution
int nOrigVars() const
Number of orig. variables.
int nVars() const
Total number of variables.
bool checkInt(const CouNumber *sol, const int from, const int upto, const std::vector< int > listInt, const bool origVarOnly, const bool stopAtFirstViol, const double precision, double &maxViol) const
check integrality of vars in sol with index between from and upto (original vars only if origVarOnly ...
const std::string & problemName() const
return problem name
Bonmin::BabSetupBase * bonBase() const
options
bool doABT() const
shall we do Aggressive Bound Tightening?
std::vector< Node > node_info
enum TrilinDecompType getTrilinDecompType()
return type of decomposition of quadrilinear terms
CouNumber * Lb() const
Return vector of lower bounds.
auxSign
"sign" of the constraint defining an auxiliary.
CouNumber * X() const
Return vector of variables.
CouNumber bestObj_
Best known objective function.
int nIntVars() const
Number of integer variables.
These are cuts of the form.
const std::vector< CouenneObject * > & Objects() const
return object vector
double constObjVal_
constant value of the objective if no variable is declared in it
void fillObjCoeff(double *&)
Fill vector with coefficients of objective function.
void setProblemName(std::string &problemName__)
void writeAMPL(const std::string &fname, bool aux)
Write nonlinear problem to a .mod file (with lots of defined variables)
std::set< exprAux *, compExpr > * auxSet_
Expression map for comparison in standardization and to count occurrences of an auxiliary.
int curnvars_
Number of elements in the x_, lb_, ub_ arrays.
std::set< exprAux *, compExpr > *& AuxSet()
Return pointer to set for comparisons.
int nOrigCons_
Number of original constraints (disregarding those that turned into auxiliary variable definition)
std::vector< exprVar * > & Variables()
Return vector of variables (symbolic representation)
nodeType
type of a node in an expression tree
bool fbbtReachedIterLimit_
true if FBBT exited for iteration limits as opposed to inability to further tighten bounds
double checkObj(const CouNumber *sol, const double &precision) const
Recompute objective value for sol.
void decomposeTerm(expression *term, CouNumber initCoe, CouNumber &c0, LinMap &lmap, QuadMap &qmap)
given (expression *) element of sum, returns (coe,ind0,ind1) depending on element:
double maxCpuTime_
maximum cpu time
int * integerRank_
each element is true if variable is integer and, if auxiliary, depends on no integer
int splitAux(CouNumber, expression *, expression *&, bool *, enum expression::auxSign &)
split a constraint w - f(x) = c into w's index (it is returned) and rest = f(x) + c
bool orbitalBranching_
use orbital branching?
void setNDefVars(int ndefined__)
CouenneConstraint * Con(int i) const
i-th constraint
double constObjVal() const
returns constant objective value if it contains no variables
Ipopt::SmartPtr< Ipopt::Journalist > JnlstPtr
bool checkNLP(const double *solution, double &obj, bool recompute=false) const
Check if solution is MINLP feasible.
bool compare(register Node &a, register Node &b) const
int * evalVector()
get evaluation order vector (numbering_)
void createUnusedOriginals()
Some originals may be unused due to their zero multiplicity (that happens when they are duplicates).
void setLastPrioSort(int givenLastPS)
std::string problemName_
problem name
bool boundTightening(t_chg_bounds *, const CglTreeInfo info, Bonmin::BabInfo *=NULL) const
tighten bounds using propagation, implied bounds and reduced costs
CouNumber & Ub(int i) const
upper bound on
bool orbitalBranching() const
return true if orbital branching activated
void setObjective(int indObj=0, expression *=NULL, const std::string &="min")
Add (non linear) objective function.
void node(int, double, double, double, int, int)
bool checkNLP0(const double *solution, double &obj, bool recompute_obj=false, const bool careAboutObj=false, const bool stopAtFirstViol=true, const bool checkAll=false, const double precision=-1) const
And finally a method to get both.
int findSOS(CbcModel *CbcModelPtr, OsiSolverInterface *solver, OsiObject **objects)
find SOS constraints in problem
bool doABT_
do Aggressive bound tightening
static void registerOptions(Ipopt::SmartPtr< Bonmin::RegisteredOptions > roptions)
Add list of options to be read from file.
CouNumber & X(int i) const
Class to represent nonlinear constraints.
std::vector< int > * Find_Orbit(int) const
int nIntVars_
Number of discrete variables.
bool operator()(register const char *a, register const char *b) const
int fake_tighten(char direction, int index, const double *X, CouNumber *olb, CouNumber *oub, t_chg_bounds *chg_bds, t_chg_bounds *f_chg) const
single fake tightening.
void addRNGConstraint(expression *, expression *=NULL, expression *=NULL)
Add range constraint, .
double getFeasTol()
returns feasibility tolerance
int ndefined_
Number of "defined variables" (aka "common expressions")
CouNumber opt_window_
window around known optimum (for testing purposes)
void installCutOff() const
Make cutoff known to the problem.
void setBase(Bonmin::BabSetupBase *base)
save CouenneBase
void flattenMul(expression *mul, CouNumber &coe, std::map< int, CouNumber > &indices)
re-organizes multiplication and stores indices (and exponents) of its variables
bool useQuadratic_
Use quadratic expressions?
void addEQConstraint(expression *, expression *=NULL)
Add equality constraint .
int nCons() const
Get number of constraints.
bool checkAuxBounds() const
return true if bounds of auxiliary variables have to be satisfied whenever a solution is tested for M...
CouNumber & x(register int index)
current variable
int nOrigIntVars_
Number of original integer variables.
Class for MINLP problems with symbolic information.
int testIntFix(int index, CouNumber xFrac, enum fixType *fixed, CouNumber *xInt, CouNumber *dualL, CouNumber *dualR, CouNumber *olb, CouNumber *oub, bool patient) const
Test fixing of an integer variable (used in getIntegerCandidate())
CouenneProblem * clone() const
Clone method (for use within CouenneCutGenerator::clone)
void addGEConstraint(expression *, expression *=NULL)
Add constraint, .
enum multiSep MultilinSep() const
return type of separator for multilinear terms
int call_iter(OsiSolverInterface *csi, t_chg_bounds *chg_bds, const CoinWarmStart *warmstart, Bonmin::BabInfo *babInfo, double *objcoe, enum nodeType type, int sense) const
bool doRCBT_
do reduced cost bound tightening
std::vector< exprVar * > variables_
Variables (original, auxiliary, and defined)
int tightenBounds(t_chg_bounds *) const
"Forward" bound tightening, that is, propagate bound of variable in an expression to the bounds of ...
void Print_Orbits() const
void initOptions(Ipopt::SmartPtr< Ipopt::OptionsList > options)
initializes parameters like doOBBT
void setCheckAuxBounds(bool value)
set the value for checkAuxBounds.
void setMaxCpuTime(double time)
set maximum CPU time
bool checkNLP2(const double *solution, const double obj, const bool careAboutObj, const bool stopAtFirstViol, const bool checkAll, const double precision) const
Return true if either solution or recomputed_solution obtained using getAuxs() from the original vari...
Define a dynamic point+bounds, with a way to save and restore previous points+bounds through a LIFO s...
void indcoe2vector(int *indexI, int *indexJ, CouNumber *coeff, std::vector< quadElem > &qcoeff)
translates triplet (indicesI, indicesJ, coefficients) into vector with pointers to variables
std::vector< expression * > & commonExprs()
ASL * asl_
AMPL structure pointer (temporary — looking forward to embedding into OS...)
int obbtInner(OsiSolverInterface *, OsiCuts &, t_chg_bounds *, Bonmin::BabInfo *) const
Optimality Based Bound Tightening – inner loop.