Loading...
Searching...
No Matches
CglRedSplit.hpp
Go to the documentation of this file.
// Last edit: 4/20/07
//
// Name: CglRedSplit.hpp
// Author: Francois Margot
// Tepper School of Business
// Carnegie Mellon University, Pittsburgh, PA 15213
// email: fmargot@andrew.cmu.edu
// Date: 2/6/05
//
// $Id$
//-----------------------------------------------------------------------------
// Copyright (C) 2005, Francois Margot and others. All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).
#ifndef CglRedSplit_H
#define CglRedSplit_H
#include "CglCutGenerator.hpp"
#include "CglRedSplitParam.hpp"
class CglRedSplit : public CglCutGenerator {
friend void CglRedSplitUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir);
public:
virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
const CglTreeInfo info = CglTreeInfo());
virtual bool needsOptimalBasis() const;
// Set the parameters to the values of the given CglRedSplitParam object.
void setParam(const CglRedSplitParam &source);
// Return the CglRedSplitParam object of the generator.
inline CglRedSplitParam getParam() const {return param;}
// Compute entries of low_is_lub and up_is_lub.
void compute_is_lub();
// Compute entries of is_integer.
void compute_is_integer();
void set_given_optsol(const double *given_sol, const int card_sol);
void print() const;
void printOptTab(OsiSolverInterface *solver) const;
//************************************************************
// TO BE REMOVED
void setLimit(int limit);
int getLimit() const;
void setAway(double value);
double getAway() const;
void setLUB(double value);
double getLUB() const;
void setEPS(double value);
double getEPS() const;
void setEPS_COEFF(double value);
double getEPS_COEFF() const;
void setEPS_COEFF_LUB(double value);
double getEPS_COEFF_LUB() const;
void setEPS_RELAX(double value);
double getEPS_RELAX() const;
void setNormIsZero(double value);
double getNormIsZero() const;
void setMinReduc(double value);
double getMinReduc() const;
void setMaxTab(double value);
double getMaxTab() const;
// END TO BE REMOVED
//************************************************************
CglRedSplit();
CglRedSplit(const CglRedSplitParam &RS_param);
CglRedSplit (const CglRedSplit &);
virtual CglCutGenerator * clone() const;
CglRedSplit &
operator=(
const CglRedSplit& rhs);
virtual
~CglRedSplit ();
virtual std::string generateCpp( FILE * fp);
private:
// Private member methods
// Method generating the cuts after all CglRedSplit members are properly set.
void generateCuts(OsiCuts & cs);
inline double rs_above_integer(double value);
void update_pi_mat(int r1, int r2, int step);
void update_redTab(int r1, int r2, int step);
void find_step(int r1, int r2, int *step,
double *reduc, double *norm);
int test_pair(int r1, int r2, double *norm);
void reduce_contNonBasicTab();
void generate_row(int index_row, double *row);
int generate_cgcut(double *row, double *rhs);
int generate_cgcut_2(int basic_ind, 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, double *slack_val);
double row_scale_factor(double *row);
int generate_packed_row(const double *xlp, double *row,
int *rowind, double *rowelem,
int *card_row, double & rhs);
void check_optsol(const int calling_place,
const double *xlp, const double *slack_val,
const int do_flip);
void check_optsol(const int calling_place,
const double *xlp, const double *slack_val,
const double *ck_row, const double ck_rhs,
const int cut_number, const int do_flip);
// Check that two vectors are different.
bool rs_are_different_vectors(const int *vect1,
const int *vect2,
const int dim);
// Check that two vectors are different.
bool rs_are_different_vectors(const double *vect1,
const double *vect2,
const int dim);
// Check that two matrices are different.
bool rs_are_different_matrices(const CoinPackedMatrix *mat1,
const CoinPackedMatrix *mat2,
const int nmaj,
const int nmin);
// Private member data
CglRedSplitParam param;
int nrow;
int ncol;
const double *colLower;
const double *colUpper;
const double *rowLower;
const double *rowUpper;
const double *rowRhs;
int card_intBasicVar_frac;
int card_intNonBasicVar;
int card_contNonBasicVar;
int card_nonBasicAtUpper;
int card_nonBasicAtLower;
int *cv_intBasicVar_frac;
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;
// Dimensions: mTab by card_intNonBasicVar.
double **intNonBasicTab;
double *rhsTab ;
const double *given_optsol;
int card_given_optsol;
int *is_integer;
int *low_is_lub;
int *up_is_lub;
OsiSolverInterface *solver;
const double *xlp;
const double *rowActivity;
const char *colType;
const CoinPackedMatrix *byRow;
};
//#############################################################################
void CglRedSplitUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir );
#endif
CglCutGenerator.hpp
CglRedSplitParam.hpp
CglRedSplitUnitTest
void CglRedSplitUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglRedSplit class.
CglCutGenerator::CglCutGenerator
CglCutGenerator()
Default constructor.
CglRedSplitParam
Class collecting parameters the Reduced-and-split cut generator.
Definition CglRedSplitParam.hpp:61
CglRedSplit::check_optsol
void check_optsol(const int calling_place, const double *xlp, const double *slack_val, const int do_flip)
Check that the generated cuts do not cut a given optimal solution.
CglRedSplit::given_optsol
const double * given_optsol
Given optimal solution that should not be cut; only for debug.
Definition CglRedSplit.hpp:402
CglRedSplit::getEPS_RELAX
double getEPS_RELAX() const
Get the value of EPS_RELAX.
CglRedSplit::setParam
void setParam(const CglRedSplitParam &source)
CglRedSplit::CglRedSplit
CglRedSplit(const CglRedSplitParam &RS_param)
Constructor with specified parameters.
CglRedSplit::cv_intBasicVar_frac
int * cv_intBasicVar_frac
Characteristic vector for integer basic structural variables with non integer value in the current lp...
Definition CglRedSplit.hpp:356
CglRedSplit::rs_are_different_vectors
bool rs_are_different_vectors(const int *vect1, const int *vect2, const int dim)
CglRedSplit::set_given_optsol
void set_given_optsol(const double *given_sol, const int card_sol)
Set given_optsol to the given optimal solution given_sol.
CglRedSplit::row_scale_factor
double row_scale_factor(double *row)
Return the scale factor for the row.
CglRedSplit::solver
OsiSolverInterface * solver
Pointer on solver. Reset by each call to generateCuts().
Definition CglRedSplit.hpp:420
CglRedSplit::card_nonBasicAtUpper
int card_nonBasicAtUpper
Number of non basic variables (structural or slack) at their upper bound in the current lp solution.
Definition CglRedSplit.hpp:348
CglRedSplit::getLUB
double getLUB() const
Get the value of LUB.
CglRedSplit::is_integer
int * is_integer
Characteristic vectors of structural integer variables or continuous variables currently fixed to int...
Definition CglRedSplit.hpp:409
CglRedSplit::needsOptimalBasis
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts (will return true).
CglRedSplit::getMinReduc
double getMinReduc() const
Get the value of minReduc.
CglRedSplit::setEPS_COEFF_LUB
void setEPS_COEFF_LUB(double value)
Set the value of EPS_COEFF_LUB, epsilon for values of coefficients for variables with absolute value ...
CglRedSplit::colType
const char * colType
Pointer on column type. Reset by each call to generateCuts().
Definition CglRedSplit.hpp:429
CglRedSplit::flip
void flip(double *row)
Change the sign of the coefficients of the continuous non basic variables at their upper bound.
CglRedSplit::generate_cgcut_2
int generate_cgcut_2(int basic_ind, double *row, double *rhs)
Generate a mixed integer Chvatal-Gomory cut, when all non basic variables are non negative and at the...
CglRedSplit::setNormIsZero
void setNormIsZero(double value)
Set the value of normIsZero, the threshold for considering a norm to be 0; Default: 1e-5.
CglRedSplit::setEPS_RELAX
void setEPS_RELAX(double value)
Set the value of EPS_RELAX, value used for relaxing the right hand side of each generated cut; Defaul...
CglRedSplit::test_pair
int test_pair(int r1, int r2, double *norm)
Test if an ordered pair of rows yields a reduction.
CglRedSplit::contNonBasicVar
int * contNonBasicVar
List of continuous non basic variables (structural or slack).
Definition CglRedSplit.hpp:367
CglRedSplit::param
CglRedSplitParam param
Object with CglRedSplitParam members.
Definition CglRedSplit.hpp:311
CglRedSplit::getEPS_COEFF
double getEPS_COEFF() const
Get the value of EPS_COEFF.
CglRedSplit::unflip
void unflip(double *row, double *rowrhs, double *slack_val)
Change the sign of the coefficients of the continuous non basic variables at their upper bound and do...
CglRedSplit::nrow
int nrow
Number of rows ( = number of slack variables) in the current LP.
Definition CglRedSplit.hpp:314
CglRedSplit::reduce_contNonBasicTab
void reduce_contNonBasicTab()
Reduce rows of contNonBasicTab.
CglRedSplit::print
void print() const
Print some of the data members.
CglRedSplit::setAway
void setAway(double value)
Set away, the minimum distance from being integer used for selecting rows for cut generation; all row...
CglRedSplit::clone
virtual CglCutGenerator * clone() const
Clone.
CglRedSplit::colLower
const double * colLower
Lower bounds for structural variables.
Definition CglRedSplit.hpp:320
CglRedSplit::rhsTab
double * rhsTab
Right hand side of the tableau.
Definition CglRedSplit.hpp:399
CglRedSplit::getMaxTab
double getMaxTab() const
Get the value of maxTab.
CglRedSplit::nTab
int nTab
Number of columns in the reduced tableau (= card_contNonBasicVar).
Definition CglRedSplit.hpp:381
CglRedSplit::rs_above_integer
double rs_above_integer(double value)
Compute the fractional part of value, allowing for small error.
CglRedSplit::nonBasicAtLower
int * nonBasicAtLower
List of non basic variables (structural or slack) at their lower bound.
Definition CglRedSplit.hpp:375
CglRedSplit::operator=
CglRedSplit & operator=(const CglRedSplit &rhs)
Assignment operator.
CglRedSplit::xlp
const double * xlp
Pointer on point to separate. Reset by each call to generateCuts().
Definition CglRedSplit.hpp:423
CglRedSplit::up_is_lub
int * up_is_lub
Characteristic vector of the structural variables whose upper bound in absolute value is larger than ...
Definition CglRedSplit.hpp:417
CglRedSplit::generateCpp
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
CglRedSplit::intBasicVar_frac
int * intBasicVar_frac
List of integer structural basic variables (in order of pivot in selected rows for cut generation).
Definition CglRedSplit.hpp:360
CglRedSplit::getParam
CglRedSplitParam getParam() const
Definition CglRedSplit.hpp:75
CglRedSplit::getEPS_COEFF_LUB
double getEPS_COEFF_LUB() const
Get the value of EPS_COEFF_LUB.
CglRedSplit::update_redTab
void update_redTab(int r1, int r2, int step)
Perform row r1 of tab := row r1 of tab - step * row r2 of tab.
CglRedSplit::byRow
const CoinPackedMatrix * byRow
Pointer on matrix of coefficient ordered by rows.
Definition CglRedSplit.hpp:433
CglRedSplit::card_nonBasicAtLower
int card_nonBasicAtLower
Number of non basic variables (structural or slack) at their lower bound in the current lp solution.
Definition CglRedSplit.hpp:352
CglRedSplit::setLUB
void setLUB(double value)
Set the value of LUB, value considered large for the absolute value of a lower or upper bound on a va...
CglRedSplit::mTab
int mTab
Number of rows in the reduced tableau (= card_intBasicVar_frac).
Definition CglRedSplit.hpp:378
CglRedSplit::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.
CglRedSplit::rowUpper
const double * rowUpper
Upper bounds for constraints.
Definition CglRedSplit.hpp:329
CglRedSplit::~CglRedSplit
virtual ~CglRedSplit()
Destructor.
CglRedSplit::generate_cgcut
int generate_cgcut(double *row, double *rhs)
Generate a mixed integer Chvatal-Gomory cut, when all non basic variables are non negative and at the...
CglRedSplit::contNonBasicTab
double ** contNonBasicTab
Current tableau for continuous non basic variables (structural or slack).
Definition CglRedSplit.hpp:390
CglRedSplit::setEPS
void setEPS(double value)
Set the value of EPS, epsilon for double computations; Default: 1e-7.
CglRedSplit::setLimit
void setLimit(int limit)
Set limit, the maximum number of non zero coefficients in generated cut; Default: 50.
CglRedSplit::compute_is_lub
void compute_is_lub()
CglRedSplit::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.
CglRedSplit::card_intBasicVar_frac
int card_intBasicVar_frac
Number of integer basic structural variables that are fractional in the current lp solution (at least...
Definition CglRedSplit.hpp:336
CglRedSplit::rs_are_different_matrices
bool rs_are_different_matrices(const CoinPackedMatrix *mat1, const CoinPackedMatrix *mat2, const int nmaj, const int nmin)
CglRedSplit::card_given_optsol
int card_given_optsol
Number of entries in given_optsol.
Definition CglRedSplit.hpp:405
CglRedSplit::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.
CglRedSplit::card_intNonBasicVar
int card_intNonBasicVar
Number of integer non basic structural variables in the current lp solution.
Definition CglRedSplit.hpp:340
CglRedSplit::ncol
int ncol
Number of structural variables in the current LP.
Definition CglRedSplit.hpp:317
CglRedSplit::CglRedSplit
CglRedSplit()
Default constructor.
CglRedSplit::setEPS_COEFF
void setEPS_COEFF(double value)
Set the value of EPS_COEFF, epsilon for values of coefficients; Default: 1e-8.
CglRedSplit::pi_mat
int ** pi_mat
Tableau of multipliers used to alter the rows used in generation.
Definition CglRedSplit.hpp:385
CglRedSplit::colUpper
const double * colUpper
Upper bounds for structural variables.
Definition CglRedSplit.hpp:323
CglRedSplit::nonBasicAtUpper
int * nonBasicAtUpper
List of non basic variables (structural or slack) at their upper bound.
Definition CglRedSplit.hpp:371
CglRedSplit::getAway
double getAway() const
Get value of away.
CglRedSplit::rs_are_different_vectors
bool rs_are_different_vectors(const double *vect1, const double *vect2, const int dim)
CglRedSplit::rowActivity
const double * rowActivity
Pointer on row activity. Reset by each call to generateCuts().
Definition CglRedSplit.hpp:426
CglRedSplit::getEPS
double getEPS() const
Get the value of EPS.
CglRedSplit::update_pi_mat
void update_pi_mat(int r1, int r2, int step)
Perform row r1 of pi := row r1 of pi - step * row r2 of pi.
CglRedSplit::rowLower
const double * rowLower
Lower bounds for constraints.
Definition CglRedSplit.hpp:326
CglRedSplit::generateCuts
void generateCuts(OsiCuts &cs)
CglRedSplit::rowRhs
const double * rowRhs
Righ hand side for constraints (upper bound for ranged constraints).
Definition CglRedSplit.hpp:332
CglRedSplit::generate_row
void generate_row(int index_row, double *row)
Generate a row of the current LP tableau.
CglRedSplit::printOptTab
void printOptTab(OsiSolverInterface *solver) const
Print the current simplex tableau.
CglRedSplit::getLimit
int getLimit() const
Get value of limit.
CglRedSplit::getNormIsZero
double getNormIsZero() const
Get the value of normIsZero.
CglRedSplit::intNonBasicTab
double ** intNonBasicTab
Current tableau for integer non basic structural variables.
Definition CglRedSplit.hpp:395
CglRedSplit::check_optsol
void check_optsol(const int calling_place, const double *xlp, const double *slack_val, const double *ck_row, const double ck_rhs, const int cut_number, const int do_flip)
Check that the generated cuts do not cut a given optimal solution.
CglRedSplit::compute_is_integer
void compute_is_integer()
CglRedSplit::low_is_lub
int * low_is_lub
Characteristic vector of the structural variables whose lower bound in absolute value is larger than ...
Definition CglRedSplit.hpp:413
CglRedSplit::setMinReduc
void setMinReduc(double value)
Set the value of minReduc, threshold for relative norm improvement for performing a reduction; Defaul...
CglRedSplit::find_step
void find_step(int r1, int r2, int *step, double *reduc, double *norm)
Find optimal integer step for changing row r1 by adding to it a multiple of another row r2.
CglRedSplit::CglRedSplit
CglRedSplit(const CglRedSplit &)
Copy constructor.
CglRedSplit::intNonBasicVar
int * intNonBasicVar
List of integer structural non basic variables.
Definition CglRedSplit.hpp:363
CglRedSplit::CglRedSplitUnitTest
friend void CglRedSplitUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglRedSplit class.
CglRedSplit::card_contNonBasicVar
int card_contNonBasicVar
Number of continuous non basic variables (structural or slack) in the current lp solution.
Definition CglRedSplit.hpp:344
CglRedSplit::setMaxTab
void setMaxTab(double value)
Set the maximum allowed value for (mTab * mTab * CoinMax(mTab, nTab)) where mTab is the number of row...
CglTreeInfo
Information about where the cut generator is invoked from.
Definition CglTreeInfo.hpp:15