source: branches/heur/Cbc/src/CbcLinked.hpp @ 885

Last change on this file since 885 was 774, checked in by forrest, 12 years ago

heuristics and nonlinear

File size: 38.4 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    double 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  using CbcHeuristic::solution ;
380  /** returns 0 if no solution, 1 if valid solution.
381      Sets solution values if good, sets objective value (only if good)
382      We leave all variables which are at one at this node of the
383      tree to that value and will
384      initially set all others to zero.  We then sort all variables in order of their cost
385      divided by the number of entries in rows which are not yet covered.  We randomize that
386      value a bit so that ties will be broken in different ways on different runs of the heuristic.
387      We then choose the best one and set it to one and repeat the exercise. 
388     
389  */
390  virtual int solution(double & objectiveValue,
391                       double * newSolution);
392  /// Resets stuff if model changes
393  virtual void resetModel(CbcModel * model);
394  /// Returns true if can deal with "odd" problems e.g. sos type 2
395  virtual bool canDealWithOdd() const
396  { return true;}
397 
398protected:
399private:
400  /// Illegal Assignment operator
401  CbcHeuristicDynamic3 & operator=(const CbcHeuristicDynamic3& rhs);
402};
403
404#include "OsiBranchingObject.hpp"
405
406/** Define Special Linked Ordered Sets.
407
408*/
409class CoinWarmStartBasis;
410
411class OsiOldLink : public OsiSOS {
412
413public:
414
415  // Default Constructor
416  OsiOldLink ();
417
418  /** Useful constructor - A valid solution is if all variables are zero
419      apart from k*numberLink to (k+1)*numberLink-1 where k is 0 through
420      numberInSet-1.  The length of weights array is numberInSet.
421      For this constructor the variables in matrix are the numberInSet*numberLink
422      starting at first. If weights null then 0,1,2..
423  */
424  OsiOldLink (const OsiSolverInterface * solver, int numberMembers,
425           int numberLinks, int first,
426           const double * weights, int setNumber);
427  /** Useful constructor - A valid solution is if all variables are zero
428      apart from k*numberLink to (k+1)*numberLink-1 where k is 0 through
429      numberInSet-1.  The length of weights array is numberInSet.
430      For this constructor the variables are given by list - grouped.
431      If weights null then 0,1,2..
432  */
433  OsiOldLink (const OsiSolverInterface * solver, int numberMembers,
434           int numberLinks, int typeSOS, const int * which,
435           const double * weights, int setNumber);
436 
437  // Copy constructor
438  OsiOldLink ( const OsiOldLink &);
439   
440  /// Clone
441  virtual OsiObject * clone() const;
442
443  // Assignment operator
444  OsiOldLink & operator=( const OsiOldLink& rhs);
445
446  // Destructor
447  virtual ~OsiOldLink ();
448 
449  using OsiObject::infeasibility ;
450  /// Infeasibility - large is 0.5
451  virtual double infeasibility(const OsiBranchingInformation * info,int & whichWay) const;
452
453  using OsiObject::feasibleRegion ;
454  /** Set bounds to fix the variable at the current (integer) value.
455
456    Given an integer value, set the lower and upper bounds to fix the
457    variable. Returns amount it had to move variable.
458  */
459  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
460
461  /** Creates a branching object
462
463    The preferred direction is set by \p way, 0 for down, 1 for up.
464  */
465  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
466
467  /// Redoes data when sequence numbers change
468  virtual void resetSequenceEtc(int numberColumns, const int * originalColumns);
469
470  /// Number of links for each member
471  inline int numberLinks() const
472  {return numberLinks_;}
473
474  /** \brief Return true if object can take part in normal heuristics
475  */
476  virtual bool canDoHeuristics() const 
477  {return false;}
478  /** \brief Return true if branch should only bound variables
479  */
480  virtual bool boundBranch() const 
481  {return false;}
482
483private:
484  /// data
485
486  /// Number of links
487  int numberLinks_;
488};
489/** Branching object for Linked ordered sets
490
491 */
492class OsiOldLinkBranchingObject : public OsiSOSBranchingObject {
493
494public:
495
496  // Default Constructor
497  OsiOldLinkBranchingObject ();
498
499  // Useful constructor
500  OsiOldLinkBranchingObject (OsiSolverInterface * solver,  const OsiOldLink * originalObject,
501                          int way,
502                          double separator);
503 
504  // Copy constructor
505  OsiOldLinkBranchingObject ( const OsiOldLinkBranchingObject &);
506   
507  // Assignment operator
508  OsiOldLinkBranchingObject & operator=( const OsiOldLinkBranchingObject& rhs);
509
510  /// Clone
511  virtual OsiBranchingObject * clone() const;
512
513  // Destructor
514  virtual ~OsiOldLinkBranchingObject ();
515 
516  using OsiBranchingObject::branch ;
517  /// Does next branch and updates state
518  virtual double branch(OsiSolverInterface * solver);
519
520  using OsiBranchingObject::print ;
521  /** \brief Print something about branch - only if log level high
522  */
523  virtual void print(const OsiSolverInterface * solver=NULL);
524private:
525  /// data
526};
527/** Define data for one link
528   
529*/
530
531
532class OsiOneLink {
533
534public:
535
536  // Default Constructor
537  OsiOneLink ();
538
539  /** Useful constructor -
540     
541  */
542  OsiOneLink (const OsiSolverInterface * solver, int xRow, int xColumn, int xyRow,
543              const char * functionString);
544 
545  // Copy constructor
546  OsiOneLink ( const OsiOneLink &);
547   
548  // Assignment operator
549  OsiOneLink & operator=( const OsiOneLink& rhs);
550
551  // Destructor
552  virtual ~OsiOneLink ();
553 
554  /// data
555
556  /// Row which defines x (if -1 then no x)
557  int xRow_;
558  /// Column which defines x
559  int xColumn_;
560  /// Output row
561  int xyRow;
562  /// Function
563  std::string function_;
564};
565/** Define Special Linked Ordered Sets. New style
566
567    members and weights may be stored in SOS object
568
569    This is for y and x*f(y) and z*g(y) etc
570
571*/
572
573
574class OsiLink : public OsiSOS {
575
576public:
577
578  // Default Constructor
579  OsiLink ();
580
581  /** Useful constructor -
582     
583  */
584  OsiLink (const OsiSolverInterface * solver, int yRow,
585           int yColumn, double meshSize);
586 
587  // Copy constructor
588  OsiLink ( const OsiLink &);
589   
590  /// Clone
591  virtual OsiObject * clone() const;
592
593  // Assignment operator
594  OsiLink & operator=( const OsiLink& rhs);
595
596  // Destructor
597  virtual ~OsiLink ();
598 
599  using OsiObject::infeasibility ;
600  /// Infeasibility - large is 0.5
601  virtual double infeasibility(const OsiBranchingInformation * info,int & whichWay) const;
602
603  using OsiObject::feasibleRegion ;
604  /** Set bounds to fix the variable at the current (integer) value.
605
606    Given an integer value, set the lower and upper bounds to fix the
607    variable. Returns amount it had to move variable.
608  */
609  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
610
611  /** Creates a branching object
612
613    The preferred direction is set by \p way, 0 for down, 1 for up.
614  */
615  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
616
617  /// Redoes data when sequence numbers change
618  virtual void resetSequenceEtc(int numberColumns, const int * originalColumns);
619
620  /// Number of links for each member
621  inline int numberLinks() const
622  {return numberLinks_;}
623
624  /** \brief Return true if object can take part in normal heuristics
625  */
626  virtual bool canDoHeuristics() const 
627  {return false;}
628  /** \brief Return true if branch should only bound variables
629  */
630  virtual bool boundBranch() const 
631  {return false;}
632
633private:
634  /// data
635  /// Current increment for y points
636  double meshSize_;
637  /// Links
638  OsiOneLink * data_;
639  /// Number of links
640  int numberLinks_;
641  /// Row which defines y
642  int yRow_;
643  /// Column which defines y
644  int yColumn_;
645};
646/** Branching object for Linked ordered sets
647
648 */
649class OsiLinkBranchingObject : public OsiTwoWayBranchingObject {
650
651public:
652
653  // Default Constructor
654  OsiLinkBranchingObject ();
655
656  // Useful constructor
657  OsiLinkBranchingObject (OsiSolverInterface * solver,  const OsiLink * originalObject,
658                          int way,
659                          double separator);
660 
661  // Copy constructor
662  OsiLinkBranchingObject ( const OsiLinkBranchingObject &);
663   
664  // Assignment operator
665  OsiLinkBranchingObject & operator=( const OsiLinkBranchingObject& rhs);
666
667  /// Clone
668  virtual OsiBranchingObject * clone() const;
669
670  // Destructor
671  virtual ~OsiLinkBranchingObject ();
672 
673  using OsiBranchingObject::branch ;
674  /// Does next branch and updates state
675  virtual double branch(OsiSolverInterface * solver);
676
677  using OsiBranchingObject::print ;
678  /** \brief Print something about branch - only if log level high
679  */
680  virtual void print(const OsiSolverInterface * solver=NULL);
681private:
682  /// data
683};
684/** Define BiLinear objects
685
686    This models x*y where one or both are integer
687
688*/
689
690
691class OsiBiLinear : public OsiObject2 {
692
693public:
694
695  // Default Constructor
696  OsiBiLinear ();
697
698  /** Useful constructor -
699      This Adds in rows and variables to construct valid Linked Ordered Set
700      Adds extra constraints to match other x/y
701      So note not const solver
702  */
703  OsiBiLinear (OsiSolverInterface * solver, int xColumn,
704               int yColumn, int xyRow, double coefficient,
705               double xMesh, double yMesh,
706               int numberExistingObjects=0,const OsiObject ** objects=NULL );
707 
708  /** Useful constructor -
709      This Adds in rows and variables to construct valid Linked Ordered Set
710      Adds extra constraints to match other x/y
711      So note not const model
712  */
713  OsiBiLinear (CoinModel * coinModel, int xColumn,
714               int yColumn, int xyRow, double coefficient,
715               double xMesh, double yMesh,
716               int numberExistingObjects=0,const OsiObject ** objects=NULL );
717 
718  // Copy constructor
719  OsiBiLinear ( const OsiBiLinear &);
720   
721  /// Clone
722  virtual OsiObject * clone() const;
723
724  // Assignment operator
725  OsiBiLinear & operator=( const OsiBiLinear& rhs);
726
727  // Destructor
728  virtual ~OsiBiLinear ();
729 
730  using OsiObject::infeasibility ;
731  /// Infeasibility - large is 0.5
732  virtual double infeasibility(const OsiBranchingInformation * info,int & whichWay) const;
733
734  using OsiObject::feasibleRegion ;
735  /** Set bounds to fix the variable at the current (integer) value.
736
737    Given an integer value, set the lower and upper bounds to fix the
738    variable. Returns amount it had to move variable.
739  */
740  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
741
742  /** Creates a branching object
743
744    The preferred direction is set by \p way, 0 for down, 1 for up.
745  */
746  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
747
748  /// Redoes data when sequence numbers change
749  virtual void resetSequenceEtc(int numberColumns, const int * originalColumns);
750
751  // This does NOT set mutable stuff
752  virtual double checkInfeasibility(const OsiBranchingInformation * info) const;
753 
754  /** \brief Return true if object can take part in normal heuristics
755  */
756  virtual bool canDoHeuristics() const 
757  {return false;}
758  /** \brief Return true if branch should only bound variables
759  */
760  virtual bool boundBranch() const 
761  { return (branchingStrategy_&4)!=0;}
762  /// X column
763  inline int xColumn() const
764  { return xColumn_;}
765  /// Y column
766  inline int yColumn() const
767  { return yColumn_;}
768  /// X row
769  inline int xRow() const
770  { return xRow_;}
771  /// Y row
772  inline int yRow() const
773  { return yRow_;}
774  /// XY row
775  inline int xyRow() const
776  { return xyRow_;}
777  /// Coefficient
778  inline double coefficient() const
779  { return coefficient_;}
780  /// Set coefficient
781  inline void setCoefficient(double value)
782  { coefficient_ = value;}
783  /// First lambda (of 4)
784  inline int firstLambda() const
785  { return firstLambda_;}
786  /// X satisfied if less than this away from mesh
787  inline double xSatisfied() const
788  { return xSatisfied_;}
789  inline void setXSatisfied(double value)
790  { xSatisfied_=value;}
791  /// Y satisfied if less than this away from mesh
792  inline double ySatisfied() const
793  { return ySatisfied_;}
794  inline void setYSatisfied(double value)
795  { ySatisfied_=value;}
796  /// X other satisfied if less than this away from mesh
797  inline double xOtherSatisfied() const
798  { return xOtherSatisfied_;}
799  inline void setXOtherSatisfied(double value)
800  { xOtherSatisfied_=value;}
801  /// Y other satisfied if less than this away from mesh
802  inline double yOtherSatisfied() const
803  { return yOtherSatisfied_;}
804  inline void setYOtherSatisfied(double value)
805  { yOtherSatisfied_=value;}
806  /// X meshSize
807  inline double xMeshSize() const
808  { return xMeshSize_;}
809  inline void setXMeshSize(double value)
810  { xMeshSize_=value;}
811  /// Y meshSize
812  inline double yMeshSize() const
813  { return yMeshSize_;}
814  inline void setYMeshSize(double value)
815  { yMeshSize_=value;}
816  /// XY satisfied if two version differ by less than this
817  inline double xySatisfied() const
818  { return xySatisfied_;}
819  inline void setXYSatisfied(double value)
820  { xySatisfied_=value;}
821  /// Set sizes and other stuff
822  void setMeshSizes(const OsiSolverInterface * solver, double x, double y);
823  /** branching strategy etc
824      bottom 2 bits
825      0 branch on either, 1 branch on x, 2 branch on y
826      next bit
827      4 set to say don't update coefficients
828      next bit
829      8 set to say don't use in feasible region
830      next bit
831      16 set to say - Always satisfied !!
832  */
833  inline int branchingStrategy() const
834  { return branchingStrategy_;}
835  inline void setBranchingStrategy(int value)
836  { branchingStrategy_=value;}
837  /** Simple quadratic bound marker.
838      0 no
839      1 L if coefficient pos, G if negative i.e. value is ub on xy
840      2 G if coefficient pos, L if negative i.e. value is lb on xy
841      3 E
842      If bound then real coefficient is 1.0 and coefficient_ is bound
843  */
844  inline int boundType() const
845  { return boundType_;}
846  inline void setBoundType(int value)
847  { boundType_ = value;}
848  /// Does work of branching
849  void newBounds(OsiSolverInterface * solver, int way, short xOrY, double separator) const;
850  /// Updates coefficients - returns number updated
851  int updateCoefficients(const double * lower, const double * upper, double * objective,
852                          CoinPackedMatrix * matrix, CoinWarmStartBasis * basis) const;
853  /// Returns true value of single xyRow coefficient
854  double xyCoefficient(const double * solution) const;
855  /// Get LU coefficients from matrix
856  void getCoefficients(const OsiSolverInterface * solver,double xB[2], double yB[2], double xybar[4]) const;
857  /// Compute lambdas (third entry in each .B is current value) (nonzero if bad)
858  double computeLambdas(const double xB[3], const double yB[3],const double xybar[4],double lambda[4]) const;
859  /// Adds in data for extra row with variable coefficients
860  void addExtraRow(int row, double multiplier);
861  /// Sets infeasibility and other when pseudo shadow prices
862  void getPseudoShadow(const OsiBranchingInformation * info);
863  /// Gets sum of movements to correct value
864  double getMovement(const OsiBranchingInformation * info);
865
866protected:
867  /// Compute lambdas if coefficients not changing
868  void computeLambdas(const OsiSolverInterface * solver,double lambda[4]) const;
869  /// data
870 
871  /// Coefficient
872  double coefficient_;
873  /// x mesh
874  double xMeshSize_;
875  /// y mesh
876  double yMeshSize_;
877  /// x satisfied if less than this away from mesh
878  double xSatisfied_;
879  /// y satisfied if less than this away from mesh
880  double ySatisfied_;
881  /// X other satisfied if less than this away from mesh
882  double xOtherSatisfied_;
883  /// Y other satisfied if less than this away from mesh
884  double yOtherSatisfied_;
885  /// xy satisfied if less than this away from true
886  double xySatisfied_;
887  /// value of x or y to branch about
888  mutable double xyBranchValue_;
889  /// x column
890  int xColumn_;
891  /// y column
892  int yColumn_;
893  /// First lambda (of 4)
894  int firstLambda_;
895  /** branching strategy etc
896      bottom 2 bits
897      0 branch on either, 1 branch on x, 2 branch on y
898      next bit
899      4 set to say don't update coefficients
900      next bit
901      8 set to say don't use in feasible region
902      next bit
903      16 set to say - Always satisfied !!
904  */
905  int branchingStrategy_;
906  /** Simple quadratic bound marker.
907      0 no
908      1 L if coefficient pos, G if negative i.e. value is ub on xy
909      2 G if coefficient pos, L if negative i.e. value is lb on xy
910      3 E
911      If bound then real coefficient is 1.0 and coefficient_ is bound
912  */
913  int boundType_;
914  /// x row
915  int xRow_;
916  /// y row (-1 if x*x)
917  int yRow_;
918  /// Output row
919  int xyRow_;
920  /// Convexity row
921  int convexity_;
922  /// Number of extra rows (coefficients to be modified)
923  int numberExtraRows_;
924  /// Multiplier for coefficient on row
925  double * multiplier_;
926  /// Row number
927  int * extraRow_;
928  /// Which chosen -1 none, 0 x, 1 y
929  mutable short chosen_;
930};
931/** Branching object for BiLinear objects
932
933 */
934class OsiBiLinearBranchingObject : public OsiTwoWayBranchingObject {
935
936public:
937
938  // Default Constructor
939  OsiBiLinearBranchingObject ();
940
941  // Useful constructor
942  OsiBiLinearBranchingObject (OsiSolverInterface * solver,  const OsiBiLinear * originalObject,
943                          int way,
944                          double separator, int chosen);
945 
946  // Copy constructor
947  OsiBiLinearBranchingObject ( const OsiBiLinearBranchingObject &);
948   
949  // Assignment operator
950  OsiBiLinearBranchingObject & operator=( const OsiBiLinearBranchingObject& rhs);
951
952  /// Clone
953  virtual OsiBranchingObject * clone() const;
954
955  // Destructor
956  virtual ~OsiBiLinearBranchingObject ();
957 
958  using OsiBranchingObject::branch ;
959  /// Does next branch and updates state
960  virtual double branch(OsiSolverInterface * solver);
961
962  using OsiBranchingObject::print ;
963  /** \brief Print something about branch - only if log level high
964  */
965  virtual void print(const OsiSolverInterface * solver=NULL);
966  /** \brief Return true if branch should only bound variables
967  */
968  virtual bool boundBranch() const; 
969private:
970  /// data
971  /// 1 means branch on x, 2 branch on y
972  short chosen_;
973};
974/** Define Continuous BiLinear objects for an == bound
975
976    This models x*y = b where both are continuous
977
978*/
979
980
981class OsiBiLinearEquality : public OsiBiLinear {
982
983public:
984
985  // Default Constructor
986  OsiBiLinearEquality ();
987
988  /** Useful constructor -
989      This Adds in rows and variables to construct Ordered Set
990      for x*y = b
991      So note not const solver
992  */
993  OsiBiLinearEquality (OsiSolverInterface * solver, int xColumn,
994               int yColumn, int xyRow, double rhs,
995                       double xMesh);
996 
997  // Copy constructor
998  OsiBiLinearEquality ( const OsiBiLinearEquality &);
999   
1000  /// Clone
1001  virtual OsiObject * clone() const;
1002
1003  // Assignment operator
1004  OsiBiLinearEquality & operator=( const OsiBiLinearEquality& rhs);
1005
1006  // Destructor
1007  virtual ~OsiBiLinearEquality ();
1008 
1009  /// Possible improvement
1010  virtual double improvement(const OsiSolverInterface * solver) const;
1011  /** change grid
1012      if type 0 then use solution and make finer
1013      if 1 then back to original
1014      returns mesh size
1015  */
1016  double newGrid(OsiSolverInterface * solver, int type) const;
1017  /// Number of points
1018  inline int numberPoints() const
1019  { return numberPoints_;}
1020  inline void setNumberPoints(int value)
1021  { numberPoints_ = value;}
1022
1023private:
1024  /// Number of points
1025  int numberPoints_;
1026};
1027/// Define a single integer class - but one where you keep branching until fixed even if satisfied
1028
1029
1030class OsiSimpleFixedInteger : public OsiSimpleInteger {
1031
1032public:
1033
1034  /// Default Constructor
1035  OsiSimpleFixedInteger ();
1036
1037  /// Useful constructor - passed solver index
1038  OsiSimpleFixedInteger (const OsiSolverInterface * solver, int iColumn);
1039 
1040  /// Useful constructor - passed solver index and original bounds
1041  OsiSimpleFixedInteger (int iColumn, double lower, double upper);
1042 
1043  /// Useful constructor - passed simple integer
1044  OsiSimpleFixedInteger (const OsiSimpleInteger &);
1045 
1046  /// Copy constructor
1047  OsiSimpleFixedInteger ( const OsiSimpleFixedInteger &);
1048   
1049  /// Clone
1050  virtual OsiObject * clone() const;
1051
1052  /// Assignment operator
1053  OsiSimpleFixedInteger & operator=( const OsiSimpleFixedInteger& rhs);
1054
1055  /// Destructor
1056  virtual ~OsiSimpleFixedInteger ();
1057 
1058  using OsiObject::infeasibility ;
1059  /// Infeasibility - large is 0.5
1060  virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const;
1061
1062  /** Creates a branching object
1063
1064    The preferred direction is set by \p way, 0 for down, 1 for up.
1065  */
1066  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
1067protected:
1068  /// data
1069 
1070};
1071/** Define a single variable class which is involved with OsiBiLinear objects.
1072    This is used so can make better decision on where to branch as it can look at
1073    all objects.
1074
1075    This version sees if it can re-use code from OsiSimpleInteger
1076    even if not an integer variable.  If not then need to duplicate code.
1077*/
1078
1079
1080class OsiUsesBiLinear : public OsiSimpleInteger {
1081
1082public:
1083
1084  /// Default Constructor
1085  OsiUsesBiLinear ();
1086
1087  /// Useful constructor - passed solver index
1088  OsiUsesBiLinear (const OsiSolverInterface * solver, int iColumn, int type);
1089 
1090  /// Useful constructor - passed solver index and original bounds
1091  OsiUsesBiLinear (int iColumn, double lower, double upper, int type);
1092 
1093  /// Useful constructor - passed simple integer
1094  OsiUsesBiLinear (const OsiSimpleInteger & rhs, int type);
1095 
1096  /// Copy constructor
1097  OsiUsesBiLinear ( const OsiUsesBiLinear & rhs);
1098   
1099  /// Clone
1100  virtual OsiObject * clone() const;
1101
1102  /// Assignment operator
1103  OsiUsesBiLinear & operator=( const OsiUsesBiLinear& rhs);
1104
1105  /// Destructor
1106  virtual ~OsiUsesBiLinear ();
1107 
1108  using OsiObject::infeasibility ;
1109  /// Infeasibility - large is 0.5
1110  virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const;
1111
1112  /** Creates a branching object
1113
1114    The preferred direction is set by \p way, 0 for down, 1 for up.
1115  */
1116  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
1117
1118  using OsiObject::feasibleRegion ;
1119  /** Set bounds to fix the variable at the current value.
1120
1121    Given an current value, set the lower and upper bounds to fix the
1122    variable. Returns amount it had to move variable.
1123  */
1124  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
1125
1126  /// Add all bi-linear objects
1127  void addBiLinearObjects(OsiSolverLink * solver);
1128protected:
1129  /// data
1130  /// Number of bilinear objects (maybe could be more general)
1131  int numberBiLinear_;
1132  /// Type of variable - 0 continuous, 1 integer
1133  int type_;
1134  /// Objects
1135  OsiObject ** objects_;
1136};
1137/** This class chooses a variable to branch on
1138
1139    This is just as OsiChooseStrong but it fakes it so only
1140    first so many are looked at in this phase
1141
1142*/
1143
1144class OsiChooseStrongSubset  : public OsiChooseStrong {
1145 
1146public:
1147   
1148  /// Default Constructor
1149  OsiChooseStrongSubset ();
1150
1151  /// Constructor from solver (so we can set up arrays etc)
1152  OsiChooseStrongSubset (const OsiSolverInterface * solver);
1153
1154  /// Copy constructor
1155  OsiChooseStrongSubset (const OsiChooseStrongSubset &);
1156   
1157  /// Assignment operator
1158  OsiChooseStrongSubset & operator= (const OsiChooseStrongSubset& rhs);
1159
1160  /// Clone
1161  virtual OsiChooseVariable * clone() const;
1162
1163  /// Destructor
1164  virtual ~OsiChooseStrongSubset ();
1165
1166  /** Sets up strong list and clears all if initialize is true.
1167      Returns number of infeasibilities.
1168      If returns -1 then has worked out node is infeasible!
1169  */
1170  virtual int setupList ( OsiBranchingInformation *info, bool initialize);
1171  /** Choose a variable
1172      Returns -
1173     -1 Node is infeasible
1174     0  Normal termination - we have a candidate
1175     1  All looks satisfied - no candidate
1176     2  We can change the bound on a variable - but we also have a strong branching candidate
1177     3  We can change the bound on a variable - but we have a non-strong branching candidate
1178     4  We can change the bound on a variable - no other candidates
1179     We can pick up branch from bestObjectIndex() and bestWhichWay()
1180     We can pick up a forced branch (can change bound) from firstForcedObjectIndex() and firstForcedWhichWay()
1181     If we have a solution then we can pick up from goodObjectiveValue() and goodSolution()
1182     If fixVariables is true then 2,3,4 are all really same as problem changed
1183  */
1184  virtual int chooseVariable( OsiSolverInterface * solver, OsiBranchingInformation *info, bool fixVariables);
1185
1186  /// Number of objects to use
1187  inline int numberObjectsToUse() const
1188  { return numberObjectsToUse_;}
1189  /// Set number of objects to use
1190  inline void setNumberObjectsToUse(int value)
1191  { numberObjectsToUse_ = value;}
1192
1193protected:
1194  // Data
1195  /// Number of objects to be used (and set in solver)
1196  int numberObjectsToUse_;
1197};
1198
1199#include <string>
1200
1201#include "CglStored.hpp"
1202
1203class CoinWarmStartBasis;
1204/** Stored Temporary Cut Generator Class - destroyed after first use */
1205class CglTemporary : public CglStored {
1206 
1207public:
1208   
1209 
1210  /**@name Generate Cuts */
1211  //@{
1212  /** Generate Mixed Integer Stored cuts for the model of the
1213      solver interface, si.
1214
1215      Insert the generated cuts into OsiCut, cs.
1216
1217      This generator just looks at previously stored cuts
1218      and inserts any that are violated by enough
1219  */
1220  virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs,
1221                             const CglTreeInfo info = CglTreeInfo()) const;
1222  //@}
1223
1224  /**@name Constructors and destructors */
1225  //@{
1226  /// Default constructor
1227  CglTemporary ();
1228 
1229  /// Copy constructor
1230  CglTemporary (const CglTemporary & rhs);
1231
1232  /// Clone
1233  virtual CglCutGenerator * clone() const;
1234
1235  /// Assignment operator
1236  CglTemporary &
1237    operator=(const CglTemporary& rhs);
1238 
1239  /// Destructor
1240  virtual
1241    ~CglTemporary ();
1242  //@}
1243     
1244private:
1245 
1246 // Private member methods
1247
1248  // Private member data
1249};
1250//#############################################################################
1251
1252/**
1253   
1254This is to allow the user to replace initialSolve and resolve
1255*/
1256
1257class OsiSolverLinearizedQuadratic : public OsiClpSolverInterface {
1258 
1259public:
1260  //---------------------------------------------------------------------------
1261  /**@name Solve methods */
1262  //@{
1263  /// Solve initial LP relaxation
1264  virtual void initialSolve();
1265  //@}
1266 
1267 
1268  /**@name Constructors and destructors */
1269  //@{
1270  /// Default Constructor
1271  OsiSolverLinearizedQuadratic ();
1272  /// Useful constructor (solution should be good)
1273  OsiSolverLinearizedQuadratic(  ClpSimplex * quadraticModel);
1274  /// Clone
1275  virtual OsiSolverInterface * clone(bool copyData=true) const;
1276 
1277  /// Copy constructor
1278  OsiSolverLinearizedQuadratic (const OsiSolverLinearizedQuadratic &);
1279 
1280  /// Assignment operator
1281  OsiSolverLinearizedQuadratic & operator=(const OsiSolverLinearizedQuadratic& rhs);
1282 
1283  /// Destructor
1284  virtual ~OsiSolverLinearizedQuadratic ();
1285 
1286  //@}
1287 
1288 
1289  /**@name Sets and Gets */
1290  //@{
1291  /// Objective value of best solution found internally
1292  inline double bestObjectiveValue() const
1293  { return bestObjectiveValue_;}
1294  /// Best solution found internally
1295  const double * bestSolution() const
1296  { return bestSolution_;}
1297  /// Set special options
1298  inline void setSpecialOptions3(int value)
1299  { specialOptions3_=value;}
1300  /// Get special options
1301  inline int specialOptions3() const
1302  { return specialOptions3_;}
1303  /// Copy of quadratic model if one
1304  ClpSimplex * quadraticModel() const
1305  { return quadraticModel_;}
1306  //@}
1307 
1308  //---------------------------------------------------------------------------
1309 
1310protected:
1311 
1312 
1313  /**@name functions */
1314  //@{
1315 
1316  /**@name Private member data */
1317  //@{
1318  /// Objective value of best solution found internally
1319  double bestObjectiveValue_;
1320  /// Copy of quadratic model if one
1321  ClpSimplex * quadraticModel_;
1322  /// Best solution found internally
1323  double * bestSolution_;
1324  /**
1325     0 bit (1) - don't do mini B&B
1326     1 bit (2) - quadratic only in objective
1327  */
1328  int specialOptions3_;
1329  //@}
1330};
1331class ClpSimplex;
1332/** Return an approximate solution to a CoinModel.
1333    Lots of bounds may be odd to force a solution.
1334    mode = 0 just tries to get a continuous solution
1335*/
1336ClpSimplex * approximateSolution(CoinModel & coinModel, 
1337                                 int numberPasses, double deltaTolerance,
1338                                 int mode=0);
1339#endif
Note: See TracBrowser for help on using the repository browser.