source: trunk/include/CbcModel.hpp @ 122

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

major changes

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 46.1 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  /// Get the specified object
321  inline CbcObject * modifiableObject(int which) const { return object_[which];};
322
323  /// Delete all object information
324  void deleteObjects();
325
326  /** Add in object information.
327 
328    Objects are cloned; the owner can delete the originals.
329  */
330  void addObjects(int numberObjects, CbcObject ** objects);
331
332  /// Ensure attached objects point to this model.
333  void synchronizeModel() ;
334
335  /** \brief Identify integer variables and create corresponding objects.
336 
337    Record integer variables and create an CbcSimpleInteger object for each
338    one.
339    If \p startAgain is true, a new scan is forced, overwriting any existing
340    integer variable information.
341  */
342
343  void findIntegers(bool startAgain);
344 
345  //@}
346
347  //---------------------------------------------------------------------------
348
349  /**@name Parameter set/get methods
350
351     The set methods return true if the parameter was set to the given value,
352     false if the value of the parameter is out of range.
353
354     The get methods return the value of the parameter.
355
356  */
357  //@{
358  /// Set an integer parameter
359  inline bool setIntParam(CbcIntParam key, int value) {
360    intParam_[key] = value;
361    return true;
362  }
363  /// Set a double parameter
364  inline bool setDblParam(CbcDblParam key, double value) {
365    dblParam_[key] = value;
366    return true;
367  }
368  /// Get an integer parameter
369  inline int getIntParam(CbcIntParam key) const {
370    return intParam_[key];
371  }
372  /// Get a double parameter
373  inline double getDblParam(CbcDblParam key) const {
374    return dblParam_[key];
375  }
376  /*! \brief Set cutoff bound on the objective function.
377
378    When using strict comparison, the bound is adjusted by a tolerance to
379    avoid accidentally cutting off the optimal solution.
380  */
381  void setCutoff(double value) ;
382
383  /// Get the cutoff bound on the objective function - always as minimize
384  inline double getCutoff() const
385  { double value ;
386    solver_->getDblParam(OsiDualObjectiveLimit,value) ;
387    return value * solver_->getObjSense() ; } ;
388
389  /// Set the \link CbcModel::CbcMaxNumNode maximum node limit \endlink
390  inline bool setMaximumNodes( int value)
391  { return setIntParam(CbcMaxNumNode,value); }
392
393  /// Get the \link CbcModel::CbcMaxNumNode maximum node limit \endlink
394  inline int getMaximumNodes() const
395  { return getIntParam(CbcMaxNumNode); }
396
397  /** Set the
398      \link CbcModel::CbcMaxNumSol maximum number of solutions \endlink
399      desired.
400  */
401  inline bool setMaximumSolutions( int value) {
402    return setIntParam(CbcMaxNumSol,value);
403  }
404  /** Get the
405      \link CbcModel::CbcMaxNumSol maximum number of solutions \endlink
406      desired.
407  */
408  inline int getMaximumSolutions() const {
409    return getIntParam(CbcMaxNumSol);
410  }
411
412  /** Set the
413      \link CbcModel::CbcMaximumSeconds maximum number of seconds \endlink
414      desired.
415  */
416  inline bool setMaximumSeconds( double value) {
417    return setDblParam(CbcMaximumSeconds,value);
418  }
419  /** Get the
420      \link CbcModel::CbcMaximumSeconds maximum number of seconds \endlink
421      desired.
422  */
423  inline double getMaximumSeconds() const {
424    return getDblParam(CbcMaximumSeconds);
425  }
426
427  /** Set the
428    \link CbcModel::CbcIntegerTolerance integrality tolerance \endlink
429  */
430  inline bool setIntegerTolerance( double value) {
431    return setDblParam(CbcIntegerTolerance,value);
432  }
433  /** Get the
434    \link CbcModel::CbcIntegerTolerance integrality tolerance \endlink
435  */
436  inline double getIntegerTolerance() const {
437    return getDblParam(CbcIntegerTolerance);
438  }
439
440  /** Set the
441      \link CbcModel::CbcInfeasibilityWeight
442            weight per integer infeasibility \endlink
443  */
444  inline bool setInfeasibilityWeight( double value) {
445    return setDblParam(CbcInfeasibilityWeight,value);
446  }
447  /** Get the
448      \link CbcModel::CbcInfeasibilityWeight
449            weight per integer infeasibility \endlink
450  */
451  inline double getInfeasibilityWeight() const {
452    return getDblParam(CbcInfeasibilityWeight);
453  }
454
455  /** Set the \link CbcModel::CbcAllowableGap allowable gap \endlink
456      between the best known solution and the best possible solution.
457  */
458  inline bool setAllowableGap( double value) {
459    return setDblParam(CbcAllowableGap,value);
460  }
461  /** Get the \link CbcModel::CbcAllowableGap allowable gap \endlink
462      between the best known solution and the best possible solution.
463  */
464  inline double getAllowableGap() const {
465    return getDblParam(CbcAllowableGap);
466  }
467
468  /** Set the \link CbcModel::CbcAllowableFractionGap fraction allowable gap \endlink
469      between the best known solution and the best possible solution.
470  */
471  inline bool setAllowableFractionGap( double value) {
472    return setDblParam(CbcAllowableFractionGap,value);
473  }
474  /** Get the \link CbcModel::CbcAllowableFractionGap fraction allowable gap \endlink
475      between the best known solution and the best possible solution.
476  */
477  inline double getAllowableFractionGap() const {
478    return getDblParam(CbcAllowableFractionGap);
479  }
480  /** Set the \link CbcModel::CbcAllowableFractionGap percentage allowable gap \endlink
481      between the best known solution and the best possible solution.
482  */
483  inline bool setAllowablePercentageGap( double value) {
484    return setDblParam(CbcAllowableFractionGap,value*0.01);
485  }
486  /** Get the \link CbcModel::CbcAllowableFractionGap percentage allowable gap \endlink
487      between the best known solution and the best possible solution.
488  */
489  inline double getAllowablePercentageGap() const {
490    return 100.0*getDblParam(CbcAllowableFractionGap);
491  }
492
493  /// Set the hotstart strategy
494  void setHotstartStrategy(int value) 
495  { hotstartStrategy_=value;};
496  /// Get the hotstart strategy
497  int getHotstartStrategy() const
498  { return hotstartStrategy_;};
499 
500  /// Set the minimum drop to continue cuts
501  inline void setMinimumDrop(double value)
502  {minimumDrop_=value;};
503  /// Get the minimum drop to continue cuts
504  inline double getMinimumDrop() const
505  { return minimumDrop_;};
506
507  /** Set the maximum number of cut passes at root node (default 20)
508      Minimum drop can also be used for fine tuning */
509  inline void setMaximumCutPassesAtRoot(int value)
510  {maximumCutPassesAtRoot_=value;};
511  /** Get the maximum number of cut passes at root node */
512  inline int getMaximumCutPassesAtRoot() const
513  { return maximumCutPassesAtRoot_;};
514
515  /** Set the maximum number of cut passes at other nodes (default 10)
516      Minimum drop can also be used for fine tuning */
517  inline void setMaximumCutPasses(int value)
518  {maximumCutPasses_=value;};
519  /** Get the maximum number of cut passes at other nodes (default 10) */
520  inline int getMaximumCutPasses() const
521  { return maximumCutPasses_;};
522  /** Get current cut pass number in this round of cuts.
523      (1 is first pass) */
524  inline int getCurrentPassNumber() const
525  { return currentPassNumber_;};
526
527  /** Set the maximum number of candidates to be evaluated for strong
528    branching.
529
530    A value of 0 disables strong branching.
531  */
532  void setNumberStrong(int number);
533  /** Get the maximum number of candidates to be evaluated for strong
534    branching.
535  */
536  inline int numberStrong() const
537  { return numberStrong_;};
538
539  /// Set how often to scan global cuts
540  void setHowOftenGlobalScan(int number);
541  /// Get how often to scan global cuts
542  inline int howOftenGlobalScan() const
543  { return howOftenGlobalScan_;};
544  /// Original columns as created by integerPresolve
545  inline int * originalColumns() const
546  { return originalColumns_;};
547
548  /** Set the print frequency.
549 
550    Controls the number of nodes evaluated between status prints.
551    If <tt>number <=0</tt> the print frequency is set to 100 nodes for large
552    problems, 1000 for small problems.
553    Print frequency has very slight overhead if small.
554  */
555  void setPrintFrequency(int number)
556  { printFrequency_=number;};
557  /// Get the print frequency
558  inline int printFrequency() const
559  { return printFrequency_;};
560  //@}
561
562  //---------------------------------------------------------------------------
563  ///@name Methods returning info on how the solution process terminated
564  //@{
565    /// Are there a numerical difficulties?
566    bool isAbandoned() const;
567    /// Is optimality proven?
568    bool isProvenOptimal() const;
569    /// Is  infeasiblity proven (or none better than cutoff)?
570    bool isProvenInfeasible() const;
571    /// Node limit reached?
572    bool isNodeLimitReached() const;
573    /// Solution limit reached?
574    bool isSolutionLimitReached() const;
575    /// Get how many iterations it took to solve the problem.
576    int getIterationCount() const
577    { return solver_->getIterationCount();};
578    /// Get how many Nodes it took to solve the problem.
579    int getNodeCount() const
580    { return numberNodes_;};
581    /** Final status of problem
582   
583      0 finished, 1 stopped, 2 difficulties
584    */
585    inline int status() const
586    { return status_;};
587 
588  //@}
589
590  //---------------------------------------------------------------------------
591  /**@name Problem information methods
592     
593     These methods call the solver's query routines to return
594     information about the problem referred to by the current object.
595     Querying a problem that has no data associated with it result in
596     zeros for the number of rows and columns, and NULL pointers from
597     the methods that return vectors.
598     
599     Const pointers returned from any data-query method are valid as
600     long as the data is unchanged and the solver is not called.
601  */
602  //@{
603  /// Number of rows in continuous (root) problem.
604  int numberRowsAtContinuous() const
605  { return numberRowsAtContinuous_;};
606
607  /// Get number of columns
608  int getNumCols() const
609  { return solver_->getNumCols();};
610 
611  /// Get number of rows
612  int getNumRows() const
613  { return solver_->getNumRows();};
614 
615  /// Get number of nonzero elements
616  CoinBigIndex getNumElements() const
617  { return solver_->getNumElements();};
618
619  /// Number of integers in problem
620  inline int numberIntegers() const
621  { return numberIntegers_;};
622  // Integer variables
623  inline const int * integerVariable() const 
624  { return integerVariable_;};
625 
626  /// Get pointer to array[getNumCols()] of column lower bounds
627  const double * getColLower() const
628  { return solver_->getColLower();};
629 
630  /// Get pointer to array[getNumCols()] of column upper bounds
631  const double * getColUpper() const
632  { return solver_->getColUpper();};
633 
634  /** Get pointer to array[getNumRows()] of row constraint senses.
635      <ul>
636      <li>'L': <= constraint
637      <li>'E': =  constraint
638      <li>'G': >= constraint
639      <li>'R': ranged constraint
640      <li>'N': free constraint
641      </ul>
642  */
643  const char * getRowSense() const
644  { return solver_->getRowSense();};
645 
646  /** Get pointer to array[getNumRows()] of rows right-hand sides
647      <ul>
648      <li> if rowsense()[i] == 'L' then rhs()[i] == rowupper()[i]
649      <li> if rowsense()[i] == 'G' then rhs()[i] == rowlower()[i]
650      <li> if rowsense()[i] == 'R' then rhs()[i] == rowupper()[i]
651      <li> if rowsense()[i] == 'N' then rhs()[i] == 0.0
652      </ul>
653  */
654  const double * getRightHandSide() const
655  { return solver_->getRightHandSide();};
656 
657  /** Get pointer to array[getNumRows()] of row ranges.
658      <ul>
659      <li> if rowsense()[i] == 'R' then
660      rowrange()[i] == rowupper()[i] - rowlower()[i]
661      <li> if rowsense()[i] != 'R' then
662      rowrange()[i] is 0.0
663      </ul>
664  */
665  const double * getRowRange() const
666  { return solver_->getRowRange();};
667 
668  /// Get pointer to array[getNumRows()] of row lower bounds
669  const double * getRowLower() const
670  { return solver_->getRowLower();};
671 
672  /// Get pointer to array[getNumRows()] of row upper bounds
673  const double * getRowUpper() const
674  { return solver_->getRowUpper();};
675 
676  /// Get pointer to array[getNumCols()] of objective function coefficients
677  const double * getObjCoefficients() const
678  { return solver_->getObjCoefficients();};
679 
680  /// Get objective function sense (1 for min (default), -1 for max)
681  double getObjSense() const
682  { return solver_->getObjSense();};
683 
684  /// Return true if variable is continuous
685  bool isContinuous(int colIndex) const
686  { return solver_->isContinuous(colIndex);};
687 
688  /// Return true if variable is binary
689  bool isBinary(int colIndex) const
690  { return solver_->isBinary(colIndex);};
691 
692  /** Return true if column is integer.
693      Note: This function returns true if the the column
694      is binary or a general integer.
695  */
696  bool isInteger(int colIndex) const
697  { return solver_->isInteger(colIndex);};
698 
699  /// Return true if variable is general integer
700  bool isIntegerNonBinary(int colIndex) const
701  { return solver_->isIntegerNonBinary(colIndex);};
702 
703  /// Return true if variable is binary and not fixed at either bound
704  bool isFreeBinary(int colIndex) const
705  { return solver_->isFreeBinary(colIndex) ;};
706 
707  /// Get pointer to row-wise copy of matrix
708  const CoinPackedMatrix * getMatrixByRow() const
709  { return solver_->getMatrixByRow();};
710 
711  /// Get pointer to column-wise copy of matrix
712  const CoinPackedMatrix * getMatrixByCol() const
713  { return solver_->getMatrixByCol();};
714 
715  /// Get solver's value for infinity
716  double getInfinity() const
717  { return solver_->getInfinity();};
718  //@}
719 
720 
721  /**@name Methods related to querying the solution */
722  //@{
723  /// Record a new incumbent solution and update objectiveValue
724  void setBestSolution(CBC_Message how,
725                       double & objectiveValue, const double *solution,
726                       bool fixVariables=false);
727  /// Just update objectiveValue
728  void setBestObjectiveValue( double objectiveValue);
729
730  /** Call this to really test if a valid solution can be feasible
731      Solution is number columns in size.
732      If fixVariables true then bounds of continuous solver updated.
733      Returns objective value (worse than cutoff if not feasible)
734 */
735  double checkSolution(double cutoff, const double * solution,
736                       bool fixVariables);
737  /** Test the current solution for feasiblility.
738
739    Scan all objects for indications of infeasibility. This is broken down
740    into simple integer infeasibility (\p numberIntegerInfeasibilities)
741    and all other reports of infeasibility (\p numberObjectInfeasibilities).
742  */
743  bool feasibleSolution(int & numberIntegerInfeasibilities,
744                        int & numberObjectInfeasibilities) const;
745
746  /** Solution to the most recent lp relaxation.
747
748    The solver's solution to the most recent lp relaxation.
749  */
750   
751  inline double * currentSolution() const
752  { return currentSolution_;};
753  /// Make sure region there and optionally copy solution
754  void reserveCurrentSolution(const double * solution=NULL);
755
756  /// Get pointer to array[getNumCols()] of primal solution vector
757  inline const double * getColSolution() const
758  { return solver_->getColSolution();};
759 
760  /// Get pointer to array[getNumRows()] of dual prices
761  inline const double * getRowPrice() const
762  { return solver_->getRowPrice();};
763 
764  /// Get a pointer to array[getNumCols()] of reduced costs
765  inline const double * getReducedCost() const
766  { return solver_->getReducedCost();};
767 
768  /// Get pointer to array[getNumRows()] of row activity levels.
769  inline const double * getRowActivity() const
770  { return solver_->getRowActivity();};
771 
772  /// Get current objective function value
773  inline double getCurrentObjValue() const
774  { return solver_->getObjValue();};
775 
776  /// Get best objective function value as minimization
777  inline double getMinimizationObjValue() const
778  { return bestObjective_;};
779  /// Set best objective function value as minimization
780  inline void setMinimizationObjValue(double value) 
781  { bestObjective_=value;};
782 
783  /// Get best objective function value
784  inline double getObjValue() const
785  { return bestObjective_ * solver_->getObjSense() ; } ;
786  /** Get best possible objective function value.
787      This is better of best possible left on tree
788      and best solution found.
789      If called from within branch and cut may be optimistic.
790  */
791  double getBestPossibleObjValue() const;
792  /// Set best objective function value
793  inline void setObjValue(double value) 
794  { bestObjective_=value * solver_->getObjSense() ;};
795 
796  /** The best solution to the integer programming problem.
797
798    The best solution to the integer programming problem found during
799    the search. If no solution is found, the method returns null.
800  */
801
802  double * bestSolution() const
803  { return bestSolution_;};
804 
805  /// Get number of solutions
806  int getSolutionCount() const
807  { return numberSolutions_;};
808 
809  /// Set number of solutions (so heuristics will be different)
810  void setSolutionCount(int value) 
811  { numberSolutions_=value;};
812  /** Current phase (so heuristics etc etc can find out).
813      0 - initial solve
814      1 - solve with cuts at root
815      2 - solve with cuts
816      3 - other e.g. strong branching
817      4 - trying to validate a solution
818      5 - at end of search
819  */
820  inline int phase() const
821  { return phase_;};
822 
823  /// Get number of heuristic solutions
824  int getNumberHeuristicSolutions() const { return numberHeuristicSolutions_;};
825
826  /// Set objective function sense (1 for min (default), -1 for max,)
827  void setObjSense(double s) { solver_->setObjSense(s);};
828
829  /// Value of objective at continuous
830  inline double getContinuousObjective() const
831  { return originalContinuousObjective_;};
832  inline void setContinuousObjective(double value)
833  { originalContinuousObjective_=value;};
834  /// Number of infeasibilities at continuous
835  inline int getContinuousInfeasibilities() const
836  { return continuousInfeasibilities_;};
837  inline void setContinuousInfeasibilities(int value)
838  { continuousInfeasibilities_=value;};
839  /// Value of objective after root node cuts added
840  inline double rootObjectiveAfterCuts() const
841  { return continuousObjective_;};
842  /** Number of times global cuts violated.  When global cut pool then this
843      should be kept for each cut and type of cut */
844  inline int numberGlobalViolations() const
845  { return numberGlobalViolations_;};
846  inline void clearNumberGlobalViolations()
847  { numberGlobalViolations_=0;};
848  /// Whether to force a resolve after takeOffCuts
849  inline bool resolveAfterTakeOffCuts() const
850  { return resolveAfterTakeOffCuts_;};
851  inline void setResolveAfterTakeOffCuts(bool yesNo)
852  { resolveAfterTakeOffCuts_=yesNo;};
853  //@}
854
855  /** \name Node selection */
856  //@{
857  // Comparison functions (which may be overridden by inheritance)
858  inline CbcCompareBase * nodeComparison() const
859  { return nodeCompare_;};
860  void setNodeComparison(CbcCompareBase * compare);
861  void setNodeComparison(CbcCompareBase & compare);
862  //@}
863
864  /** \name Tree methods and subtree methods */
865  //@{
866  /// Tree method e.g. heap (which may be overridden by inheritance)
867  inline CbcTree * tree() const
868  { return tree_;};
869  /// For modifying tree handling (original is cloned)
870  void passInTreeHandler(CbcTree & tree);
871  /** For passing in an CbcModel to do a sub Tree (with derived tree handlers).
872      Passed in model must exist for duration of branch and bound
873  */
874  void passInSubTreeModel(CbcModel & model);
875  /** For retrieving a copy of subtree model with given OsiSolver.
876      If no subtree model will use self (up to user to reset cutoff etc).
877      If solver NULL uses current
878  */
879  CbcModel * subTreeModel(OsiSolverInterface * solver=NULL) const;
880  /// Returns number of times any subtree stopped on nodes, time etc
881  inline int numberStoppedSubTrees() const
882  { return numberStoppedSubTrees_;}
883  /// Says a sub tree was stopped
884  inline void incrementSubTreeStopped()
885  { numberStoppedSubTrees_++;};
886  /** Whether to automatically do presolve before branch and bound (subTrees).
887      0 - no
888      1 - ordinary presolve
889      2 - integer presolve (dodgy)
890  */
891  inline int typePresolve() const
892  { return presolve_;};
893  inline void setTypePresolve(int value)
894  { presolve_=value;};
895  //@}
896
897  /** \name Branching Decisions
898 
899    See the CbcBranchDecision class for additional information.
900  */
901  //@{
902
903  /// Get the current branching decision method.
904  inline CbcBranchDecision * branchingMethod() const
905  { return branchingMethod_;};
906  /// Set the branching decision method.
907  inline void setBranchingMethod(CbcBranchDecision * method)
908  { branchingMethod_ = method;};
909  /** Set the branching method
910 
911    \overload
912  */
913  inline void setBranchingMethod(CbcBranchDecision & method)
914  { branchingMethod_ = &method;};
915  //@}
916
917  /** \name Row (constraint) and Column (variable) cut generation */
918  //@{
919
920  /** Perform reduced cost fixing
921
922    Fixes integer variables at their current value based on reduced cost
923    penalties.
924  */
925  void reducedCostFix() ;
926
927  /** Return an empty basis object of the specified size
928
929    A useful utility when constructing a basis for a subproblem from scratch.
930    The object returned will be of the requested capacity and appropriate for
931    the solver attached to the model.
932  */
933  CoinWarmStartBasis *getEmptyBasis(int ns = 0, int na = 0) const ;
934
935  /** Remove inactive cuts from the model
936
937    An OsiSolverInterface is expected to maintain a valid basis, but not a
938    valid solution, when loose cuts are deleted. Restoring a valid solution
939    requires calling the solver to reoptimise. If it's certain the solution
940    will not be required, set allowResolve to false to suppress
941    reoptimisation.
942  */
943  void takeOffCuts(OsiCuts &cuts, int *whichGenerator,
944                     int &numberOldActiveCuts, int &numberNewCuts,
945                     bool allowResolve) ;
946
947  /** Determine and install the active cuts that need to be added for
948    the current subproblem
949
950    The whole truth is a bit more complicated. The first action is a call to
951    addCuts1(). addCuts() then sorts through the list, installs the tight
952    cuts in the model, and does bookkeeping (adjusts reference counts).
953    The basis returned from addCuts1() is adjusted accordingly.
954   
955    If it turns out that the node should really be fathomed by bound,
956    addCuts() simply treats all the cuts as loose as it does the bookkeeping.
957  */
958  int addCuts(CbcNode * node, CoinWarmStartBasis *&lastws);
959
960  /** Traverse the tree from node to root and prep the model
961
962    addCuts1() begins the job of prepping the model to match the current
963    subproblem. The model is stripped of all cuts, and the search tree is
964    traversed from node to root to determine the changes required. Appropriate
965    bounds changes are installed, a list of cuts is collected but not
966    installed, and an appropriate basis (minus the cuts, but big enough to
967    accommodate them) is constructed.
968
969    \todo addCuts1() is called in contexts where it's known in advance that
970          all that's desired is to determine a list of cuts and do the
971          bookkeeping (adjust the reference counts). The work of installing
972          bounds and building a basis goes to waste.
973  */
974  void addCuts1(CbcNode * node, CoinWarmStartBasis *&lastws);
975
976  /// Return the list of cuts initially collected for this subproblem
977  CbcCountRowCut ** addedCuts() const
978  { return addedCuts_;};
979  /// Number of entries in the list returned by #addedCuts()
980  int currentNumberCuts() const
981  { return currentNumberCuts_;};
982  /// Global cuts
983  inline OsiCuts * globalCuts() 
984  { return &globalCuts_;};
985  /// Copy and set a pointer to a row cut which will be added instead of normal branching.
986  void setNextRowCut(const OsiRowCut & cut);
987  /// Get a pointer to current node (be careful)
988  inline CbcNode * currentNode() const
989  { return currentNode_;};
990
991  /// Get the number of cut generators
992  inline int numberCutGenerators() const
993  { return numberCutGenerators_;};
994  /// Get the list of cut generators
995  inline CbcCutGenerator ** cutGenerators() const
996  { return generator_;};
997  ///Get the specified cut generator
998  inline CbcCutGenerator * cutGenerator(int i) const
999  { return generator_[i];};
1000  ///Get the specified cut generator before any changes
1001  inline CbcCutGenerator * virginCutGenerator(int i) const
1002  { return virginGenerator_[i];};
1003  /** Add one generator - up to user to delete generators.
1004      howoften affects how generator is used. 0 or 1 means always,
1005      >1 means every that number of nodes.  Negative values have same
1006      meaning as positive but they may be switched off (-> -100) by code if
1007      not many cuts generated at continuous.  -99 is just done at root.
1008      Name is just for printout.
1009      If depth >0 overrides how often generator is called (if howOften==-1 or >0).
1010  */
1011  void addCutGenerator(CglCutGenerator * generator,
1012                       int howOften=1, const char * name=NULL,
1013                       bool normal=true, bool atSolution=false, 
1014                       bool infeasible=false,int howOftenInSub=-100,
1015                       int whatDepth=-1, int whatDepthInSub=-1);
1016//@}
1017  /** \name Strategy and sub models
1018 
1019    See the CbcStrategy class for additional information.
1020  */
1021  //@{
1022
1023  /// Get the current strategy
1024  inline CbcStrategy * strategy() const
1025  { return strategy_;};
1026  /// Set the strategy. Clones
1027  void setStrategy(CbcStrategy & strategy);
1028  /// Get the current parent model
1029  inline CbcModel * parentModel() const
1030  { return parentModel_;};
1031  /// Set the parent model
1032  inline void setParentModel(CbcModel & parentModel)
1033  { parentModel_ = &parentModel;};
1034  //@}
1035
1036
1037  /** \name Heuristics and priorities */
1038  //@{
1039  /// Add one heuristic - up to user to delete
1040  void addHeuristic(CbcHeuristic * generator);
1041  ///Get the specified heuristic
1042  inline CbcHeuristic * heuristic(int i) const
1043  { return heuristic_[i];};
1044
1045  /** Pass in branching priorities.
1046 
1047      If ifClique then priorities are on cliques otherwise priorities are
1048      on integer variables. 
1049      Other type (if exists set to default)
1050      1 is highest priority. (well actually -INT_MAX is but that's ugly)
1051      If hotstart > 0 then branches are created to force
1052      the variable to the value given by best solution.  This enables a
1053      sort of hot start.  The node choice should be greatest depth
1054      and hotstart should normally be switched off after a solution.
1055
1056      If ifNotSimpleIntegers true then appended to normal integers
1057
1058      This is now deprecated except for simple usage.  If user
1059      creates Cbcobjects then set priority in them
1060
1061      \internal Added for Kurt Spielberg.
1062  */
1063  void passInPriorities(const int * priorities, bool ifNotSimpleIntegers);
1064
1065  /// Returns priority level for an object (or 1000 if no priorities exist)
1066  inline int priority(int sequence) const
1067  { return object_[sequence]->priority();}; 
1068  //@}
1069   
1070  /**@name Setting/Accessing application data */
1071  //@{
1072    /** Set application data.
1073
1074        This is a pointer that the application can store into and
1075        retrieve from the solver interface.
1076        This field is available for the application to optionally
1077        define and use.
1078    */
1079    void setApplicationData (void * appData);
1080
1081    /// Get application data
1082    void * getApplicationData() const;
1083  //@}
1084 
1085  //---------------------------------------------------------------------------
1086
1087  /**@name Message handling */
1088  //@{
1089  /// Pass in Message handler (not deleted at end)
1090  void passInMessageHandler(CoinMessageHandler * handler);
1091  /// Set language
1092  void newLanguage(CoinMessages::Language language);
1093  inline void setLanguage(CoinMessages::Language language)
1094  {newLanguage(language);};
1095  /// Return handler
1096  inline CoinMessageHandler * messageHandler() const
1097  {return handler_;};
1098  /// Return messages
1099  inline CoinMessages messages() 
1100  {return messages_;};
1101  /// Return pointer to messages
1102  inline CoinMessages * messagesPointer() 
1103  {return &messages_;};
1104  /// Set log level
1105  inline void setLogLevel(int value)
1106  { handler_->setLogLevel(value);};
1107  /// Get log level
1108  inline int logLevel() const
1109  { return handler_->logLevel();};
1110  //@}
1111  //---------------------------------------------------------------------------
1112
1113
1114  ///@name Constructors and destructors etc
1115  //@{
1116    /// Default Constructor
1117    CbcModel(); 
1118   
1119    /// Constructor from solver
1120    CbcModel(const OsiSolverInterface &);
1121 
1122    /** Assign a solver to the model (model assumes ownership)
1123
1124      On return, \p solver will be NULL.
1125
1126      \note Parameter settings in the outgoing solver are not inherited by
1127            the incoming solver.
1128    */
1129    void assignSolver(OsiSolverInterface *&solver);
1130 
1131    /** Copy constructor .
1132      If noTree is true then tree and cuts are not copied
1133    */ 
1134    CbcModel(const CbcModel & rhs, bool noTree=false);
1135 
1136    /// Assignment operator
1137    CbcModel & operator=(const CbcModel& rhs);
1138 
1139    /// Destructor
1140     ~CbcModel ();
1141
1142    /// Returns solver - has current state
1143    OsiSolverInterface * solver() const
1144    { return solver_;};
1145
1146    /// Returns solver with continuous state
1147    OsiSolverInterface * continuousSolver() const
1148    { return continuousSolver_;};
1149  /// Clears out as much as possible (except solver)
1150  void gutsOfDestructor();
1151  //@}
1152
1153//---------------------------------------------------------------------------
1154
1155private:
1156  ///@name Private member data
1157  //@{
1158
1159  /// The solver associated with this model.
1160  OsiSolverInterface * solver_;
1161
1162  /** Ownership of the solver object
1163
1164    The convention is that CbcModel owns the null solver. Currently there
1165    is no public method to give CbcModel a solver without giving ownership,
1166    but the hook is here.
1167  */
1168  bool ourSolver_ ;
1169
1170  /// A copy of the solver, taken at the continuous (root) node.
1171  OsiSolverInterface * continuousSolver_;
1172
1173   /// Message handler
1174  CoinMessageHandler * handler_;
1175
1176  /** Flag to say if handler_ is the default handler.
1177 
1178    The default handler is deleted when the model is deleted. Other
1179    handlers (supplied by the client) will not be deleted.
1180  */
1181  bool defaultHandler_;
1182
1183  /// Cbc messages
1184  CoinMessages messages_;
1185
1186  /// Array for integer parameters
1187  int intParam_[CbcLastIntParam];
1188
1189  /// Array for double parameters
1190  double dblParam_[CbcLastDblParam];
1191
1192  /** Pointer to an empty warm start object
1193
1194    It turns out to be useful to have this available as a base from
1195    which to build custom warm start objects. This is typed as CoinWarmStart
1196    rather than CoinWarmStartBasis to allow for the possibility that a
1197    client might want to apply a solver that doesn't use a basis-based warm
1198    start. See getEmptyBasis for an example of how this field can be used.
1199  */
1200  mutable CoinWarmStart *emptyWarmStart_ ;
1201
1202  /** Pointer to a warm start basis.  */
1203  CoinWarmStartBasis *basis_;
1204
1205  /// Best objective
1206  double bestObjective_;
1207  /// Best possible objective
1208  double bestPossibleObjective_;
1209
1210  /// Array holding the incumbent (best) solution.
1211  double * bestSolution_;
1212
1213  /** Array holding the current solution.
1214
1215    This array is used more as a temporary.
1216  */
1217  double * currentSolution_;
1218
1219  /// Global cuts
1220  OsiCuts globalCuts_;
1221
1222  /// Minimum degradation in objective value to continue cut generation
1223  double minimumDrop_;
1224  /// Number of solutions
1225  int numberSolutions_;
1226  /// Hotstart strategy 0 =off, 1=branch if incorrect,2=branch even if correct, ....
1227  int hotstartStrategy_;
1228  /// Number of heuristic solutions
1229  int numberHeuristicSolutions_;
1230  /// Cumulative number of nodes
1231  int numberNodes_;
1232  /// Cumulative number of iterations
1233  int numberIterations_;
1234  /// Status of problem - 0 finished, 1 stopped, 2 difficulties
1235  int status_;
1236  /// Number of integers in problem
1237  int numberIntegers_;
1238  /// Number of rows at continuous
1239  int numberRowsAtContinuous_;
1240  /// Maximum number of cuts
1241  int maximumNumberCuts_;
1242  /** Current phase (so heuristics etc etc can find out).
1243      0 - initial solve
1244      1 - solve with cuts at root
1245      2 - solve with cuts
1246      3 - other e.g. strong branching
1247      4 - trying to validate a solution
1248      5 - at end of search
1249  */
1250  int phase_;
1251
1252  /// Number of entries in #addedCuts_
1253  int currentNumberCuts_;
1254
1255  /** Current limit on search tree depth
1256
1257    The allocated size of #walkback_. Increased as needed.
1258  */
1259  int maximumDepth_;
1260  /** Array used to assemble the path between a node and the search tree root
1261
1262    The array is resized when necessary. #maximumDepth_  is the current
1263    allocated size.
1264  */
1265  CbcNodeInfo ** walkback_;
1266
1267  /** The list of cuts initially collected for this subproblem
1268
1269    When the subproblem at this node is rebuilt, a set of cuts is collected
1270    for inclusion in the constraint system. If any of these cuts are
1271    subsequently removed because they have become loose, the corresponding
1272    entry is set to NULL.
1273  */
1274  CbcCountRowCut ** addedCuts_;
1275
1276  /** A pointer to a row cut which will be added instead of normal branching.
1277      After use it should be set to NULL.
1278  */
1279  OsiRowCut * nextRowCut_;
1280
1281  /// Current node so can be used elsewhere
1282  CbcNode * currentNode_;
1283
1284  /// Indices of integer variables
1285  int * integerVariable_;
1286  /// 0 bit - check if cuts valid (if on list)
1287  int specialOptions_;
1288  /// User node comparison function
1289  CbcCompareBase * nodeCompare_;
1290  /// Tree
1291  CbcTree * tree_;
1292  /// A pointer to model to be used for subtrees
1293  CbcModel * subTreeModel_;
1294  /// Number of times any subtree stopped on nodes, time etc
1295  int numberStoppedSubTrees_;
1296  /// Variable selection function
1297  CbcBranchDecision * branchingMethod_;
1298  /// Strategy
1299  CbcStrategy * strategy_;
1300  /// Parent model
1301  CbcModel * parentModel_;
1302  /** Whether to automatically do presolve before branch and bound.
1303      0 - no
1304      1 - ordinary presolve
1305      2 - integer presolve (dodgy)
1306  */
1307  /// Pointer to user-defined data structure
1308  void * appData_;
1309  int presolve_;
1310  /** Maximum number of candidates to consider for strong branching.
1311
1312    To disable strong branching, set this to 0.
1313  */
1314  int numberStrong_;
1315
1316  /// Print frequency
1317  int printFrequency_;
1318  /// Number of cut generators
1319  int numberCutGenerators_;
1320  // Cut generators
1321  CbcCutGenerator ** generator_;
1322  // Cut generators before any changes
1323  CbcCutGenerator ** virginGenerator_;
1324  /// Number of heuristics
1325  int numberHeuristics_;
1326  // Heuristic solvers
1327  CbcHeuristic ** heuristic_;
1328
1329  /// Total number of objects
1330  int numberObjects_;
1331
1332  /** \brief Integer and Clique and ... information
1333
1334    \note The code assumes that the first objects on the list will be
1335          SimpleInteger objects for each integer variable, followed by
1336          Clique objects. Portions of the code that understand Clique objects
1337          will fail if they do not immediately follow the SimpleIntegers.
1338          Large chunks of the code will fail if the first objects are not
1339          SimpleInteger. As of 2003.08, SimpleIntegers and Cliques are the only
1340          objects.
1341  */
1342  CbcObject ** object_;
1343
1344 
1345  /// Original columns as created by integerPresolve
1346  int * originalColumns_;
1347  /// How often to scan global cuts
1348  int howOftenGlobalScan_;
1349  /** Number of times global cuts violated.  When global cut pool then this
1350      should be kept for each cut and type of cut */
1351  int numberGlobalViolations_;
1352  /** Value of objective at continuous
1353      (Well actually after initial round of cuts)
1354  */
1355  double continuousObjective_;
1356  /** Value of objective before root node cuts added
1357  */
1358  double originalContinuousObjective_;
1359  /// Number of infeasibilities at continuous
1360  int continuousInfeasibilities_;
1361  /// Maximum number of cut passes at root
1362  int maximumCutPassesAtRoot_;
1363  /// Maximum number of cut passes
1364  int maximumCutPasses_;
1365  /// Current cut pass number
1366  int currentPassNumber_;
1367  /// Whether to force a resolve after takeOffCuts
1368  bool resolveAfterTakeOffCuts_;
1369 //@}
1370};
1371
1372#endif
Note: See TracBrowser for help on using the repository browser.