Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
CglProbing.hpp
Go to the documentation of this file.
1 // $Id: CglProbing.hpp 1201 2014-03-07 17:24:04Z forrest $
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 ( );
126  int minimumSize=2, int maximumSize=100);
128  void deleteCliques();
133  int type);
135 
138  const double * tightLower() const;
141  const double * tightUpper() const;
143  const char * tightenBounds() const
144  { return tightenBounds_;}
146 
149  const double * relaxedRowLower() const;
152  const double * relaxedRowUpper() const;
154 
157  void setMode(int mode);
160  int getMode() const;
162 
165  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 
213  inline int numberThisTime() const
215  { return numberThisTime_;}
217  inline const int * lookedAt() const
218  { return lookedAt_;}
220 
223  void setRowCuts(int type);
227  int rowCuts() const;
229  typedef struct {
231  unsigned int equality:1; // nonzero if clique is ==
232  } CliqueType;
233 
236  inline int numberCliques() const
238  { return numberCliques_;}
240  inline CliqueType * cliqueType() const
241  { return cliqueType_;}
243  inline int * cliqueStart() const
244  { return cliqueStart_;}
246  inline CliqueEntry * cliqueEntry() const
247  { return cliqueEntry_;}
249 
257  void setUsingObjective(int yesNo);
259  int getUsingObjective() const;
261 
264  void tightenThese(const OsiSolverInterface & solver, int number, const int * which);
267 
270  CglProbing ();
272 
274  CglProbing (
275  const CglProbing &);
276 
278  virtual CglCutGenerator * clone() const;
279 
281  CglProbing &
282  operator=(
283  const CglProbing& rhs);
284 
286  virtual
287  ~CglProbing ();
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);
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 
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
425  } disaggregation;
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 
505  CglImplication ();
507 
510 
513  const CglImplication &);
514 
516  virtual CglCutGenerator * clone() const;
517 
520  operator=(
521  const CglImplication& rhs);
522 
524  virtual
525  ~CglImplication ();
527  virtual std::string generateCpp( FILE * fp);
529 
531  inline void setProbingInfo(CglTreeProbingInfo * info)
533  { probingInfo_=info;}
535 
536 private:
542 };
543 #endif
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 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.
int getMode() const
Get.
int getMaxPassRoot() const
Get maximum number of passes per node (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.
disaggregation * cutVector_
Definition: CglProbing.hpp:426
int maxStack_
Maximum number of variables to look at in one probe.
Definition: CglProbing.hpp:396
double * colLower_
Lower bounds on columns.
Definition: CglProbing.hpp:371
void setupRowCliqueInformation(const OsiSolverInterface &si)
Sets up clique information for each row.
int maxProbe_
Maximum number of unsatisfied variables to probe.
Definition: CglProbing.hpp:394
int getMaxLook() const
Get maximum number of variables to look at in one probe.
This just uses implication info.
Definition: CglProbing.hpp:490
void setMaxElements(int value)
Set maximum number of elements in row for it to be considered.
CliqueEntry * cliqueRow_
For each column with nonzero in row copy this gives a clique &quot;number&quot;.
Definition: CglProbing.hpp:450
int * lookedAt_
Which ones looked at this time.
Definition: CglProbing.hpp:418
int getMaxProbe() const
Get maximum number of unsatisfied variables to look at.
int maxStackRoot_
Maximum number of variables to look at in one probe at root.
Definition: CglProbing.hpp:404
void setMaxLookRoot(int value)
Set maximum number of variables to look at in one probe (root node)
int maxElements_
Maximum number of elements in row for scan.
Definition: CglProbing.hpp:398
int numberCliques() const
Number of cliques.
Definition: CglProbing.hpp:237
void setMaxPass(int value)
Set maximum number of passes per node.
virtual CglCutGenerator * clone() const
Clone.
CglTreeProbingInfo * probingInfo_
Pointer to tree probing info.
Definition: CglProbing.hpp:540
int numberColumns_
Number of columns in problem ( must == current)
Definition: CglProbing.hpp:377
void setWhenAtUBInDisaggregation(disaggregationAction &dis, bool whenAtUB)
Definition: CglProbing.hpp:474
int maxProbeRoot_
Maximum number of unsatisfied variables to probe at root.
Definition: CglProbing.hpp:402
const double * relaxedRowLower() const
Lower.
CliqueEntry * cliqueEntry() const
Entries for clique.
Definition: CglProbing.hpp:246
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
int numberRows_
Number of rows in snapshot (or when cliqueRow stuff computed)
Definition: CglProbing.hpp:375
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
int * cliqueStart() const
Start of each clique.
Definition: CglProbing.hpp:243
CglImplication & operator=(const CglImplication &rhs)
Assignment operator.
int maxPass_
Maximum number of passes to do in probing.
Definition: CglProbing.hpp:390
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
CliqueType * cliqueType() const
Clique type.
Definition: CglProbing.hpp:240
int * cliqueStart_
Start of each clique.
Definition: CglProbing.hpp:433
double * rowUpper_
Upper bounds on rows.
Definition: CglProbing.hpp:369
int number01Integers_
Number of 0-1 integer variables.
Definition: CglProbing.hpp:412
void setMode(int mode)
Set.
const int * lookedAt() const
Which ones looked at this time.
Definition: CglProbing.hpp:217
CglImplication()
Default constructor.
int * endFixStart_
End of fixes for a column.
Definition: CglProbing.hpp:443
CliqueType * cliqueType_
Clique type.
Definition: CglProbing.hpp:431
void setAffectedInDisaggregation(disaggregationAction &dis, int affected)
Definition: CglProbing.hpp:459
char * tightenBounds_
If not null and [i] !=0 then also tighten even if continuous.
Definition: CglProbing.hpp:454
const char * tightenBounds() const
Array which says tighten continuous.
Definition: CglProbing.hpp:143
void deleteSnapshot()
Deletes snapshot.
int * zeroFixStart_
Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.
Definition: CglProbing.hpp:441
int createCliques(OsiSolverInterface &si, int minimumSize=2, int maximumSize=100)
Creates cliques for use by probing.
const double * tightUpper() const
Upper.
int * whichClique_
Clique numbers for one or zero fixes.
Definition: CglProbing.hpp:445
int * cliqueRowStart_
cliqueRow_ starts for each row
Definition: CglProbing.hpp:452
int logLevel_
Log level - 0 none, 1 - a bit, 2 - more details.
Definition: CglProbing.hpp:392
void setProbingInfo(CglTreeProbingInfo *info)
Set implication.
Definition: CglProbing.hpp:532
Abstract Base Class for describing an interface to a solver.
void setMaxLook(int value)
Set maximum number of variables to look at in one probe.
virtual CglCutGenerator * clone() const
Clone.
void setMaxElementsRoot(int value)
Set maximum number of elements in row for it to be considered (root node)
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.
int * oneFixStart_
Start of oneFixes cliques for a column in matrix or -1 if not in any clique.
Definition: CglProbing.hpp:438
int totalTimesCalled_
Total number of times called.
Definition: CglProbing.hpp:416
unsigned int affected
Definition: CglProbing.hpp:21
int mode_
Mode - 0 lazy using snapshot, 1 just unsatisfied, 2 all.
Definition: CglProbing.hpp:383
OsiSolverInterface * cliqueModel(const OsiSolverInterface *model, int type)
Create a fake model by adding cliques if type&amp;4 then delete rest of model first, if 1 then add proper...
CliqueEntry * cliqueEntry_
Entries for clique.
Definition: CglProbing.hpp:435
Derived class to pick up probing info.
Definition: CglTreeInfo.hpp:79
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)
bool zeroOneInDisaggregation(const disaggregationAction &dis)
Definition: CglProbing.hpp:466
double * colUpper_
Upper bounds on columns.
Definition: CglProbing.hpp:373
int numberIntegers_
Number of integer variables.
Definition: CglProbing.hpp:410
int maxPassRoot_
Maximum number of passes to do in probing at root.
Definition: CglProbing.hpp:400
void setMaxProbe(int value)
Set maximum number of unsatisfied variables to look at.
Cut Generator Base Class.
int numberCliques_
Cliques Number of cliques.
Definition: CglProbing.hpp:429
virtual bool mayGenerateRowCutsInTree() const
Returns true if may generate Row cuts in tree (rather than root node).
Only useful type of disaggregation is most normal For now just done for 0-1 variables Can be used for...
Definition: CglProbing.hpp:16
CglProbing()
Default constructor.
bool affectedToUBInDisaggregation(const disaggregationAction &dis)
Definition: CglProbing.hpp:476
const double * relaxedRowUpper() const
Upper.
int rowCuts() const
Get.
double primalTolerance_
Tolerance to see if infeasible.
Definition: CglProbing.hpp:379
int getUsingObjective() const
Get.
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate probing/disaggregation cuts for the model of the solver interface, si.
void setZeroOneInDisaggregation(disaggregationAction &dis, bool zeroOne)
Definition: CglProbing.hpp:470
struct CglProbing::disaggregation_struct_tag disaggregation
Disaggregation cuts and for building cliques.
double * rowLower_
Lower bounds on rows.
Definition: CglProbing.hpp:367
void CglProbingUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglProbing class.
int numberThisTime_
Number looked at this time.
Definition: CglProbing.hpp:414
int getMaxLookRoot() const
Get maximum number of variables to look at in one probe (root node)
Sparse Matrix Base Class.
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.
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
int getMaxElements() const
Get maximum number of elements in row for it to be considered.
int numberThisTime() const
Number looked at this time.
Definition: CglProbing.hpp:214
const double * tightLower() const
Lower.
virtual ~CglImplication()
Destructor.
int CoinBigIndex
int getLogLevel() const
Get log level.
void setLogLevel(int value)
Set log level - 0 none, 1 - a bit, 2 - more details.
void setAffectedToUBInDisaggregation(disaggregationAction &dis, bool affectedToUB)
Definition: CglProbing.hpp:478
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any inforamtion.
Disaggregation cuts and for building cliques.
Definition: CglProbing.hpp:420
void tightenThese(const OsiSolverInterface &solver, int number, const int *which)
Mark variables to be tightened.
int getMaxPass() const
Get maximum number of passes per node.
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 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...
Validate cuts against a known solution.
void setUsingObjective(int yesNo)
Set 0 don&#39;t 1 do -1 don&#39;t even think about it.
friend void CglProbingUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglProbing class.
bool whenAtUBInDisaggregation(const disaggregationAction &dis)
Definition: CglProbing.hpp:472
int maxElementsRoot_
Maximum number of elements in row for scan at root.
Definition: CglProbing.hpp:406
int generateCutsAndModify(const OsiSolverInterface &si, OsiCuts &cs, CglTreeInfo *info)
int usingObjective_
Whether to include objective as constraint.
Definition: CglProbing.hpp:408
void setMaxProbeRoot(int value)
Set maximum number of unsatisfied variables to look at (root node)
void setRowCuts(int type)
Set 0 no cuts, 1 just disaggregation type, 2 coefficient ( 3 both)
int getMaxElementsRoot() const
Get maximum number of elements in row for it to be considered (root node)
CoinPackedMatrix * columnCopy_
Column copy (only if snapshot)
Definition: CglProbing.hpp:365
int affectedInDisaggregation(const disaggregationAction &dis)
Definition: CglProbing.hpp:457
virtual ~CglProbing()
Destructor.
Probing Cut Generator Class.
Definition: CglProbing.hpp:25
void setMaxPassRoot(int value)
Set maximum number of passes per node (root node)
CoinPackedMatrix * rowCopy_
Row copy (only if snapshot)
Definition: CglProbing.hpp:363
CglProbing & operator=(const CglProbing &rhs)
Assignment operator.
void deleteCliques()
Delete all clique information.
int getMaxProbeRoot() const
Get maximum number of unsatisfied variables to look at (root node)