coin-Cgl
CglProbing.hpp
Go to the documentation of this file.
1 // Copyright (C) 2002, International Business Machines
2 // Corporation and others. All Rights Reserved.
3 #ifndef CglProbing_H
4 #define CglProbing_H
5 
6 #include <string>
7 
8 #include "CglCutGenerator.hpp"
13  typedef struct {
14  //unsigned int zeroOne:1; // nonzero if affected variable is 0-1
15  //unsigned int whenAtUB:1; // nonzero if fixing happens when this variable at 1
16  //unsigned int affectedToUB:1; // nonzero if affected variable fixed to UB
17  //unsigned int affected:29; // If 0-1 then 0-1 sequence, otherwise true
18  unsigned int affected;
20 
22 class CglProbing : public CglCutGenerator {
23  friend void CglProbingUnitTest(const OsiSolverInterface * siP,
24  const std::string mpdDir );
25 
26 public:
27 
28 
96  virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs,
97  const CglTreeInfo info = CglTreeInfo()) const;
98  int generateCutsAndModify( const OsiSolverInterface & si, OsiCuts & cs,
99  CglTreeInfo * info);
101 
112  int snapshot ( const OsiSolverInterface & si,
113  char * possible=NULL,
114  bool withObjective=true);
116  void deleteSnapshot ( );
122  int createCliques( OsiSolverInterface & si,
123  int minimumSize=2, int maximumSize=100);
125  void deleteCliques();
127 
130  const double * tightLower() const;
133  const double * tightUpper() const;
135  const char * tightenBounds() const
136  { return tightenBounds_;}
138 
141  const double * relaxedRowLower() const;
144  const double * relaxedRowUpper() const;
146 
149  void setMode(int mode);
152  int getMode() const;
154 
157  void setMaxPass(int value);
160  int getMaxPass() const;
162  void setLogLevel(int value);
164  int getLogLevel() const;
166  void setMaxProbe(int value);
168  int getMaxProbe() const;
170  void setMaxLook(int value);
172  int getMaxLook() const;
174  void setMaxElements(int value);
176  int getMaxElements() const;
178  void setMaxPassRoot(int value);
180  int getMaxPassRoot() const;
182  void setMaxProbeRoot(int value);
184  int getMaxProbeRoot() const;
186  void setMaxLookRoot(int value);
188  int getMaxLookRoot() const;
190  void setMaxElementsRoot(int value);
192  int getMaxElementsRoot() const;
200  virtual bool mayGenerateRowCutsInTree() const;
202 
205  inline int numberThisTime() const
207  { return numberThisTime_;}
209  inline const int * lookedAt() const
210  { return lookedAt_;}
212 
215  void setRowCuts(int type);
219  int rowCuts() const;
221 
229  void setUsingObjective(int yesNo);
231  int getUsingObjective() const;
233 
236  void tightenThese(const OsiSolverInterface & solver, int number, const int * which);
239 
242  CglProbing ();
244 
246  CglProbing (
247  const CglProbing &);
248 
250  virtual CglCutGenerator * clone() const;
251 
253  CglProbing &
254  operator=(
255  const CglProbing& rhs);
256 
258  virtual
259  ~CglProbing ();
260 
262  virtual void refreshSolver(OsiSolverInterface * solver);
264  virtual std::string generateCpp( FILE * fp);
266 
267 private:
268 
269  // Private member methods
272  int probe( const OsiSolverInterface & si,
274  const OsiRowCutDebugger * debugger,
275  OsiCuts & cs,
276  double * colLower, double * colUpper, CoinPackedMatrix *rowCopy,
277  CoinPackedMatrix *columnCopy,const CoinBigIndex * rowStartPos,
278  const int * realRow, const double * rowLower, const double * rowUpper,
279  const char * intVar, double * minR, double * maxR, int * markR,
280  CglTreeInfo * info) const;
282  int probeCliques( const OsiSolverInterface & si,
283  const OsiRowCutDebugger * debugger,
284  OsiCuts & cs,
285  double * colLower, double * colUpper, CoinPackedMatrix *rowCopy,
286  CoinPackedMatrix *columnCopy, const int * realRow,
287  double * rowLower, double * rowUpper,
288  char * intVar, double * minR, double * maxR, int * markR,
289  CglTreeInfo * info) const;
291  int probeSlacks( const OsiSolverInterface & si,
292  const OsiRowCutDebugger * debugger,
293  OsiCuts & cs,
294  double * colLower, double * colUpper, CoinPackedMatrix *rowCopy,
295  CoinPackedMatrix *columnCopy,
296  double * rowLower, double * rowUpper,
297  char * intVar, double * minR, double * maxR,int * markR,
298  CglTreeInfo * info) const;
301  int gutsOfGenerateCuts( const OsiSolverInterface & si,
302  OsiCuts & cs,
303  double * rowLower, double * rowUpper,
304  double * colLower, double * colUpper,
305  CglTreeInfo * info) const;
307  void setupRowCliqueInformation(const OsiSolverInterface & si);
310  int tighten(double *colLower, double * colUpper,
311  const int *column, const double *rowElements,
312  const CoinBigIndex *rowStart,const CoinBigIndex * rowStartPos,
313  const int * rowLength,
314  double *rowLower, double *rowUpper,
315  int nRows,int nCols,char * intVar,int maxpass,
316  double tolerance) const;
318  void tighten2(double *colLower, double * colUpper,
319  const int *column, const double *rowElements,
320  const CoinBigIndex *rowStart,
321  const int * rowLength,
322  double *rowLower, double *rowUpper,
323  double * minR, double * maxR, int * markR,
324  int nRows) const;
326 
327  // Private member data
328 
331 
334  CoinPackedMatrix * rowCopy_;
337  CoinPackedMatrix * columnCopy_;
339  double * rowLower_;
341  double * rowUpper_;
343  mutable double * colLower_;
345  mutable double * colUpper_;
347  mutable int numberRows_;
349  mutable int numberColumns_;
355  int mode_;
360  mutable int rowCuts_;
362  int maxPass_;
386  mutable int numberThisTime_;
388  mutable int totalTimesCalled_;
390  mutable int * lookedAt_;
392  typedef struct disaggregation_struct_tag {
393  int sequence; // integer variable
394  // index will be NULL if no probing done yet
395  int length; // length of newValue
396  disaggregationAction * index; // columns whose bounds will be changed
397  } disaggregation;
403  typedef struct {
404  unsigned int equality:1; // nonzero if clique is ==
405  } cliqueType;
431 };
433 { return dis.affected&0x1fffffff;}
435  int affected)
436 { dis.affected = affected|(dis.affected&0xe0000000);}
437 #ifdef NDEBUG
438 inline bool zeroOneInDisaggregation(const disaggregationAction & )
439 { return true;}
440 #else
442 //{ return (dis.affected&0x80000000)!=0;}
443 { assert ((dis.affected&0x80000000)!=0); return true;}
444 #endif
445 inline void setZeroOneInDisaggregation(disaggregationAction & dis,bool zeroOne)
446 { dis.affected = (zeroOne ? 0x80000000 : 0)|(dis.affected&0x7fffffff);}
448 { return (dis.affected&0x40000000)!=0;}
449 inline void setWhenAtUBInDisaggregation(disaggregationAction & dis,bool whenAtUB)
450 { dis.affected = (whenAtUB ? 0x40000000 : 0)|(dis.affected&0xbfffffff);}
452 { return (dis.affected&0x20000000)!=0;}
453 inline void setAffectedToUBInDisaggregation(disaggregationAction & dis,bool affectedToUB)
454 { dis.affected = (affectedToUB ? 0x20000000 : 0)|(dis.affected&0xdfffffff);}
455 
456 //#############################################################################
462 void CglProbingUnitTest(const OsiSolverInterface * siP,
463  const std::string mpdDir );
466 
467 public:
468 
474  virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs,
475  const CglTreeInfo info = CglTreeInfo()) const;
477 
480  CglImplication ();
482 
485 
488  const CglImplication &);
489 
491  virtual CglCutGenerator * clone() const;
492 
495  operator=(
496  const CglImplication& rhs);
497 
499  virtual
500  ~CglImplication ();
502  virtual std::string generateCpp( FILE * fp);
504 
506  inline void setProbingInfo(CglTreeProbingInfo * info)
508  { probingInfo_=info;}
510 
511 private:
517 };
518 #endif
int numberRows_
Number of rows in snapshot (or when cliqueRow stuff computed)
Definition: CglProbing.hpp:347
virtual ~CglProbing()
Destructor.
int totalTimesCalled_
Total number of times called.
Definition: CglProbing.hpp:388
void setMaxLookRoot(int value)
Set maximum number of variables to look at in one probe (root node)
const double * tightLower() const
Lower.
void tighten2(double *colLower, double *colUpper, const int *column, const double *rowElements, const CoinBigIndex *rowStart, const int *rowLength, double *rowLower, double *rowUpper, double *minR, double *maxR, int *markR, int nRows) const
This just sets minima and maxima on rows.
CglImplication()
Default constructor.
void setMaxElements(int value)
Set maximum number of elements in row for it to be considered.
void setProbingInfo(CglTreeProbingInfo *info)
Set implication.
Definition: CglProbing.hpp:507
struct CglProbing::disaggregation_struct_tag disaggregation
Disaggregation cuts and for building cliques.
CglImplication & operator=(const CglImplication &rhs)
Assignment operator.
int rowCuts() const
Get.
void setMaxProbe(int value)
Set maximum number of unsatisfied variables to look at.
int getLogLevel() const
Get log level.
virtual CglCutGenerator * clone() const
Clone.
int * cliqueRowStart_
cliqueRow_ starts for each row
Definition: CglProbing.hpp:427
char * tightenBounds_
If not null and [i] !=0 then also tighten even if continuous.
Definition: CglProbing.hpp:429
virtual bool mayGenerateRowCutsInTree() const
Returns true if may generate Row cuts in tree (rather than root node).
bool zeroOneInDisaggregation(const disaggregationAction &dis)
Definition: CglProbing.hpp:441
void setAffectedToUBInDisaggregation(disaggregationAction &dis, bool affectedToUB)
Definition: CglProbing.hpp:453
int * oneFixStart_
Start of oneFixes cliques for a column in matrix or -1 if not in any clique.
Definition: CglProbing.hpp:413
void CglProbingUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglProbing class.
int * zeroFixStart_
Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.
Definition: CglProbing.hpp:416
int probeCliques(const OsiSolverInterface &si, const OsiRowCutDebugger *debugger, OsiCuts &cs, double *colLower, double *colUpper, CoinPackedMatrix *rowCopy, CoinPackedMatrix *columnCopy, const int *realRow, double *rowLower, double *rowUpper, char *intVar, double *minR, double *maxR, int *markR, CglTreeInfo *info) const
Does probing and adding cuts (with cliques)
CglTreeProbingInfo * probingInfo_
Pointer to tree probing info.
Definition: CglProbing.hpp:515
void setAffectedInDisaggregation(disaggregationAction &dis, int affected)
Definition: CglProbing.hpp:434
int getUsingObjective() const
Get.
int probeSlacks(const OsiSolverInterface &si, const OsiRowCutDebugger *debugger, OsiCuts &cs, double *colLower, double *colUpper, CoinPackedMatrix *rowCopy, CoinPackedMatrix *columnCopy, double *rowLower, double *rowUpper, char *intVar, double *minR, double *maxR, int *markR, CglTreeInfo *info) const
Does probing and adding cuts for clique slacks.
void setRowCuts(int type)
Set 0 no cuts, 1 just disaggregation type, 2 coefficient ( 3 both)
virtual CglCutGenerator * clone() const
Clone.
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any inforamtion.
void setMaxPassRoot(int value)
Set maximum number of passes per node (root node)
int getMaxElements() const
Get maximum number of elements in row for it to be considered.
CglProbing()
Default constructor.
int generateCutsAndModify(const OsiSolverInterface &si, OsiCuts &cs, CglTreeInfo *info)
Generate probing/disaggregation cuts for the model of the solver interface, si.
int probe(const OsiSolverInterface &si, const OsiRowCutDebugger *debugger, OsiCuts &cs, double *colLower, double *colUpper, CoinPackedMatrix *rowCopy, CoinPackedMatrix *columnCopy, const CoinBigIndex *rowStartPos, const int *realRow, const double *rowLower, const double *rowUpper, const char *intVar, double *minR, double *maxR, int *markR, CglTreeInfo *info) const
Does probing and adding cuts (without cliques and mode_!=0)
int getMaxPassRoot() const
Get maximum number of passes per node (root node)
virtual ~CglImplication()
Destructor.
int numberCliques_
Cliques Number of cliques.
Definition: CglProbing.hpp:401
int number01Integers_
Number of 0-1 integer variables.
Definition: CglProbing.hpp:384
int maxPassRoot_
Maximum number of passes to do in probing at root.
Definition: CglProbing.hpp:372
double * rowLower_
Lower bounds on rows.
Definition: CglProbing.hpp:339
int getMaxLook() const
Get maximum number of variables to look at in one probe.
double * rowUpper_
Upper bounds on rows.
Definition: CglProbing.hpp:341
void setMaxProbeRoot(int value)
Set maximum number of unsatisfied variables to look at (root node)
void setMaxElementsRoot(int value)
Set maximum number of elements in row for it to be considered (root node)
friend void CglProbingUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglProbing class.
void setUsingObjective(int yesNo)
Set 0 don't 1 do -1 don't even think about it.
disaggregation * cutVector_
Disaggregation cuts and for building cliques.
Definition: CglProbing.hpp:398
cliqueType * cliqueType_
Disaggregation cuts and for building cliques.
Definition: CglProbing.hpp:406
int getMaxLookRoot() const
Get maximum number of variables to look at in one probe (root node)
int getMaxProbe() const
Get maximum number of unsatisfied variables to look at.
CoinPackedMatrix * columnCopy_
Column copy (only if snapshot)
Definition: CglProbing.hpp:337
int getMaxPass() const
Get maximum number of passes per node.
void setMaxLook(int value)
Set maximum number of variables to look at in one probe.
const int * lookedAt() const
Which ones looked at this time.
Definition: CglProbing.hpp:209
int numberThisTime_
Number looked at this time.
Definition: CglProbing.hpp:386
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const
Generate probing/disaggregation cuts for the model of the solver interface, si.
Only useful type of disaggregation is most normal For now just done for 0-1 variables Can be used for...
Definition: CglProbing.hpp:13
int getMode() const
Get.
void deleteSnapshot()
Deletes snapshot.
Probing Cut Generator Class.
Definition: CglProbing.hpp:22
unsigned int affected
Definition: CglProbing.hpp:18
const double * tightUpper() const
Upper.
double * colUpper_
Upper bounds on columns.
Definition: CglProbing.hpp:345
int maxElements_
Maximum number of elements in row for scan.
Definition: CglProbing.hpp:370
int * endFixStart_
End of fixes for a column.
Definition: CglProbing.hpp:418
double primalTolerance_
Tolerance to see if infeasible.
Definition: CglProbing.hpp:351
int tighten(double *colLower, double *colUpper, const int *column, const double *rowElements, const CoinBigIndex *rowStart, const CoinBigIndex *rowStartPos, const int *rowLength, double *rowLower, double *rowUpper, int nRows, int nCols, char *intVar, int maxpass, double tolerance) const
This tightens column bounds (and can declare infeasibility) It may also declare rows to be redundant...
Derived class to pick up probing info.
Definition: CglTreeInfo.hpp:74
int logLevel_
Log level - 0 none, 1 - a bit, 2 - more details.
Definition: CglProbing.hpp:364
int createCliques(OsiSolverInterface &si, int minimumSize=2, int maximumSize=100)
Creates cliques for use by probing.
Cut Generator Base Class.
void setWhenAtUBInDisaggregation(disaggregationAction &dis, bool whenAtUB)
Definition: CglProbing.hpp:449
cliqueEntry * cliqueRow_
For each column with nonzero in row copy this gives a clique "number".
Definition: CglProbing.hpp:425
void setZeroOneInDisaggregation(disaggregationAction &dis, bool zeroOne)
Definition: CglProbing.hpp:445
bool whenAtUBInDisaggregation(const disaggregationAction &dis)
Definition: CglProbing.hpp:447
int * lookedAt_
Which ones looked at this time.
Definition: CglProbing.hpp:390
int getMaxElementsRoot() const
Get maximum number of elements in row for it to be considered (root node)
const double * relaxedRowUpper() const
Upper.
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const
Generate cuts from implication table Insert generated cuts into the cut set cs.
void deleteCliques()
Delete all clique information.
int affectedInDisaggregation(const disaggregationAction &dis)
Definition: CglProbing.hpp:432
int getMaxProbeRoot() const
Get maximum number of unsatisfied variables to look at (root node)
int usingObjective_
Whether to include objective as constraint.
Definition: CglProbing.hpp:380
int rowCuts_
Row cuts flag 0 no cuts, 1 just disaggregation type, 2 coefficient ( 3 both), 4 just column cuts -n a...
Definition: CglProbing.hpp:360
int maxElementsRoot_
Maximum number of elements in row for scan at root.
Definition: CglProbing.hpp:378
This just uses implication info.
Definition: CglProbing.hpp:465
void tightenThese(const OsiSolverInterface &solver, int number, const int *which)
Mark variables to be tightened.
int snapshot(const OsiSolverInterface &si, char *possible=NULL, bool withObjective=true)
Create a copy of matrix which is to be used this is to speed up process and to give global cuts Can g...
CoinPackedMatrix * rowCopy_
Row copy (only if snapshot)
Definition: CglProbing.hpp:335
Disaggregation cuts and for building cliques.
Definition: CglProbing.hpp:392
bool affectedToUBInDisaggregation(const disaggregationAction &dis)
Definition: CglProbing.hpp:451
CglProbing & operator=(const CglProbing &rhs)
Assignment operator.
void setMaxPass(int value)
Set maximum number of passes per node.
const double * relaxedRowLower() const
Lower.
int numberColumns_
Number of columns in problem ( must == current)
Definition: CglProbing.hpp:349
int * whichClique_
Clique numbers for one or zero fixes.
Definition: CglProbing.hpp:420
cliqueEntry * cliqueEntry_
Entries for clique.
Definition: CglProbing.hpp:410
int gutsOfGenerateCuts(const OsiSolverInterface &si, OsiCuts &cs, double *rowLower, double *rowUpper, double *colLower, double *colUpper, CglTreeInfo *info) const
Does most of work of generateCuts Returns number of infeasibilities.
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:13
void setMode(int mode)
Set.
double * colLower_
Lower bounds on columns.
Definition: CglProbing.hpp:343
int maxStack_
Maximum number of variables to look at in one probe.
Definition: CglProbing.hpp:368
int maxProbe_
Maximum number of unsatisfied variables to probe.
Definition: CglProbing.hpp:366
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
void setupRowCliqueInformation(const OsiSolverInterface &si)
Sets up clique information for each row.
int numberThisTime() const
Number looked at this time.
Definition: CglProbing.hpp:206
const char * tightenBounds() const
Array which says tighten continuous.
Definition: CglProbing.hpp:135
void setLogLevel(int value)
Set log level - 0 none, 1 - a bit, 2 - more details.
int maxPass_
Maximum number of passes to do in probing.
Definition: CglProbing.hpp:362
int numberIntegers_
Number of integer variables.
Definition: CglProbing.hpp:382
int maxStackRoot_
Maximum number of variables to look at in one probe at root.
Definition: CglProbing.hpp:376
int maxProbeRoot_
Maximum number of unsatisfied variables to probe at root.
Definition: CglProbing.hpp:374
int * cliqueStart_
Start of each clique.
Definition: CglProbing.hpp:408
int mode_
Mode - 0 lazy using snapshot, 1 just unsatisfied, 2 all.
Definition: CglProbing.hpp:355