source: trunk/include/CbcModel.hpp @ 94

Last change on this file since 94 was 94, checked in by forrest, 15 years ago

correct branch cut handling

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 45.2 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef CbcModel_H
4#define CbcModel_H
5
6#include <string>
7#include <vector>
8
9#include "CoinFinite.hpp"
10#include "CoinMessageHandler.hpp"
11#include "OsiSolverInterface.hpp"
12#include "OsiCuts.hpp"
13#include "CoinWarmStartBasis.hpp"
14#include "CbcCompareBase.hpp"
15#include "CbcMessage.hpp"
16
17//class OsiSolverInterface;
18
19class CbcCutGenerator;
20class OsiRowCut;
21class OsiRowCutDebugger;
22class CglCutGenerator;
23class CbcHeuristic;
24class CbcObject;
25class CbcTree;
26
27//#############################################################################
28
29/** Simple Branch and bound class
30
31  The initialSolve() method solves the initial LP relaxation of the MIP
32  problem. The branchAndBound() method can then be called to finish using
33  a branch and cut algorithm.
34
35  <h3>Search Tree Traversal</h3>
36
37  Subproblems (aka nodes) requiring additional evaluation are stored using
38  the CbcNode and CbcNodeInfo objects. Ancestry linkage is maintained in the
39  CbcNodeInfo object. Evaluation of a subproblem within branchAndBound()
40  proceeds as follows:
41  <ul>
42    <li> The node representing the most promising parent subproblem is popped
43         from the heap which holds the set of subproblems requiring further
44         evaluation.
45    <li> Using branching instructions stored in the node, and information in
46         its ancestors, the model and solver are adjusted to create the
47         active subproblem.
48    <li> If the parent subproblem will require further evaluation
49         (<i>i.e.</i>, there are branches remaining) its node is pushed back
50         on the heap. Otherwise, the node is deleted.  This may trigger
51         recursive deletion of ancestors.
52    <li> The newly created subproblem is evaluated.
53    <li> If the subproblem requires further evaluation, a node is created.
54         All information needed to recreate the subproblem (branching
55         information, row and column cuts) is placed in the node and the node
56         is added to the set of subproblems awaiting further evaluation.
57  </ul>
58  Note that there is never a node representing the active subproblem; the model
59  and solver represent the active subproblem.
60
61  <h3>Row (Constraint) Cut Handling</h3>
62
63  For a typical subproblem, the sequence of events is as follows:
64  <ul>
65    <li> The subproblem is rebuilt for further evaluation: One result of a
66         call to addCuts() is a traversal of ancestors, leaving a list of all
67         cuts used in the ancestors in #addedCuts_. This list is then scanned
68         to construct a basis that includes only tight cuts. Entries for
69         loose cuts are set to NULL.
70    <li> The subproblem is evaluated: One result of a call to solveWithCuts()
71         is the return of a set of newly generated cuts for the subproblem.
72         #addedCuts_ is also kept up-to-date as old cuts become loose.
73    <li> The subproblem is stored for further processing: A call to
74         CbcNodeInfo::addCuts() adds the newly generated cuts to the
75         CbcNodeInfo object associated with this node.
76  </ul>
77  See CbcCountRowCut for details of the bookkeeping associated with cut
78  management.
79*/
80
81class CbcModel  {
82 
83public:
84
85enum CbcIntParam {
86  /** The maximum number of nodes before terminating */
87  CbcMaxNumNode=0,
88  /** The maximum number of solutions before terminating */
89  CbcMaxNumSol,
90  /** Fathoming discipline
91
92    Controls objective function comparisons for purposes of fathoming by bound
93    or determining monotonic variables.
94
95    If 1, action is taken only when the current objective is strictly worse
96    than the target. Implementation is handled by adding a small tolerance to
97    the target.
98  */
99  CbcFathomDiscipline,
100  /** Just a marker, so that a static sized array can store parameters. */
101  CbcLastIntParam
102};
103
104enum CbcDblParam {
105  /** The maximum amount the value of an integer variable can vary from
106      integer and still be considered feasible. */
107  CbcIntegerTolerance=0,
108  /** The objective is assumed to worsen by this amount for each
109      integer infeasibility. */
110  CbcInfeasibilityWeight,
111  /** The amount by which to tighten the objective function cutoff when
112      a new solution is discovered. */
113  CbcCutoffIncrement,
114  /** Stop when the gap between the objective value of the best known solution
115    and the best bound on the objective of any solution is less than this.
116 
117    This is an absolute value. Conversion from a percentage is left to the
118    client.
119  */
120  CbcAllowableGap,
121  /** Stop when the gap between the objective value of the best known solution
122    and the best bound on the objective of any solution is less than this
123    fraction of of the absolute value of best known solution.
124 
125    Code stops if either this test or CbcAllowableGap test succeeds
126  */
127  CbcAllowableFractionGap,
128  /** \brief The maximum number of seconds before terminating.
129             A double should be adequate! */
130  CbcMaximumSeconds,
131  /** \brief The time at start of model.
132             So that other pieces of code can access */
133  CbcStartSeconds,
134  /** Just a marker, so that a static sized array can store parameters. */
135  CbcLastDblParam
136};
137
138  //---------------------------------------------------------------------------
139
140public:
141  ///@name Solve methods
142  //@{
143    /** \brief Solve the initial LP relaxation
144
145      Invoke the solver's %initialSolve() method.
146    */
147    void initialSolve(); 
148
149    /** \brief Invoke the branch \& cut algorithm
150
151      The method assumes that initialSolve() has been called to solve the
152      LP relaxation. It processes the root node, then proceeds to explore the
153      branch & cut search tree. The search ends when the tree is exhausted or
154      one of several execution limits is reached.
155    */
156     void branchAndBound();
157
158    /** \brief create a clean model from partially fixed problem
159
160      The method creates a new model with given bounds and with no tree.
161    */
162     CbcModel *  cleanModel(const double * lower, const double * upper);
163    /** \brief Invoke the branch \& cut algorithm on partially fixed problem
164
165      The method presolves the given model and does branch and cut. The search
166      ends when the tree is exhausted or maximum nodes is reached.
167
168      If better solution found then it is saved.
169
170      Returns 0 if search completed and solution, 1 if not completed and solution,
171      2 if completed and no solution, 3 if not completed and no solution.
172
173      Normally okay to do cleanModel immediately followed by subBranchandBound
174      (== other form of subBranchAndBound)
175      but may need to get at model for advanced features.
176
177      Deletes model2
178    */
179     int subBranchAndBound(CbcModel * model2,
180                           CbcModel * presolvedModel,
181                           int maximumNodes);
182    /** \brief Invoke the branch \& cut algorithm on partially fixed problem
183
184      The method creates a new model with given bounds, presolves it
185      then proceeds to explore the branch & cut search tree. The search
186      ends when the tree is exhausted or maximum nodes is reached.
187
188      If better solution found then it is saved.
189
190      Returns 0 if search completed and solution, 1 if not completed and solution,
191      2 if completed and no solution, 3 if not completed and no solution.
192
193      This is just subModel immediately followed by other version of
194      subBranchandBound.
195
196    */
197     int subBranchAndBound(const double * lower, const double * upper,
198                            int maximumNodes);
199
200    /** \brief Process root node and return a strengthened model
201
202      The method assumes that initialSolve() has been called to solve the
203      LP relaxation. It processes the root node and then returns a pointer
204      to the strengthened model (or NULL if infeasible)
205    */
206     OsiSolverInterface *  strengthenedModel();
207    /** \brief Evaluate a subproblem using cutting planes and heuristics
208
209      The method invokes a main loop which generates cuts, applies heuristics,
210      and reoptimises using the solver's native %resolve() method.
211      It returns true if the subproblem remains feasible at the end of the
212      evaluation.
213    */
214    bool solveWithCuts(OsiCuts & cuts, int numberTries,CbcNode * node,
215                       int & numberOldActiveCuts, int & numberNewCuts,
216                       int & maximumWhich, int * & whichGenerator);
217
218    /** \brief Reoptimise an LP relaxation
219   
220      Invoke the solver's %resolve() method.
221    */
222    bool resolve();
223  //@}
224
225  /** \name Presolve methods */
226  //@{
227
228  /** Identify cliques and construct corresponding objects.
229
230      Find cliques with size in the range
231      [\p atLeastThisMany, \p lessThanThis] and construct corresponding
232      CbcClique objects.
233      If \p makeEquality is true then a new model may be returned if
234      modifications had to be made, otherwise \c this is returned.
235      If the problem is infeasible #numberObjects_ is set to -1.
236      A client must use deleteObjects() before a second call to findCliques().
237      If priorities exist, clique priority is set to the default.
238  */
239  CbcModel * findCliques(bool makeEquality, int atLeastThisMany,
240                         int lessThanThis, int defaultValue=1000);
241
242  /** Do integer presolve, creating a new (presolved) model.
243
244    Returns the new model, or NULL if feasibility is lost.
245    If weak is true then just does a normal presolve
246 
247    \todo It remains to work out the cleanest way of getting a solution to
248          the original problem at the end. So this is very preliminary.
249   */
250  CbcModel * integerPresolve(bool weak=false);
251
252  /** Do integer presolve, modifying the current model.
253
254      Returns true if the model remains feasible after presolve.
255  */
256  bool integerPresolveThisModel(OsiSolverInterface * originalSolver,bool weak=false);
257
258
259  /// Put back information into the original model after integer presolve.
260  void originalModel(CbcModel * presolvedModel,bool weak);
261
262  /** \brief For variables involved in VUB constraints, see if we can tighten
263             bounds by solving lp's
264
265      Returns false if feasibility is lost.
266      If CglProbing is available, it will be tried as well to see if it can
267      tighten bounds.
268      This routine is just a front end for tightenVubs(int,const int*,double).
269
270      If <tt>type = -1</tt> all variables are processed (could be very slow).
271      If <tt>type = 0</tt> only variables involved in VUBs are processed.
272      If <tt>type = n > 0</tt>, only the n most expensive VUB variables
273      are processed, where it is assumed that x is at its maximum so delta
274      would have to go to 1 (if x not at bound).
275
276      If \p allowMultipleBinary is true, then a VUB constraint is a row with
277      one continuous variable and any number of binary variables.
278
279      If <tt>useCutoff < 1.0e30</tt>, the original objective is installed as a
280      constraint with \p useCutoff as a bound.
281  */
282  bool tightenVubs(int type,bool allowMultipleBinary=false,
283                   double useCutoff=1.0e50);
284 
285  /** \brief For variables involved in VUB constraints, see if we can tighten
286             bounds by solving lp's
287
288    This version is just handed a list of variables to be processed.
289  */
290  bool tightenVubs(int numberVubs, const int * which,
291                   double useCutoff=1.0e50);
292  /**
293    Analyze problem to find a minimum change in the objective function.
294  */
295  void analyzeObjective();
296
297
298  //@}
299
300  /** \name Object manipulation routines
301 
302    See CbcObject for an explanation of `object' in the context of CbcModel.
303  */
304  //@{
305
306  /// Get the number of objects
307  inline int numberObjects() const { return numberObjects_;};
308  /// Set the number of objects
309  inline void setNumberObjects(int number) 
310  {  numberObjects_=number;};
311
312  /// Get the array of objects
313  inline CbcObject ** objects() const { return object_;};
314
315  /// Get the specified object
316  const inline CbcObject * object(int which) const { return object_[which];};
317
318  /// Delete all object information
319  void deleteObjects();
320
321  /** Add in object information.
322 
323    Objects are cloned; the owner can delete the originals.
324  */
325  void addObjects(int numberObjects, CbcObject ** objects);
326
327  /// Ensure attached objects point to this model.
328  void synchronizeModel() ;
329
330  /** \brief Identify integer variables and create corresponding objects.
331 
332    Record integer variables and create an CbcSimpleInteger object for each
333    one.
334    If \p startAgain is true, a new scan is forced, overwriting any existing
335    integer variable information.
336  */
337
338  void findIntegers(bool startAgain);
339 
340  //@}
341
342  //---------------------------------------------------------------------------
343
344  /**@name Parameter set/get methods
345
346     The set methods return true if the parameter was set to the given value,
347     false if the value of the parameter is out of range.
348
349     The get methods return the value of the parameter.
350
351  */
352  //@{
353  /// Set an integer parameter
354  inline bool setIntParam(CbcIntParam key, int value) {
355    intParam_[key] = value;
356    return true;
357  }
358  /// Set a double parameter
359  inline bool setDblParam(CbcDblParam key, double value) {
360    dblParam_[key] = value;
361    return true;
362  }
363  /// Get an integer parameter
364  inline int getIntParam(CbcIntParam key) const {
365    return intParam_[key];
366  }
367  /// Get a double parameter
368  inline double getDblParam(CbcDblParam key) const {
369    return dblParam_[key];
370  }
371  /*! \brief Set cutoff bound on the objective function.
372
373    When using strict comparison, the bound is adjusted by a tolerance to
374    avoid accidentally cutting off the optimal solution.
375  */
376  void setCutoff(double value) ;
377
378  /// Get the cutoff bound on the objective function - always as minimize
379  inline double getCutoff() const
380  { double value ;
381    solver_->getDblParam(OsiDualObjectiveLimit,value) ;
382    return value * solver_->getObjSense() ; } ;
383
384  /// Set the \link CbcModel::CbcMaxNumNode maximum node limit \endlink
385  inline bool setMaximumNodes( int value)
386  { return setIntParam(CbcMaxNumNode,value); }
387
388  /// Get the \link CbcModel::CbcMaxNumNode maximum node limit \endlink
389  inline int getMaximumNodes() const
390  { return getIntParam(CbcMaxNumNode); }
391
392  /** Set the
393      \link CbcModel::CbcMaxNumSol maximum number of solutions \endlink
394      desired.
395  */
396  inline bool setMaximumSolutions( int value) {
397    return setIntParam(CbcMaxNumSol,value);
398  }
399  /** Get the
400      \link CbcModel::CbcMaxNumSol maximum number of solutions \endlink
401      desired.
402  */
403  inline int getMaximumSolutions() const {
404    return getIntParam(CbcMaxNumSol);
405  }
406
407  /** Set the
408      \link CbcModel::CbcMaximumSeconds maximum number of seconds \endlink
409      desired.
410  */
411  inline bool setMaximumSeconds( double value) {
412    return setDblParam(CbcMaximumSeconds,value);
413  }
414  /** Get the
415      \link CbcModel::CbcMaximumSeconds maximum number of seconds \endlink
416      desired.
417  */
418  inline double getMaximumSeconds() const {
419    return getDblParam(CbcMaximumSeconds);
420  }
421
422  /** Set the
423    \link CbcModel::CbcIntegerTolerance integrality tolerance \endlink
424  */
425  inline bool setIntegerTolerance( double value) {
426    return setDblParam(CbcIntegerTolerance,value);
427  }
428  /** Get the
429    \link CbcModel::CbcIntegerTolerance integrality tolerance \endlink
430  */
431  inline double getIntegerTolerance() const {
432    return getDblParam(CbcIntegerTolerance);
433  }
434
435  /** Set the
436      \link CbcModel::CbcInfeasibilityWeight
437            weight per integer infeasibility \endlink
438  */
439  inline bool setInfeasibilityWeight( double value) {
440    return setDblParam(CbcInfeasibilityWeight,value);
441  }
442  /** Get the
443      \link CbcModel::CbcInfeasibilityWeight
444            weight per integer infeasibility \endlink
445  */
446  inline double getInfeasibilityWeight() const {
447    return getDblParam(CbcInfeasibilityWeight);
448  }
449
450  /** Set the \link CbcModel::CbcAllowableGap allowable gap \endlink
451      between the best known solution and the best possible solution.
452  */
453  inline bool setAllowableGap( double value) {
454    return setDblParam(CbcAllowableGap,value);
455  }
456  /** Get the \link CbcModel::CbcAllowableGap allowable gap \endlink
457      between the best known solution and the best possible solution.
458  */
459  inline double getAllowableGap() const {
460    return getDblParam(CbcAllowableGap);
461  }
462
463  /** Set the \link CbcModel::CbcAllowableFractionGap fraction allowable gap \endlink
464      between the best known solution and the best possible solution.
465  */
466  inline bool setAllowableFractionGap( double value) {
467    return setDblParam(CbcAllowableFractionGap,value);
468  }
469  /** Get the \link CbcModel::CbcAllowableFractionGap fraction allowable gap \endlink
470      between the best known solution and the best possible solution.
471  */
472  inline double getAllowableFractionGap() const {
473    return getDblParam(CbcAllowableFractionGap);
474  }
475  /** Set the \link CbcModel::CbcAllowableFractionGap percentage allowable gap \endlink
476      between the best known solution and the best possible solution.
477  */
478  inline bool setAllowablePercentageGap( double value) {
479    return setDblParam(CbcAllowableFractionGap,value*0.01);
480  }
481  /** Get the \link CbcModel::CbcAllowableFractionGap percentage allowable gap \endlink
482      between the best known solution and the best possible solution.
483  */
484  inline double getAllowablePercentageGap() const {
485    return 100.0*getDblParam(CbcAllowableFractionGap);
486  }
487
488  /// Set the hotstart strategy
489  void setHotstartStrategy(int value) 
490  { hotstartStrategy_=value;};
491  /// Get the hotstart strategy
492  int getHotstartStrategy() const
493  { return hotstartStrategy_;};
494 
495  /// Set the minimum drop to continue cuts
496  inline void setMinimumDrop(double value)
497  {minimumDrop_=value;};
498  /// Get the minimum drop to continue cuts
499  inline double getMinimumDrop() const
500  { return minimumDrop_;};
501
502  /** Set the maximum number of cut passes at root node (default 20)
503      Minimum drop can also be used for fine tuning */
504  inline void setMaximumCutPassesAtRoot(int value)
505  {maximumCutPassesAtRoot_=value;};
506  /** Get the maximum number of cut passes at root node */
507  inline int getMaximumCutPassesAtRoot() const
508  { return maximumCutPassesAtRoot_;};
509
510  /** Set the maximum number of cut passes at other nodes (default 10)
511      Minimum drop can also be used for fine tuning */
512  inline void setMaximumCutPasses(int value)
513  {maximumCutPasses_=value;};
514  /** Get the maximum number of cut passes at other nodes (default 10) */
515  inline int getMaximumCutPasses() const
516  { return maximumCutPasses_;};
517  /** Get current cut pass number in this round of cuts.
518      (1 is first pass) */
519  inline int getCurrentPassNumber() const
520  { return currentPassNumber_;};
521
522  /** Set the maximum number of candidates to be evaluated for strong
523    branching.
524
525    A value of 0 disables strong branching.
526  */
527  void setNumberStrong(int number);
528  /** Get the maximum number of candidates to be evaluated for strong
529    branching.
530  */
531  inline int numberStrong() const
532  { return numberStrong_;};
533
534  /// Set how often to scan global cuts
535  void setHowOftenGlobalScan(int number);
536  /// Get how often to scan global cuts
537  inline int howOftenGlobalScan() const
538  { return howOftenGlobalScan_;};
539
540  /** Set the print frequency.
541 
542    Controls the number of nodes evaluated between status prints.
543    If <tt>number <=0</tt> the print frequency is set to 100 nodes for large
544    problems, 1000 for small problems.
545    Print frequency has very slight overhead if small.
546  */
547  void setPrintFrequency(int number)
548  { printFrequency_=number;};
549  /// Get the print frequency
550  inline int printFrequency() const
551  { return printFrequency_;};
552  //@}
553
554  //---------------------------------------------------------------------------
555  ///@name Methods returning info on how the solution process terminated
556  //@{
557    /// Are there a numerical difficulties?
558    bool isAbandoned() const;
559    /// Is optimality proven?
560    bool isProvenOptimal() const;
561    /// Is  infeasiblity proven (or none better than cutoff)?
562    bool isProvenInfeasible() const;
563    /// Node limit reached?
564    bool isNodeLimitReached() const;
565    /// Solution limit reached?
566    bool isSolutionLimitReached() const;
567    /// Get how many iterations it took to solve the problem.
568    int getIterationCount() const
569    { return solver_->getIterationCount();};
570    /// Get how many Nodes it took to solve the problem.
571    int getNodeCount() const
572    { return numberNodes_;};
573    /** Final status of problem
574   
575      0 finished, 1 stopped, 2 difficulties
576    */
577    inline int status() const
578    { return status_;};
579 
580  //@}
581
582  //---------------------------------------------------------------------------
583  /**@name Problem information methods
584     
585     These methods call the solver's query routines to return
586     information about the problem referred to by the current object.
587     Querying a problem that has no data associated with it result in
588     zeros for the number of rows and columns, and NULL pointers from
589     the methods that return vectors.
590     
591     Const pointers returned from any data-query method are valid as
592     long as the data is unchanged and the solver is not called.
593  */
594  //@{
595  /// Number of rows in continuous (root) problem.
596  int numberRowsAtContinuous() const
597  { return numberRowsAtContinuous_;};
598
599  /// Get number of columns
600  int getNumCols() const
601  { return solver_->getNumCols();};
602 
603  /// Get number of rows
604  int getNumRows() const
605  { return solver_->getNumRows();};
606 
607  /// Get number of nonzero elements
608  int getNumElements() const
609  { return solver_->getNumElements();};
610
611  /// Number of integers in problem
612  inline int numberIntegers() const
613  { return numberIntegers_;};
614  // Integer variables
615  inline const int * integerVariable() const 
616  { return integerVariable_;};
617 
618  /// Get pointer to array[getNumCols()] of column lower bounds
619  const double * getColLower() const
620  { return solver_->getColLower();};
621 
622  /// Get pointer to array[getNumCols()] of column upper bounds
623  const double * getColUpper() const
624  { return solver_->getColUpper();};
625 
626  /** Get pointer to array[getNumRows()] of row constraint senses.
627      <ul>
628      <li>'L': <= constraint
629      <li>'E': =  constraint
630      <li>'G': >= constraint
631      <li>'R': ranged constraint
632      <li>'N': free constraint
633      </ul>
634  */
635  const char * getRowSense() const
636  { return solver_->getRowSense();};
637 
638  /** Get pointer to array[getNumRows()] of rows right-hand sides
639      <ul>
640      <li> if rowsense()[i] == 'L' then rhs()[i] == rowupper()[i]
641      <li> if rowsense()[i] == 'G' then rhs()[i] == rowlower()[i]
642      <li> if rowsense()[i] == 'R' then rhs()[i] == rowupper()[i]
643      <li> if rowsense()[i] == 'N' then rhs()[i] == 0.0
644      </ul>
645  */
646  const double * getRightHandSide() const
647  { return solver_->getRightHandSide();};
648 
649  /** Get pointer to array[getNumRows()] of row ranges.
650      <ul>
651      <li> if rowsense()[i] == 'R' then
652      rowrange()[i] == rowupper()[i] - rowlower()[i]
653      <li> if rowsense()[i] != 'R' then
654      rowrange()[i] is 0.0
655      </ul>
656  */
657  const double * getRowRange() const
658  { return solver_->getRowRange();};
659 
660  /// Get pointer to array[getNumRows()] of row lower bounds
661  const double * getRowLower() const
662  { return solver_->getRowLower();};
663 
664  /// Get pointer to array[getNumRows()] of row upper bounds
665  const double * getRowUpper() const
666  { return solver_->getRowUpper();};
667 
668  /// Get pointer to array[getNumCols()] of objective function coefficients
669  const double * getObjCoefficients() const
670  { return solver_->getObjCoefficients();};
671 
672  /// Get objective function sense (1 for min (default), -1 for max)
673  double getObjSense() const
674  { return solver_->getObjSense();};
675 
676  /// Return true if variable is continuous
677  bool isContinuous(int colIndex) const
678  { return solver_->isContinuous(colIndex);};
679 
680  /// Return true if variable is binary
681  bool isBinary(int colIndex) const
682  { return solver_->isBinary(colIndex);};
683 
684  /** Return true if column is integer.
685      Note: This function returns true if the the column
686      is binary or a general integer.
687  */
688  bool isInteger(int colIndex) const
689  { return solver_->isInteger(colIndex);};
690 
691  /// Return true if variable is general integer
692  bool isIntegerNonBinary(int colIndex) const
693  { return solver_->isIntegerNonBinary(colIndex);};
694 
695  /// Return true if variable is binary and not fixed at either bound
696  bool isFreeBinary(int colIndex) const
697  { return solver_->isFreeBinary(colIndex) ;};
698 
699  /// Get pointer to row-wise copy of matrix
700  const CoinPackedMatrix * getMatrixByRow() const
701  { return solver_->getMatrixByRow();};
702 
703  /// Get pointer to column-wise copy of matrix
704  const CoinPackedMatrix * getMatrixByCol() const
705  { return solver_->getMatrixByCol();};
706 
707  /// Get solver's value for infinity
708  double getInfinity() const
709  { return solver_->getInfinity();};
710  //@}
711 
712 
713  /**@name Methods related to querying the solution */
714  //@{
715  /// Record a new incumbent solution and update objectiveValue
716  void setBestSolution(CBC_Message how,
717                       double & objectiveValue, const double *solution,
718                       bool fixVariables=false);
719  /// Just update objectiveValue
720  void setBestObjectiveValue( double objectiveValue);
721
722  /** Call this to really test if a valid solution can be feasible
723      Solution is number columns in size.
724      If fixVariables true then bounds of continuous solver updated.
725      Returns objective value (worse than cutoff if not feasible)
726 */
727  double checkSolution(double cutoff, const double * solution,
728                       bool fixVariables);
729  /** Test the current solution for feasiblility.
730
731    Scan all objects for indications of infeasibility. This is broken down
732    into simple integer infeasibility (\p numberIntegerInfeasibilities)
733    and all other reports of infeasibility (\p numberObjectInfeasibilities).
734  */
735  bool feasibleSolution(int & numberIntegerInfeasibilities,
736                        int & numberObjectInfeasibilities) const;
737
738  /** Solution to the most recent lp relaxation.
739
740    The solver's solution to the most recent lp relaxation.
741  */
742   
743  inline double * currentSolution() const
744  { return currentSolution_;};
745  /// Make sure region there
746  void reserveCurrentSolution();
747
748  /// Get pointer to array[getNumCols()] of primal solution vector
749  inline const double * getColSolution() const
750  { return solver_->getColSolution();};
751 
752  /// Get pointer to array[getNumRows()] of dual prices
753  inline const double * getRowPrice() const
754  { return solver_->getRowPrice();};
755 
756  /// Get a pointer to array[getNumCols()] of reduced costs
757  inline const double * getReducedCost() const
758  { return solver_->getReducedCost();};
759 
760  /// Get pointer to array[getNumRows()] of row activity levels.
761  inline const double * getRowActivity() const
762  { return solver_->getRowActivity();};
763 
764  /// Get current objective function value
765  inline double getCurrentObjValue() const
766  { return solver_->getObjValue();};
767 
768  /// Get best objective function value as minimization
769  inline double getMinimizationObjValue() const
770  { return bestObjective_;};
771  /// Set best objective function value as minimization
772  inline void setMinimizationObjValue(double value) 
773  { bestObjective_=value;};
774 
775  /// Get best objective function value
776  inline double getObjValue() const
777  { return bestObjective_ * solver_->getObjSense() ; } ;
778  /** Get best possible objective function value.
779      This is better of best possible left on tree
780      and best solution found.
781      If called from within branch and cut may be optimistic.
782  */
783  double getBestPossibleObjValue() const;
784  /// Set best objective function value
785  inline void setObjValue(double value) 
786  { bestObjective_=value * solver_->getObjSense() ;};
787 
788  /** The best solution to the integer programming problem.
789
790    The best solution to the integer programming problem found during
791    the search. If no solution is found, the method returns null.
792  */
793
794  double * bestSolution() const
795  { return bestSolution_;};
796 
797  /// Get number of solutions
798  int getSolutionCount() const
799  { return numberSolutions_;};
800 
801  /// Set number of solutions (so heuristics will be different)
802  void setSolutionCount(int value) 
803  { numberSolutions_=value;};
804  /** Current phase (so heuristics etc etc can find out).
805      0 - initial solve
806      1 - solve with cuts at root
807      2 - solve with cuts
808      3 - other e.g. strong branching
809      4 - trying to validate a solution
810      5 - at end of search
811  */
812  inline int phase() const
813  { return phase_;};
814 
815  /// Get number of heuristic solutions
816  int getNumberHeuristicSolutions() const { return numberHeuristicSolutions_;};
817
818  /// Set objective function sense (1 for min (default), -1 for max,)
819  void setObjSense(double s) { solver_->setObjSense(s);};
820
821  /// Value of objective at continuous
822  inline double getContinuousObjective() const
823  { return originalContinuousObjective_;};
824  inline void setContinuousObjective(double value)
825  { originalContinuousObjective_=value;};
826  /// Number of infeasibilities at continuous
827  inline int getContinuousInfeasibilities() const
828  { return continuousInfeasibilities_;};
829  inline void setContinuousInfeasibilities(int value)
830  { continuousInfeasibilities_=value;};
831  /// Value of objective after root node cuts added
832  inline double rootObjectiveAfterCuts() const
833  { return continuousObjective_;};
834  /** Number of times global cuts violated.  When global cut pool then this
835      should be kept for each cut and type of cut */
836  inline int numberGlobalViolations() const
837  { return numberGlobalViolations_;};
838  inline void clearNumberGlobalViolations()
839  { numberGlobalViolations_=0;};
840  /// Whether to force a resolve after takeOffCuts
841  inline bool resolveAfterTakeOffCuts() const
842  { return resolveAfterTakeOffCuts_;};
843  inline void setResolveAfterTakeOffCuts(bool yesNo)
844  { resolveAfterTakeOffCuts_=yesNo;};
845  //@}
846
847  /** \name Node selection */
848  //@{
849  // Comparison functions (which may be overridden by inheritance)
850  inline CbcCompareBase * nodeComparison() const
851  { return nodeCompare_;};
852  inline void setNodeComparison(CbcCompareBase * compare)
853  { nodeCompare_ = compare;};
854  inline void setNodeComparison(CbcCompareBase & compare)
855  { nodeCompare_ = &compare;};
856  //@}
857
858  /** \name Tree methods and subtree methods */
859  //@{
860  /// Tree method e.g. heap (which may be overridden by inheritance)
861  inline CbcTree * tree() const
862  { return tree_;};
863  /// For modifying tree handling (original is cloned)
864  void passInTreeHandler(CbcTree & tree);
865  /** For passing in an CbcModel to do a sub Tree (with derived tree handlers).
866      Passed in model must exist for duration of branch and bound
867  */
868  void passInSubTreeModel(CbcModel & model);
869  /** For retrieving a copy of subtree model with given OsiSolver.
870      If no subtree model will use self (up to user to reset cutoff etc).
871      If solver NULL uses current
872  */
873  CbcModel * subTreeModel(OsiSolverInterface * solver=NULL) const;
874  /// Returns number of times any subtree stopped on nodes, time etc
875  inline int numberStoppedSubTrees() const
876  { return numberStoppedSubTrees_;}
877  /// Says a sub tree was stopped
878  inline void incrementSubTreeStopped()
879  { numberStoppedSubTrees_++;};
880  /** Whether to automatically do presolve before branch and bound (subTrees).
881      0 - no
882      1 - ordinary presolve
883      2 - integer presolve (dodgy)
884  */
885  inline int typePresolve() const
886  { return presolve_;};
887  inline void setTypePresolve(int value)
888  { presolve_=value;};
889  //@}
890
891  /** \name Branching Decisions
892 
893    See the CbcBranchDecision class for additional information.
894  */
895  //@{
896
897  /// Get the current branching decision method.
898  inline CbcBranchDecision * branchingMethod() const
899  { return branchingMethod_;};
900  /// Set the branching decision method.
901  inline void setBranchingMethod(CbcBranchDecision * method)
902  { branchingMethod_ = method;};
903  /** Set the branching method
904 
905    \overload
906  */
907  inline void setBranchingMethod(CbcBranchDecision & method)
908  { branchingMethod_ = &method;};
909  //@}
910
911  /** \name Row (constraint) and Column (variable) cut generation */
912  //@{
913
914  /** Perform reduced cost fixing
915
916    Fixes integer variables at their current value based on reduced cost
917    penalties.
918  */
919  void reducedCostFix() ;
920
921  /** Return an empty basis object of the specified size
922
923    A useful utility when constructing a basis for a subproblem from scratch.
924    The object returned will be of the requested capacity and appropriate for
925    the solver attached to the model.
926  */
927  CoinWarmStartBasis *getEmptyBasis(int ns = 0, int na = 0) const ;
928
929  /** Remove inactive cuts from the model
930
931    An OsiSolverInterface is expected to maintain a valid basis, but not a
932    valid solution, when loose cuts are deleted. Restoring a valid solution
933    requires calling the solver to reoptimise. If it's certain the solution
934    will not be required, set allowResolve to false to suppress
935    reoptimisation.
936  */
937  void takeOffCuts(OsiCuts &cuts, int *whichGenerator,
938                     int &numberOldActiveCuts, int &numberNewCuts,
939                     bool allowResolve) ;
940
941  /** Determine and install the active cuts that need to be added for
942    the current subproblem
943
944    The whole truth is a bit more complicated. The first action is a call to
945    addCuts1(). addCuts() then sorts through the list, installs the tight
946    cuts in the model, and does bookkeeping (adjusts reference counts).
947    The basis returned from addCuts1() is adjusted accordingly.
948   
949    If it turns out that the node should really be fathomed by bound,
950    addCuts() simply treats all the cuts as loose as it does the bookkeeping.
951  */
952  int addCuts(CbcNode * node, CoinWarmStartBasis *&lastws);
953
954  /** Traverse the tree from node to root and prep the model
955
956    addCuts1() begins the job of prepping the model to match the current
957    subproblem. The model is stripped of all cuts, and the search tree is
958    traversed from node to root to determine the changes required. Appropriate
959    bounds changes are installed, a list of cuts is collected but not
960    installed, and an appropriate basis (minus the cuts, but big enough to
961    accommodate them) is constructed.
962
963    \todo addCuts1() is called in contexts where it's known in advance that
964          all that's desired is to determine a list of cuts and do the
965          bookkeeping (adjust the reference counts). The work of installing
966          bounds and building a basis goes to waste.
967  */
968  void addCuts1(CbcNode * node, CoinWarmStartBasis *&lastws);
969
970  /// Return the list of cuts initially collected for this subproblem
971  CbcCountRowCut ** addedCuts() const
972  { return addedCuts_;};
973  /// Number of entries in the list returned by #addedCuts()
974  int currentNumberCuts() const
975  { return currentNumberCuts_;};
976  /// Global cuts
977  inline OsiCuts * globalCuts() 
978  { return &globalCuts_;};
979  /// Copy and set a pointer to a row cut which will be added instead of normal branching.
980  void setNextRowCut(const OsiRowCut & cut);
981  /// Get a pointer to current node (be careful)
982  inline CbcNode * currentNode() const
983  { return currentNode_;};
984
985  /// Get the number of cut generators
986  inline int numberCutGenerators() const
987  { return numberCutGenerators_;};
988  /// Get the list of cut generators
989  inline CbcCutGenerator ** cutGenerators() const
990  { return generator_;};
991  ///Get the specified cut generator
992  inline CbcCutGenerator * cutGenerator(int i) const
993  { return generator_[i];};
994  ///Get the specified cut generator before any changes
995  inline CbcCutGenerator * virginCutGenerator(int i) const
996  { return virginGenerator_[i];};
997  /** Add one generator - up to user to delete generators.
998      howoften affects how generator is used. 0 or 1 means always,
999      >1 means every that number of nodes.  Negative values have same
1000      meaning as positive but they may be switched off (-> -100) by code if
1001      not many cuts generated at continuous.  -99 is just done at root.
1002      Name is just for printout.
1003      If depth >0 overrides how often generator is called (if howOften==-1 or >0).
1004  */
1005  void addCutGenerator(CglCutGenerator * generator,
1006                       int howOften=1, const char * name=NULL,
1007                       bool normal=true, bool atSolution=false, 
1008                       bool infeasible=false,int howOftenInSub=-100,
1009                       int whatDepth=-1, int whatDepthInSub=-1);
1010//@}
1011
1012  /** \name Heuristics and priorities */
1013  //@{
1014  /// Add one heuristic - up to user to delete
1015  void addHeuristic(CbcHeuristic * generator);
1016  ///Get the specified heuristic
1017  inline CbcHeuristic * heuristic(int i) const
1018  { return heuristic_[i];};
1019
1020  /** Pass in branching priorities.
1021 
1022      If ifClique then priorities are on cliques otherwise priorities are
1023      on integer variables. 
1024      Other type (if exists set to default)
1025      1 is highest priority. (well actually -INT_MAX is but that's ugly)
1026      If hotstart > 0 then branches are created to force
1027      the variable to the value given by best solution.  This enables a
1028      sort of hot start.  The node choice should be greatest depth
1029      and hotstart should normally be switched off after a solution.
1030
1031      If ifNotSimpleIntegers true then appended to normal integers
1032
1033      \internal Added for Kurt Spielberg.
1034  */
1035  void passInPriorities(const int * priorities, bool ifNotSimpleIntegers,
1036                        int defaultValue=1000);
1037
1038  /// Priorities
1039  inline const int * priority() const { return priority_;};
1040
1041  /// Returns priority level for an object (or 1000 if no priorities exist)
1042  inline int priority(int sequence) const
1043  { 
1044    if (priority_)
1045      return priority_[sequence];
1046    else
1047      return 1000;
1048  };
1049  //@}
1050   
1051  /**@name Setting/Accessing application data */
1052  //@{
1053    /** Set application data.
1054
1055        This is a pointer that the application can store into and
1056        retrieve from the solver interface.
1057        This field is available for the application to optionally
1058        define and use.
1059    */
1060    void setApplicationData (void * appData);
1061
1062    /// Get application data
1063    void * getApplicationData() const;
1064  //@}
1065 
1066  //---------------------------------------------------------------------------
1067
1068  /**@name Message handling */
1069  //@{
1070  /// Pass in Message handler (not deleted at end)
1071  void passInMessageHandler(CoinMessageHandler * handler);
1072  /// Set language
1073  void newLanguage(CoinMessages::Language language);
1074  inline void setLanguage(CoinMessages::Language language)
1075  {newLanguage(language);};
1076  /// Return handler
1077  inline CoinMessageHandler * messageHandler() const
1078  {return handler_;};
1079  /// Return messages
1080  inline CoinMessages messages() 
1081  {return messages_;};
1082  /// Return pointer to messages
1083  inline CoinMessages * messagesPointer() 
1084  {return &messages_;};
1085  /// Set log level
1086  inline void setLogLevel(int value)
1087  { handler_->setLogLevel(value);};
1088  /// Get log level
1089  inline int logLevel() const
1090  { return handler_->logLevel();};
1091  //@}
1092  //---------------------------------------------------------------------------
1093
1094
1095  ///@name Constructors and destructors etc
1096  //@{
1097    /// Default Constructor
1098    CbcModel(); 
1099   
1100    /// Constructor from solver
1101    CbcModel(const OsiSolverInterface &);
1102 
1103    /** Assign a solver to the model (model assumes ownership)
1104
1105      On return, \p solver will be NULL.
1106
1107      \note Parameter settings in the outgoing solver are not inherited by
1108            the incoming solver.
1109    */
1110    void assignSolver(OsiSolverInterface *&solver);
1111 
1112    /** Copy constructor .
1113      If noTree is true then tree and cuts are not copied
1114    */ 
1115    CbcModel(const CbcModel & rhs, bool noTree=false);
1116 
1117    /// Assignment operator
1118    CbcModel & operator=(const CbcModel& rhs);
1119 
1120    /// Destructor
1121     ~CbcModel ();
1122
1123    /// Returns solver - has current state
1124    OsiSolverInterface * solver() const
1125    { return solver_;};
1126
1127    /// Returns solver with continuous state
1128    OsiSolverInterface * continuousSolver() const
1129    { return continuousSolver_;};
1130  /// Clears out as much as possible (except solver)
1131  void gutsOfDestructor();
1132  //@}
1133
1134//---------------------------------------------------------------------------
1135
1136private:
1137  ///@name Private member data
1138  //@{
1139
1140  /// The solver associated with this model.
1141  OsiSolverInterface * solver_;
1142
1143  /** Ownership of the solver object
1144
1145    The convention is that CbcModel owns the null solver. Currently there
1146    is no public method to give CbcModel a solver without giving ownership,
1147    but the hook is here.
1148  */
1149  bool ourSolver_ ;
1150
1151  /// A copy of the solver, taken at the continuous (root) node.
1152  OsiSolverInterface * continuousSolver_;
1153
1154   /// Message handler
1155  CoinMessageHandler * handler_;
1156
1157  /** Flag to say if handler_ is the default handler.
1158 
1159    The default handler is deleted when the model is deleted. Other
1160    handlers (supplied by the client) will not be deleted.
1161  */
1162  bool defaultHandler_;
1163
1164  /// Cbc messages
1165  CoinMessages messages_;
1166
1167  /// Array for integer parameters
1168  int intParam_[CbcLastIntParam];
1169
1170  /// Array for double parameters
1171  double dblParam_[CbcLastDblParam];
1172
1173  /** Pointer to an empty warm start object
1174
1175    It turns out to be useful to have this available as a base from
1176    which to build custom warm start objects. This is typed as CoinWarmStart
1177    rather than CoinWarmStartBasis to allow for the possibility that a
1178    client might want to apply a solver that doesn't use a basis-based warm
1179    start. See getEmptyBasis for an example of how this field can be used.
1180  */
1181  mutable CoinWarmStart *emptyWarmStart_ ;
1182
1183  /** Pointer to a warm start basis.  */
1184  CoinWarmStartBasis *basis_;
1185
1186  /// Best objective
1187  double bestObjective_;
1188  /// Best possible objective
1189  double bestPossibleObjective_;
1190
1191  /// Array holding the incumbent (best) solution.
1192  double * bestSolution_;
1193
1194  /** Array holding the current solution.
1195
1196    This array is used more as a temporary.
1197  */
1198  double * currentSolution_;
1199
1200  /// Global cuts
1201  OsiCuts globalCuts_;
1202
1203  /// Minimum degradation in objective value to continue cut generation
1204  double minimumDrop_;
1205  /// Number of solutions
1206  int numberSolutions_;
1207  /// Hotstart strategy 0 =off, 1=branch if incorrect,2=branch even if correct, ....
1208  int hotstartStrategy_;
1209  /// Number of heuristic solutions
1210  int numberHeuristicSolutions_;
1211  /// Cumulative number of nodes
1212  int numberNodes_;
1213  /// Cumulative number of iterations
1214  int numberIterations_;
1215  /// Status of problem - 0 finished, 1 stopped, 2 difficulties
1216  int status_;
1217  /// Number of integers in problem
1218  int numberIntegers_;
1219  /// Number of rows at continuous
1220  int numberRowsAtContinuous_;
1221  /// Maximum number of cuts
1222  int maximumNumberCuts_;
1223  /** Current phase (so heuristics etc etc can find out).
1224      0 - initial solve
1225      1 - solve with cuts at root
1226      2 - solve with cuts
1227      3 - other e.g. strong branching
1228      4 - trying to validate a solution
1229      5 - at end of search
1230  */
1231  int phase_;
1232
1233  /// Number of entries in #addedCuts_
1234  int currentNumberCuts_;
1235
1236  /** Current limit on search tree depth
1237
1238    The allocated size of #walkback_. Increased as needed.
1239  */
1240  int maximumDepth_;
1241  /** Array used to assemble the path between a node and the search tree root
1242
1243    The array is resized when necessary. #maximumDepth_  is the current
1244    allocated size.
1245  */
1246  CbcNodeInfo ** walkback_;
1247
1248  /** The list of cuts initially collected for this subproblem
1249
1250    When the subproblem at this node is rebuilt, a set of cuts is collected
1251    for inclusion in the constraint system. If any of these cuts are
1252    subsequently removed because they have become loose, the corresponding
1253    entry is set to NULL.
1254  */
1255  CbcCountRowCut ** addedCuts_;
1256
1257  /** A pointer to a row cut which will be added instead of normal branching.
1258      After use it should be set to NULL.
1259  */
1260  OsiRowCut * nextRowCut_;
1261
1262  /// Current node so can be used elsewhere
1263  CbcNode * currentNode_;
1264
1265  /// Indices of integer variables
1266  int * integerVariable_;
1267  /// 0 bit - check if cuts valid (if on list)
1268  int specialOptions_;
1269  /// User node comparison function
1270  CbcCompareBase * nodeCompare_;
1271  /// Tree
1272  CbcTree * tree_;
1273  /// A pointer to model to be used for subtrees
1274  CbcModel * subTreeModel_;
1275  /// Number of times any subtree stopped on nodes, time etc
1276  int numberStoppedSubTrees_;
1277  /// Variable selection function
1278  CbcBranchDecision * branchingMethod_;
1279  /** Whether to automatically do presolve before branch and bound.
1280      0 - no
1281      1 - ordinary presolve
1282      2 - integer presolve (dodgy)
1283  */
1284  /// Pointer to user-defined data structure
1285  void * appData_;
1286  int presolve_;
1287  /** Maximum number of candidates to consider for strong branching.
1288
1289    To disable strong branching, set this to 0.
1290  */
1291  int numberStrong_;
1292
1293  /// Print frequency
1294  int printFrequency_;
1295  /// Number of cut generators
1296  int numberCutGenerators_;
1297  // Cut generators
1298  CbcCutGenerator ** generator_;
1299  // Cut generators before any changes
1300  CbcCutGenerator ** virginGenerator_;
1301  /// Number of heuristics
1302  int numberHeuristics_;
1303  // Heuristic solvers
1304  CbcHeuristic ** heuristic_;
1305
1306  /// Total number of objects
1307  int numberObjects_;
1308
1309  /** \brief Integer and Clique and ... information
1310
1311    \note The code assumes that the first objects on the list will be
1312          SimpleInteger objects for each integer variable, followed by
1313          Clique objects. Portions of the code that understand Clique objects
1314          will fail if they do not immediately follow the SimpleIntegers.
1315          Large chunks of the code will fail if the first objects are not
1316          SimpleInteger. As of 2003.08, SimpleIntegers and Cliques are the only
1317          objects.
1318  */
1319  CbcObject ** object_;
1320
1321 
1322  /// Original columns as created by integerPresolve
1323  int * originalColumns_;
1324  /// Priorities
1325  int * priority_;
1326  /// How often to scan global cuts
1327  int howOftenGlobalScan_;
1328  /** Number of times global cuts violated.  When global cut pool then this
1329      should be kept for each cut and type of cut */
1330  int numberGlobalViolations_;
1331  /** Value of objective at continuous
1332      (Well actually after initial round of cuts)
1333  */
1334  double continuousObjective_;
1335  /** Value of objective before root node cuts added
1336  */
1337  double originalContinuousObjective_;
1338  /// Number of infeasibilities at continuous
1339  int continuousInfeasibilities_;
1340  /// Maximum number of cut passes at root
1341  int maximumCutPassesAtRoot_;
1342  /// Maximum number of cut passes
1343  int maximumCutPasses_;
1344  /// Current cut pass number
1345  int currentPassNumber_;
1346  /// Whether to force a resolve after takeOffCuts
1347  bool resolveAfterTakeOffCuts_;
1348 //@}
1349};
1350
1351#endif
Note: See TracBrowser for help on using the repository browser.