CglTwomir.hpp

Go to the documentation of this file.

// $Id: CglTwomir.hpp 1119 2013-04-06 20:24:18Z 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;
class CglTwomir : public CglCutGenerator {

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


public:

  std::string probname_;
    
  virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs, 
                             const CglTreeInfo info = CglTreeInfo());
  virtual bool needsOptimalBasis() const;

  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;}

  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_;}

  void setAway(double value);
  double getAway() const;
  void setAwayAtRoot(double value);
  double getAwayAtRoot() const;
  virtual int maximumLengthOfCutInTree() const
  { return max_elements_;}

  void passInOriginalSolver(OsiSolverInterface * solver);
  inline OsiSolverInterface * originalSolver() const
  { return originalSolver_;}
  inline void setTwomirType(int type)
  { twomirType_=type;}
  inline int twomirType() const
  { return twomirType_;}

  CglTwomir ();

  CglTwomir (const CglTwomir &);

  virtual CglCutGenerator * clone() const;

  CglTwomir & operator=(const CglTwomir& rhs);
  
  virtual  ~CglTwomir ();
  virtual std::string generateCpp( FILE * fp);
  virtual void refreshSolver(OsiSolverInterface * solver);
      
private:
  // Private member data
  CoinThreadRandom randomNumberGenerator_;
  OsiSolverInterface * originalSolver_;
  double away_;
  double awayAtRoot_;
  int twomirType_;
  bool do_mir_;
  bool do_2mir_;
  bool do_tab_;
  bool do_form_;

  int t_min_;  
  int t_max_;  
  int q_min_;  
  int q_max_;  
  int a_max_;  
  int max_elements_; 
  int max_elements_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);

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


#endif