// Name: CglRedSplit2Param.hpp // Author: Giacomo Nannicini // Singapore University of Technology and Design // Singapore // email: nannicini@sutd.edu.sg // Date: 03/09/09 //----------------------------------------------------------------------------- // Copyright (C) 2010, Giacomo Nannicini and others. All Rights Reserved. #ifndef CglRedSplit2Param_H #define CglRedSplit2Param_H #include "CglParam.hpp" #include /**@name CglRedSplit2 Parameters */ //@{ /** Class collecting parameters the Reduced-and-split cut generator. An important thing to note is that the cut generator allows for the selection of a number of strategies that can be combined together. By default, a selection that typically yields a good compromise between speed and cut strenght is made. The selection can be changed by resetting the default choices (see the functions whose name starts with "reset") or by setting the parameter use_default_strategies to false in the constructors. After this, the chosen strategies can be added to the list by using the functions whose name starts with "add". All strategies will be combined together: if we choose 3 row selection strategies, 2 column selection strategies, and 2 possible numbers of rows, we end up with a total of 3*2*2 combinations. For a detailed explanation of the parameters and their meaning, see the paper by Cornuejols and Nannicini: "Practical strategies for generating rank-1 split cuts in mixed-integer linear programming", on Mathematical Programming Computation. Parameters of the generator are listed below. - MAXDYN: Maximum ratio between largest and smallest non zero coefficients in a cut. See method setMAXDYN(). - EPS_ELIM: Precision for deciding if a coefficient is zero when eliminating slack variables. See method setEPS_ELIM(). - MINVIOL: Minimum violation for the current basic solution in a generated cut. See method setMINVIOL(). - EPS_RELAX_ABS: Absolute relaxation of cut rhs. - EPS_RELAX_REL: Relative relaxation of cut rhs. - MAX_SUPP_ABS: Maximum cut support (absolute). - MAX_SUPP_REL: Maximum cut support (relative): the formula to compute maximum cut support is MAX_SUPP_ABS + ncol*MAX_SUPP_REL. - USE_INTSLACKS: Use integer slacks to generate cuts. (not implemented). See method setUSE_INTSLACKS(). - normIsZero: Norm of a vector is considered zero if smaller than this value. See method setNormIsZero(). - minNormReduction: a cut is generated if the new norm of the row on the continuous nonbasics is reduced by at least this factor (relative reduction). - away: Look only at basic integer variables whose current value is at least this value from being integer. See method setAway(). - maxSumMultipliers: maximum sum (in absolute value) of row multipliers - normalization: normalization factor for the norm of lambda in the coefficient reduction algorithm (convex min problem) - numRowsReduction: Maximum number of rows in the linear system for norm reduction. - columnSelectionStrategy: parameter to select which columns should be used for coefficient reduction. - rowSelectionStrategy: parameter to select which rows should be used for coefficient reduction. - timeLimit: Time limit (in seconds) for cut generation. - maxNumCuts: Maximum number of cuts that can be returned at each pass; we could generate more cuts than this number (see below) - maxNumComputedCuts: Maximum number of cuts that can be computed by the generator at each pass - maxNonzeroesTab : Rows of the simplex tableau with more than this number of nonzeroes will not be considered for reduction. Only works if RS_FAST_* are defined in CglRedSplit2. - skipGomory: Skip traditional Gomory cuts, i.e. GMI cuts arising from a single row of the tableau (instead of a combination). Default is 1 (true), because we assume that they are generated by a traditional Gomory generator anyway. */ //@} class CglRedSplit2Param : public CglParam { public: /** Enumerations for parameters */ /** Row selection strategies; same names as in the paper */ enum RowSelectionStrategy{ /* Pick rows that introduce the fewest nonzeroes on integer nonbasics */ RS1, /* Pick rows that introduce the fewest nonzeroes on the set of working continuous nonbasics */ RS2, /* Pick rows that introduce the fewest nonzeroes on both integer and working continuous nonbasics */ RS3, /* Same as RS0 but with greedy algorithm */ RS4, /* Same as RS1 but with greedy algorithm */ RS5, /* Same as RS2 but with greedy algorithm */ RS6, /* Pick rows with smallest angle in the space of integer and working continuous nonbasics */ RS7, /* Pick rows with smallest angle in the space of working continuous nonbasics */ RS8, /* Use all strategies */ RS_ALL, /* Use best ones - that is, RS8 and RS7 */ RS_BEST }; /** Column selection strategies; again, look them up in the paper. */ enum ColumnSelectionStrategy{ /* C-3P */ CS1, CS2, CS3, /* C-5P */ CS4, CS5, CS6, CS7, CS8, /* I-2P-2/3 */ CS9, CS10, /* I-2P-4/5 */ CS11, CS12, /* I-2P-1/2 */ CS13, CS14, /* I-3P */ CS15, CS16, CS17, /* I-4P */ CS18, CS19, CS20, CS21, /* Use all strategies up to this point */ CS_ALL, /* Use best strategies (same effect as CS_ALL, because it turns out that using all strategies is the best thing to do) */ CS_BEST, /* Optimize over all continuous nonbasic columns; this does not give good results, but we use it for testing Lift & Project + RedSplit */ CS_ALLCONT, /* Lift & Project specific strategy: only select variables which are nonbasic in the tableau but are basic in the point to cut off. This strategy cannot be used outside L&P. It is not very effective even with L&P, but is left here for testing.*/ CS_LAP_NONBASICS }; /** Scaling strategies for new nonbasic columns for Lift & Project; * "factor" is the value of columnScalingBoundLAP_ */ enum ColumnScalingStrategy{ /* No scaling */ SC_NONE, /* Multiply by |xbar[i]| where xbar[i] is the value of the corresponding component of the point that we want to cut off */ SC_LINEAR, /* Multiply by min(factor,|xbar[i]|) */ SC_LINEAR_BOUNDED, /* Multiply by min(factor,log(|xbar[i]|)) */ SC_LOG_BOUNDED, /* Multiply all new nonbasics by factor */ SC_UNIFORM, /* Multiply only nonzero coefficients by factor */ SC_UNIFORM_NZ }; /**@name Set/get methods */ //@{ /** Set away, the minimum distance from being integer used for selecting rows for cut generation; all rows whose pivot variable should be integer but is more than away from integrality will be selected; Default: 0.005 */ virtual void setAway(double value); /// Get value of away inline double getAway() const {return away_;} /** Set the value of EPS_ELIM, epsilon for values of coefficients when eliminating slack variables; Default: 0.0 */ void setEPS_ELIM(double value); /** Get the value of EPS_ELIM */ double getEPS_ELIM() const {return EPS_ELIM;} /** Set EPS_RELAX_ABS */ virtual void setEPS_RELAX_ABS(double eps_ra); /** Get value of EPS_RELAX_ABS */ inline double getEPS_RELAX_ABS() const {return EPS_RELAX_ABS;} /** Set EPS_RELAX_REL */ virtual void setEPS_RELAX_REL(double eps_rr); /** Get value of EPS_RELAX_REL */ inline double getEPS_RELAX_REL() const {return EPS_RELAX_REL;} // Set the maximum ratio between largest and smallest non zero // coefficients in a cut. Default: 1e6. virtual void setMAXDYN(double value); /** Get the value of MAXDYN */ inline double getMAXDYN() const {return MAXDYN;} /** Set the value of MINVIOL, the minimum violation for the current basic solution in a generated cut. Default: 1e-3 */ virtual void setMINVIOL(double value); /** Get the value of MINVIOL */ inline double getMINVIOL() const {return MINVIOL;} /** Maximum absolute support of the cutting planes. Default: INT_MAX. Aliases for consistency with our naming scheme. */ inline void setMAX_SUPP_ABS(int value) {setMAX_SUPPORT(value);} inline int getMAX_SUPP_ABS() const {return MAX_SUPPORT;} /** Maximum relative support of the cutting planes. Default: 0.0. The maximum support is MAX_SUPP_ABS + MAX_SUPPREL*ncols. */ inline void setMAX_SUPP_REL(double value); inline double getMAX_SUPP_REL() const {return MAX_SUPP_REL;} /** Set the value of USE_INTSLACKS. Default: 0 */ virtual void setUSE_INTSLACKS(int value); /** Get the value of USE_INTSLACKS */ inline int getUSE_INTSLACKS() const {return USE_INTSLACKS;} /** Set the value of normIsZero, the threshold for considering a norm to be 0; Default: 1e-5 */ virtual void setNormIsZero(double value); /** Get the value of normIsZero */ inline double getNormIsZero() const {return normIsZero_;} /** Set the value of minNormReduction; Default: 0.1 */ virtual void setMinNormReduction(double value); /** Get the value of normIsZero */ inline double getMinNormReduction() const {return minNormReduction_;} /** Set the value of maxSumMultipliers; Default: 10 */ virtual void setMaxSumMultipliers(int value); /** Get the value of maxSumMultipliers */ inline int getMaxSumMultipliers() const {return maxSumMultipliers_;} /** Set the value of normalization; Default: 0.0001 */ virtual void setNormalization(double value); /** Get the value of normalization */ inline double getNormalization() const {return normalization_;} /** Set the value of numRowsReduction, max number of rows that are used * for each row reduction step. In particular, the linear system will * involve a numRowsReduction*numRowsReduction matrix */ virtual void addNumRowsReduction(int value); /// get the value inline std::vector getNumRowsReduction() const {return numRowsReduction_;} /// reset inline void resetNumRowsReduction() {numRowsReduction_.clear();} /** Add the value of columnSelectionStrategy */ virtual void addColumnSelectionStrategy(ColumnSelectionStrategy value); /// get the value inline std::vector getColumnSelectionStrategy() const {return columnSelectionStrategy_;} /// reset inline void resetColumnSelectionStrategy(){columnSelectionStrategy_.clear();} /** Set the value for rowSelectionStrategy, which changes the way we choose * the rows for the reduction step */ virtual void addRowSelectionStrategy(RowSelectionStrategy value); /// get the value inline std::vector getRowSelectionStrategy() const {return rowSelectionStrategy_;}; /// reset inline void resetRowSelectionStrategy() {rowSelectionStrategy_.clear();} /** Set the value of numRowsReductionLAP, max number of rows that are used * for each row reduction step during Lift & Project. * In particular, the linear system will involve a * numRowsReduction*numRowsReduction matrix */ virtual void addNumRowsReductionLAP(int value); /// get the value inline std::vector getNumRowsReductionLAP() const {return numRowsReductionLAP_;} /// reset inline void resetNumRowsReductionLAP() {numRowsReductionLAP_.clear();} /** Add the value of columnSelectionStrategyLAP */ virtual void addColumnSelectionStrategyLAP(ColumnSelectionStrategy value); /// get the value inline std::vector getColumnSelectionStrategyLAP() const {return columnSelectionStrategyLAP_;} /// reset inline void resetColumnSelectionStrategyLAP(){columnSelectionStrategyLAP_.clear();} /** Set the value for rowSelectionStrategyLAP, which changes the way we * choose the rows for the reduction step */ virtual void addRowSelectionStrategyLAP(RowSelectionStrategy value); /// get the value inline std::vector getRowSelectionStrategyLAP() const {return rowSelectionStrategyLAP_;}; /// reset inline void resetRowSelectionStrategyLAP() {rowSelectionStrategyLAP_.clear();} /** Set the value for columnScalingStrategyLAP, which sets the way nonbasic * columns that are basic in the fractional point to cut off are scaled */ virtual void setColumnScalingStrategyLAP(ColumnScalingStrategy value); /// get the value inline ColumnScalingStrategy getColumnScalingStrategyLAP() const {return columnScalingStrategyLAP_; }; /** Set the value for the bound in the column scaling factor */ virtual void setColumnScalingBoundLAP(double value); /// get the value inline double getColumnScalingBoundLAP() const {return columnScalingBoundLAP_;}; /** Set the value of the time limit for cut generation (in seconds) */ virtual void setTimeLimit(double value); /// get the value inline double getTimeLimit() const {return timeLimit_;} /** Set the value for the maximum number of cuts that can be returned */ virtual void setMaxNumCuts(int value); /// get the value inline int getMaxNumCuts() const {return maxNumCuts_;} /** Set the value for the maximum number of cuts that can be computed */ virtual void setMaxNumComputedCuts(int value); /// get the value inline int getMaxNumComputedCuts() const {return maxNumComputedCuts_;} /** Set the value for the maximum number of nonzeroes in a row of * the simplex tableau for the row to be considered */ virtual void setMaxNonzeroesTab(int value); /// get the value inline int getMaxNonzeroesTab() const {return maxNonzeroesTab_;} /** Set the value of skipGomory: should we skip simple Gomory cuts, * i.e. GMI cuts derived from a single row of the simple tableau? * This is 1 (true) by default: we only generate cuts from linear * combinations of at least two rows. */ virtual void setSkipGomory(int value); /// get the value inline int getSkipGomory() const {return skipGomory_;} //@} /**@name Constructors and destructors */ //@{ /// Default constructor. If use_default_strategies is true, we add /// to the list of strategies the default ones. If is false, the /// list of strategies is left empty (must be populated before usage!). CglRedSplit2Param(bool use_default_strategies = true, double eps = 1e-12, double eps_coeff = 1e-11, double eps_elim = 0.0, double eps_relax_abs = 1e-11, double eps_relax_rel = 1e-13, double max_dyn = 1e6, double min_viol = 1e-3, int max_supp_abs = 1000, double max_supp_rel = 0.1, int use_int_slacks = 0, double norm_zero = 1e-5, double minNormReduction = 0.1, int maxSumMultipliers = 10, double normalization = 0.0001, double away = 0.005, double timeLimit = 60, int maxNumCuts = 10000, int maxNumComputedCuts = 10000, int maxNonzeroesTab = 1000, double columnScalingBoundLAP = 5.0, int skipGomory = 1); /// Constructor from CglParam. If use_default_strategies is true, we /// add to the list of strategies the default ones. If is false, the /// list of strategies is left empty (must be populated before /// usage!). CglRedSplit2Param(const CglParam &source, bool use_default_strategies = true, double eps_elim = 0.0, double eps_relax_abs = 1e-11, double eps_relax_rel = 1e-13, double max_dyn = 1e6, double min_viol = 1e-3, double max_supp_rel = 0.1, int use_int_slacks = 0, double norm_zero = 1e-5, double minNormReduction = 0.1, int maxSumMultipliers = 10, double normalization = 0.0001, double away = 0.005, double timeLimit = 60, int maxNumCuts = 10000, int maxNumComputedCuts = 10000, int maxNonzeroesTab = 1000, double columnScalingBoundLAP = 5.0, int skipGomory = 1); /// Copy constructor CglRedSplit2Param(const CglRedSplit2Param &source); /// Clone virtual CglRedSplit2Param* clone() const; /// Assignment operator virtual CglRedSplit2Param& operator=(const CglRedSplit2Param &rhs); /// Destructor virtual ~CglRedSplit2Param(); //@} protected: /**@name Parameters */ //@{ /** Epsilon for value of coefficients when eliminating slack variables. Default: 0.0. */ double EPS_ELIM; /** Value added to the right hand side of each generated cut to relax it. Default: 1e-11 */ double EPS_RELAX_ABS; /** For a generated cut with right hand side rhs_val, EPS_RELAX_EPS * fabs(rhs_val) is used to relax the constraint. Default: 1e-13 */ double EPS_RELAX_REL; // Maximum ratio between largest and smallest non zero // coefficients in a cut. Default: 1e6. double MAXDYN; /// Minimum violation for the current basic solution in a generated cut. /// Default: 1e-3. double MINVIOL; /// Maximum support - relative part of the formula double MAX_SUPP_REL; /// Use integer slacks to generate cuts if USE_INTSLACKS = 1. Default: 0. int USE_INTSLACKS; /// Norm of a vector is considered zero if smaller than normIsZero; /// Default: 1e-5. double normIsZero_; /// Minimum reduction to accept a new row. double minNormReduction_; /// Maximum sum of the vector of row multipliers to generate a cut int maxSumMultipliers_; /// Normalization factor for the norm of lambda in the quadratic /// minimization problem that is solved during the coefficient reduction step double normalization_; /// Use row only if pivot variable should be integer but is more /// than away_ from being integer. Default: 0.005 double away_; /// Maximum number of rows to use for the reduction of a given row. std::vector numRowsReduction_; /// Column selection method std::vector columnSelectionStrategy_; /// Row selection method std::vector rowSelectionStrategy_; /// Maximum number of rows to use for the reduction during Lift & Project std::vector numRowsReductionLAP_; /// Column selection method for Lift & Project std::vector columnSelectionStrategyLAP_; /// Row selection method for Lift & Project std::vector rowSelectionStrategyLAP_; /// Column scaling strategy for the nonbasics columns that were basic in /// the point that we want to cut off (Lift & Project only) ColumnScalingStrategy columnScalingStrategyLAP_; /// Minimum value for column scaling (Lift & Project only) double columnScalingBoundLAP_; /// Time limit double timeLimit_; /// Maximum number of returned cuts int maxNumCuts_; /// Maximum number of computed cuts int maxNumComputedCuts_; /// Maximum number of nonzeroes in tableau row for reduction int maxNonzeroesTab_; /// Skip simple Gomory cuts int skipGomory_; //@} }; #endif