diff options
Diffstat (limited to 'build/Bonmin/include/coin/CglTwomir.hpp')
| -rw-r--r-- | build/Bonmin/include/coin/CglTwomir.hpp | 565 |
1 files changed, 565 insertions, 0 deletions
diff --git a/build/Bonmin/include/coin/CglTwomir.hpp b/build/Bonmin/include/coin/CglTwomir.hpp new file mode 100644 index 0000000..ba00380 --- /dev/null +++ b/build/Bonmin/include/coin/CglTwomir.hpp @@ -0,0 +1,565 @@ +// $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; +/** 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 + + |