source: trunk/include/CbcModel.hpp @ 102

Last change on this file since 102 was 102, checked in by forrest, 16 years ago

add originalColumns_

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