source: stable/2.4/Cbc/src/CbcLinked.hpp @ 1271

Last change on this file since 1271 was 1271, checked in by forrest, 10 years ago

Creating new stable branch 2.4 from trunk (rev 1270)

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