Loading...
Searching...
No Matches
CglRedSplit2.hpp
Go to the documentation of this file.
// Last edit: 04/03/10
//
// Name: CglRedSplit2.hpp
// Author: Giacomo Nannicini
// Singapore University of Technology and Design
// Singapore
// email: nannicini@sutd.edu.sg
// based on CglRedSplit by Francois Margot
// Date: 03/09/09
//-----------------------------------------------------------------------------
// Copyright (C) 2010, Giacomo Nannicini and others. All Rights Reserved.
#ifndef CglRedSplit2_H
#define CglRedSplit2_H
#include "CglCutGenerator.hpp"
#include "CglRedSplit2Param.hpp"
#include "CoinWarmStartBasis.hpp"
#include "CoinHelperFunctions.hpp"
#include "CoinTime.hpp"
class CglRedSplit2 : public CglCutGenerator {
friend void CglRedSplit2UnitTest(const OsiSolverInterface * siP,
const std::string mpdDir);
public:
virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
const CglTreeInfo info = CglTreeInfo());
virtual bool needsOptimalBasis() const;
// Generate the row multipliers computed by Reduce-and-Split from the
// given OsiSolverInterface. The multipliers are written in lambda;
// lambda should be of size nrow*maxNumMultipliers. We generate at most
// maxNumMultipliers m-vectors of row multipliers, and return the number
// of m-vectors that were generated.
// If the caller wants to know which variables are basic in each row
// (same order as lambda), basicVariables should be non-NULL (size nrow).
// This method can also generate the cuts corresponding to the multipliers
// returned; it suffices to pass non-NULL OsiCuts.
// This method is not needed by the typical user; however, it is useful
// in the context of generating Lift & Project cuts.
int generateMultipliers(const OsiSolverInterface& si, int* lambda,
int maxNumMultipliers, int* basicVariables = NULL,
OsiCuts* cs = NULL);
// Try to improve a Lift & Project cut, by employing the
// Reduce-and-Split procedure. We start from a row of a L&P tableau,
// and generate a cut trying to reduce the coefficients on the
// nonbasic variables. Note that this L&P tableau will in general
// have nonbasic variables which are nonzero in the point that we
// want to cut off, so we should be careful. Arguments:
// OsiSolverInterface which contains the simplex tableau, initial
// row from which the cut is derived, row rhs, row number of the
// source row (if it is in the simplex tableau; otherwise, a
// negative number; needed to avoid using duplicate rows), point
// that we want to cut off (note: this is NOT a basic solution for
// the OsiSolverInterace!), list of variables which are basic in
// xbar but are nonbasic in the OsiSolverInterface. The computed cut
// is written in OsiRowCut* cs. Finally, if a starting disjunction
// is provided in the vector lambda (of size ncols, i.e. a
// disjunction on the structural variables), the disjunction is
// modified according to the cut which is produced.
int tiltLandPcut(const OsiSolverInterface* si, double* row,
double rowRhs, int rownumber, const double* xbar,
const int* newnonbasics, OsiRowCut* cs, int* lambda = NULL);
// Set the parameters to the values of the given CglRedSplit2Param object.
void setParam(const CglRedSplit2Param &source);
// Return the CglRedSplit2Param object of the generator.
inline CglRedSplit2Param& getParam() {return param;}
void print() const;
void printOptTab(OsiSolverInterface *solver) const;
CglRedSplit2();
CglRedSplit2(const CglRedSplit2Param &RS_param);
CglRedSplit2(const CglRedSplit2 &);
virtual CglCutGenerator * clone() const;
CglRedSplit2 & operator=(const CglRedSplit2& rhs);
virtual ~CglRedSplit2 ();
private:
// Private member methods
// Method generating the cuts after all CglRedSplit2 members are
// properly set. This does the actual work. Returns the number of
// generated cuts (or multipliers).
// Will generate cuts if cs != NULL, and will generate multipliers
// if lambda != NULL.
int generateCuts(OsiCuts* cs, int maxNumCuts, int* lambda = NULL);
inline double rs_above_integer(const double value) const;
void fill_workNonBasicTab(CglRedSplit2Param::ColumnSelectionStrategy
strategy, const int* ignore_list = NULL);
void fill_workNonBasicTab(const int* newnonbasics, const double* xbar,
CglRedSplit2Param::ColumnScalingStrategy scaling);
void reduce_workNonBasicTab(int numRows,
CglRedSplit2Param::RowSelectionStrategy
rowSelectionStrategy,
int maxIterations);
void generate_row(int index_row, double *row);
int generate_cgcut(double *row, double *rhs);
void eliminate_slacks(double *row,
const double *elements,
const CoinBigIndex *start,
const int *indices,
const int *rowLength,
const double *rhs, double *rowrhs);
void flip(double *row);
void unflip(double *row, double *rowrhs);
int check_dynamism(double *row);
int generate_packed_row(const double *xlp, double *row,
int *rowind, double *rowelem,
int *card_row, double & rhs);
// Compute entries of is_integer.
void compute_is_integer();
// Check that two vectors are different.
bool rs_are_different_vectors(const int *vect1,
const int *vect2,
const int dim);
// allocate matrix of integers
void rs_allocmatINT(int ***v, int m, int n);
// deallocate matrix of integers
void rs_deallocmatINT(int ***v, int m);
// allocate matrix of doubles
void rs_allocmatDBL(double ***v, int m, int n);
// deallocate matrix of doubles
void rs_deallocmatDBL(double ***v, int m);
// print a vector of integers
void rs_printvecINT(const char *vecstr, const int *x, int n) const;
// print a vector of doubles
void rs_printvecDBL(const char *vecstr, const double *x, int n) const;
// print a matrix of integers
void rs_printmatINT(const char *vecstr, const int * const *x, int m, int n) const;
// print a matrix of doubles
void rs_printmatDBL(const char *vecstr, const double * const *x, int m, int n) const;
// dot product
double rs_dotProd(const double *u, const double *v, int dim) const;
double rs_dotProd(const int *u, const double *v, int dim) const;
// From Numerical Recipes in C: LU decomposition
int ludcmp(double **a, int n, int *indx, double *d, double* vv) const;
// from Numerical Recipes in C: backward substitution
void lubksb(double **a, int n, int *indx, double *b) const;
// Check if the linear combination given by listOfRows with given multipliers
// improves the norm of row #rowindex; note: multipliers are rounded!
// Returns the difference with respect to the old norm (if negative there is
// an improvement, if positive norm increases)
double compute_norm_change(double oldnorm, const int* listOfRows,
int numElemList, const double* multipliers) const;
// Compute the list of rows that should be used to reduce row #rowIndex
int get_list_rows_reduction(int rowIndex, int numRowsReduction,
int* list, const double* norm,
CglRedSplit2Param::RowSelectionStrategy
rowSelectionStrategy) const;
// Sorts the rows by increasing number of nonzeroes with respect to a given
// row (rowIndex), on the nonbasic variables (whichTab == 0 means only
// integer, whichTab == 1 means only workTab, whichTab == 2 means both).
// The array for sorting must be allocated (and deleted) by caller.
// Corresponds to BRS1 in the paper.
int sort_rows_by_nonzeroes(struct sortElement* array, int rowIndex,
int maxRows, int whichTab) const;
// Greedy variant of the previous function; slower but typically
// more effective. Corresponds to BRS2 in the paper.
int sort_rows_by_nonzeroes_greedy(struct sortElement* array, int rowIndex,
int maxRows, int whichTab) const;
// Sorts the rows by decreasing absolute value of the cosine of the
// angle with respect to a given row (rowIndex), on the nonbasic
// variables (whichTab == 0 means only integer, whichTab == 1 means
// only workTab, whichTab == 2 means both). The array for sorting
// must be allocated (and deleted) by caller. Very effective
// strategy in practice. Corresponds to BRS3 in the paper.
int sort_rows_by_cosine(struct sortElement* array, int rowIndex,
int maxRows, int whichTab) const;
// Did we hit the time limit?
inline bool checkTime() const{
if ((CoinCpuTime() - startTime) < param.getTimeLimit()){
return true;
}
return false;
}
// Private member data
CglRedSplit2Param param;
int nrow;
int ncol;
int numRedRows;
const double *colLower;
const double *colUpper;
const double *rowLower;
const double *rowUpper;
const double *rowRhs;
const double *reducedCost;
const double *rowPrice;
const double* objective;
int card_intBasicVar;
int card_intBasicVar_frac;
int card_intNonBasicVar;
int card_contNonBasicVar;
int card_workNonBasicVar;
int card_nonBasicAtUpper;
int card_nonBasicAtLower;
int *cv_intBasicVar;
int *cv_intBasicVar_frac;
int *cv_fracRowsTab;
int *intBasicVar;
int *intBasicVar_frac;
int *intNonBasicVar;
// slacks are considered continuous (no harm if this is not the case).
int *contNonBasicVar;
int *nonBasicAtUpper;
int *nonBasicAtLower;
int mTab;
int nTab;
int **pi_mat;
double **contNonBasicTab;
double **workNonBasicTab;
// Dimensions: mTab by card_intNonBasicVar.
double **intNonBasicTab;
double *rhsTab;
double *norm;
int *is_integer;
OsiSolverInterface *solver;
const double *xlp;
const double *rowActivity;
const CoinPackedMatrix *byRow;
double startTime;
};
//#############################################################################
void CglRedSplit2UnitTest(const OsiSolverInterface * siP,
const std::string mpdDir );
#endif
CglCutGenerator.hpp
CglRedSplit2Param.hpp
CglRedSplit2UnitTest
void CglRedSplit2UnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests some of the methods in the CglRedSplit2 class.
CglCutGenerator::CglCutGenerator
CglCutGenerator()
Default constructor.
CglRedSplit2Param
Class collecting parameters the Reduced-and-split cut generator.
Definition CglRedSplit2Param.hpp:88
CglRedSplit2Param::RowSelectionStrategy
RowSelectionStrategy
Enumerations for parameters.
Definition CglRedSplit2Param.hpp:94
CglRedSplit2Param::ColumnSelectionStrategy
ColumnSelectionStrategy
Column selection strategies; again, look them up in the paper.
Definition CglRedSplit2Param.hpp:122
CglRedSplit2Param::ColumnScalingStrategy
ColumnScalingStrategy
Scaling strategies for new nonbasic columns for Lift & Project; "factor" is the value of columnScalin...
Definition CglRedSplit2Param.hpp:154
CglRedSplit2::setParam
void setParam(const CglRedSplit2Param &source)
CglRedSplit2::rs_dotProd
double rs_dotProd(const int *u, const double *v, int dim) const
CglRedSplit2::rowUpper
const double * rowUpper
Upper bounds for constraints.
Definition CglRedSplit2.hpp:352
CglRedSplit2::rs_above_integer
double rs_above_integer(const double value) const
Compute the fractional part of value, allowing for small error.
CglRedSplit2::card_nonBasicAtLower
int card_nonBasicAtLower
Number of non basic variables (structural or slack) at their lower bound in the current lp solution.
Definition CglRedSplit2.hpp:391
CglRedSplit2::CglRedSplit2UnitTest
friend void CglRedSplit2UnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests some of the methods in the CglRedSplit2 class.
CglRedSplit2::numRedRows
int numRedRows
Number of rows which have been reduced.
Definition CglRedSplit2.hpp:340
CglRedSplit2::cv_fracRowsTab
int * cv_fracRowsTab
Characteristic vector for rows of the tableau selected for reduction with non integer value in the cu...
Definition CglRedSplit2.hpp:402
CglRedSplit2::generateMultipliers
int generateMultipliers(const OsiSolverInterface &si, int *lambda, int maxNumMultipliers, int *basicVariables=NULL, OsiCuts *cs=NULL)
CglRedSplit2::print
void print() const
Print some of the data members; used for debugging.
CglRedSplit2::unflip
void unflip(double *row, double *rowrhs)
Change the sign of the coefficients of the continuous non basic variables at their upper bound and do...
CglRedSplit2::xlp
const double * xlp
Pointer on point to separate. Reset by each call to generateCuts().
Definition CglRedSplit2.hpp:467
CglRedSplit2::objective
const double * objective
Objective coefficients.
Definition CglRedSplit2.hpp:364
CglRedSplit2::compute_norm_change
double compute_norm_change(double oldnorm, const int *listOfRows, int numElemList, const double *multipliers) const
CglRedSplit2::cv_intBasicVar_frac
int * cv_intBasicVar_frac
Characteristic vector for integer basic structural variables with non integer value in the current lp...
Definition CglRedSplit2.hpp:398
CglRedSplit2::workNonBasicTab
double ** workNonBasicTab
Current tableau for continuous non basic variables (structural or slack).
Definition CglRedSplit2.hpp:445
CglRedSplit2::mTab
int mTab
Number of rows in the reduced tableau (= card_intBasicVar).
Definition CglRedSplit2.hpp:428
CglRedSplit2::sort_rows_by_nonzeroes_greedy
int sort_rows_by_nonzeroes_greedy(struct sortElement *array, int rowIndex, int maxRows, int whichTab) const
CglRedSplit2::rs_allocmatDBL
void rs_allocmatDBL(double ***v, int m, int n)
CglRedSplit2::card_intBasicVar
int card_intBasicVar
Number of integer basic structural variables.
Definition CglRedSplit2.hpp:367
CglRedSplit2::rs_deallocmatDBL
void rs_deallocmatDBL(double ***v, int m)
CglRedSplit2::rowRhs
const double * rowRhs
Righ hand side for constraints (upper bound for ranged constraints).
Definition CglRedSplit2.hpp:355
CglRedSplit2::get_list_rows_reduction
int get_list_rows_reduction(int rowIndex, int numRowsReduction, int *list, const double *norm, CglRedSplit2Param::RowSelectionStrategy rowSelectionStrategy) const
CglRedSplit2::colUpper
const double * colUpper
Upper bounds for structural variables.
Definition CglRedSplit2.hpp:346
CglRedSplit2::generate_cgcut
int generate_cgcut(double *row, double *rhs)
Generate a mixed integer Gomory cut, when all non basic variables are non negative and at their lower...
CglRedSplit2::flip
void flip(double *row)
Change the sign of the coefficients of the continuous non basic variables at their upper bound.
CglRedSplit2::card_contNonBasicVar
int card_contNonBasicVar
Number of continuous non basic variables (structural or slack) in the current lp solution.
Definition CglRedSplit2.hpp:379
CglRedSplit2::intNonBasicTab
double ** intNonBasicTab
Simplex tableau for integer non basic structural variables.
Definition CglRedSplit2.hpp:450
CglRedSplit2::compute_is_integer
void compute_is_integer()
CglRedSplit2::eliminate_slacks
void eliminate_slacks(double *row, const double *elements, const CoinBigIndex *start, const int *indices, const int *rowLength, const double *rhs, double *rowrhs)
Use multiples of the initial inequalities to cancel out the coefficients of the slack variables.
CglRedSplit2::fill_workNonBasicTab
void fill_workNonBasicTab(const int *newnonbasics, const double *xbar, CglRedSplit2Param::ColumnScalingStrategy scaling)
Fill workNonBasicTab, alternate version for Lift & Project: also reduces columns which are now nonbas...
CglRedSplit2::tiltLandPcut
int tiltLandPcut(const OsiSolverInterface *si, double *row, double rowRhs, int rownumber, const double *xbar, const int *newnonbasics, OsiRowCut *cs, int *lambda=NULL)
CglRedSplit2::rs_printvecDBL
void rs_printvecDBL(const char *vecstr, const double *x, int n) const
CglRedSplit2::generate_row
void generate_row(int index_row, double *row)
Generate a linear combination of the rows of the current LP tableau, using the row multipliers stored...
CglRedSplit2::contNonBasicTab
double ** contNonBasicTab
Simplex tableau for continuous non basic variables (structural or slack).
Definition CglRedSplit2.hpp:440
CglRedSplit2::cv_intBasicVar
int * cv_intBasicVar
Characteristic vector for integer basic structural variables.
Definition CglRedSplit2.hpp:394
CglRedSplit2::card_intNonBasicVar
int card_intNonBasicVar
Number of integer non basic structural variables in the current lp solution.
Definition CglRedSplit2.hpp:375
CglRedSplit2::rs_allocmatINT
void rs_allocmatINT(int ***v, int m, int n)
CglRedSplit2::startTime
double startTime
Time at which cut computations began.
Definition CglRedSplit2.hpp:478
CglRedSplit2::CglRedSplit2
CglRedSplit2()
Default constructor.
CglRedSplit2::ludcmp
int ludcmp(double **a, int n, int *indx, double *d, double *vv) const
CglRedSplit2::generateCuts
int generateCuts(OsiCuts *cs, int maxNumCuts, int *lambda=NULL)
CglRedSplit2::rs_dotProd
double rs_dotProd(const double *u, const double *v, int dim) const
CglRedSplit2::reducedCost
const double * reducedCost
Reduced costs for columns.
Definition CglRedSplit2.hpp:358
CglRedSplit2::nTab
int nTab
Number of columns in the reduced tableau (= card_contNonBasicVar).
Definition CglRedSplit2.hpp:431
CglRedSplit2::solver
OsiSolverInterface * solver
Pointer on solver. Reset by each call to generateCuts().
Definition CglRedSplit2.hpp:464
CglRedSplit2::intBasicVar_frac
int * intBasicVar_frac
List of integer structural basic variables with fractional value (in order of pivot in selected rows ...
Definition CglRedSplit2.hpp:410
CglRedSplit2::rs_printmatDBL
void rs_printmatDBL(const char *vecstr, const double *const *x, int m, int n) const
CglRedSplit2::check_dynamism
int check_dynamism(double *row)
Returns 1 if the row has acceptable max/min coeff ratio.
CglRedSplit2::operator=
CglRedSplit2 & operator=(const CglRedSplit2 &rhs)
Assignment operator.
CglRedSplit2::CglRedSplit2
CglRedSplit2(const CglRedSplit2Param &RS_param)
Constructor with specified parameters.
CglRedSplit2::rowLower
const double * rowLower
Lower bounds for constraints.
Definition CglRedSplit2.hpp:349
CglRedSplit2::rowPrice
const double * rowPrice
Row price.
Definition CglRedSplit2.hpp:361
CglRedSplit2::rs_deallocmatINT
void rs_deallocmatINT(int ***v, int m)
CglRedSplit2::getParam
CglRedSplit2Param & getParam()
Definition CglRedSplit2.hpp:132
CglRedSplit2::nonBasicAtLower
int * nonBasicAtLower
List of non basic variables (structural or slack) at their lower bound.
Definition CglRedSplit2.hpp:425
CglRedSplit2::param
CglRedSplit2Param param
Object with CglRedSplit2Param members.
Definition CglRedSplit2.hpp:331
CglRedSplit2::byRow
const CoinPackedMatrix * byRow
Pointer on matrix of coefficient ordered by rows.
Definition CglRedSplit2.hpp:474
CglRedSplit2::nrow
int nrow
Number of rows ( = number of slack variables) in the current LP.
Definition CglRedSplit2.hpp:334
CglRedSplit2::nonBasicAtUpper
int * nonBasicAtUpper
List of non basic variables (structural or slack) at their upper bound.
Definition CglRedSplit2.hpp:421
CglRedSplit2::rowActivity
const double * rowActivity
Pointer on row activity. Reset by each call to generateCuts().
Definition CglRedSplit2.hpp:470
CglRedSplit2::clone
virtual CglCutGenerator * clone() const
Clone.
CglRedSplit2::colLower
const double * colLower
Lower bounds for structural variables.
Definition CglRedSplit2.hpp:343
CglRedSplit2::is_integer
int * is_integer
Characteristic vectors of structural integer variables or continuous variables currently fixed to int...
Definition CglRedSplit2.hpp:461
CglRedSplit2::checkTime
bool checkTime() const
Definition CglRedSplit2.hpp:314
CglRedSplit2::ncol
int ncol
Number of structural variables in the current LP.
Definition CglRedSplit2.hpp:337
CglRedSplit2::reduce_workNonBasicTab
void reduce_workNonBasicTab(int numRows, CglRedSplit2Param::RowSelectionStrategy rowSelectionStrategy, int maxIterations)
Reduce rows of workNonBasicTab, i.e.
CglRedSplit2::intBasicVar
int * intBasicVar
List of integer structural basic variables (in order of pivot in selected rows for cut generation).
Definition CglRedSplit2.hpp:406
CglRedSplit2::CglRedSplit2
CglRedSplit2(const CglRedSplit2 &)
Copy constructor.
CglRedSplit2::rs_printvecINT
void rs_printvecINT(const char *vecstr, const int *x, int n) const
CglRedSplit2::lubksb
void lubksb(double **a, int n, int *indx, double *b) const
CglRedSplit2::needsOptimalBasis
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts (will return true).
CglRedSplit2::printOptTab
void printOptTab(OsiSolverInterface *solver) const
Print the current simplex tableau.
CglRedSplit2::rs_printmatINT
void rs_printmatINT(const char *vecstr, const int *const *x, int m, int n) const
CglRedSplit2::card_nonBasicAtUpper
int card_nonBasicAtUpper
Number of non basic variables (structural or slack) at their upper bound in the current lp solution.
Definition CglRedSplit2.hpp:387
CglRedSplit2::generateCuts
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate Reduce-and-Split Mixed Integer Gomory cuts for the model of the solver interface si.
CglRedSplit2::card_intBasicVar_frac
int card_intBasicVar_frac
Number of integer basic structural variables that are fractional in the current lp solution (at least...
Definition CglRedSplit2.hpp:371
CglRedSplit2::rs_are_different_vectors
bool rs_are_different_vectors(const int *vect1, const int *vect2, const int dim)
CglRedSplit2::card_workNonBasicVar
int card_workNonBasicVar
Number of continuous non basic variables (structural or slack) in the current working set for coeffic...
Definition CglRedSplit2.hpp:383
CglRedSplit2::~CglRedSplit2
virtual ~CglRedSplit2()
Destructor.
CglRedSplit2::norm
double * norm
Norm of rows in workNonBasicTab; needed for faster computations.
Definition CglRedSplit2.hpp:457
CglRedSplit2::sort_rows_by_nonzeroes
int sort_rows_by_nonzeroes(struct sortElement *array, int rowIndex, int maxRows, int whichTab) const
CglRedSplit2::sort_rows_by_cosine
int sort_rows_by_cosine(struct sortElement *array, int rowIndex, int maxRows, int whichTab) const
CglRedSplit2::contNonBasicVar
int * contNonBasicVar
List of continuous non basic variables (structural or slack).
Definition CglRedSplit2.hpp:417
CglRedSplit2::fill_workNonBasicTab
void fill_workNonBasicTab(CglRedSplit2Param::ColumnSelectionStrategy strategy, const int *ignore_list=NULL)
Fill workNonBasicTab, depending on the column selection strategy.
CglRedSplit2::generate_packed_row
int generate_packed_row(const double *xlp, double *row, int *rowind, double *rowelem, int *card_row, double &rhs)
Generate the packed cut from the row representation.
CglRedSplit2::intNonBasicVar
int * intNonBasicVar
List of integer structural non basic variables.
Definition CglRedSplit2.hpp:413
CglRedSplit2::rhsTab
double * rhsTab
Right hand side of the tableau.
Definition CglRedSplit2.hpp:454
CglRedSplit2::pi_mat
int ** pi_mat
Tableau of multipliers used to alter the rows used in generation.
Definition CglRedSplit2.hpp:435
CglTreeInfo
Information about where the cut generator is invoked from.
Definition CglTreeInfo.hpp:15