Cgl  0.60.3
CglProbing.hpp
Go to the documentation of this file.
1 // $Id$
2 // Copyright (C) 2002, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
5 
6 #ifndef CglProbing_H
7 #define CglProbing_H
8 
9 #include <string>
10 
11 #include "CglCutGenerator.hpp"
16  typedef struct {
17  //unsigned int zeroOne:1; // nonzero if affected variable is 0-1
18  //unsigned int whenAtUB:1; // nonzero if fixing happens when this variable at 1
19  //unsigned int affectedToUB:1; // nonzero if affected variable fixed to UB
20  //unsigned int affected:29; // If 0-1 then 0-1 sequence, otherwise true
21  unsigned int affected;
23 
25 class CglProbing : public CglCutGenerator {
26  friend void CglProbingUnitTest(const OsiSolverInterface * siP,
27  const std::string mpdDir );
28 
29 public:
30 
31 
99  virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs,
100  const CglTreeInfo info = CglTreeInfo());
101  int generateCutsAndModify( const OsiSolverInterface & si, OsiCuts & cs,
102  CglTreeInfo * info);
104 
115  int snapshot ( const OsiSolverInterface & si,
116  char * possible=NULL,
117  bool withObjective=true);
119  void deleteSnapshot ( );
125  int createCliques( OsiSolverInterface & si,
126  int minimumSize=2, int maximumSize=100);
132  OsiSolverInterface * cliqueModel(const OsiSolverInterface * model,
133  int type);
135 
139  const double * tightLower() const;
141  const double * tightUpper() const;
143  const char * tightenBounds() const
144  { return tightenBounds_;}
146 
150  const double * relaxedRowLower() const;
152  const double * relaxedRowUpper() const;
154 
158  void setMode(int mode);
160  int getMode() const;
162 
166  void setMaxPass(int value);
168  int getMaxPass() const;
170  void setLogLevel(int value);
172  int getLogLevel() const;
174  void setMaxProbe(int value);
176  int getMaxProbe() const;
178  void setMaxLook(int value);
180  int getMaxLook() const;
182  void setMaxElements(int value);
184  int getMaxElements() const;
186  void setMaxPassRoot(int value);
188  int getMaxPassRoot() const;
190  void setMaxProbeRoot(int value);
192  int getMaxProbeRoot() const;
194  void setMaxLookRoot(int value);
196  int getMaxLookRoot() const;
198  void setMaxElementsRoot(int value);
200  int getMaxElementsRoot() const;
208  virtual bool mayGenerateRowCutsInTree() const;
210 
214  inline int numberThisTime() const
215  { return numberThisTime_;}
217  inline const int * lookedAt() const
218  { return lookedAt_;}
220 
225  void setRowCuts(int type);
227  int rowCuts() const;
229  typedef struct {
231  unsigned int equality:1; // nonzero if clique is ==
232  } CliqueType;
233 
237  inline int numberCliques() const
238  { return numberCliques_;}
240  inline CliqueType * cliqueType() const
241  { return cliqueType_;}
243  inline CoinBigIndex * cliqueStart() const
244  { return cliqueStart_;}
246  inline CliqueEntry * cliqueEntry() const
247  { return cliqueEntry_;}
249 
257  void setUsingObjective(int yesNo);
259  int getUsingObjective() const;
261 
265  void tightenThese(const OsiSolverInterface & solver, int number, const int * which);
267 
272 
275  const CglProbing &);
276 
278  virtual CglCutGenerator * clone() const;
279 
281  CglProbing &
283  const CglProbing& rhs);
284 
286  virtual
288 
290  virtual void refreshSolver(OsiSolverInterface * solver);
292  virtual std::string generateCpp( FILE * fp);
294 
295 private:
296 
297  // Private member methods
300  int probe( const OsiSolverInterface & si,
302  const OsiRowCutDebugger * debugger,
303  OsiCuts & cs,
304  double * colLower, double * colUpper, CoinPackedMatrix *rowCopy,
305  CoinPackedMatrix *columnCopy,const CoinBigIndex * rowStartPos,
306  const int * realRow, const double * rowLower, const double * rowUpper,
307  const char * intVar, double * minR, double * maxR, int * markR,
308  CglTreeInfo * info);
310  int probeCliques( const OsiSolverInterface & si,
311  const OsiRowCutDebugger * debugger,
312  OsiCuts & cs,
313  double * colLower, double * colUpper, CoinPackedMatrix *rowCopy,
314  CoinPackedMatrix *columnCopy, const int * realRow,
315  double * rowLower, double * rowUpper,
316  char * intVar, double * minR, double * maxR, int * markR,
317  CglTreeInfo * info);
319  int probeSlacks( const OsiSolverInterface & si,
320  const OsiRowCutDebugger * debugger,
321  OsiCuts & cs,
322  double * colLower, double * colUpper, CoinPackedMatrix *rowCopy,
323  CoinPackedMatrix *columnCopy,
324  double * rowLower, double * rowUpper,
325  char * intVar, double * minR, double * maxR,int * markR,
326  CglTreeInfo * info);
329  int gutsOfGenerateCuts( const OsiSolverInterface & si,
330  OsiCuts & cs,
331  double * rowLower, double * rowUpper,
332  double * colLower, double * colUpper,
333  CglTreeInfo * info);
335  void setupRowCliqueInformation(const OsiSolverInterface & si);
338  int tighten(double *colLower, double * colUpper,
339  const int *column, const double *rowElements,
340  const CoinBigIndex *rowStart,const CoinBigIndex * rowStartPos,
341  const int * rowLength,
342  double *rowLower, double *rowUpper,
343  int nRows,int nCols,char * intVar,int maxpass,
344  double tolerance);
346  void tighten2(double *colLower, double * colUpper,
347  const int *column, const double *rowElements,
348  const CoinBigIndex *rowStart,
349  const int * rowLength,
350  double *rowLower, double *rowUpper,
351  double * minR, double * maxR, int * markR,
352  int nRows);
354 
355  // Private member data
356 
359 
363  CoinPackedMatrix * rowCopy_;
365  CoinPackedMatrix * columnCopy_;
367  double * rowLower_;
369  double * rowUpper_;
371  double * colLower_;
373  double * colUpper_;
383  int mode_;
388  int rowCuts_;
390  int maxPass_;
418  int * lookedAt_;
420  typedef struct disaggregation_struct_tag {
421  int sequence; // integer variable
422  // index will be NULL if no probing done yet
423  int length; // length of newValue
424  disaggregationAction * index; // columns whose bounds will be changed
433  CoinBigIndex * cliqueStart_;
456 };
458 { return dis.affected&0x1fffffff;}
460  int affected)
461 { dis.affected = affected|(dis.affected&0xe0000000);}
462 #ifdef NDEBUG
463 inline bool zeroOneInDisaggregation(const disaggregationAction & )
464 { return true;}
465 #else
467 //{ return (dis.affected&0x80000000)!=0;}
468 { assert ((dis.affected&0x80000000)!=0); return true;}
469 #endif
470 inline void setZeroOneInDisaggregation(disaggregationAction & dis,bool zeroOne)
471 { dis.affected = (zeroOne ? 0x80000000 : 0)|(dis.affected&0x7fffffff);}
473 { return (dis.affected&0x40000000)!=0;}
474 inline void setWhenAtUBInDisaggregation(disaggregationAction & dis,bool whenAtUB)
475 { dis.affected = (whenAtUB ? 0x40000000 : 0)|(dis.affected&0xbfffffff);}
477 { return (dis.affected&0x20000000)!=0;}
478 inline void setAffectedToUBInDisaggregation(disaggregationAction & dis,bool affectedToUB)
479 { dis.affected = (affectedToUB ? 0x20000000 : 0)|(dis.affected&0xdfffffff);}
480 
481 //#############################################################################
487 void CglProbingUnitTest(const OsiSolverInterface * siP,
488  const std::string mpdDir );
491 
492 public:
493 
499  virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs,
500  const CglTreeInfo info = CglTreeInfo());
502 
507 
510 
513  const CglImplication &);
514 
516  virtual CglCutGenerator * clone() const;
517 
521  const CglImplication& rhs);
522 
524  virtual
527  virtual std::string generateCpp( FILE * fp);
529 
532  inline void setProbingInfo(CglTreeProbingInfo * info)
533  { probingInfo_=info;}
535 
536 private:
542 };
543 #endif
void setZeroOneInDisaggregation(disaggregationAction &dis, bool zeroOne)
Definition: CglProbing.hpp:470
void CglProbingUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglProbing class.
void setAffectedToUBInDisaggregation(disaggregationAction &dis, bool affectedToUB)
Definition: CglProbing.hpp:478
bool affectedToUBInDisaggregation(const disaggregationAction &dis)
Definition: CglProbing.hpp:476
int affectedInDisaggregation(const disaggregationAction &dis)
Definition: CglProbing.hpp:457
void setAffectedInDisaggregation(disaggregationAction &dis, int affected)
Definition: CglProbing.hpp:459
void setWhenAtUBInDisaggregation(disaggregationAction &dis, bool whenAtUB)
Definition: CglProbing.hpp:474
bool zeroOneInDisaggregation(const disaggregationAction &dis)
Definition: CglProbing.hpp:466
bool whenAtUBInDisaggregation(const disaggregationAction &dis)
Definition: CglProbing.hpp:472
Cut Generator Base Class.
This just uses implication info
Definition: CglProbing.hpp:490
virtual CglCutGenerator * clone() const
Clone.
CglImplication(const CglImplication &)
Copy constructor.
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate cuts from implication table Insert generated cuts into the cut set cs.
virtual ~CglImplication()
Destructor.
CglTreeProbingInfo * probingInfo_
Pointer to tree probing info.
Definition: CglProbing.hpp:540
CglImplication()
Default constructor.
CglImplication(CglTreeProbingInfo *info)
Constructor with info.
CglImplication & operator=(const CglImplication &rhs)
Assignment operator.
void setProbingInfo(CglTreeProbingInfo *info)
Set implication.
Definition: CglProbing.hpp:532
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
Probing Cut Generator Class.
Definition: CglProbing.hpp:25
CglProbing(const CglProbing &)
Copy constructor.
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)
Does probing and adding cuts (without cliques and mode_!=0)
int getMaxPass() const
Get maximum number of passes per node.
int getMode() const
Get.
double * colUpper_
Upper bounds on columns.
Definition: CglProbing.hpp:373
disaggregation * cutVector_
Definition: CglProbing.hpp:426
void setMaxProbe(int value)
Set maximum number of unsatisfied variables to look at.
int getMaxProbe() const
Get maximum number of unsatisfied variables to look at.
CliqueType * cliqueType_
Clique type.
Definition: CglProbing.hpp:431
int getLogLevel() const
Get log level.
int maxElementsRoot_
Maximum number of elements in row for scan at root.
Definition: CglProbing.hpp:406
void deleteCliques()
Delete all clique information.
virtual CglCutGenerator * clone() const
Clone.
int maxProbe_
Maximum number of unsatisfied variables to probe.
Definition: CglProbing.hpp:394
int * endFixStart_
End of fixes for a column.
Definition: CglProbing.hpp:443
int getMaxElements() const
Get maximum number of elements in row for it to be considered.
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any inforamtion.
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)
Does probing and adding cuts (with cliques)
int getMaxPassRoot() const
Get maximum number of passes per node (root node)
CliqueType * cliqueType() const
Clique type.
Definition: CglProbing.hpp:240
const double * relaxedRowLower() const
Lower.
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:388
double * rowLower_
Lower bounds on rows.
Definition: CglProbing.hpp:367
const char * tightenBounds() const
Array which says tighten continuous.
Definition: CglProbing.hpp:143
void setMaxProbeRoot(int value)
Set maximum number of unsatisfied variables to look at (root node)
struct CglProbing::disaggregation_struct_tag disaggregation
Disaggregation cuts and for building cliques.
friend void CglProbingUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglProbing class.
int getMaxElementsRoot() const
Get maximum number of elements in row for it to be considered (root node)
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
int number01Integers_
Number of 0-1 integer variables.
Definition: CglProbing.hpp:412
CoinPackedMatrix * rowCopy_
Row copy (only if snapshot)
Definition: CglProbing.hpp:363
int maxPass_
Maximum number of passes to do in probing.
Definition: CglProbing.hpp:390
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)
This tightens column bounds (and can declare infeasibility) It may also declare rows to be redundant.
int * zeroFixStart_
Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.
Definition: CglProbing.hpp:441
int maxElements_
Maximum number of elements in row for scan.
Definition: CglProbing.hpp:398
void setMaxLookRoot(int value)
Set maximum number of variables to look at in one probe (root node)
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)
Does probing and adding cuts for clique slacks.
int generateCutsAndModify(const OsiSolverInterface &si, OsiCuts &cs, CglTreeInfo *info)
int rowCuts() const
Get.
int maxStackRoot_
Maximum number of variables to look at in one probe at root.
Definition: CglProbing.hpp:404
CglProbing()
Default constructor.
double * colLower_
Lower bounds on columns.
Definition: CglProbing.hpp:371
void setLogLevel(int value)
Set log level - 0 none, 1 - a bit, 2 - more details.
int getMaxProbeRoot() const
Get maximum number of unsatisfied variables to look at (root node)
int numberRows_
Number of rows in snapshot (or when cliqueRow stuff computed)
Definition: CglProbing.hpp:375
const int * lookedAt() const
Which ones looked at this time.
Definition: CglProbing.hpp:217
CglProbing & operator=(const CglProbing &rhs)
Assignment operator.
CliqueEntry * cliqueRow_
For each column with nonzero in row copy this gives a clique "number".
Definition: CglProbing.hpp:450
void setMaxLook(int value)
Set maximum number of variables to look at in one probe.
int numberIntegers_
Number of integer variables.
Definition: CglProbing.hpp:410
void setRowCuts(int type)
Set 0 no cuts, 1 just disaggregation type, 2 coefficient ( 3 both)
void setUsingObjective(int yesNo)
Set 0 don't 1 do -1 don't even think about it.
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...
const double * tightLower() const
Lower.
void setMaxElements(int value)
Set maximum number of elements in row for it to be considered.
int mode_
Mode - 0 lazy using snapshot, 1 just unsatisfied, 2 all.
Definition: CglProbing.hpp:383
int * cliqueRowStart_
cliqueRow_ starts for each row
Definition: CglProbing.hpp:452
int gutsOfGenerateCuts(const OsiSolverInterface &si, OsiCuts &cs, double *rowLower, double *rowUpper, double *colLower, double *colUpper, CglTreeInfo *info)
Does most of work of generateCuts Returns number of infeasibilities.
CoinPackedMatrix * columnCopy_
Column copy (only if snapshot)
Definition: CglProbing.hpp:365
CoinBigIndex * cliqueStart() const
Start of each clique.
Definition: CglProbing.hpp:243
int numberCliques_
Cliques Number of cliques.
Definition: CglProbing.hpp:429
double primalTolerance_
Tolerance to see if infeasible.
Definition: CglProbing.hpp:379
int logLevel_
Log level - 0 none, 1 - a bit, 2 - more details.
Definition: CglProbing.hpp:392
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)
This just sets minima and maxima on rows.
char * tightenBounds_
If not null and [i] !=0 then also tighten even if continuous.
Definition: CglProbing.hpp:454
virtual bool mayGenerateRowCutsInTree() const
Returns true if may generate Row cuts in tree (rather than root node).
int numberCliques() const
Number of cliques.
Definition: CglProbing.hpp:237
const double * relaxedRowUpper() const
Upper.
double * rowUpper_
Upper bounds on rows.
Definition: CglProbing.hpp:369
int getMaxLook() const
Get maximum number of variables to look at in one probe.
void setupRowCliqueInformation(const OsiSolverInterface &si)
Sets up clique information for each row.
int * oneFixStart_
Start of oneFixes cliques for a column in matrix or -1 if not in any clique.
Definition: CglProbing.hpp:438
void setMode(int mode)
Set.
int totalTimesCalled_
Total number of times called.
Definition: CglProbing.hpp:416
int maxProbeRoot_
Maximum number of unsatisfied variables to probe at root.
Definition: CglProbing.hpp:402
CoinBigIndex * cliqueStart_
Start of each clique.
Definition: CglProbing.hpp:433
virtual ~CglProbing()
Destructor.
int maxStack_
Maximum number of variables to look at in one probe.
Definition: CglProbing.hpp:396
const double * tightUpper() const
Upper.
int numberThisTime_
Number looked at this time.
Definition: CglProbing.hpp:414
void setMaxPass(int value)
Set maximum number of passes per node.
int numberColumns_
Number of columns in problem ( must == current)
Definition: CglProbing.hpp:377
int createCliques(OsiSolverInterface &si, int minimumSize=2, int maximumSize=100)
Creates cliques for use by probing.
int getUsingObjective() const
Get.
void setMaxPassRoot(int value)
Set maximum number of passes per node (root node)
int numberThisTime() const
Number looked at this time.
Definition: CglProbing.hpp:214
int maxPassRoot_
Maximum number of passes to do in probing at root.
Definition: CglProbing.hpp:400
void deleteSnapshot()
Deletes snapshot.
CliqueEntry * cliqueEntry() const
Entries for clique.
Definition: CglProbing.hpp:246
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate probing/disaggregation cuts for the model of the solver interface, si.
int * whichClique_
Clique numbers for one or zero fixes.
Definition: CglProbing.hpp:445
OsiSolverInterface * cliqueModel(const OsiSolverInterface *model, int type)
Create a fake model by adding cliques if type&4 then delete rest of model first, if 1 then add proper...
int * lookedAt_
Which ones looked at this time.
Definition: CglProbing.hpp:418
int getMaxLookRoot() const
Get maximum number of variables to look at in one probe (root node)
CliqueEntry * cliqueEntry_
Entries for clique.
Definition: CglProbing.hpp:435
void setMaxElementsRoot(int value)
Set maximum number of elements in row for it to be considered (root node)
int usingObjective_
Whether to include objective as constraint.
Definition: CglProbing.hpp:408
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
Disaggregation cuts and for building cliques.
Definition: CglProbing.hpp:420
Derived class to pick up probing info.
Definition: CglTreeInfo.hpp:86
Only useful type of disaggregation is most normal For now just done for 0-1 variables Can be used for...
Definition: CglProbing.hpp:16
unsigned int affected
Definition: CglProbing.hpp:21