This file is indexed.

/usr/include/coin/CglTwomir.hpp is in coinor-libcgl-dev 0.58.9-1+b1.

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
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
// $Id: CglTwomir.hpp 1123 2013-04-06 20:47:24Z stefan $
// Copyright (C) 2002, International Business Machines
// Corporation and others.  All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).

#ifndef CglTwomir_H
#define CglTwomir_H
#include <string>

#include "CglCutGenerator.hpp"
#include "CoinFactorization.hpp"

typedef struct
{

  int nz;             /* current length of arrays index[] and coeff[] */
  int max_nz;         /* max length of arrays index[] and coeff[] */
  double *coeff;      /* coefficient of each variable in the constraint */
  int *index;         /* index of the variable (value in 0 ... nrow+ncol) */
  double rhs;         /* rhs of the constraint */
  char sense;         /* ?? is it necessary */

} DGG_constraint_t;

typedef struct{
  int n;
  DGG_constraint_t **c;
  int *ctype;
  double *alpha;
} DGG_list_t;

/******************** BASIS INFORMATION ADTs **********************************/
typedef struct{
  int q_min;
  int q_max;
  int t_min;
  int t_max;
  int a_max;
  int max_elements;
} cutParams;

typedef struct
{
  double gomory_threshold; /* factional variable must be this away from int */
  int ncol,        /* number of columns in LP */
    nrow,        /* number of constaints in LP */
    ninteger;    /* number of integer variables in LP */

  int nbasic_col,  /* number of basic columns in the LP */
    nbasic_row;  /* number of basic rows in the LP */

  /* the following arrays are all of size (ncol+nrow) */
  int *info;       /* description of each variable (see below) */
  double *lb;      /* specifies the lower bound (if any) of each variable */
  double *ub;      /* specifies the upper bound (if any) of each variable */
  double *x;       /* current solution */
  double *rc;      /* current reduced cost */
  double *opt_x;

  cutParams cparams;
} DGG_data_t;

/* the following macros allow us to decode the info of the DGG_data
   type. The encoding is as follows,
   bit 1 : if the variable is basic or not (non-basic).
   bit 2 : if the variable is integer or or not (rational).
   bit 3 : if the variable is structural or not (artifical). 
   bit 4 : if the variable is non-basic and at its upper bound 
   (else if non-basic at lower bound). */

#define DGG_isBasic(data,idx) ((data->info[idx])&1)
#define DGG_isInteger(data,idx) ((data->info[idx] >> 1)&1)
#define DGG_isStructural(data,idx) ((data->info[idx] >> 2)&1)
#define DGG_isEqualityConstraint(data,idx) ((data->info[idx] >> 3)&1)
#define DGG_isNonBasicAtUB(data,idx) ((data->info[idx] >> 4)&1)
#define DGG_isNonBasicAtLB(data,idx) ((data->info[idx] >> 5)&1)
#define DGG_isConstraintBoundedAbove(data,idx) ((data->info[idx] >> 6)&1)
#define DGG_isConstraintBoundedBelow(data,idx) ((data->info[idx] >> 7)&1)

#define DGG_setIsBasic(data,idx) ((data->info[idx]) |= 1)
#define DGG_setIsInteger(data,idx) ((data->info[idx]) |= (1<<1))
#define DGG_setIsStructural(data,idx) ((data->info[idx]) |= (1<<2))
#define DGG_setEqualityConstraint(data,idx) ((data->info[idx]) |= (1<<3))
#define DGG_setIsNonBasicAtUB(data,idx) ((data->info[idx]) |= (1<<4))
#define DGG_setIsNonBasicAtLB(data,idx) ((data->info[idx]) |= (1<<5))
#define DGG_setIsConstraintBoundedAbove(data,idx) ((data->info[idx]) |= (1<<6))
#define DGG_setIsConstraintBoundedBelow(data,idx) ((data->info[idx]) |= (1<<7))

class CoinWarmStartBasis;
/** Twostep MIR Cut Generator Class */
class CglTwomir : public CglCutGenerator {

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


public:

  /// Problem name
  std::string probname_;
    
  /**@name Generate Cuts */
  //@{
  /** Generate Two step MIR cuts either from the tableau rows or from the
      formulation rows
  */
  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;

  /**@name Change criterion on which scalings to use (default = 1,1,1,1) */
  //@{
  /// Set
  void setMirScale (int tmin, int tmax) {t_min_ = tmin; t_max_ = tmax;}
  void setTwomirScale (int qmin, int qmax) {q_min_ = qmin; q_max_ = qmax;}
  void setAMax (int a) {a_max_ = a;}
  void setMaxElements (int n) {max_elements_ = n;}
  void setMaxElementsRoot (int n) {max_elements_root_ = n;}
  void setCutTypes (bool mir, bool twomir, bool tab, bool form)
  { do_mir_ = mir; do_2mir_ = twomir; do_tab_ = tab; do_form_ = form;}
  void setFormulationRows (int n) {form_nrows_ = n;}

  /// Get
  int getTmin() const {return t_min_;}
  int getTmax() const {return t_max_;}
  int getQmin() const {return q_min_;}
  int getQmax() const {return q_max_;}
  int getAmax() const {return a_max_;}
  int getMaxElements() const {return max_elements_;}
  int getMaxElementsRoot() const {return max_elements_root_;}
  int getIfMir() const { return do_mir_;}
  int getIfTwomir() const { return do_2mir_;}
  int getIfTableau() const { return do_tab_;}
  int getIfFormulation() const { return do_form_;}
  //@}

  /**@name Change criterion on which variables to look at.  All ones
   more than "away" away from integrality will be investigated 
  (default 0.05) */
  //@{
  /// Set away
  void setAway(double value);
  /// Get away
  double getAway() const;
  /// Set away at root
  void setAwayAtRoot(double value);
  /// Get away at root
  double getAwayAtRoot() const;
  /// Return maximum length of cut in tree
  virtual int maximumLengthOfCutInTree() const
  { return max_elements_;}
  //@}

  /**@name Change way TwoMir works */
  //@{
  /// Pass in a copy of original solver (clone it)
  void passInOriginalSolver(OsiSolverInterface * solver);
  /// Returns original solver
  inline OsiSolverInterface * originalSolver() const
  { return originalSolver_;}
  /// Set type - 0 normal, 1 add original matrix one, 2 replace
  inline void setTwomirType(int type)
  { twomirType_=type;}
  /// Return type
  inline int twomirType() const
  { return twomirType_;}
  //@}

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

  /// Copy constructor 
  CglTwomir (const CglTwomir &);

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

  /// Assignment operator 
  CglTwomir & operator=(const CglTwomir& rhs);
  
  /// Destructor 
  virtual  ~CglTwomir ();
  /// Create C++ lines to get to current state
  virtual std::string generateCpp( FILE * fp);
  /// This can be used to refresh any inforamtion
  virtual void refreshSolver(OsiSolverInterface * solver);
  //@}
      
private:
  // Private member data
  /**@name Private member data */
  //@{
  /// Threadsafe random number generator
  CoinThreadRandom randomNumberGenerator_;
  /// Original solver
  OsiSolverInterface * originalSolver_;
  /// Only investigate if more than this away from integrality
  double away_;
  /// Only investigate if more than this away from integrality (at root)
  double awayAtRoot_;
  /// Type - 0 normal, 1 add original matrix one, 2 replace
  int twomirType_;
  bool do_mir_;
  bool do_2mir_;
  bool do_tab_;
  bool do_form_;

  int t_min_;  /// t_min - first value of t to use for tMIR inequalities
  int t_max_;  /// t_max - last value of t to use for tMIR inequalities
  int q_min_;  /// q_min - first value of t to use for 2-Step tMIR inequalities
  int q_max_;  /// q_max - last value of t to use for 2-Step tMIR inequalities
  int a_max_;  /// a_max - maximum value of bhat/alpha
  int max_elements_; /// Maximum number of elements in cut
  int max_elements_root_; /// Maximum number of elements in cut at root
  int form_nrows_; //number of rows on which formulation cuts will be generated
  //@}
};

//#############################################################################

/*
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <math.h>
#include <float.h>
#include <cassert>
#include <iostream.h>
*/

/******************** DEBUG DEFINITIONS ***************************************/

#define DGG_DEBUG_DGG 1
#define DGG_TRACE_ERRORS 0
#define DGG_DISPLAY   0
#define DGG_AUTO_CHECK_CUT_OFF_OPTIMAL 1

/******************** CONFIGURATION DEFAULTS **********************************/

#define DGG_DEFAULT_METHOD 2
#define DGG_DEFAULT_TMIN 1
#define DGG_DEFAULT_TMAX 1
#define DGG_DEFAULT_TAUMIN 2
#define DGG_DEFAULT_TAUMAX 6
#define DGG_DEFAULT_MAX_CUTS 500
#define DGG_DEFAULT_IMPROVEMENT_THRESH 0.001
#define DGG_DEFAULT_NBELOW_THRESH INT_MAX 
#define DGG_DEFAULT_NROOT_ROUNDS 2
#define DGG_DEFAULT_NEGATIVE_SCALED_TWOSTEPS 0
#define DGG_DEFAULT_ALPHA_RULE 0
#define DGG_DEFAULT_CUT_INC 250
#define DGG_DEFAULT_CUT_FORM 0
#define DGG_DEFAULT_NICEFY 0
#define DGG_DEFAULT_ONLY_DELAYED 0
#define DGG_DEFAULT_DELAYED_FREQ 9999999 
#define DGG_DEFAULT_LPROWS_FREQ 9999999
#define DGG_DEFAULT_WHICH_FORMULATION_CUTS 2

/******************** SOLVER CONFIGURATION DEFINITIONS ************************/

#define DGG_OSI 0
#define DGG_CPX 1
#define DGG_QSO 2

/* determines the solver to be used */
#define DGG_SOLVER DGG_OSI

/* adds checking routines to make sure solver works as expected */
#define DGG_DEBUG_SOLVER 0

/* turn off screen output from solver */
#define DGG_SOLVER_SCREEN_FLAG 0

/******************** CUT DEFINITIONS *****************************************/

/* internal names for cut types */
#define DGG_TMIR_CUT 1
#define DGG_2STEP_CUT 2

/* internal names for alpha-selection rules */
#define DGG_ALPHA_MIN_SUM 0
#define DGG_ALPHA_RANDOM_01 1
#define DGG_ALPHA_RANDOM_COEFF 2
#define DGG_ALPHA_ALL 3
#define DGG_ALPHA_MAX_STEEP 5

/******************** PRECISION & NUMERICAL ISSUES DEFINITIONS ****************/

/* how steep a cut must be before adding it to the lp */
#define DGG_MIN_STEEPNESS 1.0e-4
#define DGG_MAX_L2NORM 1.0e7

/* 0 = min steepness, 1 = max norm */
#define DGG_NORM_CRITERIA 1

/* internal representation of +infinity */
#define UB_MAX DBL_MAX

/* used to define how fractional a basic-integer variable must be
   before choosing to use it to generate a TMIR cut on.
   OSI's default is 1.0e-7 */
#define DGG_GOMORY_THRESH 0.005

#define DGG_RHS_THRESH 0.005

/* used for comparing variables to their upper bounds.
   OSI's default is 1.0e-7.
   We set it to 1.0e6 because e-7 seems too sensitive. 
   In fact, with e-7 the problem dsbmip.mps complains. */
#define DGG_BOUND_THRESH 1.0e-6

/* used for comparing the lhs (activity) value of a tableau row
   with the rhs. This is only used for debugging purposes. */
#define DGG_EQUALITY_THRESH 1.0e-5

/* used for comparing a variable's lower bound to 0.0
   and determining if we need to shift the variable    */
#define DGG_SHIFT_THRESH 1.0e-6

/* used for determing how far from an integer is still an integer.
   This value is used for comparing coefficients to integers.
   OSI's default is 1.0e-10.                               */
#define DGG_INTEGRALITY_THRESH 1.0e-10

/* the min value that a coeff can have in the tableau row
   before being set to zero. */
#define CBC_CHECK_CUT
#ifndef CBC_CHECK_CUT
#define DGG_MIN_TABLEAU_COEFFICIENT 1.0e-8
#else
#define DGG_MIN_TABLEAU_COEFFICIENT 1.0e-12
#endif

/* smallest value rho is allowed to have for a simple 2-step MIR
   (ie: not an extended two-step MIR) */
#define DGG_MIN_RHO 1.0e-7
#define DGG_MIN_ALPHA 1.0e-7

/* when a slack is null: used to check if a cut is satisfied or not. */
#define DGG_NULL_SLACK 1.0e-5

/* nicefy constants */
#define DGG_NICEFY_MIN_ABSVALUE 1.0e-13
#define DGG_NICEFY_MIN_FIX 1.0e-7
#define DGG_NICEFY_MAX_PADDING 1.0e-6
#define DGG_NICEFY_MAX_RATIO 1.0e9


/******************** ERROR-CATCHING MACROS ***********************************/
#if DGG_TRACE_ERRORS > 0

#define __DGG_PRINT_LOC__(F) fprintf(((F==0)?stdout:F), " in %s (%s:%d)\n", __func__, __FILE__, __LINE__)

#define DGG_THROW(A,REST...) {\
 fprintf(stdout, ##REST); \
 __DGG_PRINT_LOC__(stdout); \
 return (A);}

#define DGG_IF_EXIT(A,B,REST...) {\
 if(A) {\
 fprintf(stdout, ##REST); \
 __DGG_PRINT_LOC__(stdout); \
 exit(B);}}

#define DGG_CHECKRVAL(A,B) {\
 if(A) {\
   __DGG_PRINT_LOC__(stdout); \
   return B; } }

#define DGG_CHECKRVAL1(A,B) {\
 if(A) {\
   __DGG_PRINT_LOC__(stdout); \
   rval = B; goto CLEANUP; } }

#define DGG_WARNING(A, REST...) {\
  if(A) {\
	  fprintf(stdout, ##REST); \
		__DGG_PRINT_LOC__(stdout); \
		}}

#define DGG_TEST(A,B,REST...) {\
 if(A) DGG_THROW(B,##REST) }

#define DGG_TEST2(A,B,C,REST)   {DGG_TEST(A,B,C,REST) }
#define DGG_TEST3(A,B,C,D,REST) {DGG_TEST(A,B,C,D,REST) }

#else

#define DGG_IF_EXIT(A,B,REST) {if(A) {fprintf(stdout, REST);exit(B);}}

#define DGG_THROW(A,B) return(A)

#define DGG_CHECKRVAL(A,B) {  if(A) return(B); }
#define DGG_CHECKRVAL1(A,B){ if(A) { rval = B; goto CLEANUP; } }

#define DGG_TEST(A,B,REST) { if(A) return(B);}
#define DGG_TEST2(A,B,REST,C) { DGG_TEST(A,B,REST) }
#define DGG_TEST3(A,B,REST,C,D) { DGG_TEST(A,B,REST) }

#endif

/******************** SIMPLE MACROS AND FUNCTIONS *****************************/

#define DGG_MIN(a,b) ( (a<b)?a:b )
#define DGG_MAX(a,b) ( (a>b)?a:b )
#define KREM(vht,alpha,tau)  (DGG_MIN( ceil(vht / alpha), tau ) - 1)
#define LMIN(vht, d, bht) (DGG_MIN( floor(d*bht/bht), d))
#define ABOV(v) (v - floor(v))
#define QINT(vht,bht,tau) ( (int)floor( (vht*(tau-1))/bht ) )
#define V2I(bht,tau,i) ( ((i+1)*bht / tau) )

int DGG_is_even(double vht, double bht, int tau, int q);
double frac_part(double value);
int DGG_is_a_multiple_of_b(double a, double b);


/* free function for DGG_data_t. Frees internal arrays and data structure */
int DGG_freeData( DGG_data_t *data );

/******************** CONSTRAINT ADTs *****************************************/
DGG_constraint_t* DGG_newConstraint(int max_arrays);
void DGG_freeConstraint(DGG_constraint_t *c);
DGG_constraint_t *DGG_copyConstraint(DGG_constraint_t *c);
void DGG_scaleConstraint(DGG_constraint_t *c, int t);

/******************** CONFIGURATION *******************************************/
void DGG_list_init (DGG_list_t *l);
int DGG_list_addcut (DGG_list_t *l, DGG_constraint_t *cut, int ctype, double alpha);
void DGG_list_delcut (DGG_list_t *l, int i);
void DGG_list_free(DGG_list_t *l);

/******************* SOLVER SPECIFIC METHODS **********************************/
DGG_data_t *DGG_getData(const void *solver_ptr);

/******************* CONSTRAINT MANIPULATION **********************************/

/* DGG_transformConstraint: manipulates a constraint in the following way: 

packs everything in output

1 - variables at their upper bounds are substituted for their 
complements. This is done by adjusting the coefficients and 
the right hand side (simple substitution). 

2 - variables with non-zero lower bounds are shifted.            */

int DGG_transformConstraint( DGG_data_t *data,
                             double **x_out, 
			     double **rc_out,
                             char **isint_out,
                             DGG_constraint_t *constraint );

/* DGG_unTransformConstraint : 

1 - Undoes step (1) of DGG_transformConstraint 
2 - Undoes step (2) of DGG_transformConstraint                  */
 
int DGG_unTransformConstraint( DGG_data_t *data, 
                               DGG_constraint_t *constraint );

/* substitutes each slack variable by the structural variables which 
   define it. This function, hence, changes the constraint 'cut'.    */

int DGG_substituteSlacks( const void *solver_ptr, 
                          DGG_data_t *data, 
                          DGG_constraint_t *cut );

int DGG_nicefyConstraint( const void *solver_ptr, 
                          DGG_data_t *data,
			  DGG_constraint_t *cut);

/******************* CUT GENERATION *******************************************/
int DGG_getFormulaConstraint( int row_idx,  
                              const void *solver_ptr,   
			      DGG_data_t *data, 
                              DGG_constraint_t* row );

int DGG_getTableauConstraint( int index, 
                              const void *solver_ptr, 
                              DGG_data_t *data, 
                              DGG_constraint_t* tabrow,
                              const int * colIsBasic,
                              const int * rowIsBasic,
                              CoinFactorization & factorization,
                              int mode );

DGG_constraint_t* DGG_getSlackExpression(const void *solver_ptr, DGG_data_t* data, int row_index);

  int DGG_generateTabRowCuts( DGG_list_t *list,
			      DGG_data_t *data,
			      const void *solver_ptr );

  int DGG_generateFormulationCuts( DGG_list_t *list,
				   DGG_data_t *data,
				   const void *solver_ptr,
				   int nrows,
				   CoinThreadRandom & generator);


  int DGG_generateFormulationCutsFromBase( DGG_constraint_t *base,
					   double slack,
					   DGG_list_t *list,
					   DGG_data_t *data,
					   const void *solver_ptr,
					   CoinThreadRandom & generator);

  int DGG_generateCutsFromBase( DGG_constraint_t *base,
				DGG_list_t *list,
				DGG_data_t *data,
				const void *solver_ptr );

int DGG_buildMir( char *isint,
                  DGG_constraint_t *base,
                  DGG_constraint_t **cut_out );

int DGG_build2step( double alpha,
                    char *isint,
                    DGG_constraint_t *base,
                    DGG_constraint_t **cut_out );

  int DGG_addMirToList   ( DGG_constraint_t *base,
			   char *isint,
			   double *x,
			   DGG_list_t *list,
			   DGG_data_t *data,
			   DGG_constraint_t *orig_base );

  int DGG_add2stepToList ( DGG_constraint_t *base,
			   char *isint,
			   double *x,
			   double *rc,
			   DGG_list_t *list,
			   DGG_data_t *data,
			   DGG_constraint_t *orig_base );

/******************* CUT INFORMATION ******************************************/

double DGG_cutLHS(DGG_constraint_t *c, double *x);
int DGG_isCutDesirable(DGG_constraint_t *c, DGG_data_t *d);

/******************* TEST / DEBUGGING ROUTINES ********************************/

int DGG_isConstraintViolated(DGG_data_t *d, DGG_constraint_t *c);

int DGG_isBaseTrivial(DGG_data_t *d, DGG_constraint_t* c);
int DGG_is2stepValid(double alpha, double bht);

int DGG_cutsOffPoint(double *x, DGG_constraint_t *cut);

//#############################################################################
/** A function that tests the methods in the CglTwomir 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 CglTwomirUnitTest(const OsiSolverInterface * siP,
		       const std::string mpdDir);


#endif