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 quadElem;
00033 class LinMap;
00034 class QuadMap;
00035
00036 template <class T> class CouenneSolverInterface;
00037
00038
00039 const CouNumber feas_tolerance_default = 1e-5;
00040
00041
00050 class CouenneProblem {
00051
00054 class GlobalCutOff {
00055 private:
00056 GlobalCutOff(const GlobalCutOff&);
00057 double cutoff_;
00058 public:
00059 GlobalCutOff () : cutoff_ (COIN_DBL_MAX) {}
00060 GlobalCutOff (double c) : cutoff_ (c) {}
00061 ~GlobalCutOff() {}
00062 inline void setCutOff (double cutoff) {cutoff_ = cutoff;}
00063 inline double getCutOff() const {return cutoff_;}
00064 };
00065
00067 enum fixType {UNFIXED, FIXED, CONTINUOUS};
00068
00069 protected:
00070
00072 std::string problemName_;
00073
00074 std::vector <exprVar *> variables_;
00075 std::vector <CouenneObjective *> objectives_;
00076 std::vector <CouenneConstraint *> constraints_;
00077
00079 std::vector <expression *> commonexprs_;
00080
00081 mutable Domain domain_;
00082
00085 std::set <exprAux *, compExpr> *auxSet_;
00086
00088 mutable int curnvars_;
00089
00091 int nIntVars_;
00092
00094 mutable CouNumber *optimum_;
00095
00097 CouNumber bestObj_;
00098
00100 int *quadIndex_;
00101
00103 bool *commuted_;
00104
00107 int *numbering_;
00108
00110 int ndefined_;
00111
00116 DepGraph *graph_;
00117
00119 int nOrigVars_;
00120
00123 int nOrigCons_;
00124
00126 int nOrigIntVars_;
00127
00129 mutable GlobalCutOff* pcutoff_;
00130
00132 mutable bool created_pcutoff_;
00133
00134 bool doFBBT_;
00135 bool doRCBT_;
00136 bool doOBBT_;
00137 bool doABT_;
00138
00139 int logObbtLev_;
00140 int logAbtLev_;
00141
00143 JnlstPtr jnlst_;
00144
00146 CouNumber opt_window_;
00147
00149 bool useQuadratic_;
00150
00152 CouNumber feas_tolerance_;
00153
00157 std::vector <std::set <int> > dependence_;
00158
00162 std::vector <CouenneObject *> objects_;
00163
00166 mutable int *integerRank_;
00167
00169 mutable std::vector <int> numberInRank_;
00170
00172 double maxCpuTime_;
00173
00175 Bonmin::BabSetupBase *bonBase_;
00176
00177 #ifdef COIN_HAS_ASL
00179 ASL *asl_;
00180 #endif
00181
00185 int *unusedOriginalsIndices_;
00186
00188 int nUnusedOriginals_;
00189
00190 public:
00191
00192 CouenneProblem (ASL * = NULL,
00193 Bonmin::BabSetupBase *base = NULL,
00194 JnlstPtr jnlst = NULL);
00195 CouenneProblem (const CouenneProblem &);
00196 ~CouenneProblem ();
00197
00199 void initOptions(SmartPtr<OptionsList> options);
00200
00202 CouenneProblem *clone () const
00203 {return new CouenneProblem (*this);}
00204
00205 int nObjs () const {return (int) objectives_. size ();}
00206 int nCons () const {return (int) constraints_. size ();}
00207 int nOrigCons () const {return nOrigCons_;}
00208
00209 inline int nOrigVars () const {return nOrigVars_;}
00210 inline int nDefVars () const {return ndefined_;}
00211 inline int nOrigIntVars () const {return nOrigIntVars_;}
00212 inline int nIntVars () const {return nIntVars_;}
00213 inline int nVars () const {return (int) variables_. size ();}
00214
00215 void setNDefVars(int ndefined__) { ndefined_ = ndefined__; }
00216
00218 inline int evalOrder (int i) const
00219 {return numbering_ [i];}
00220
00222 inline int *evalVector ()
00223 {return numbering_;}
00224
00225
00226 inline CouenneConstraint *Con (int i) const {return constraints_ [i];}
00227 inline CouenneObjective *Obj (int i) const {return objectives_ [i];}
00228
00230 inline exprVar *Var (int i) const
00231 {return variables_ [i];}
00232
00234 inline std::vector <exprVar *> &Variables ()
00235 {return variables_;}
00236
00238 inline std::set <exprAux *, compExpr> *& AuxSet ()
00239 {return auxSet_;}
00240
00242 inline DepGraph *getDepGraph ()
00243 {return graph_;}
00244
00246 inline Domain *domain () const
00247 {return &domain_;}
00248
00249 inline std::vector <expression *>& commonExprs() { return commonexprs_; }
00250
00251
00252 inline CouNumber &X (int i) const {return domain_.x (i);}
00253 inline CouNumber &Lb (int i) const {return domain_.lb (i);}
00254 inline CouNumber &Ub (int i) const {return domain_.ub (i);}
00255
00256
00257 inline CouNumber *X () const {return domain_.x ();}
00258 inline CouNumber *Lb () const {return domain_.lb ();}
00259 inline CouNumber *Ub () const {return domain_.ub ();}
00260
00261
00262 CouNumber *&bestSol () const {return optimum_;}
00263 CouNumber bestObj () const {return bestObj_;}
00264
00266 bool *&Commuted ()
00267 {return commuted_;}
00268
00270 void addObjective (expression *, const std::string &);
00271
00272
00273 void addEQConstraint (expression *, expression *);
00274 void addGEConstraint (expression *, expression *);
00275 void addLEConstraint (expression *, expression *);
00276 void addRNGConstraint (expression *, expression *,
00277 expression *);
00278
00283 expression *addVariable (bool isint = false, Domain *d = NULL);
00284
00287 exprAux *addAuxiliary (expression *);
00288
00290 void reformulate (CouenneCutGenerator * = NULL);
00291
00295 bool standardize ();
00296
00299 void print (std::ostream & = std::cout);
00300
00301 #ifdef COIN_HAS_ASL
00303 int readnl (const struct ASL *);
00304
00306 expression *nl2e (struct expr *, const ASL *asl);
00307 #endif
00308
00309
00310 bool doFBBT () const {return doFBBT_;}
00311 bool doRCBT () const {return doRCBT_;}
00312 bool doOBBT () const {return doOBBT_;}
00313 bool doABT () const {return doABT_;}
00314
00315 int logObbtLev () const {return logObbtLev_;}
00316 int logAbtLev () const {return logAbtLev_;}
00317
00330 void writeAMPL (const std::string &fname, bool aux);
00331
00335 void writeGAMS (const std::string &fname);
00336
00339
00340 void initAuxs () const;
00341
00343 void getAuxs (CouNumber *) const;
00344
00346 bool boundTightening (t_chg_bounds *,
00347 Bonmin::BabInfo * = NULL) const;
00348
00350 bool btCore (t_chg_bounds *chg_bds) const;
00351
00353 int obbt (const CouenneCutGenerator *cg,
00354 const OsiSolverInterface &csi,
00355 OsiCuts &cs,
00356 const CglTreeInfo &info,
00357 Bonmin::BabInfo * babInfo,
00358 t_chg_bounds *chg_bds);
00359
00363 bool aggressiveBT (Bonmin::OsiTMINLPInterface *nlp,
00364 t_chg_bounds *,
00365 Bonmin::BabInfo * = NULL) const;
00366
00369 int redCostBT (const OsiSolverInterface *psi,
00370 t_chg_bounds *chg_bds) const;
00371
00374 int tightenBounds (t_chg_bounds *) const;
00375
00377 int impliedBounds (t_chg_bounds *) const;
00378
00380 void fillQuadIndices ();
00381
00383 void fillObjCoeff (double *&);
00384
00387 void auxiliarize (exprVar *, exprVar * = NULL);
00388
00390 void setCutOff (CouNumber cutoff) const;
00391
00393 CouNumber getCutOff () const
00394 {return pcutoff_ -> getCutOff ();}
00395
00397 void installCutOff () const;
00398
00400 ConstJnlstPtr Jnlst() const
00401 {return ConstPtr(jnlst_);}
00402
00404 bool checkNLP (const double *solution, double &obj, bool recompute = false) const;
00405
00408 int getIntegerCandidate (const double *xFrac, double *xInt, double *lb, double *ub) const;
00409
00411 bool readOptimum (std::string *fname = NULL);
00412
00414 void readCutoff (const std::string &fname);
00415
00417 static void registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions);
00418
00420 exprAux *linStandardize (bool addAux,
00421 CouNumber c0,
00422 LinMap &lmap,
00423 QuadMap &qmap);
00424
00427 int splitAux (CouNumber, expression *, expression *&, bool *);
00428
00430 void indcoe2vector (int *indexL,
00431 CouNumber *coeff,
00432 std::vector <std::pair <exprVar *, CouNumber> > &lcoeff);
00433
00435 void indcoe2vector (int *indexI,
00436 int *indexJ,
00437 CouNumber *coeff,
00438 std::vector <quadElem> &qcoeff);
00439
00450 void decomposeTerm (expression *term,
00451 CouNumber initCoe,
00452 CouNumber &c0,
00453 LinMap &lmap,
00454 QuadMap &qmap);
00455
00457 const std::string &problemName () const
00458 {return problemName_;}
00459
00460 void setProblemName(std::string& problemName__)
00461 { problemName_ = problemName__; }
00462
00464 const std::vector <std::set <int> > &Dependence () const
00465 {return dependence_;}
00466
00468 const std::vector <CouenneObject *> &Objects () const
00469 {return objects_;}
00470
00472 int findSOS (OsiSolverInterface *solver, OsiObject ** objects);
00473
00475 inline void setMaxCpuTime (double time)
00476 {maxCpuTime_ = time;}
00477
00479 inline double getMaxCpuTime () const
00480 {return maxCpuTime_;}
00481
00483 inline void setBase (Bonmin::BabSetupBase *base) {
00484 bonBase_ = base;
00485 jnlst_ = base -> journalist ();
00486 }
00487
00492 void createUnusedOriginals ();
00493
00497 void restoreUnusedOriginals (CouNumber * = NULL) const;
00498
00500 int *unusedOriginalsIndices () {return unusedOriginalsIndices_;}
00501
00503 int nUnusedOriginals () {return nUnusedOriginals_;}
00504
00505 protected:
00506
00512 int fake_tighten (char direction,
00513 int index,
00514 const double *X,
00515 CouNumber *olb,
00516 CouNumber *oub,
00517 t_chg_bounds *chg_bds,
00518 t_chg_bounds *f_chg) const;
00519
00521 int obbtInner (OsiSolverInterface *,
00522 OsiCuts &,
00523 t_chg_bounds *,
00524 Bonmin::BabInfo *) const;
00525
00526 int obbt_iter (OsiSolverInterface *csi,
00527 t_chg_bounds *chg_bds,
00528 const CoinWarmStart *warmstart,
00529 Bonmin::BabInfo *babInfo,
00530 double *objcoe,
00531 int sense,
00532 int index) const;
00533
00534 int call_iter (OsiSolverInterface *csi,
00535 t_chg_bounds *chg_bds,
00536 const CoinWarmStart *warmstart,
00537 Bonmin::BabInfo *babInfo,
00538 double *objcoe,
00539 enum nodeType type,
00540 int sense) const;
00541
00545 void analyzeSparsity (CouNumber,
00546 LinMap &,
00547 QuadMap &);
00548
00551 void flattenMul (expression *mul,
00552 CouNumber &coe,
00553 std::map <int, CouNumber> &indices);
00554
00556 void realign ();
00557
00559 void fillDependence (Bonmin::BabSetupBase *base, CouenneCutGenerator * = NULL);
00560
00562 void fillIntegerRank () const;
00563
00565 int testIntFix (int index,
00566 CouNumber xFrac,
00567 enum fixType *fixed,
00568 CouNumber *xInt,
00569 CouNumber *dualL, CouNumber *dualR,
00570 CouNumber *olb, CouNumber *oub,
00571 bool patient) const;
00572 };
00573
00574
00577 bool BranchingFBBT (CouenneProblem *problem,
00578 OsiObject *Object,
00579 OsiSolverInterface *solver);
00580
00581 #endif
00582