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

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

add threaded to trunk

File size: 37.6 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
847protected:
848  /// Compute lambdas if coefficients not changing
849  void computeLambdas(const OsiSolverInterface * solver,double lambda[4]) const;
850  /// data
851 
852  /// Coefficient
853  double coefficient_;
854  /// x mesh
855  double xMeshSize_;
856  /// y mesh
857  double yMeshSize_;
858  /// x satisfied if less than this away from mesh
859  double xSatisfied_;
860  /// y satisfied if less than this away from mesh
861  double ySatisfied_;
862  /// X other satisfied if less than this away from mesh
863  double xOtherSatisfied_;
864  /// Y other satisfied if less than this away from mesh
865  double yOtherSatisfied_;
866  /// xy satisfied if less than this away from true
867  double xySatisfied_;
868  /// value of x or y to branch about
869  mutable double xyBranchValue_;
870  /// x column
871  int xColumn_;
872  /// y column
873  int yColumn_;
874  /// First lambda (of 4)
875  int firstLambda_;
876  /** branching strategy etc
877      bottom 2 bits
878      0 branch on either, 1 branch on x, 2 branch on y
879      next bit
880      4 set to say don't update coefficients
881      next bit
882      8 set to say don't use in feasible region
883      next bit
884      16 set to say - Always satisfied !!
885  */
886  int branchingStrategy_;
887  /** Simple quadratic bound marker.
888      0 no
889      1 L if coefficient pos, G if negative i.e. value is ub on xy
890      2 G if coefficient pos, L if negative i.e. value is lb on xy
891      3 E
892      If bound then real coefficient is 1.0 and coefficient_ is bound
893  */
894  int boundType_;
895  /// x row
896  int xRow_;
897  /// y row (-1 if x*x)
898  int yRow_;
899  /// Output row
900  int xyRow_;
901  /// Convexity row
902  int convexity_;
903  /// Number of extra rows (coefficients to be modified)
904  int numberExtraRows_;
905  /// Multiplier for coefficient on row
906  double * multiplier_;
907  /// Row number
908  int * extraRow_;
909  /// Which chosen -1 none, 0 x, 1 y
910  mutable short chosen_;
911};
912/** Branching object for BiLinear objects
913
914 */
915class OsiBiLinearBranchingObject : public OsiTwoWayBranchingObject {
916
917public:
918
919  // Default Constructor
920  OsiBiLinearBranchingObject ();
921
922  // Useful constructor
923  OsiBiLinearBranchingObject (OsiSolverInterface * solver,  const OsiBiLinear * originalObject,
924                          int way,
925                          double separator, int chosen);
926 
927  // Copy constructor
928  OsiBiLinearBranchingObject ( const OsiBiLinearBranchingObject &);
929   
930  // Assignment operator
931  OsiBiLinearBranchingObject & operator=( const OsiBiLinearBranchingObject& rhs);
932
933  /// Clone
934  virtual OsiBranchingObject * clone() const;
935
936  // Destructor
937  virtual ~OsiBiLinearBranchingObject ();
938 
939  /// Does next branch and updates state
940  virtual double branch(OsiSolverInterface * solver);
941
942  /** \brief Print something about branch - only if log level high
943  */
944  virtual void print(const OsiSolverInterface * solver=NULL);
945  /** \brief Return true if branch should only bound variables
946  */
947  virtual bool boundBranch() const; 
948private:
949  /// data
950  /// 1 means branch on x, 2 branch on y
951  short chosen_;
952};
953/** Define Continuous BiLinear objects for an == bound
954
955    This models x*y = b where both are continuous
956
957*/
958
959
960class OsiBiLinearEquality : public OsiBiLinear {
961
962public:
963
964  // Default Constructor
965  OsiBiLinearEquality ();
966
967  /** Useful constructor -
968      This Adds in rows and variables to construct Ordered Set
969      for x*y = b
970      So note not const solver
971  */
972  OsiBiLinearEquality (OsiSolverInterface * solver, int xColumn,
973               int yColumn, int xyRow, double rhs,
974                       double xMesh);
975 
976  // Copy constructor
977  OsiBiLinearEquality ( const OsiBiLinearEquality &);
978   
979  /// Clone
980  virtual OsiObject * clone() const;
981
982  // Assignment operator
983  OsiBiLinearEquality & operator=( const OsiBiLinearEquality& rhs);
984
985  // Destructor
986  virtual ~OsiBiLinearEquality ();
987 
988  /// Possible improvement
989  virtual double improvement(const OsiSolverInterface * solver) const;
990  /** change grid
991      if type 0 then use solution and make finer
992      if 1 then back to original
993      returns mesh size
994  */
995  double newGrid(OsiSolverInterface * solver, int type) const;
996  /// Number of points
997  inline int numberPoints() const
998  { return numberPoints_;};
999  inline void setNumberPoints(int value)
1000  { numberPoints_ = value;};
1001
1002private:
1003  /// Number of points
1004  int numberPoints_;
1005};
1006/// Define a single integer class - but one where you keep branching until fixed even if satisfied
1007
1008
1009class OsiSimpleFixedInteger : public OsiSimpleInteger {
1010
1011public:
1012
1013  /// Default Constructor
1014  OsiSimpleFixedInteger ();
1015
1016  /// Useful constructor - passed solver index
1017  OsiSimpleFixedInteger (const OsiSolverInterface * solver, int iColumn);
1018 
1019  /// Useful constructor - passed solver index and original bounds
1020  OsiSimpleFixedInteger (int iColumn, double lower, double upper);
1021 
1022  /// Useful constructor - passed simple integer
1023  OsiSimpleFixedInteger (const OsiSimpleInteger &);
1024 
1025  /// Copy constructor
1026  OsiSimpleFixedInteger ( const OsiSimpleFixedInteger &);
1027   
1028  /// Clone
1029  virtual OsiObject * clone() const;
1030
1031  /// Assignment operator
1032  OsiSimpleFixedInteger & operator=( const OsiSimpleFixedInteger& rhs);
1033
1034  /// Destructor
1035  virtual ~OsiSimpleFixedInteger ();
1036 
1037  /// Infeasibility - large is 0.5
1038  virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const;
1039  /** Creates a branching object
1040
1041    The preferred direction is set by \p way, 0 for down, 1 for up.
1042  */
1043  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
1044protected:
1045  /// data
1046 
1047};
1048/** Define a single variable class which is involved with OsiBiLinear objects.
1049    This is used so can make better decision on where to branch as it can look at
1050    all objects.
1051
1052    This version sees if it can re-use code from OsiSimpleInteger
1053    even if not an integer variable.  If not then need to duplicate code.
1054*/
1055
1056
1057class OsiUsesBiLinear : public OsiSimpleInteger {
1058
1059public:
1060
1061  /// Default Constructor
1062  OsiUsesBiLinear ();
1063
1064  /// Useful constructor - passed solver index
1065  OsiUsesBiLinear (const OsiSolverInterface * solver, int iColumn, int type);
1066 
1067  /// Useful constructor - passed solver index and original bounds
1068  OsiUsesBiLinear (int iColumn, double lower, double upper, int type);
1069 
1070  /// Useful constructor - passed simple integer
1071  OsiUsesBiLinear (const OsiSimpleInteger & rhs, int type);
1072 
1073  /// Copy constructor
1074  OsiUsesBiLinear ( const OsiUsesBiLinear & rhs);
1075   
1076  /// Clone
1077  virtual OsiObject * clone() const;
1078
1079  /// Assignment operator
1080  OsiUsesBiLinear & operator=( const OsiUsesBiLinear& rhs);
1081
1082  /// Destructor
1083  virtual ~OsiUsesBiLinear ();
1084 
1085  /// Infeasibility - large is 0.5
1086  virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const;
1087  /** Creates a branching object
1088
1089    The preferred direction is set by \p way, 0 for down, 1 for up.
1090  */
1091  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
1092  /** Set bounds to fix the variable at the current value.
1093
1094    Given an current value, set the lower and upper bounds to fix the
1095    variable. Returns amount it had to move variable.
1096  */
1097  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
1098  /// Add all bi-linear objects
1099  void addBiLinearObjects(OsiSolverLink * solver);
1100protected:
1101  /// data
1102  /// Number of bilinear objects (maybe could be more general)
1103  int numberBiLinear_;
1104  /// Type of variable - 0 continuous, 1 integer
1105  int type_;
1106  /// Objects
1107  OsiObject ** objects_;
1108};
1109/** This class chooses a variable to branch on
1110
1111    This is just as OsiChooseStrong but it fakes it so only
1112    first so many are looked at in this phase
1113
1114*/
1115
1116class OsiChooseStrongSubset  : public OsiChooseStrong {
1117 
1118public:
1119   
1120  /// Default Constructor
1121  OsiChooseStrongSubset ();
1122
1123  /// Constructor from solver (so we can set up arrays etc)
1124  OsiChooseStrongSubset (const OsiSolverInterface * solver);
1125
1126  /// Copy constructor
1127  OsiChooseStrongSubset (const OsiChooseStrongSubset &);
1128   
1129  /// Assignment operator
1130  OsiChooseStrongSubset & operator= (const OsiChooseStrongSubset& rhs);
1131
1132  /// Clone
1133  virtual OsiChooseVariable * clone() const;
1134
1135  /// Destructor
1136  virtual ~OsiChooseStrongSubset ();
1137
1138  /** Sets up strong list and clears all if initialize is true.
1139      Returns number of infeasibilities.
1140      If returns -1 then has worked out node is infeasible!
1141  */
1142  virtual int setupList ( OsiBranchingInformation *info, bool initialize);
1143  /** Choose a variable
1144      Returns -
1145     -1 Node is infeasible
1146     0  Normal termination - we have a candidate
1147     1  All looks satisfied - no candidate
1148     2  We can change the bound on a variable - but we also have a strong branching candidate
1149     3  We can change the bound on a variable - but we have a non-strong branching candidate
1150     4  We can change the bound on a variable - no other candidates
1151     We can pick up branch from bestObjectIndex() and bestWhichWay()
1152     We can pick up a forced branch (can change bound) from firstForcedObjectIndex() and firstForcedWhichWay()
1153     If we have a solution then we can pick up from goodObjectiveValue() and goodSolution()
1154     If fixVariables is true then 2,3,4 are all really same as problem changed
1155  */
1156  virtual int chooseVariable( OsiSolverInterface * solver, OsiBranchingInformation *info, bool fixVariables);
1157
1158  /// Number of objects to use
1159  inline int numberObjectsToUse() const
1160  { return numberObjectsToUse_;};
1161  /// Set number of objects to use
1162  inline void setNumberObjectsToUse(int value)
1163  { numberObjectsToUse_ = value;};
1164
1165protected:
1166  // Data
1167  /// Number of objects to be used (and set in solver)
1168  int numberObjectsToUse_;
1169};
1170
1171#include <string>
1172
1173#include "CglStored.hpp"
1174
1175class CoinWarmStartBasis;
1176/** Stored Temporary Cut Generator Class - destroyed after first use */
1177class CglTemporary : public CglStored {
1178 
1179public:
1180   
1181 
1182  /**@name Generate Cuts */
1183  //@{
1184  /** Generate Mixed Integer Stored cuts for the model of the
1185      solver interface, si.
1186
1187      Insert the generated cuts into OsiCut, cs.
1188
1189      This generator just looks at previously stored cuts
1190      and inserts any that are violated by enough
1191  */
1192  virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs,
1193                             const CglTreeInfo info = CglTreeInfo()) const;
1194  //@}
1195
1196  /**@name Constructors and destructors */
1197  //@{
1198  /// Default constructor
1199  CglTemporary ();
1200 
1201  /// Copy constructor
1202  CglTemporary (const CglTemporary & rhs);
1203
1204  /// Clone
1205  virtual CglCutGenerator * clone() const;
1206
1207  /// Assignment operator
1208  CglTemporary &
1209    operator=(const CglTemporary& rhs);
1210 
1211  /// Destructor
1212  virtual
1213    ~CglTemporary ();
1214  //@}
1215     
1216private:
1217 
1218 // Private member methods
1219
1220  // Private member data
1221};
1222//#############################################################################
1223
1224/**
1225   
1226This is to allow the user to replace initialSolve and resolve
1227*/
1228
1229class OsiSolverLinearizedQuadratic : public OsiClpSolverInterface {
1230 
1231public:
1232  //---------------------------------------------------------------------------
1233  /**@name Solve methods */
1234  //@{
1235  /// Solve initial LP relaxation
1236  virtual void initialSolve();
1237  //@}
1238 
1239 
1240  /**@name Constructors and destructors */
1241  //@{
1242  /// Default Constructor
1243  OsiSolverLinearizedQuadratic ();
1244  /// Useful constructor (solution should be good)
1245  OsiSolverLinearizedQuadratic(  ClpSimplex * quadraticModel);
1246  /// Clone
1247  virtual OsiSolverInterface * clone(bool copyData=true) const;
1248 
1249  /// Copy constructor
1250  OsiSolverLinearizedQuadratic (const OsiSolverLinearizedQuadratic &);
1251 
1252  /// Assignment operator
1253  OsiSolverLinearizedQuadratic & operator=(const OsiSolverLinearizedQuadratic& rhs);
1254 
1255  /// Destructor
1256  virtual ~OsiSolverLinearizedQuadratic ();
1257 
1258  //@}
1259 
1260 
1261  /**@name Sets and Gets */
1262  //@{
1263  /// Objective value of best solution found internally
1264  inline double bestObjectiveValue() const
1265  { return bestObjectiveValue_;};
1266  /// Best solution found internally
1267  const double * bestSolution() const
1268  { return bestSolution_;};
1269  /// Set special options
1270  inline void setSpecialOptions3(int value)
1271  { specialOptions3_=value;};
1272  /// Get special options
1273  inline int specialOptions3() const
1274  { return specialOptions3_;};
1275  /// Copy of quadratic model if one
1276  ClpSimplex * quadraticModel() const
1277  { return quadraticModel_;};
1278  //@}
1279 
1280  //---------------------------------------------------------------------------
1281 
1282protected:
1283 
1284 
1285  /**@name functions */
1286  //@{
1287 
1288  /**@name Private member data */
1289  //@{
1290  /// Objective value of best solution found internally
1291  double bestObjectiveValue_;
1292  /// Copy of quadratic model if one
1293  ClpSimplex * quadraticModel_;
1294  /// Best solution found internally
1295  double * bestSolution_;
1296  /**
1297     0 bit (1) - don't do mini B&B
1298     1 bit (2) - quadratic only in objective
1299  */
1300  int specialOptions3_;
1301  //@}
1302};
1303class ClpSimplex;
1304/** Return an approximate solution to a CoinModel.
1305    Lots of bounds may be odd to force a solution.
1306    mode = 0 just tries to get a continuous solution
1307*/
1308ClpSimplex * approximateSolution(CoinModel & coinModel, 
1309                                 int numberPasses, double deltaTolerance,
1310                                 int mode=0);
1311#endif
Note: See TracBrowser for help on using the repository browser.