00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #ifndef COUENNE_PROBLEM_HPP
00012 #define COUENNE_PROBLEM_HPP
00013
00014 #include <vector>
00015
00016 #include "OsiRowCut.hpp"
00017 #include "BonBabInfos.hpp"
00018
00019 #include "CouenneTypes.hpp"
00020 #include "expression.hpp"
00021 #include "exprAux.hpp"
00022 #include "CouenneProblemElem.hpp"
00023 #include "CouenneObject.hpp"
00024 #include "CouenneJournalist.hpp"
00025 #include "domain.hpp"
00026
00027 struct ASL;
00028 struct expr;
00029
00030 class DepGraph;
00031 class CouenneCutGenerator;
00032 class CouenneSolverInterface;
00033 class quadElem;
00034 class LinMap;
00035 class QuadMap;
00036
00037
00038 const CouNumber feas_tolerance_default = 1e-5;
00039
00040
00049 class CouenneProblem {
00050
00053 class GlobalCutOff {
00054 private:
00055 GlobalCutOff(const GlobalCutOff&);
00056 double cutoff_;
00057 public:
00058 GlobalCutOff () : cutoff_ (COIN_DBL_MAX) {}
00059 GlobalCutOff (double c) : cutoff_ (c) {}
00060 ~GlobalCutOff() {}
00061 inline void setCutOff (double cutoff) {cutoff_ = cutoff;}
00062 inline double getCutOff() const {return cutoff_;}
00063 };
00064
00066 enum fixType {UNFIXED, FIXED, CONTINUOUS};
00067
00068 protected:
00069
00071 std::string problemName_;
00072
00073 std::vector <exprVar *> variables_;
00074 std::vector <CouenneObjective *> objectives_;
00075 std::vector <CouenneConstraint *> constraints_;
00076
00078 std::vector <expression *> commonexprs_;
00079
00080 mutable Domain domain_;
00081
00084 std::set <exprAux *, compExpr> *auxSet_;
00085
00087 mutable int curnvars_;
00088
00090 int nIntVars_;
00091
00093 mutable CouNumber *optimum_;
00094
00096 CouNumber bestObj_;
00097
00099 int *quadIndex_;
00100
00102 bool *commuted_;
00103
00106 int *numbering_;
00107
00109 int ndefined_;
00110
00115 DepGraph *graph_;
00116
00118 int nOrigVars_;
00119
00122 int nOrigCons_;
00123
00125 int nOrigIntVars_;
00126
00128 mutable GlobalCutOff* pcutoff_;
00129
00131 mutable bool created_pcutoff_;
00132
00133 bool doFBBT_;
00134 bool doRCBT_;
00135 bool doOBBT_;
00136 bool doABT_;
00137
00138 int logObbtLev_;
00139 int logAbtLev_;
00140
00142 JnlstPtr jnlst_;
00143
00145 CouNumber opt_window_;
00146
00148 bool useQuadratic_;
00149
00151 CouNumber feas_tolerance_;
00152
00156 std::vector <std::set <int> > dependence_;
00157
00161 std::vector <CouenneObject> objects_;
00162
00165 mutable int *integerRank_;
00166
00168 mutable std::vector <int> numberInRank_;
00169
00171 double maxCpuTime_;
00172
00174 Bonmin::BabSetupBase *bonBase_;
00175
00176 #ifdef COIN_HAS_ASL
00178 ASL *asl_;
00179 #endif
00180
00184 int *unusedOriginalsIndices_;
00185
00187 int nUnusedOriginals_;
00188
00189 public:
00190
00191 CouenneProblem (ASL * = NULL,
00192 Bonmin::BabSetupBase *base = NULL,
00193 JnlstPtr jnlst = NULL);
00194 CouenneProblem (const CouenneProblem &);
00195 ~CouenneProblem ();
00196
00198 void initOptions(SmartPtr<OptionsList> options);
00199
00201 CouenneProblem *clone () const
00202 {return new CouenneProblem (*this);}
00203
00204 int nObjs () const {return (int) objectives_. size ();}
00205 int nCons () const {return (int) constraints_. size ();}
00206 int nOrigCons () const {return nOrigCons_;}
00207
00208 inline int nOrigVars () const {return nOrigVars_;}
00209 inline int nDefVars () const {return ndefined_;}
00210 inline int nOrigIntVars () const {return nOrigIntVars_;}
00211 inline int nIntVars () const {return nIntVars_;}
00212 inline int nVars () const {return (int) variables_. size ();}
00213
00215 inline int evalOrder (int i) const
00216 {return numbering_ [i];}
00217
00219 inline int *evalVector ()
00220 {return numbering_;}
00221
00222
00223 inline CouenneConstraint *Con (int i) const {return constraints_ [i];}
00224 inline CouenneObjective *Obj (int i) const {return objectives_ [i];}
00225
00227 inline exprVar *Var (int i) const
00228 {return variables_ [i];}
00229
00231 inline std::vector <exprVar *> &Variables ()
00232 {return variables_;}
00233
00235 inline std::set <exprAux *, compExpr> *& AuxSet ()
00236 {return auxSet_;}
00237
00239 inline DepGraph *getDepGraph ()
00240 {return graph_;}
00241
00243 inline Domain *domain () const
00244 {return &domain_;}
00245
00246
00247 inline CouNumber &X (int i) const {return domain_.x (i);}
00248 inline CouNumber &Lb (int i) const {return domain_.lb (i);}
00249 inline CouNumber &Ub (int i) const {return domain_.ub (i);}
00250
00251
00252 inline CouNumber *X () const {return domain_.x ();}
00253 inline CouNumber *Lb () const {return domain_.lb ();}
00254 inline CouNumber *Ub () const {return domain_.ub ();}
00255
00256
00257 CouNumber *&bestSol () const {return optimum_;}
00258 CouNumber bestObj () const {return bestObj_;}
00259
00261 bool *&Commuted ()
00262 {return commuted_;}
00263
00265 void addObjective (expression *, const std::string &);
00266
00267
00268 void addEQConstraint (expression *, expression *);
00269 void addGEConstraint (expression *, expression *);
00270 void addLEConstraint (expression *, expression *);
00271 void addRNGConstraint (expression *, expression *,
00272 expression *);
00273
00278 expression *addVariable (bool isint = false, Domain *d = NULL);
00279
00282 exprAux *addAuxiliary (expression *);
00283
00285 void reformulate ();
00286
00290 bool standardize ();
00291
00294 void print (std::ostream & = std::cout);
00295
00296 #ifdef COIN_HAS_ASL
00298 int readnl (const struct ASL *);
00299
00301 expression *nl2e (struct expr *, const ASL *asl);
00302 #endif
00303
00304
00305 bool doFBBT () const {return doFBBT_;}
00306 bool doRCBT () const {return doRCBT_;}
00307 bool doOBBT () const {return doOBBT_;}
00308 bool doABT () const {return doABT_;}
00309
00310 int logObbtLev () const {return logObbtLev_;}
00311 int logAbtLev () const {return logAbtLev_;}
00312
00325 void writeAMPL (const std::string &fname, bool aux);
00326
00330 void writeGAMS (const std::string &fname);
00331
00334
00335 void initAuxs () const;
00336
00338 void getAuxs (CouNumber *) const;
00339
00341 bool boundTightening (t_chg_bounds *,
00342 Bonmin::BabInfo * = NULL) const;
00343
00345 bool btCore (t_chg_bounds *chg_bds) const;
00346
00348 int obbt (const CouenneCutGenerator *cg,
00349 const OsiSolverInterface &csi,
00350 OsiCuts &cs,
00351 const CglTreeInfo &info,
00352 Bonmin::BabInfo * babInfo,
00353 t_chg_bounds *chg_bds);
00354
00358 bool aggressiveBT (Bonmin::OsiTMINLPInterface *nlp,
00359 t_chg_bounds *,
00360 Bonmin::BabInfo * = NULL) const;
00361
00364 int redCostBT (const OsiSolverInterface *psi,
00365 t_chg_bounds *chg_bds) const;
00366
00369 int tightenBounds (t_chg_bounds *) const;
00370
00372 int impliedBounds (t_chg_bounds *) const;
00373
00375 void fillQuadIndices ();
00376
00378 void fillObjCoeff (double *&);
00379
00382 void auxiliarize (exprVar *, exprVar * = NULL);
00383
00385 void setCutOff (CouNumber cutoff) const;
00386
00388 CouNumber getCutOff () const
00389 {return pcutoff_ -> getCutOff ();}
00390
00392 void installCutOff () const;
00393
00395 ConstJnlstPtr Jnlst() const
00396 {return ConstPtr(jnlst_);}
00397
00399 bool checkNLP (const double *solution, double &obj, bool recompute = false) const;
00400
00403 int getIntegerCandidate (const double *xFrac, double *xInt, double *lb, double *ub) const;
00404
00406 bool readOptimum (std::string *fname = NULL);
00407
00409 void readCutoff (const std::string &fname);
00410
00412 static void registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions);
00413
00415 exprAux *linStandardize (bool addAux,
00416 CouNumber c0,
00417 LinMap &lmap,
00418 QuadMap &qmap);
00419
00422 int splitAux (CouNumber, expression *, expression *&, bool *);
00423
00425 void indcoe2vector (int *indexL,
00426 CouNumber *coeff,
00427 std::vector <std::pair <exprVar *, CouNumber> > &lcoeff);
00428
00430 void indcoe2vector (int *indexI,
00431 int *indexJ,
00432 CouNumber *coeff,
00433 std::vector <quadElem> &qcoeff);
00434
00445 void decomposeTerm (expression *term,
00446 CouNumber initCoe,
00447 CouNumber &c0,
00448 LinMap &lmap,
00449 QuadMap &qmap);
00450
00452 const std::string &problemName () const
00453 {return problemName_;}
00454
00456 const std::vector <std::set <int> > &Dependence () const
00457 {return dependence_;}
00458
00460 const std::vector <CouenneObject> &Objects () const
00461 {return objects_;}
00462
00464 int findSOS (OsiSolverInterface *solver, OsiObject ** objects);
00465
00467 inline void setMaxCpuTime (double time)
00468 {maxCpuTime_ = time;}
00469
00471 inline double getMaxCpuTime () const
00472 {return maxCpuTime_;}
00473
00475 inline void setBase (Bonmin::BabSetupBase *base) {
00476 bonBase_ = base;
00477 jnlst_ = base -> journalist ();
00478 }
00479
00484 void createUnusedOriginals ();
00485
00489 void restoreUnusedOriginals (CouNumber * = NULL) const;
00490
00492 int *unusedOriginalsIndices () {return unusedOriginalsIndices_;}
00493
00495 int nUnusedOriginals () {return nUnusedOriginals_;}
00496
00497 protected:
00498
00504 int fake_tighten (char direction,
00505 int index,
00506 const double *X,
00507 CouNumber *olb,
00508 CouNumber *oub,
00509 t_chg_bounds *chg_bds,
00510 t_chg_bounds *f_chg) const;
00511
00513 int obbtInner (CouenneSolverInterface *,
00514 OsiCuts &,
00515 t_chg_bounds *,
00516 Bonmin::BabInfo *) const;
00517
00518 int obbt_iter (CouenneSolverInterface *csi,
00519 t_chg_bounds *chg_bds,
00520 const CoinWarmStart *warmstart,
00521 Bonmin::BabInfo *babInfo,
00522 double *objcoe,
00523 int sense,
00524 int index) const;
00525
00526 int call_iter (CouenneSolverInterface *csi,
00527 t_chg_bounds *chg_bds,
00528 const CoinWarmStart *warmstart,
00529 Bonmin::BabInfo *babInfo,
00530 double *objcoe,
00531 enum nodeType type,
00532 int sense) const;
00533
00537 void analyzeSparsity (CouNumber,
00538 LinMap &,
00539 QuadMap &);
00540
00543 void flattenMul (expression *mul,
00544 CouNumber &coe,
00545 std::map <int, CouNumber> &indices);
00546
00548 void realign ();
00549
00551 void fillDependence (Bonmin::BabSetupBase *base);
00552
00554 void fillIntegerRank () const;
00555
00557 int testIntFix (int index,
00558 CouNumber xFrac,
00559 enum fixType *fixed,
00560 CouNumber *xInt,
00561 CouNumber *dualL, CouNumber *dualR,
00562 CouNumber *olb, CouNumber *oub,
00563 bool patient) const;
00564 };
00565
00566 #endif