This file is indexed.

/usr/include/coin/CglGMI.hpp is in coinor-libcgl-dev 0.58.4-2ubuntu2.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
// Last edit: 02/05/2013
//
// Name:     CglGMI.hpp
// Author:   Giacomo Nannicini
//           Singapore University of Technology and Design, Singapore
//           email: nannicini@sutd.edu.sg
// Date:     11/17/09
//-----------------------------------------------------------------------------
// Copyright (C) 2009, Giacomo Nannicini.  All Rights Reserved.

#ifndef CglGMI_H
#define CglGMI_H

#include "CglCutGenerator.hpp"
#include "CglGMIParam.hpp"
#include "CoinWarmStartBasis.hpp"
#include "CoinFactorization.hpp"

/* Enable tracking of rejection of cutting planes. If this is disabled,
   the cut generator is slightly faster. If defined, it enables proper use
   of setTrackRejection and related functions. */
//#define TRACK_REJECT

/* Debug output */
//#define GMI_TRACE

/* Debug output: print optimal tableau */
//#define GMI_TRACETAB

/* Print reason for cut rejection, whenever a cut is discarded */
//#define GMI_TRACE_CLEAN

/** Gomory cut generator with several cleaning procedures, used to test
 *  the numerical safety of the resulting cuts 
 */

class CglGMI : public CglCutGenerator {

  friend void CglGMIUnitTest(const OsiSolverInterface * siP,
			     const std::string mpdDir);
public:

  /** Public enum: all possible reasons for cut rejection */
  enum RejectionType{
    failureFractionality,
    failureDynamism,
    failureViolation,
    failureSupport,
    failureScale
  };

  /**@name generateCuts */
  //@{
  /** Generate Gomory Mixed-Integer cuts for the model of the solver
      interface si.

      Insert the generated cuts into OsiCuts cs.

      Warning: This generator currently works only with the Lp solvers Clp or 
      Cplex9.0 or higher. It requires access to the optimal tableau and 
      optimal basis inverse and makes assumptions on the way slack variables 
      are added by the solver. The Osi implementations for Clp and Cplex 
      verify these assumptions.

      When calling the generator, the solver interface si must contain
      an optimized problem and information related to the optimal
      basis must be available through the OsiSolverInterface methods
      (si->optimalBasisIsAvailable() must return 'true'). It is also
      essential that the integrality of structural variable i can be
      obtained using si->isInteger(i).

  */
  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
			    const CglTreeInfo info = CglTreeInfo());

  /// Return true if needs optimal basis to do cuts (will return true)
  virtual bool needsOptimalBasis() const { return true; }
  //@}

  /**@name Common Methods */
  //@{
  // Function for checking equality with user tolerance
  inline bool areEqual(double x, double y, 
		       double epsAbs = 1e-12, 
		       double epsRel = 1e-12) {
    return (fabs((x) - (y)) <= 
	    std::max(epsAbs, epsRel * std::max(fabs(x), fabs(y))));
  }

  // Function for checking is a number is zero
  inline bool isZero(double x, double epsZero = 1e-20) {
    return (fabs(x) <= epsZero);
  }


  // Function for checking if a number is integer
  inline bool isIntegerValue(double x, 
			     double intEpsAbs = 1e-9,
			     double intEpsRel = 1e-15) {
    return (fabs((x) - floor((x)+0.5)) <= 
	    std::max(intEpsAbs, intEpsRel * fabs(x)));
  }

  
  //@}
  
  
  /**@name Public Methods */
  //@{

  // Set the parameters to the values of the given CglGMIParam object.
  void setParam(const CglGMIParam &source); 
  // Return the CglGMIParam object of the generator. 
  inline CglGMIParam getParam() const {return param;}
  inline CglGMIParam & getParam() {return param;}

  // Compute entries of is_integer.
  void computeIsInteger();

  /// Print the current simplex tableau  
  void printOptTab(OsiSolverInterface *solver) const;

  /// Set/get tracking of the rejection of cutting planes.
  /// Note that all rejection related functions will not do anything 
  /// unless the generator is compiled with the define GMI_TRACK_REJECTION
  void setTrackRejection(bool value);
  bool getTrackRejection();

  /// Get number of cuts rejected for given reason; see above
  int getNumberRejectedCuts(RejectionType reason);

  /// Reset counters for cut rejection tracking; see above
  void resetRejectionCounters();

  /// Get total number of generated cuts since last resetRejectionCounters()
  int getNumberGeneratedCuts();
  
  //@}

  /**@name Constructors and destructors */
  //@{
  /// Default constructor 
  CglGMI();

  /// Constructor with specified parameters 
  CglGMI(const CglGMIParam &param);
 
  /// Copy constructor 
  CglGMI(const CglGMI &);

  /// Clone
  virtual CglCutGenerator * clone() const;

  /// Assignment operator 
  CglGMI & operator=(const CglGMI& rhs);
  
  /// Destructor 
  virtual ~CglGMI();
  /// Create C++ lines to get to current state
  virtual std::string generateCpp( FILE * fp);

  //@}
    
private:
  
  // Private member methods

/**@name Private member methods */

  //@{

  // Method generating the cuts after all CglGMI members are properly set.
  void generateCuts(OsiCuts & cs);

  /// Compute the fractional part of value, allowing for small error.
  inline double aboveInteger(double value) const; 

  /// Compute the fractionalities involved in the cut, and the cut rhs.
  /// Returns true if cut is accepted, false if discarded
  inline bool computeCutFractionality(double varRhs, double& cutRhs);

  /// Compute the cut coefficient on a given variable
  inline double computeCutCoefficient(double rowElem, int index);

  /// Use multiples of the initial inequalities to cancel out the coefficient
  /// on a slack variables. 
  inline void eliminateSlack(double cutElem, int cutIndex, double* cut,
			      double& cutRhs, const double *elements, 
			      const int *rowStart, const int *indices, 
			      const int *rowLength, const double *rhs);

  /// Change the sign of the coefficients of the non basic
  /// variables at their upper bound.
  inline void flip(double& rowElem, int rowIndex);

  /// Change the sign of the coefficients of the non basic
  /// variables at their upper bound and do the translations restoring
  /// the original bounds. Modify the right hand side
  /// accordingly. Two functions: one for original variables, one for slacks.
  inline void unflipOrig(double& rowElem, int rowIndex, double& rowRhs);
  inline void unflipSlack(double& rowElem, int rowIndex, double& rowRhs,
			   const double* slack_val);

  /// Pack a row of ncol elements
  inline void packRow(double* row, double* rowElem, int* rowIndex,
		       int& rowNz);

  /// Clean the cutting plane; the cleaning procedure does several things
  /// like removing small coefficients, scaling, and checks several
  /// acceptance criteria. If this returns false, the cut should be discarded.
  /// There are several cleaning procedures available, that can be selected
  /// via the parameter param.setCLEANING_PROCEDURE(int value)
  bool cleanCut(double* cutElem, int* cutIndex, int& cutNz,
		 double& cutRhs, const double* xbar);

  /// Cut cleaning procedures: return true if successfull, false if
  /// cut should be discarded by the caller of if problems encountered

  /// Check the violation
  bool checkViolation(const double* cutElem, const int* cutIndex,
		       int cutNz, double cutrhs, const double* xbar);

  /// Check the dynamism
  bool checkDynamism(const double* cutElem, const int* cutIndex,
		      int cutNz);

  /// Check the support
  bool checkSupport(int cutNz);

  /// Remove small coefficients and adjust the rhs accordingly
  bool removeSmallCoefficients(double* cutElem, int* cutIndex, 
				 int& cutNz, double& cutRhs);

  /// Adjust the rhs by relaxing by a small amount (relative or absolute)
  void relaxRhs(double& rhs);

  /// Scale the cutting plane in different ways;
  /// scaling_type possible values:
  /// 0 : scale to obtain integral cut
  /// 1 : scale based on norm, to obtain cut norm equal to ncol
  /// 2 : scale to obtain largest coefficient equal to 1
  bool scaleCut(double* cutElem, int* cutIndex, int cutNz,
		 double& cutRhs, int scalingType);

  /// Scale the cutting plane in order to generate integral coefficients
  bool scaleCutIntegral(double* cutElem, int* cutIndex, int cutNz,
			  double& cutRhs);

  /// Compute the nearest rational number; used by scale_row_integral
  bool nearestRational(double val, double maxdelta, long maxdnom,
			long& numerator, long& denominator);

  /// Compute the greatest common divisor
  long computeGcd(long a, long b);

  /// print a vector of integers
  void printvecINT(const char *vecstr, const int *x, int n) const;
  /// print a vector of doubles: dense form
  void printvecDBL(const char *vecstr, const double *x, int n) const;
  /// print a vector of doubles: sparse form
  void printvecDBL(const char *vecstr, const double *elem, const int * index, 
		   int nz) const;

  /// Recompute the simplex tableau for want of a better accuracy.
  /// Requires an empty CoinFactorization object to do the computations,
  /// and two empty (already allocated) arrays which will contain 
  /// the basis indices on exit. Returns 0 if successfull.
  int factorize(CoinFactorization & factorization,
		int* colBasisIndex, int* rowBasisIndex);


  //@}

  
  // Private member data

/**@name Private member data */

  //@{

  /// Object with CglGMIParam members. 
  CglGMIParam param;

  /// Number of rows ( = number of slack variables) in the current LP.
  int nrow; 

  /// Number of structural variables in the current LP.
  int ncol;

  /// Lower bounds for structural variables
  const double *colLower;

  /// Upper bounds for structural variables
  const double *colUpper;
  
  /// Lower bounds for constraints
  const double *rowLower;

  /// Upper bounds for constraints
  const double *rowUpper;

  /// Righ hand side for constraints (upper bound for ranged constraints).
  const double *rowRhs;

  /// Characteristic vectors of structural integer variables or continuous
  /// variables currently fixed to integer values. 
  bool *isInteger;

  /// Current basis status: columns
  int *cstat;

  /// Current basis status: rows
  int *rstat;

  /// Pointer on solver. Reset by each call to generateCuts().
  OsiSolverInterface *solver;

  /// Pointer on point to separate. Reset by each call to generateCuts().
  const double *xlp;

  /// Pointer on row activity. Reset by each call to generateCuts().
  const double *rowActivity;

  /// Pointer on matrix of coefficient ordered by rows. 
  /// Reset by each call to generateCuts().
  const CoinPackedMatrix *byRow;

  /// Pointer on matrix of coefficient ordered by columns. 
  /// Reset by each call to generateCuts().
  const CoinPackedMatrix *byCol;

  /// Fractionality of the cut and related quantities.
  double f0;
  double f0compl;
  double ratiof0compl;

#if defined(TRACK_REJECT) || defined (TRACK_REJECT_SIMPLE)
  /// Should we track the reason of each cut rejection?
  bool trackRejection;
  /// Number of failures by type
  int fracFail;
  int dynFail;
  int violFail;
  int suppFail;
  int smallCoeffFail;
  int scaleFail;
  /// Total number of generated cuts
  int numGeneratedCuts;
#endif

  //@}
};

//#############################################################################
/** A function that tests the methods in the CglGMI class. The
    only reason for it not to be a member method is that this way it doesn't
    have to be compiled into the library. And that's a gain, because the
    library should be compiled with optimization on, but this method should be
    compiled with debugging. */
void CglGMIUnitTest(const OsiSolverInterface * siP,
			 const std::string mpdDir );


#endif