source: trunk/Cbc/src/CbcLinked.hpp @ 692

Last change on this file since 692 was 692, checked in by forrest, 13 years ago

changes so OsiIntegers? have pseudocosts updated on branch

File size: 37.7 KB
Line 
1// Copyright (C) 2006, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef CglLinked_H
4#define CglLinked_H
5/* THIS CONTAINS STUFF THAT SHOULD BE IN
6   OsiSolverLink
7   OsiBranchLink
8   CglTemporary
9*/
10#include "CoinModel.hpp"
11#include "OsiClpSolverInterface.hpp"
12#include "OsiChooseVariable.hpp"
13#include "CbcFathom.hpp"
14class CbcModel;
15class CoinPackedMatrix;
16class OsiLinkedBound;
17class OsiObject;
18class CglStored;
19/**
20   
21This is to allow the user to replace initialSolve and resolve
22This version changes coefficients
23*/
24
25class OsiSolverLink : public CbcOsiSolver {
26 
27public:
28  //---------------------------------------------------------------------------
29  /**@name Solve methods */
30  //@{
31  /// Solve initial LP relaxation
32  virtual void initialSolve();
33 
34  /// Resolve an LP relaxation after problem modification
35  virtual void resolve();
36
37  /**
38     Problem specific
39     Returns -1 if node fathomed and no solution
40              0 if did nothing
41              1 if node fathomed and solution
42     allFixed is true if all LinkedBound variables are fixed
43  */
44  virtual int fathom(bool allFixed) ;
45  /** Solves nonlinear problem from CoinModel using SLP - may be used as crash
46      for other algorithms when number of iterations small.
47      Also exits if all problematical variables are changing
48      less than deltaTolerance
49      Returns solution array
50  */
51  double * nonlinearSLP(int numberPasses,double deltaTolerance);
52  /** Solve linearized quadratic objective branch and bound.
53      Return cutoff and OA cut
54  */
55  double linearizedBAB(CglStored * cut) ;
56  /** Solves nonlinear problem from CoinModel using SLP - and then tries to get
57      heuristic solution
58      Returns solution array
59      mode -
60      0 just get continuous
61      1 round and try normal bab
62      2 use defaultBound_ to bound integer variables near current solution
63  */
64  double * heuristicSolution(int numberPasses,double deltaTolerance,int mode);
65  //@}
66 
67 
68  /**@name Constructors and destructors */
69  //@{
70  /// Default Constructor
71  OsiSolverLink ();
72 
73  /** This creates from a coinModel object
74
75      if errors.then number of sets is -1
76     
77      This creates linked ordered sets information.  It assumes -
78
79      for product terms syntax is yy*f(zz)
80      also just f(zz) is allowed
81      and even a constant
82
83      modelObject not const as may be changed as part of process.
84  */
85  OsiSolverLink(  CoinModel & modelObject);
86  // Other way with existing object
87  void load(  CoinModel & modelObject,bool tightenBounds=false,int logLevel=1);
88  /// Clone
89  virtual OsiSolverInterface * clone(bool copyData=true) const;
90 
91  /// Copy constructor
92  OsiSolverLink (const OsiSolverLink &);
93 
94  /// Assignment operator
95  OsiSolverLink & operator=(const OsiSolverLink& rhs);
96 
97  /// Destructor
98  virtual ~OsiSolverLink ();
99 
100  //@}
101 
102 
103  /**@name Sets and Gets */
104  //@{
105  /// Add a bound modifier
106  void addBoundModifier(bool upperBoundAffected, bool useUpperBound, int whichVariable, int whichVariableAffected, 
107                        double multiplier=1.0);
108  /// Update coefficients - returns number updated if in updating mode
109  int updateCoefficients(ClpSimplex * solver, CoinPackedMatrix * matrix);
110  /// Analyze constraints to see which are convex (quadratic)
111  void analyzeObjects();
112  /// Add reformulated bilinear constraints
113  void addTighterConstraints();
114  /// Objective value of best solution found internally
115  inline double bestObjectiveValue() const
116  { return bestObjectiveValue_;};
117  /// Set objective value of best solution found internally
118  inline void setBestObjectiveValue(double value)
119  { bestObjectiveValue_ = value;};
120  /// Best solution found internally
121  inline const double * bestSolution() const
122  { return bestSolution_;};
123  /// Set best solution found internally
124  void setBestSolution(const double * solution, int numberColumns);
125  /// Set special options
126  inline void setSpecialOptions2(int value)
127  { specialOptions2_=value;};
128  /// Say convex (should work it out) - if convex false then strictly concave
129  void sayConvex(bool convex);
130  /// Get special options
131  inline int specialOptions2() const
132  { return specialOptions2_;};
133  /** Clean copy of matrix
134      So we can add rows
135  */
136  CoinPackedMatrix * cleanMatrix() const
137  { return matrix_;};
138  /** Row copy of matrix
139      Just genuine columns and rows
140      Linear part
141  */
142  CoinPackedMatrix * originalRowCopy() const
143  { return originalRowCopy_;};
144  /// Copy of quadratic model if one
145  ClpSimplex * quadraticModel() const
146  { return quadraticModel_;};
147  /// Gets correct form for a quadratic row - user to delete
148  CoinPackedMatrix * quadraticRow(int rowNumber,double * linear) const;
149  /// Default meshSize
150  inline double defaultMeshSize() const
151  { return defaultMeshSize_;};
152  inline void setDefaultMeshSize(double value)
153  { defaultMeshSize_=value;};
154  /// Default maximumbound
155  inline double defaultBound() const
156  { return defaultBound_;};
157  inline void setDefaultBound(double value)
158  { defaultBound_=value;};
159  /// Set integer priority
160  inline void setIntegerPriority(int value)
161  { integerPriority_=value;};
162  /// Get integer priority
163  inline int integerPriority() const
164  { return integerPriority_;};
165  /// Objective transfer variable if one
166  inline int objectiveVariable() const
167  { return objectiveVariable_;}
168  /// Set biLinear priority
169  inline void setBiLinearPriority(int value)
170  { biLinearPriority_=value;};
171  /// Get biLinear priority
172  inline int biLinearPriority() const
173  { return biLinearPriority_;};
174  /// Return CoinModel
175  inline const CoinModel * coinModel() const
176  { return &coinModel_;};
177  /// Set all biLinear priorities on x-x variables
178  void setBiLinearPriorities(int value, double meshSize=1.0);
179  /** Set options and priority on all or some biLinear variables
180      1 - on I-I
181      2 - on I-x
182      4 - on x-x
183      or combinations.
184      -1 means leave (for priority value and strategy value)
185  */
186  void setBranchingStrategyOnVariables(int strategyValue, int priorityValue=-1,
187                                       int mode=7);
188  /// Set all mesh sizes on x-x variables
189  void setMeshSizes(double value);
190  /** Two tier integer problem where when set of variables with priority
191      less than this are fixed the problem becomes an easier integer problem
192  */
193  void setFixedPriority(int priorityValue);
194  //@}
195 
196  //---------------------------------------------------------------------------
197 
198protected:
199 
200 
201  /**@name functions */
202  //@{
203  /// Do real work of initialize
204  //void initialize(ClpSimplex * & solver, OsiObject ** & object) const;
205  /// Do real work of delete
206  void gutsOfDestructor(bool justNullify=false);
207  /// Do real work of copy
208  void gutsOfCopy(const OsiSolverLink & rhs) ;
209  //@}
210 
211  /**@name Private member data */
212  //@{
213  /** Clean copy of matrix
214      Marked coefficients will be multiplied by L or U
215  */
216  CoinPackedMatrix * matrix_;
217  /** Row copy of matrix
218      Just genuine columns and rows
219  */
220  CoinPackedMatrix * originalRowCopy_;
221  /// Copy of quadratic model if one
222  ClpSimplex * quadraticModel_;
223  /// Number of rows with nonLinearities
224  int numberNonLinearRows_;
225  /// Starts of lists
226  int * startNonLinear_;
227  /// Row number for a list
228  int * rowNonLinear_;
229  /** Indicator whether is convex, concave or neither
230      -1 concave, 0 neither, +1 convex
231  */
232  int * convex_;
233  /// Indices in a list/row
234  int * whichNonLinear_;
235  /// Model in CoinModel format
236  CoinModel coinModel_;
237  /// Number of variables in tightening phase
238  int numberVariables_;
239  /// Information
240  OsiLinkedBound * info_;
241  /**
242     0 bit (1) - call fathom (may do mini B&B)
243     1 bit (2) - quadratic only in objective (add OA cuts)
244     2 bit (4) - convex
245     3 bit (8) - try adding OA cuts
246     4 bit (16) - add linearized constraints
247  */
248  int specialOptions2_;
249  /// Objective transfer row if one
250  int objectiveRow_;
251  /// Objective transfer variable if one
252  int objectiveVariable_;
253  /// Objective value of best solution found internally
254  double bestObjectiveValue_;
255  /// Default mesh
256  double defaultMeshSize_;
257  /// Default maximum bound
258  double defaultBound_;
259  /// Best solution found internally
260  double * bestSolution_;
261  /// Priority for integers
262  int integerPriority_;
263  /// Priority for bilinear
264  int biLinearPriority_;
265  /// Number of variables which when fixed help
266  int numberFix_;
267  /// list of fixed variables
268  int * fixVariables_;
269  //@}
270};
271/**
272   List of bounds which depend on other bounds
273*/
274
275class OsiLinkedBound {
276 
277public:
278  //---------------------------------------------------------------------------
279  /**@name Action methods */
280  //@{
281  /// Update other bounds
282  void updateBounds(ClpSimplex * solver);
283  //@}
284 
285 
286  /**@name Constructors and destructors */
287  //@{
288  /// Default Constructor
289  OsiLinkedBound ();
290  /// Useful Constructor
291  OsiLinkedBound(OsiSolverInterface * model, int variable,
292                 int numberAffected, const int * positionL, 
293                 const int * positionU, const double * multiplier);
294 
295  /// Copy constructor
296  OsiLinkedBound (const OsiLinkedBound &);
297 
298  /// Assignment operator
299  OsiLinkedBound & operator=(const OsiLinkedBound& rhs);
300 
301  /// Destructor
302  ~OsiLinkedBound ();
303 
304  //@}
305 
306  /**@name Sets and Gets */
307  //@{
308  /// Get variable
309  inline int variable() const
310  { return variable_;};
311  /// Add a bound modifier
312  void addBoundModifier(bool upperBoundAffected, bool useUpperBound, int whichVariable, 
313                        double multiplier=1.0);
314  //@}
315 
316private:
317  typedef struct {
318    /*
319      0 - LB of variable affected
320      1 - UB of variable affected
321      2 - element in position (affected) affected
322    */
323    unsigned int affect:2;
324    unsigned int ubUsed:1; // nonzero if UB of this variable is used
325    /*
326       0 - use x*multiplier
327       1 - use multiplier/x
328       2 - if UB use min of current upper and x*multiplier, if LB use max of current lower and x*multiplier
329    */
330    unsigned int type:4; // type of computation
331    unsigned int affected:25; // variable or element affected
332    float multiplier; // to use in computation
333  } boundElementAction;
334 
335  /**@name Private member data */
336  //@{
337  /// Pointer back to model
338  OsiSolverInterface * model_;
339  /// Variable
340  int variable_;
341  /// Number of variables/elements affected
342  int numberAffected_;
343  /// Maximum number of variables/elements affected
344  int maximumAffected_;
345  /// Actions
346  boundElementAction * affected_;
347  //@}
348};
349#include "CbcHeuristic.hpp"
350/** heuristic - just picks up any good solution
351 */
352
353class CbcHeuristicDynamic3 : public CbcHeuristic {
354public:
355 
356  // Default Constructor
357  CbcHeuristicDynamic3 ();
358 
359  /* Constructor with model
360   */
361  CbcHeuristicDynamic3 (CbcModel & model);
362 
363  // Copy constructor
364  CbcHeuristicDynamic3 ( const CbcHeuristicDynamic3 &);
365 
366  // Destructor
367  ~CbcHeuristicDynamic3 ();
368 
369  /// Clone
370  virtual CbcHeuristic * clone() const;
371 
372  /// update model
373  virtual void setModel(CbcModel * model);
374 
375  /** returns 0 if no solution, 1 if valid solution.
376      Sets solution values if good, sets objective value (only if good)
377      We leave all variables which are at one at this node of the
378      tree to that value and will
379      initially set all others to zero.  We then sort all variables in order of their cost
380      divided by the number of entries in rows which are not yet covered.  We randomize that
381      value a bit so that ties will be broken in different ways on different runs of the heuristic.
382      We then choose the best one and set it to one and repeat the exercise. 
383     
384  */
385  virtual int solution(double & objectiveValue,
386                       double * newSolution);
387  /// Resets stuff if model changes
388  virtual void resetModel(CbcModel * model);
389  /// Returns true if can deal with "odd" problems e.g. sos type 2
390  virtual bool canDealWithOdd() const
391  { return true;};
392 
393protected:
394private:
395  /// Illegal Assignment operator
396  CbcHeuristicDynamic3 & operator=(const CbcHeuristicDynamic3& rhs);
397};
398
399#include "OsiBranchingObject.hpp"
400
401/** Define Special Linked Ordered Sets.
402
403*/
404class CoinWarmStartBasis;
405
406class OsiOldLink : public OsiSOS {
407
408public:
409
410  // Default Constructor
411  OsiOldLink ();
412
413  /** Useful constructor - A valid solution is if all variables are zero
414      apart from k*numberLink to (k+1)*numberLink-1 where k is 0 through
415      numberInSet-1.  The length of weights array is numberInSet.
416      For this constructor the variables in matrix are the numberInSet*numberLink
417      starting at first. If weights null then 0,1,2..
418  */
419  OsiOldLink (const OsiSolverInterface * solver, int numberMembers,
420           int numberLinks, int first,
421           const double * weights, int setNumber);
422  /** Useful constructor - A valid solution is if all variables are zero
423      apart from k*numberLink to (k+1)*numberLink-1 where k is 0 through
424      numberInSet-1.  The length of weights array is numberInSet.
425      For this constructor the variables are given by list - grouped.
426      If weights null then 0,1,2..
427  */
428  OsiOldLink (const OsiSolverInterface * solver, int numberMembers,
429           int numberLinks, int typeSOS, const int * which,
430           const double * weights, int setNumber);
431 
432  // Copy constructor
433  OsiOldLink ( const OsiOldLink &);
434   
435  /// Clone
436  virtual OsiObject * clone() const;
437
438  // Assignment operator
439  OsiOldLink & operator=( const OsiOldLink& rhs);
440
441  // Destructor
442  virtual ~OsiOldLink ();
443 
444  /// Infeasibility - large is 0.5
445  virtual double infeasibility(const OsiBranchingInformation * info,int & whichWay) const;
446
447  /** Set bounds to fix the variable at the current (integer) value.
448
449    Given an integer value, set the lower and upper bounds to fix the
450    variable. Returns amount it had to move variable.
451  */
452  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
453
454  /** Creates a branching object
455
456    The preferred direction is set by \p way, 0 for down, 1 for up.
457  */
458  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
459
460  /// Redoes data when sequence numbers change
461  virtual void resetSequenceEtc(int numberColumns, const int * originalColumns);
462
463  /// Number of links for each member
464  inline int numberLinks() const
465  {return numberLinks_;};
466
467  /** \brief Return true if object can take part in normal heuristics
468  */
469  virtual bool canDoHeuristics() const 
470  {return false;};
471  /** \brief Return true if branch should only bound variables
472  */
473  virtual bool boundBranch() const 
474  {return false;};
475
476private:
477  /// data
478
479  /// Number of links
480  int numberLinks_;
481};
482/** Branching object for Linked ordered sets
483
484 */
485class OsiOldLinkBranchingObject : public OsiSOSBranchingObject {
486
487public:
488
489  // Default Constructor
490  OsiOldLinkBranchingObject ();
491
492  // Useful constructor
493  OsiOldLinkBranchingObject (OsiSolverInterface * solver,  const OsiOldLink * originalObject,
494                          int way,
495                          double separator);
496 
497  // Copy constructor
498  OsiOldLinkBranchingObject ( const OsiOldLinkBranchingObject &);
499   
500  // Assignment operator
501  OsiOldLinkBranchingObject & operator=( const OsiOldLinkBranchingObject& rhs);
502
503  /// Clone
504  virtual OsiBranchingObject * clone() const;
505
506  // Destructor
507  virtual ~OsiOldLinkBranchingObject ();
508 
509  /// Does next branch and updates state
510  virtual double branch(OsiSolverInterface * solver);
511
512  /** \brief Print something about branch - only if log level high
513  */
514  virtual void print(const OsiSolverInterface * solver=NULL);
515private:
516  /// data
517};
518/** Define data for one link
519   
520*/
521
522
523class OsiOneLink {
524
525public:
526
527  // Default Constructor
528  OsiOneLink ();
529
530  /** Useful constructor -
531     
532  */
533  OsiOneLink (const OsiSolverInterface * solver, int xRow, int xColumn, int xyRow,
534              const char * functionString);
535 
536  // Copy constructor
537  OsiOneLink ( const OsiOneLink &);
538   
539  // Assignment operator
540  OsiOneLink & operator=( const OsiOneLink& rhs);
541
542  // Destructor
543  virtual ~OsiOneLink ();
544 
545  /// data
546
547  /// Row which defines x (if -1 then no x)
548  int xRow_;
549  /// Column which defines x
550  int xColumn_;
551  /// Output row
552  int xyRow;
553  /// Function
554  std::string function_;
555};
556/** Define Special Linked Ordered Sets. New style
557
558    members and weights may be stored in SOS object
559
560    This is for y and x*f(y) and z*g(y) etc
561
562*/
563
564
565class OsiLink : public OsiSOS {
566
567public:
568
569  // Default Constructor
570  OsiLink ();
571
572  /** Useful constructor -
573     
574  */
575  OsiLink (const OsiSolverInterface * solver, int yRow,
576           int yColumn, double meshSize);
577 
578  // Copy constructor
579  OsiLink ( const OsiLink &);
580   
581  /// Clone
582  virtual OsiObject * clone() const;
583
584  // Assignment operator
585  OsiLink & operator=( const OsiLink& rhs);
586
587  // Destructor
588  virtual ~OsiLink ();
589 
590  /// Infeasibility - large is 0.5
591  virtual double infeasibility(const OsiBranchingInformation * info,int & whichWay) const;
592
593  /** Set bounds to fix the variable at the current (integer) value.
594
595    Given an integer value, set the lower and upper bounds to fix the
596    variable. Returns amount it had to move variable.
597  */
598  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
599
600  /** Creates a branching object
601
602    The preferred direction is set by \p way, 0 for down, 1 for up.
603  */
604  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
605
606  /// Redoes data when sequence numbers change
607  virtual void resetSequenceEtc(int numberColumns, const int * originalColumns);
608
609  /// Number of links for each member
610  inline int numberLinks() const
611  {return numberLinks_;};
612
613  /** \brief Return true if object can take part in normal heuristics
614  */
615  virtual bool canDoHeuristics() const 
616  {return false;};
617  /** \brief Return true if branch should only bound variables
618  */
619  virtual bool boundBranch() const 
620  {return false;};
621
622private:
623  /// data
624  /// Current increment for y points
625  double meshSize_;
626  /// Links
627  OsiOneLink * data_;
628  /// Number of links
629  int numberLinks_;
630  /// Row which defines y
631  int yRow_;
632  /// Column which defines y
633  int yColumn_;
634};
635/** Branching object for Linked ordered sets
636
637 */
638class OsiLinkBranchingObject : public OsiTwoWayBranchingObject {
639
640public:
641
642  // Default Constructor
643  OsiLinkBranchingObject ();
644
645  // Useful constructor
646  OsiLinkBranchingObject (OsiSolverInterface * solver,  const OsiLink * originalObject,
647                          int way,
648                          double separator);
649 
650  // Copy constructor
651  OsiLinkBranchingObject ( const OsiLinkBranchingObject &);
652   
653  // Assignment operator
654  OsiLinkBranchingObject & operator=( const OsiLinkBranchingObject& rhs);
655
656  /// Clone
657  virtual OsiBranchingObject * clone() const;
658
659  // Destructor
660  virtual ~OsiLinkBranchingObject ();
661 
662  /// Does next branch and updates state
663  virtual double branch(OsiSolverInterface * solver);
664
665  /** \brief Print something about branch - only if log level high
666  */
667  virtual void print(const OsiSolverInterface * solver=NULL);
668private:
669  /// data
670};
671/** Define BiLinear objects
672
673    This models x*y where one or both are integer
674
675*/
676
677
678class OsiBiLinear : public OsiObject2 {
679
680public:
681
682  // Default Constructor
683  OsiBiLinear ();
684
685  /** Useful constructor -
686      This Adds in rows and variables to construct valid Linked Ordered Set
687      Adds extra constraints to match other x/y
688      So note not const solver
689  */
690  OsiBiLinear (OsiSolverInterface * solver, int xColumn,
691               int yColumn, int xyRow, double coefficient,
692               double xMesh, double yMesh,
693               int numberExistingObjects=0,const OsiObject ** objects=NULL );
694 
695  /** Useful constructor -
696      This Adds in rows and variables to construct valid Linked Ordered Set
697      Adds extra constraints to match other x/y
698      So note not const model
699  */
700  OsiBiLinear (CoinModel * coinModel, int xColumn,
701               int yColumn, int xyRow, double coefficient,
702               double xMesh, double yMesh,
703               int numberExistingObjects=0,const OsiObject ** objects=NULL );
704 
705  // Copy constructor
706  OsiBiLinear ( const OsiBiLinear &);
707   
708  /// Clone
709  virtual OsiObject * clone() const;
710
711  // Assignment operator
712  OsiBiLinear & operator=( const OsiBiLinear& rhs);
713
714  // Destructor
715  virtual ~OsiBiLinear ();
716 
717  /// Infeasibility - large is 0.5
718  virtual double infeasibility(const OsiBranchingInformation * info,int & whichWay) const;
719
720  /** Set bounds to fix the variable at the current (integer) value.
721
722    Given an integer value, set the lower and upper bounds to fix the
723    variable. Returns amount it had to move variable.
724  */
725  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
726
727  /** Creates a branching object
728
729    The preferred direction is set by \p way, 0 for down, 1 for up.
730  */
731  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
732
733  /// Redoes data when sequence numbers change
734  virtual void resetSequenceEtc(int numberColumns, const int * originalColumns);
735
736  // This does NOT set mutable stuff
737  virtual double checkInfeasibility(const OsiBranchingInformation * info) const;
738 
739  /** \brief Return true if object can take part in normal heuristics
740  */
741  virtual bool canDoHeuristics() const 
742  {return false;};
743  /** \brief Return true if branch should only bound variables
744  */
745  virtual bool boundBranch() const 
746  { return (branchingStrategy_&4)!=0;};
747  /// X column
748  inline int xColumn() const
749  { return xColumn_;};
750  /// Y column
751  inline int yColumn() const
752  { return yColumn_;};
753  /// X row
754  inline int xRow() const
755  { return xRow_;};
756  /// Y row
757  inline int yRow() const
758  { return yRow_;};
759  /// XY row
760  inline int xyRow() const
761  { return xyRow_;};
762  /// Coefficient
763  inline double coefficient() const
764  { return coefficient_;};
765  /// Set coefficient
766  inline void setCoefficient(double value)
767  { coefficient_ = value;};
768  /// First lambda (of 4)
769  inline int firstLambda() const
770  { return firstLambda_;};
771  /// X satisfied if less than this away from mesh
772  inline double xSatisfied() const
773  { return xSatisfied_;};
774  inline void setXSatisfied(double value)
775  { xSatisfied_=value;};
776  /// Y satisfied if less than this away from mesh
777  inline double ySatisfied() const
778  { return ySatisfied_;};
779  inline void setYSatisfied(double value)
780  { ySatisfied_=value;};
781  /// X other satisfied if less than this away from mesh
782  inline double xOtherSatisfied() const
783  { return xOtherSatisfied_;};
784  inline void setXOtherSatisfied(double value)
785  { xOtherSatisfied_=value;};
786  /// Y other satisfied if less than this away from mesh
787  inline double yOtherSatisfied() const
788  { return yOtherSatisfied_;};
789  inline void setYOtherSatisfied(double value)
790  { yOtherSatisfied_=value;};
791  /// X meshSize
792  inline double xMeshSize() const
793  { return xMeshSize_;};
794  inline void setXMeshSize(double value)
795  { xMeshSize_=value;};
796  /// Y meshSize
797  inline double yMeshSize() const
798  { return yMeshSize_;};
799  inline void setYMeshSize(double value)
800  { yMeshSize_=value;};
801  /// XY satisfied if two version differ by less than this
802  inline double xySatisfied() const
803  { return xySatisfied_;};
804  inline void setXYSatisfied(double value)
805  { xySatisfied_=value;};
806  /** branching strategy etc
807      bottom 2 bits
808      0 branch on either, 1 branch on x, 2 branch on y
809      next bit
810      4 set to say don't update coefficients
811      next bit
812      8 set to say don't use in feasible region
813      next bit
814      16 set to say - Always satisfied !!
815  */
816  inline int branchingStrategy() const
817  { return branchingStrategy_;};
818  inline void setBranchingStrategy(int value)
819  { branchingStrategy_=value;};
820  /** Simple quadratic bound marker.
821      0 no
822      1 L if coefficient pos, G if negative i.e. value is ub on xy
823      2 G if coefficient pos, L if negative i.e. value is lb on xy
824      3 E
825      If bound then real coefficient is 1.0 and coefficient_ is bound
826  */
827  inline int boundType() const
828  { return boundType_;};
829  inline void setBoundType(int value)
830  { boundType_ = value;};
831  /// Does work of branching
832  void newBounds(OsiSolverInterface * solver, int way, short xOrY, double separator) const;
833  /// Updates coefficients - returns number updated
834  int updateCoefficients(const double * lower, const double * upper, double * objective,
835                          CoinPackedMatrix * matrix, CoinWarmStartBasis * basis) const;
836  /// Returns true value of single xyRow coefficient
837  double xyCoefficient(const double * solution) const;
838  /// Get LU coefficients from matrix
839  void getCoefficients(const OsiSolverInterface * solver,double xB[2], double yB[2], double xybar[4]) const;
840  /// Compute lambdas (third entry in each .B is current value) (nonzero if bad)
841  double computeLambdas(const double xB[3], const double yB[3],const double xybar[4],double lambda[4]) const;
842  /// Adds in data for extra row with variable coefficients
843  void addExtraRow(int row, double multiplier);
844  /// Sets infeasibility and other when pseudo shadow prices
845  void getPseudoShadow(const OsiBranchingInformation * info);
846  /// Gets sum of movements to correct value
847  double getMovement(const OsiBranchingInformation * info);
848
849protected:
850  /// Compute lambdas if coefficients not changing
851  void computeLambdas(const OsiSolverInterface * solver,double lambda[4]) const;
852  /// data
853 
854  /// Coefficient
855  double coefficient_;
856  /// x mesh
857  double xMeshSize_;
858  /// y mesh
859  double yMeshSize_;
860  /// x satisfied if less than this away from mesh
861  double xSatisfied_;
862  /// y satisfied if less than this away from mesh
863  double ySatisfied_;
864  /// X other satisfied if less than this away from mesh
865  double xOtherSatisfied_;
866  /// Y other satisfied if less than this away from mesh
867  double yOtherSatisfied_;
868  /// xy satisfied if less than this away from true
869  double xySatisfied_;
870  /// value of x or y to branch about
871  mutable double xyBranchValue_;
872  /// x column
873  int xColumn_;
874  /// y column
875  int yColumn_;
876  /// First lambda (of 4)
877  int firstLambda_;
878  /** branching strategy etc
879      bottom 2 bits
880      0 branch on either, 1 branch on x, 2 branch on y
881      next bit
882      4 set to say don't update coefficients
883      next bit
884      8 set to say don't use in feasible region
885      next bit
886      16 set to say - Always satisfied !!
887  */
888  int branchingStrategy_;
889  /** Simple quadratic bound marker.
890      0 no
891      1 L if coefficient pos, G if negative i.e. value is ub on xy
892      2 G if coefficient pos, L if negative i.e. value is lb on xy
893      3 E
894      If bound then real coefficient is 1.0 and coefficient_ is bound
895  */
896  int boundType_;
897  /// x row
898  int xRow_;
899  /// y row (-1 if x*x)
900  int yRow_;
901  /// Output row
902  int xyRow_;
903  /// Convexity row
904  int convexity_;
905  /// Number of extra rows (coefficients to be modified)
906  int numberExtraRows_;
907  /// Multiplier for coefficient on row
908  double * multiplier_;
909  /// Row number
910  int * extraRow_;
911  /// Which chosen -1 none, 0 x, 1 y
912  mutable short chosen_;
913};
914/** Branching object for BiLinear objects
915
916 */
917class OsiBiLinearBranchingObject : public OsiTwoWayBranchingObject {
918
919public:
920
921  // Default Constructor
922  OsiBiLinearBranchingObject ();
923
924  // Useful constructor
925  OsiBiLinearBranchingObject (OsiSolverInterface * solver,  const OsiBiLinear * originalObject,
926                          int way,
927                          double separator, int chosen);
928 
929  // Copy constructor
930  OsiBiLinearBranchingObject ( const OsiBiLinearBranchingObject &);
931   
932  // Assignment operator
933  OsiBiLinearBranchingObject & operator=( const OsiBiLinearBranchingObject& rhs);
934
935  /// Clone
936  virtual OsiBranchingObject * clone() const;
937
938  // Destructor
939  virtual ~OsiBiLinearBranchingObject ();
940 
941  /// Does next branch and updates state
942  virtual double branch(OsiSolverInterface * solver);
943
944  /** \brief Print something about branch - only if log level high
945  */
946  virtual void print(const OsiSolverInterface * solver=NULL);
947  /** \brief Return true if branch should only bound variables
948  */
949  virtual bool boundBranch() const; 
950private:
951  /// data
952  /// 1 means branch on x, 2 branch on y
953  short chosen_;
954};
955/** Define Continuous BiLinear objects for an == bound
956
957    This models x*y = b where both are continuous
958
959*/
960
961
962class OsiBiLinearEquality : public OsiBiLinear {
963
964public:
965
966  // Default Constructor
967  OsiBiLinearEquality ();
968
969  /** Useful constructor -
970      This Adds in rows and variables to construct Ordered Set
971      for x*y = b
972      So note not const solver
973  */
974  OsiBiLinearEquality (OsiSolverInterface * solver, int xColumn,
975               int yColumn, int xyRow, double rhs,
976                       double xMesh);
977 
978  // Copy constructor
979  OsiBiLinearEquality ( const OsiBiLinearEquality &);
980   
981  /// Clone
982  virtual OsiObject * clone() const;
983
984  // Assignment operator
985  OsiBiLinearEquality & operator=( const OsiBiLinearEquality& rhs);
986
987  // Destructor
988  virtual ~OsiBiLinearEquality ();
989 
990  /// Possible improvement
991  virtual double improvement(const OsiSolverInterface * solver) const;
992  /** change grid
993      if type 0 then use solution and make finer
994      if 1 then back to original
995      returns mesh size
996  */
997  double newGrid(OsiSolverInterface * solver, int type) const;
998  /// Number of points
999  inline int numberPoints() const
1000  { return numberPoints_;};
1001  inline void setNumberPoints(int value)
1002  { numberPoints_ = value;};
1003
1004private:
1005  /// Number of points
1006  int numberPoints_;
1007};
1008/// Define a single integer class - but one where you keep branching until fixed even if satisfied
1009
1010
1011class OsiSimpleFixedInteger : public OsiSimpleInteger {
1012
1013public:
1014
1015  /// Default Constructor
1016  OsiSimpleFixedInteger ();
1017
1018  /// Useful constructor - passed solver index
1019  OsiSimpleFixedInteger (const OsiSolverInterface * solver, int iColumn);
1020 
1021  /// Useful constructor - passed solver index and original bounds
1022  OsiSimpleFixedInteger (int iColumn, double lower, double upper);
1023 
1024  /// Useful constructor - passed simple integer
1025  OsiSimpleFixedInteger (const OsiSimpleInteger &);
1026 
1027  /// Copy constructor
1028  OsiSimpleFixedInteger ( const OsiSimpleFixedInteger &);
1029   
1030  /// Clone
1031  virtual OsiObject * clone() const;
1032
1033  /// Assignment operator
1034  OsiSimpleFixedInteger & operator=( const OsiSimpleFixedInteger& rhs);
1035
1036  /// Destructor
1037  virtual ~OsiSimpleFixedInteger ();
1038 
1039  /// Infeasibility - large is 0.5
1040  virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const;
1041  /** Creates a branching object
1042
1043    The preferred direction is set by \p way, 0 for down, 1 for up.
1044  */
1045  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
1046protected:
1047  /// data
1048 
1049};
1050/** Define a single variable class which is involved with OsiBiLinear objects.
1051    This is used so can make better decision on where to branch as it can look at
1052    all objects.
1053
1054    This version sees if it can re-use code from OsiSimpleInteger
1055    even if not an integer variable.  If not then need to duplicate code.
1056*/
1057
1058
1059class OsiUsesBiLinear : public OsiSimpleInteger {
1060
1061public:
1062
1063  /// Default Constructor
1064  OsiUsesBiLinear ();
1065
1066  /// Useful constructor - passed solver index
1067  OsiUsesBiLinear (const OsiSolverInterface * solver, int iColumn, int type);
1068 
1069  /// Useful constructor - passed solver index and original bounds
1070  OsiUsesBiLinear (int iColumn, double lower, double upper, int type);
1071 
1072  /// Useful constructor - passed simple integer
1073  OsiUsesBiLinear (const OsiSimpleInteger & rhs, int type);
1074 
1075  /// Copy constructor
1076  OsiUsesBiLinear ( const OsiUsesBiLinear & rhs);
1077   
1078  /// Clone
1079  virtual OsiObject * clone() const;
1080
1081  /// Assignment operator
1082  OsiUsesBiLinear & operator=( const OsiUsesBiLinear& rhs);
1083
1084  /// Destructor
1085  virtual ~OsiUsesBiLinear ();
1086 
1087  /// Infeasibility - large is 0.5
1088  virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const;
1089  /** Creates a branching object
1090
1091    The preferred direction is set by \p way, 0 for down, 1 for up.
1092  */
1093  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
1094  /** Set bounds to fix the variable at the current value.
1095
1096    Given an current value, set the lower and upper bounds to fix the
1097    variable. Returns amount it had to move variable.
1098  */
1099  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
1100  /// Add all bi-linear objects
1101  void addBiLinearObjects(OsiSolverLink * solver);
1102protected:
1103  /// data
1104  /// Number of bilinear objects (maybe could be more general)
1105  int numberBiLinear_;
1106  /// Type of variable - 0 continuous, 1 integer
1107  int type_;
1108  /// Objects
1109  OsiObject ** objects_;
1110};
1111/** This class chooses a variable to branch on
1112
1113    This is just as OsiChooseStrong but it fakes it so only
1114    first so many are looked at in this phase
1115
1116*/
1117
1118class OsiChooseStrongSubset  : public OsiChooseStrong {
1119 
1120public:
1121   
1122  /// Default Constructor
1123  OsiChooseStrongSubset ();
1124
1125  /// Constructor from solver (so we can set up arrays etc)
1126  OsiChooseStrongSubset (const OsiSolverInterface * solver);
1127
1128  /// Copy constructor
1129  OsiChooseStrongSubset (const OsiChooseStrongSubset &);
1130   
1131  /// Assignment operator
1132  OsiChooseStrongSubset & operator= (const OsiChooseStrongSubset& rhs);
1133
1134  /// Clone
1135  virtual OsiChooseVariable * clone() const;
1136
1137  /// Destructor
1138  virtual ~OsiChooseStrongSubset ();
1139
1140  /** Sets up strong list and clears all if initialize is true.
1141      Returns number of infeasibilities.
1142      If returns -1 then has worked out node is infeasible!
1143  */
1144  virtual int setupList ( OsiBranchingInformation *info, bool initialize);
1145  /** Choose a variable
1146      Returns -
1147     -1 Node is infeasible
1148     0  Normal termination - we have a candidate
1149     1  All looks satisfied - no candidate
1150     2  We can change the bound on a variable - but we also have a strong branching candidate
1151     3  We can change the bound on a variable - but we have a non-strong branching candidate
1152     4  We can change the bound on a variable - no other candidates
1153     We can pick up branch from bestObjectIndex() and bestWhichWay()
1154     We can pick up a forced branch (can change bound) from firstForcedObjectIndex() and firstForcedWhichWay()
1155     If we have a solution then we can pick up from goodObjectiveValue() and goodSolution()
1156     If fixVariables is true then 2,3,4 are all really same as problem changed
1157  */
1158  virtual int chooseVariable( OsiSolverInterface * solver, OsiBranchingInformation *info, bool fixVariables);
1159
1160  /// Number of objects to use
1161  inline int numberObjectsToUse() const
1162  { return numberObjectsToUse_;};
1163  /// Set number of objects to use
1164  inline void setNumberObjectsToUse(int value)
1165  { numberObjectsToUse_ = value;};
1166
1167protected:
1168  // Data
1169  /// Number of objects to be used (and set in solver)
1170  int numberObjectsToUse_;
1171};
1172
1173#include <string>
1174
1175#include "CglStored.hpp"
1176
1177class CoinWarmStartBasis;
1178/** Stored Temporary Cut Generator Class - destroyed after first use */
1179class CglTemporary : public CglStored {
1180 
1181public:
1182   
1183 
1184  /**@name Generate Cuts */
1185  //@{
1186  /** Generate Mixed Integer Stored cuts for the model of the
1187      solver interface, si.
1188
1189      Insert the generated cuts into OsiCut, cs.
1190
1191      This generator just looks at previously stored cuts
1192      and inserts any that are violated by enough
1193  */
1194  virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs,
1195                             const CglTreeInfo info = CglTreeInfo()) const;
1196  //@}
1197
1198  /**@name Constructors and destructors */
1199  //@{
1200  /// Default constructor
1201  CglTemporary ();
1202 
1203  /// Copy constructor
1204  CglTemporary (const CglTemporary & rhs);
1205
1206  /// Clone
1207  virtual CglCutGenerator * clone() const;
1208
1209  /// Assignment operator
1210  CglTemporary &
1211    operator=(const CglTemporary& rhs);
1212 
1213  /// Destructor
1214  virtual
1215    ~CglTemporary ();
1216  //@}
1217     
1218private:
1219 
1220 // Private member methods
1221
1222  // Private member data
1223};
1224//#############################################################################
1225
1226/**
1227   
1228This is to allow the user to replace initialSolve and resolve
1229*/
1230
1231class OsiSolverLinearizedQuadratic : public OsiClpSolverInterface {
1232 
1233public:
1234  //---------------------------------------------------------------------------
1235  /**@name Solve methods */
1236  //@{
1237  /// Solve initial LP relaxation
1238  virtual void initialSolve();
1239  //@}
1240 
1241 
1242  /**@name Constructors and destructors */
1243  //@{
1244  /// Default Constructor
1245  OsiSolverLinearizedQuadratic ();
1246  /// Useful constructor (solution should be good)
1247  OsiSolverLinearizedQuadratic(  ClpSimplex * quadraticModel);
1248  /// Clone
1249  virtual OsiSolverInterface * clone(bool copyData=true) const;
1250 
1251  /// Copy constructor
1252  OsiSolverLinearizedQuadratic (const OsiSolverLinearizedQuadratic &);
1253 
1254  /// Assignment operator
1255  OsiSolverLinearizedQuadratic & operator=(const OsiSolverLinearizedQuadratic& rhs);
1256 
1257  /// Destructor
1258  virtual ~OsiSolverLinearizedQuadratic ();
1259 
1260  //@}
1261 
1262 
1263  /**@name Sets and Gets */
1264  //@{
1265  /// Objective value of best solution found internally
1266  inline double bestObjectiveValue() const
1267  { return bestObjectiveValue_;};
1268  /// Best solution found internally
1269  const double * bestSolution() const
1270  { return bestSolution_;};
1271  /// Set special options
1272  inline void setSpecialOptions3(int value)
1273  { specialOptions3_=value;};
1274  /// Get special options
1275  inline int specialOptions3() const
1276  { return specialOptions3_;};
1277  /// Copy of quadratic model if one
1278  ClpSimplex * quadraticModel() const
1279  { return quadraticModel_;};
1280  //@}
1281 
1282  //---------------------------------------------------------------------------
1283 
1284protected:
1285 
1286 
1287  /**@name functions */
1288  //@{
1289 
1290  /**@name Private member data */
1291  //@{
1292  /// Objective value of best solution found internally
1293  double bestObjectiveValue_;
1294  /// Copy of quadratic model if one
1295  ClpSimplex * quadraticModel_;
1296  /// Best solution found internally
1297  double * bestSolution_;
1298  /**
1299     0 bit (1) - don't do mini B&B
1300     1 bit (2) - quadratic only in objective
1301  */
1302  int specialOptions3_;
1303  //@}
1304};
1305class ClpSimplex;
1306/** Return an approximate solution to a CoinModel.
1307    Lots of bounds may be odd to force a solution.
1308    mode = 0 just tries to get a continuous solution
1309*/
1310ClpSimplex * approximateSolution(CoinModel & coinModel, 
1311                                 int numberPasses, double deltaTolerance,
1312                                 int mode=0);
1313#endif
Note: See TracBrowser for help on using the repository browser.