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

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

take out };

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