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};
372 int nObjs ()
const {
return (
int)
objectives_. size ();}
373 int nCons ()
const {
return (
int)
constraints_. size ();}
376 inline int nOrigVars ()
const {
return nOrigVars_;}
377 inline int nDefVars ()
const {
return ndefined_;}
379 inline int nIntVars ()
const {
return nIntVars_;}
380 inline int nVars ()
const {
return (
int)
variables_. size ();}
396 void ChangeBounds (
const double * ,
const double *,
int )
const;
416 inline CouenneObjective *Obj (
int i)
const {
return objectives_ [i];}
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);
503 bool doRCBT ()
const {
return doRCBT_;}
504 bool doOBBT ()
const {
return doOBBT_;}
505 bool doABT ()
const {
return doABT_;}
522 void writeAMPL (
const std::string &fname,
bool aux);
527 void writeGAMS (
const std::string &fname);
533 void writeLP (
const std::string &fname);
549 bool btCore (t_chg_bounds *chg_bds)
const;
552 int obbt (
const CouenneCutGenerator *cg,
557 t_chg_bounds *chg_bds);
570 t_chg_bounds *chg_bds)
const;
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 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
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.
void initAuxs() const
Initialize auxiliary variables and their bounds from original variables.
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.
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.
bool aggressiveBT(Bonmin::OsiTMINLPInterface *nlp, t_chg_bounds *, const CglTreeInfo &info, Bonmin::BabInfo *=NULL) const
aggressive bound tightening.
~CouenneProblem()
Destructor.
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.
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.
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.
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.
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
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 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.
int getLastPrioSort() const
double CouNumber
main number type in Couenne
bool doOBBT_
do Optimality-based bound tightening
void addLEConstraint(expression *, expression *=NULL)
Add constraint, .
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.
CouenneRecordBestSol * getRecordBestSol() const
returns recorded best solution
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
std::vector< Node > node_info
enum TrilinDecompType getTrilinDecompType()
return type of decomposition of quadrilinear terms
auxSign
"sign" of the constraint defining an auxiliary.
CouNumber bestObj_
Best known objective function.
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__)
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
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.
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 .
bool checkAuxBounds() const
return true if bounds of auxiliary variables have to be satisfied whenever a solution is tested for M...
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...
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.