source: trunk/Couenne/src/problem/CouenneProblem.hpp @ 28

Last change on this file since 28 was 28, checked in by stefan, 13 years ago

let AuxSet?() return a reference to auxSet_ instead of its value, so user can set it from outside

File size: 17.1 KB
Line 
1/*
2 * Name:    CouenneProblem.hpp
3 * Author:  Pietro Belotti
4 * Purpose: define the class CouenneProblem
5 *
6 * (C) Carnegie-Mellon University, 2006-08.
7 * This file is licensed under the Common Public License (CPL)
8 */
9
10#ifndef COUENNE_PROBLEM_HPP
11#define COUENNE_PROBLEM_HPP
12
13#include <vector>
14
15#include "OsiRowCut.hpp"
16#include "BonBabInfos.hpp"
17
18#include "CouenneTypes.hpp"
19#include "expression.hpp"
20#include "exprAux.hpp"
21#include "CouenneProblemElem.hpp"
22#include "CouenneObject.hpp"
23#include "CouenneJournalist.hpp"
24#include "domain.hpp"
25
26struct ASL;
27struct expr;
28
29class DepGraph;
30class CouenneCutGenerator;
31class CouenneSolverInterface;
32class quadElem;
33class LinMap;
34class QuadMap;
35
36// default tolerance for checking feasibility (and integrality) of NLP solutions
37const CouNumber feas_tolerance_default = 1e-5;
38
39
40/** Class for MINLP problems with symbolic information
41 *
42 *  It is read from an AMPL .nl file and contains variables, AMPL's
43 *  "defined variables" (aka common expressions), objective(s), and
44 *  constraints in the form of expression's. Changes throughout the
45 *  program occur in standardization.
46 */
47
48class CouenneProblem {
49
50  /// Class for storing a global cutoff for a CouenneProblem and all
51  /// its clones
52  class GlobalCutOff {
53  private:
54    GlobalCutOff(const GlobalCutOff&);
55    double cutoff_;
56  public:
57    GlobalCutOff ()         : cutoff_ (COIN_DBL_MAX) {}
58    GlobalCutOff (double c) : cutoff_ (c) {}
59    ~GlobalCutOff() {}
60    inline void setCutOff (double cutoff) {cutoff_ = cutoff;}
61    inline double getCutOff() const {return cutoff_;}
62  };
63
64  /// structure to record fixed, non-fixed, and continuous variables
65  enum fixType {UNFIXED, FIXED, CONTINUOUS};
66
67 protected:
68
69  /// problem name
70  std::string problemName_;
71
72  std::vector <exprVar           *> variables_;   ///< Variables (original, auxiliary, and defined)
73  std::vector <CouenneObjective  *> objectives_;  ///< Objectives
74  std::vector <CouenneConstraint *> constraints_; ///< Constraints
75
76  /// AMPL's common expressions (read from AMPL through structures cexps and cexps1)
77  std::vector <expression *> commonexprs_; 
78
79  mutable Domain domain_; ///< current point and bounds;
80
81  /// Expression map for comparison in standardization and to count
82  /// occurrences of an auxiliary
83  std::set <exprAux *, compExpr> *auxSet_;
84
85  /// Number of elements in the x_, lb_, ub_ arrays
86  mutable int curnvars_;
87
88  /// Number of discrete variables
89  int nIntVars_;
90
91  /// Best solution known to be loaded from file -- for testing purposes
92  mutable CouNumber *optimum_;
93
94  /// Best known objective function
95  CouNumber bestObj_;
96
97  /// Indices of variables appearing in products (used for SDP cuts)
98  int *quadIndex_;
99
100  /// Variables that have commuted to auxiliary
101  bool *commuted_;
102
103  /// numbering of variables. No variable xi with associated pi(i)
104  /// greater than pi(j) should be evaluated before variable xj
105  int *numbering_;
106
107  /// Number of "defined variables" (aka "common expressions")
108  int ndefined_;
109
110  /// Dependence (acyclic) graph: shows dependence of all auxiliary
111  /// variables on one another and on original variables. Used to
112  /// create a numbering of all variables for evaluation and bound
113  /// tightening (reverse order for implied bounds)
114  DepGraph *graph_;
115
116  /// Number of original variables
117  int nOrigVars_;
118
119  /// Number of original constraints (disregarding those that turned
120  /// into auxiliary variable definition)
121  int nOrigCons_;
122
123  /// Number of original integer variables
124  int nOrigIntVars_;
125
126  /// Pointer to a global cutoff object
127  mutable GlobalCutOff* pcutoff_;
128
129  /// flag indicating if this class is creator of global cutoff object
130  mutable bool created_pcutoff_;
131
132  bool doFBBT_;  ///< do Feasibility-based bound tightening
133  bool doOBBT_;  ///< do Optimality-based  bound tightening
134  bool doABT_;   ///< do Aggressive        bound tightening
135
136  int logObbtLev_;   ///< frequency of Optimality-based bound tightening
137  int logAbtLev_;    ///< frequency of Aggressive       bound tightening
138
139  /// SmartPointer to the Journalist
140  JnlstPtr jnlst_;
141
142  /// window around known optimum (for testing purposes)
143  CouNumber opt_window_;
144
145  /// Use quadratic expressions?
146  bool useQuadratic_;
147
148  /// feasibility tolerance (to be used in checkNLP)
149  CouNumber feas_tolerance_;
150
151  /// inverse dependence structure: for each variable x give set of
152  /// auxiliary variables (or better, their indices) whose expression
153  /// depends on x
154  std::vector <std::set <int> > dependence_;
155
156  /// vector of pointer to CouenneObjects. Used by CouenneVarObjects
157  /// when finding all objects related to (having as argument) a
158  /// single variable
159  std::vector <CouenneObject> objects_;
160
161  /// each element is true if variable is integer and, if auxiliary,
162  /// depends on no integer
163  mutable int *integerRank_;
164
165  /// numberInRank_ [i] is the number of integer variables in rank i
166  mutable std::vector <int> numberInRank_;
167
168  /// maximum cpu time
169  double maxCpuTime_;
170
171 public:
172
173  CouenneProblem  (const ASL * = NULL,
174                   Bonmin::BabSetupBase *base = NULL,
175                   JnlstPtr jnlst = NULL);  ///< Constructor
176  CouenneProblem  (const CouenneProblem &); ///< Copy constructor
177  ~CouenneProblem ();                       ///< Destructor
178
179  /// Clone method (for use within CouenneCutGenerator::clone)
180  CouenneProblem *clone () const
181  {return new CouenneProblem (*this);}
182
183  int nObjs     () const {return (int) objectives_.   size ();} ///< Get number of objectives
184  int nCons     () const {return (int) constraints_.  size ();} ///< Get number of constraints
185  int nOrigCons () const {return nOrigCons_;}                   ///< Get number of original constraints
186
187  inline int nOrigVars    () const {return nOrigVars_;}                ///< Number of orig. variables
188  inline int nOrigIntVars () const {return nOrigIntVars_;}             ///< Number of original integers
189  inline int nIntVars     () const {return nIntVars_;}                 ///< Number of integer variables
190  inline int nVars        () const {return (int) variables_. size ();} ///< Total number of variables
191
192  /// get evaluation order index
193  inline int evalOrder (int i) const
194  {return numbering_ [i];}
195
196  /// get evaluation order vector (numbering_)
197  inline int *evalVector ()
198  {return numbering_;}
199
200  // get elements from vectors
201  inline CouenneConstraint *Con (int i) const {return constraints_ [i];} ///< i-th constraint
202  inline CouenneObjective  *Obj (int i) const {return objectives_  [i];} ///< i-th objective
203
204  /// Return pointer to i-th variable
205  inline exprVar *Var   (int i) const 
206  {return variables_ [i];}
207
208  /// Return vector of variables (symbolic representation)
209  inline std::vector <exprVar *> &Variables () 
210  {return variables_;}
211
212  /// Return pointer to set for comparisons
213  inline std::set <exprAux *, compExpr> *& AuxSet () 
214  {return auxSet_;}
215
216  /// Return pointer to dependence graph
217  inline DepGraph *getDepGraph () 
218  {return graph_;}
219
220  /// return current point & bounds
221  inline Domain *domain () const
222  {return &domain_;}
223
224  // Get and set current variable and bounds
225  inline CouNumber   &X     (int i) const {return domain_.x   (i);} ///< \f$x_i\f$
226  inline CouNumber   &Lb    (int i) const {return domain_.lb  (i);} ///< lower bound on \f$x_i\f$
227  inline CouNumber   &Ub    (int i) const {return domain_.ub  (i);} ///< upper bound on\f$x_i\f$
228
229  // get and set current variable and bounds
230  inline CouNumber  *X     () const {return domain_.();} ///< Return vector of variables
231  inline CouNumber  *Lb    () const {return domain_.lb ();} ///< Return vector of lower bounds
232  inline CouNumber  *Ub    () const {return domain_.ub ();} ///< Return vector of upper bounds
233
234  // get optimal solution and objective value
235  CouNumber  *bestSol () const {return optimum_;} ///< Best known solution (read from file)
236  CouNumber   bestObj () const {return bestObj_;} ///< Objective of best known solution
237
238  /// Get vector of commuted variables
239  bool *&Commuted () 
240  {return commuted_;}
241
242  /// Add (non linear) objective function
243  void addObjective     (expression *, const std::string &);
244
245  // Add (non linear) "=", ">=", "<=", and range constraints
246  void addEQConstraint  (expression *, expression *); ///< Add equality constraint \f$ h(x) = b\f$
247  void addGEConstraint  (expression *, expression *); ///< Add \f$\ge\f$ constraint, \f$h(x)\ge b\f$
248  void addLEConstraint  (expression *, expression *); ///< Add \f$\le\f$ constraint, \f$h(x)\le b\f$
249  void addRNGConstraint (expression *, expression *, 
250                         expression *);               ///< Add range constraint, \f$a\le h(x)\le b\f$
251
252  /// Add original variable.
253  ///
254  /// @param isint if true, this variable is integer, otherwise it is
255  /// continuous
256  expression *addVariable (bool isint = false, Domain *d = NULL);
257
258  /// Add auxiliary variable and associate it with expression given as
259  /// argument (used in standardization)
260  exprAux *addAuxiliary (expression *);
261
262  /// Break problem's nonlinear constraints in simple expressions to be
263  /// convexified later
264  void standardize ();
265
266  /// Display current representation of problem: objective, linear and
267  /// nonlinear constraints, and auxiliary variables.
268  void print (std::ostream & = std::cout);
269
270  /// Read problem from .nl file using the Ampl Solver Library (ASL)
271  int readnl (const struct ASL *);
272
273  /// Generate a Couenne expression from an ASL expression
274  expression *nl2e (struct expr *, const ASL *asl);
275
276  // bound tightening parameters
277  bool doFBBT () const {return doFBBT_;} ///< shall we do Feasibility Based Bound Tightening?
278  bool doOBBT () const {return doOBBT_;} ///< shall we do Optimality  Based Bound Tightening?
279  bool doABT  () const {return doABT_;}  ///< shall we do Aggressive        Bound Tightening?
280
281  int  logObbtLev () const {return logObbtLev_;} ///< How often shall we do OBBT?
282  int  logAbtLev  () const {return logAbtLev_;}  ///< How often shall we do ABT?
283
284  /// Write nonlinear problem to a .mod file (with lots of defined
285  /// variables)
286  ///
287  /// @param fname Name of the .mod file to be written
288  ///
289  /// @param aux controls the use of auxiliaries. If true, a problem
290  /// is written with auxiliary variables written with their
291  /// associated expression, i.e. \f$w_i = h_i(x,y,w)\f$ and bounds
292  /// \f$l_i \le w_i \le u_i\f$, while if false these constraints are
293  /// written in the form \f$l_i \le h_i (x,y) \le u_i\f$.
294  ///
295  /// Note: if used before standardization, writes original AMPL formulation
296  void writeAMPL (const std::string &fname, bool aux);
297
298  /// Write nonlinear problem to a .gms file
299  ///
300  /// @param fname Name of the .gams file to be written.
301  void writeGAMS (const std::string &fname);
302
303  /// Initialize auxiliary variables and their bounds from original
304  /// variables
305  //void initAuxs (const CouNumber *, const CouNumber *, const CouNumber *);
306  void initAuxs () const;
307
308  /// Get auxiliary variables from original variables
309  void getAuxs (CouNumber *) const;
310
311  /// tighten bounds using propagation, implied bounds and reduced costs
312  bool boundTightening (t_chg_bounds *, 
313                        Bonmin::BabInfo * = NULL) const;
314
315  /// core of the bound tightening procedure
316  bool btCore (t_chg_bounds *chg_bds) const;
317
318  /// Optimality Based Bound Tightening
319  int obbt (const CouenneCutGenerator *cg,
320            const OsiSolverInterface &csi,
321            OsiCuts &cs,
322            const CglTreeInfo &info,
323            Bonmin::BabInfo * babInfo,
324            t_chg_bounds *chg_bds);
325
326  /// aggressive bound tightening. Fake bounds in order to cut
327  /// portions of the solution space by fathoming on
328  /// bounds/infeasibility
329  bool aggressiveBT (Bonmin::OsiTMINLPInterface *nlp,
330                     t_chg_bounds *, 
331                     Bonmin::BabInfo * = NULL) const;
332
333  /// procedure to strengthen variable bounds. Return false if problem
334  /// turns out to be infeasible with given bounds, true otherwise.
335  int redCostBT (const OsiSolverInterface *psi,
336                 t_chg_bounds *chg_bds) const;
337
338  /// "Forward" bound tightening, that is, propagate bound of variable
339  /// \f$x\f$ in an expression \f$w = f(x)\f$ to the bounds of \f$w\f$.
340  int tightenBounds (t_chg_bounds *) const;
341
342  /// "Backward" bound tightening, aka implied bounds.
343  int impliedBounds (t_chg_bounds *) const;
344
345  /// Look for quadratic terms to be used with SDP cuts
346  void fillQuadIndices ();
347
348  /// Fill vector with coefficients of objective function
349  void fillObjCoeff (double *&);
350
351  /// Replace all occurrences of original variable with new aux given
352  /// as argument
353  void auxiliarize (exprVar *, exprVar * = NULL);
354
355  /// Set cutoff
356  void setCutOff (CouNumber cutoff) const;
357
358  /// Set cutoff
359  CouNumber getCutOff () const
360  {return pcutoff_ -> getCutOff ();}
361
362  /// Make cutoff known to the problem
363  void installCutOff () const;
364
365  /// Provide Journalist
366  ConstJnlstPtr Jnlst() const 
367  {return ConstPtr(jnlst_);}
368
369  /// Check if solution is MINLP feasible
370  bool checkNLP (const double *solution, double &obj, bool recompute = false) const;
371
372  /// generate integer NLP point Y starting from fractional solution
373  /// using bound tightening
374  int getIntegerCandidate (const double *xFrac, double *xInt, double *lb, double *ub) const;
375
376  /// Read best known solution from file given in argument
377  bool readOptimum (std::string *fname = NULL);
378
379  /// Read cutoff value (for testing purposes)
380  void readCutoff (const std::string &fname);
381
382  /// Add list of options to be read from file
383  static void registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions);
384
385  /// standardization of linear exprOp's
386  exprAux *linStandardize (bool addAux, 
387                           CouNumber c0, 
388                           LinMap  &lmap,
389                           QuadMap &qmap);
390
391  /// split a constraint w - f(x) = c into w's index (it is returned)
392  /// and rest = f(x) + c
393  int splitAux (CouNumber, expression *, expression *&, bool *);
394
395  /// translates pair (indices, coefficients) into vector with pointers to variables
396  void indcoe2vector (int *indexL,
397                      CouNumber *coeff,
398                      std::vector <std::pair <exprVar *, CouNumber> > &lcoeff);
399
400  /// translates triplet (indicesI, indicesJ, coefficients) into vector with pointers to variables
401  void indcoe2vector (int *indexI,
402                      int *indexJ,
403                      CouNumber *coeff,
404                      std::vector <quadElem> &qcoeff);
405
406  /// given (expression *) element of sum, returns (coe,ind0,ind1)
407  /// depending on element:
408  ///
409  /// 1) a * x_i ^ 2   ---> (a,i,?)   return COU_EXPRPOW
410  /// 2) a * x_i       ---> (a,i,?)   return COU_EXPRVAR
411  /// 3) a * x_i * x_j ---> (a,i,j)   return COU_EXPRMUL
412  /// 4) a             ---> (a,?,?)   return COU_EXPRCONST
413  ///
414  /// x_i and/or x_j may come from standardizing other (linear or
415  /// quadratic operator) sub-expressions
416  void decomposeTerm (expression *term,
417                      CouNumber initCoe,
418                      CouNumber &c0,
419                      LinMap  &lmap,
420                      QuadMap &qmap);
421
422  /// return problem name
423  const std::string &problemName () const
424  {return problemName_;}
425
426  /// return inverse dependence structure
427  const std::vector <std::set <int> > &Dependence () const
428  {return dependence_;}
429
430  /// return object vector
431  const std::vector <CouenneObject> &Objects () const
432  {return objects_;}
433
434  /// find SOS constraints in problem
435  int findSOS (OsiSolverInterface *solver, OsiObject ** objects);
436
437  /// set maximum CPU time
438  inline void setMaxCpuTime (double time)
439  {maxCpuTime_ = time;}
440
441  /// return maximum CPU time
442  inline double getMaxCpuTime () const
443  {return maxCpuTime_;}
444
445protected:
446
447  /// single fake tightening. Return
448  ///
449  /// -1   if infeasible
450  ///  0   if no improvement
451  /// +1   if improved
452  int fake_tighten (char direction,  ///< 0: left, 1: right
453                    int index,       ///< index of the variable tested
454                    const double *X, ///< point round which tightening is done
455                    CouNumber *olb,  ///< cur. lower bound
456                    CouNumber *oub,  ///< cur. upper bound
457                    t_chg_bounds *chg_bds,
458                    t_chg_bounds *f_chg) const;
459
460  /// Optimality Based Bound Tightening -- inner loop
461  int obbtInner (CouenneSolverInterface *, 
462                 OsiCuts &,
463                 t_chg_bounds *, 
464                 Bonmin::BabInfo *) const;
465
466  int obbt_iter (CouenneSolverInterface *csi, 
467                 t_chg_bounds *chg_bds, 
468                 const CoinWarmStart *warmstart, 
469                 Bonmin::BabInfo *babInfo,
470                 double *objcoe,
471                 int sense, 
472                 int index) const;
473
474  int call_iter (CouenneSolverInterface *csi, 
475                 t_chg_bounds *chg_bds, 
476                 const CoinWarmStart *warmstart, 
477                 Bonmin::BabInfo *babInfo,
478                 double *objcoe,
479                 enum nodeType type,
480                 int sense) const;
481
482  /// analyze sparsity of potential exprQuad/exprGroup and change
483  /// linear/quadratic maps accordingly, if necessary by adding new
484  /// auxiliary variables and including them in the linear map
485  void analyzeSparsity (CouNumber, 
486                        LinMap &,
487                        QuadMap &);
488
489  /// re-organizes multiplication and stores indices (and exponents) of
490  /// its variables
491  void flattenMul (expression *mul, 
492                   CouNumber &coe, 
493                   std::map <int, CouNumber> &indices);
494
495  /// clear all spurious variables pointers not referring to the variables_ vector
496  void realign ();
497
498  /// fill dependence_ structure
499  void fillDependence (Bonmin::BabSetupBase *base);
500
501  /// fill freeIntegers_ array
502  void fillIntegerRank () const;
503
504  /// Test fixing of an integer variable (used in getIntegerCandidate())
505  int testIntFix (int index, 
506                  CouNumber xFrac, 
507                  enum fixType *fixed,
508                  CouNumber *xInt,
509                  CouNumber *dualL, CouNumber *dualR,
510                  CouNumber *olb,   CouNumber *oub,
511                  bool patient) const;
512};
513
514#endif
Note: See TracBrowser for help on using the repository browser.