#include <CglLandPSimplex.hpp>
Collaboration diagram for LAP::CglLandPSimplex:
Public Member Functions | |
CglLandPSimplex (const OsiSolverInterface &si, const CglLandP::CachedData &cached, bool reducedSpace, int numPivots) | |
Usefull onstructor. | |
~CglLandPSimplex () | |
Destructor. | |
void | cacheUpdate (const CglLandP::CachedData &cached, bool reducedSpace=0) |
Update cached information in case of basis change in a round. | |
bool | resetSolver (const CoinWarmStartBasis *basis) |
reset the solver to optimal basis | |
bool | findBestCut (int var, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters ¶ms) |
Perfom pivots to find the best cuts. | |
bool | generateMig (int row, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters ¶ms) const |
Find Gomory cut (i.e. | |
CglLandPSimplex () | |
No default constructor. | |
void | setLogLevel (int level) |
void | setSi (OsiSolverInterface *si) |
void | freeSi () |
Public Attributes | |
extraInfo | extra |
Protected Member Functions | |
bool | changeBasis (int incoming, int leaving, int direction) |
Perform a change in the basis (direction is 1 if leaving variable is going to ub, 0 otherwise). | |
int | findCutImprovingPivotRow (int &direction, int &gammaSign, double tolerance) |
Find a row which can be used to perform an improving pivot return index of the cut or -1 if none exists (i.e., find the leaving variable). | |
int | fastFindCutImprovingPivotRow (int &direction, int &gammaSign, double tolerance) |
Find a row which can be used to perform an improving pivot the fast way (i.e., find the leaving variable). | |
int | rescanReducedCosts (int &direction, int &gammaSign, double tolerance) |
Rescan reduced costs tables. | |
int | fastFindBestPivotColumn (int direction, int gammaSign, double pivotTol, double rhsTol, bool reducedSpace, bool allowNonImproving, double &bestSigma) |
Find the column which leads to the best cut (i.e., find incoming variable). | |
int | findBestPivotColumn (int direction, double pivotTol, bool reducedSpace, bool allowDegeneratePivot, bool modularize) |
Find the column which leads to the best cut (i.e., find incoming variable). | |
int | findBestPivot (int &leaving, int &direction, const CglLandP::Parameters ¶ms) |
Find incoming and leaving variables which lead to the most violated adjacent normalized lift-and-project cut. | |
double | computeCglpObjective (double gamma, bool strengthen) |
Compute the objective value of the Cglp with linear combintation of the two rows by gamma. | |
double | computeCglpObjective (TabRow &row) const |
Compute the objective value of the Cglp for given row and rhs (if strengthening shall be applied row should have been modularized). | |
double | intersectionCutCoef (double alpha_i, double beta) const |
return the coefficients of the intersection cut | |
double | strengthenedIntersectionCutCoef (int i, double alpha_i, double beta) const |
return the coefficients of the strengthened intersection cut | |
double | newRowCoefficient (int j, double gamma) const |
return the coefficient of the new row (combining row_k + gamma row_i). | |
double | modularizedCoef (double alpha, double beta) const |
compute the modularized row coefficient for an integer variable | |
double | computeCglpRedCost (int direction, int gammaSign) |
Compute the reduced cost of Cglp. | |
void | computeRedCostConstantsInRow () |
Compute the value of sigma and thau (which are constants for a row i as defined in Mike Perregaard thesis. | |
void | createIntersectionCut (const TabRow &row, OsiRowCut &cut) const |
Create the intersection cut of row k. | |
void | createMIG (TabRow &row, OsiRowCut &cut) const |
Create MIG cut from row k. | |
double | normCoef (TabRow &row) |
Compute normalization coefficient corresponding to sum of multipliers for cuts derived from row. | |
void | scale (OsiRowCut &cut, double norma) |
scale the cut passed as argument using provided normalization factor | |
void | scale (OsiRowCut &cut) |
scale the cut passed as argument | |
void | modularizeRow (TabRow &row) |
Modularize row. | |
void | pullTableauRow (TabRow &row) const |
Get the row i of the tableau. | |
void | adjustTableauRow (int var, TabRow &row, int direction) |
Adjust the row of the tableau to reflect leaving variable direction. | |
void | resetOriginalTableauRow (int var, TabRow &row, int direction) |
reset the tableau row after a call to adjustTableauRow | |
double | getLoBound (int index) |
Get lower bound for variable or constraint. | |
double | getUpBound (int index) |
Get upper bound for variable or constraint. | |
void | printTableau (std::ostream &os) |
print the tableau of current basis. | |
Private Types | |
clp | |
cplex | |
xpress | |
enum | lpSolver { clp, cplex, xpress } |
Private Member Functions | |
void | updateM1_M2_M3 (TabRow &row, double tolerance, bool recucedSpace, bool alwaysComputeCheap) |
Private Attributes | |
lpSolver | solver_ |
bool | own_ |
Own the data or not? | |
int | nNegativeRc_ |
number of negative reduced costs in current iteration | |
int | nNegativeRcRows_ |
number of rows with a <0 rc in current iteration | |
CoinMessageHandler * | handler_ |
Message handler. | |
CoinMessages | messages_ |
Messages. | |
Work infos | |
CglLandPSimplex::TabRow | row_k_ |
Source row for cut. | |
CglLandPSimplex::TabRow | perturbed_row_k_ |
Perturbed source row. | |
CglLandPSimplex::TabRow | row_i_ |
Row of leaving candidate. | |
CglLandPSimplex::TabRow | newRow_ |
Stores the new row. | |
CoinPackedVector | gammas_ |
vector to sort the gammas | |
double * | rWk1_ |
first work vector in row space. | |
double * | rWk2_ |
scond work vector in row space. | |
double * | rWk3_ |
third work vector in row space. | |
double * | rWk4_ |
fourth work vector in row space. | |
int * | rIntWork_ |
integer valued work vector on the rows | |
bool * | rowFlags_ |
Flag rows which we don't want to try anymore. | |
bool * | colHasToComputeContrib_ |
Flag columns for which contribution has to be computed in reduced cost(if in reduced space remove nonbasic structurals). | |
bool * | colCandidateToLeave_ |
Flag columns which have to be considered for leaving the basis. | |
int * | basics_ |
Store the basics variable. | |
int * | nonBasics_ |
Stores the nonBasicVariables. | |
int * | inM1_ |
Stores the variables which are always in M1 for a given k. | |
int * | inM2_ |
Stores the variables which are always in M2 for a given k. | |
int * | inM3_ |
Stores the variables which could be either in M1 or M2. | |
double | tau_ |
temporarily stores the value of thau for the current row | |
double | sigma_ |
stores the cglp value of the normalized cut obtained from row k_ | |
CoinWarmStartBasis | basis_ |
Keep track of basis status. | |
double * | colsolToCut_ |
Pointer to the solution to cut (need to be modified after each pivot because we are only considering slacks). | |
double * | colsol_ |
Pointer to the current basic solution. | |
int | numcols_ |
cached numcols | |
int | numrows_ |
cached numrows | |
double * | loBounds_ |
Source row for cut. | |
double * | upBounds_ |
Source row for cut. | |
bool | inDegenerateSequence_ |
Say if we are in a sequence of degenerate pivots. | |
double | chosenReducedCostVal_ |
Value for the reduced cost chosen for pivoting. | |
const bool * | integers_ |
pointer to array of integer info for both structural and slacks | |
Interfaces to the solver | |
OsiSolverInterface * | si_ |
Pointer to the solver interface. | |
Classes | |
struct | extraInfo |
struct | TabRow |
Definition at line 53 of file CglLandPSimplex.hpp.
enum LAP::CglLandPSimplex::lpSolver [private] |
LAP::CglLandPSimplex::CglLandPSimplex | ( | const OsiSolverInterface & | si, | |
const CglLandP::CachedData & | cached, | |||
bool | reducedSpace, | |||
int | numPivots | |||
) |
Usefull onstructor.
LAP::CglLandPSimplex::~CglLandPSimplex | ( | ) |
Destructor.
LAP::CglLandPSimplex::CglLandPSimplex | ( | ) | [inline] |
void LAP::CglLandPSimplex::cacheUpdate | ( | const CglLandP::CachedData & | cached, | |
bool | reducedSpace = 0 | |||
) |
Update cached information in case of basis change in a round.
bool LAP::CglLandPSimplex::resetSolver | ( | const CoinWarmStartBasis * | basis | ) |
reset the solver to optimal basis
bool LAP::CglLandPSimplex::findBestCut | ( | int | var, | |
OsiRowCut & | cut, | |||
const CglLandP::CachedData & | cached, | |||
const CglLandP::Parameters & | params | |||
) |
Perfom pivots to find the best cuts.
bool LAP::CglLandPSimplex::generateMig | ( | int | row, | |
OsiRowCut & | cut, | |||
const CglLandP::CachedData & | cached, | |||
const CglLandP::Parameters & | params | |||
) | const |
Find Gomory cut (i.e.
don't do extra setup required for pivots).
void LAP::CglLandPSimplex::setLogLevel | ( | int | level | ) | [inline] |
Definition at line 123 of file CglLandPSimplex.hpp.
References handler_, and CoinMessageHandler::setLogLevel().
void LAP::CglLandPSimplex::setSi | ( | OsiSolverInterface * | si | ) | [inline] |
void LAP::CglLandPSimplex::freeSi | ( | ) | [inline] |
bool LAP::CglLandPSimplex::changeBasis | ( | int | incoming, | |
int | leaving, | |||
int | direction | |||
) | [protected] |
Perform a change in the basis (direction is 1 if leaving variable is going to ub, 0 otherwise).
int LAP::CglLandPSimplex::findCutImprovingPivotRow | ( | int & | direction, | |
int & | gammaSign, | |||
double | tolerance | |||
) | [protected] |
Find a row which can be used to perform an improving pivot return index of the cut or -1 if none exists (i.e., find the leaving variable).
int LAP::CglLandPSimplex::fastFindCutImprovingPivotRow | ( | int & | direction, | |
int & | gammaSign, | |||
double | tolerance | |||
) | [protected] |
Find a row which can be used to perform an improving pivot the fast way (i.e., find the leaving variable).
int LAP::CglLandPSimplex::rescanReducedCosts | ( | int & | direction, | |
int & | gammaSign, | |||
double | tolerance | |||
) | [protected] |
Rescan reduced costs tables.
int LAP::CglLandPSimplex::fastFindBestPivotColumn | ( | int | direction, | |
int | gammaSign, | |||
double | pivotTol, | |||
double | rhsTol, | |||
bool | reducedSpace, | |||
bool | allowNonImproving, | |||
double & | bestSigma | |||
) | [protected] |
Find the column which leads to the best cut (i.e., find incoming variable).
int LAP::CglLandPSimplex::findBestPivotColumn | ( | int | direction, | |
double | pivotTol, | |||
bool | reducedSpace, | |||
bool | allowDegeneratePivot, | |||
bool | modularize | |||
) | [protected] |
Find the column which leads to the best cut (i.e., find incoming variable).
int LAP::CglLandPSimplex::findBestPivot | ( | int & | leaving, | |
int & | direction, | |||
const CglLandP::Parameters & | params | |||
) | [protected] |
Find incoming and leaving variables which lead to the most violated adjacent normalized lift-and-project cut.
leaving | variable | |
direction | leaving direction | |
numTryRows | number rows tried | |
pivotTol | pivot tolerance | |
reducedSpace | separaration space (reduced or full) | |
allowNonStrictlyImproving | wether or not to allow non stricly improving pivots. |
double LAP::CglLandPSimplex::computeCglpObjective | ( | double | gamma, | |
bool | strengthen | |||
) | [protected] |
Compute the objective value of the Cglp with linear combintation of the two rows by gamma.
double LAP::CglLandPSimplex::computeCglpObjective | ( | TabRow & | row | ) | const [protected] |
Compute the objective value of the Cglp for given row and rhs (if strengthening shall be applied row should have been modularized).
double LAP::CglLandPSimplex::intersectionCutCoef | ( | double | alpha_i, | |
double | beta | |||
) | const [inline, protected] |
return the coefficients of the intersection cut
Definition at line 407 of file CglLandPSimplex.hpp.
Referenced by strengthenedIntersectionCutCoef().
double LAP::CglLandPSimplex::strengthenedIntersectionCutCoef | ( | int | i, | |
double | alpha_i, | |||
double | beta | |||
) | const [inline, protected] |
return the coefficients of the strengthened intersection cut
Definition at line 415 of file CglLandPSimplex.hpp.
References flopc::floor(), integers_, and intersectionCutCoef().
double LAP::CglLandPSimplex::newRowCoefficient | ( | int | j, | |
double | gamma | |||
) | const [inline, protected] |
return the coefficient of the new row (combining row_k + gamma row_i).
Definition at line 433 of file CglLandPSimplex.hpp.
References LAP::CglLandPSimplex::TabRow::row, row_i_, and row_k_.
double LAP::CglLandPSimplex::modularizedCoef | ( | double | alpha, | |
double | beta | |||
) | const [inline, protected] |
compute the modularized row coefficient for an integer variable
Definition at line 440 of file CglLandPSimplex.hpp.
References flopc::floor().
double LAP::CglLandPSimplex::computeCglpRedCost | ( | int | direction, | |
int | gammaSign | |||
) | [protected] |
Compute the reduced cost of Cglp.
void LAP::CglLandPSimplex::computeRedCostConstantsInRow | ( | ) | [protected] |
Compute the value of sigma and thau (which are constants for a row i as defined in Mike Perregaard thesis.
void LAP::CglLandPSimplex::createIntersectionCut | ( | const TabRow & | row, | |
OsiRowCut & | cut | |||
) | const [protected] |
Create the intersection cut of row k.
Create MIG cut from row k.
double LAP::CglLandPSimplex::normCoef | ( | TabRow & | row | ) | [protected] |
Compute normalization coefficient corresponding to sum of multipliers for cuts derived from row.
void LAP::CglLandPSimplex::scale | ( | OsiRowCut & | cut, | |
double | norma | |||
) | [protected] |
scale the cut passed as argument using provided normalization factor
void LAP::CglLandPSimplex::scale | ( | OsiRowCut & | cut | ) | [protected] |
scale the cut passed as argument
void LAP::CglLandPSimplex::modularizeRow | ( | TabRow & | row | ) | [protected] |
Modularize row.
void LAP::CglLandPSimplex::pullTableauRow | ( | TabRow & | row | ) | const [protected] |
Get the row i of the tableau.
void LAP::CglLandPSimplex::adjustTableauRow | ( | int | var, | |
TabRow & | row, | |||
int | direction | |||
) | [protected] |
Adjust the row of the tableau to reflect leaving variable direction.
void LAP::CglLandPSimplex::resetOriginalTableauRow | ( | int | var, | |
TabRow & | row, | |||
int | direction | |||
) | [protected] |
reset the tableau row after a call to adjustTableauRow
double LAP::CglLandPSimplex::getLoBound | ( | int | index | ) | [inline, protected] |
Get lower bound for variable or constraint.
Definition at line 241 of file CglLandPSimplex.hpp.
References loBounds_.
double LAP::CglLandPSimplex::getUpBound | ( | int | index | ) | [inline, protected] |
Get upper bound for variable or constraint.
Definition at line 243 of file CglLandPSimplex.hpp.
References upBounds_.
void LAP::CglLandPSimplex::printTableau | ( | std::ostream & | os | ) | [protected] |
print the tableau of current basis.
void LAP::CglLandPSimplex::updateM1_M2_M3 | ( | TabRow & | row, | |
double | tolerance, | |||
bool | recucedSpace, | |||
bool | alwaysComputeCheap | |||
) | [private] |
extraInfo LAP::CglLandPSimplex::extra [mutable] |
Definition at line 156 of file CglLandPSimplex.hpp.
lpSolver LAP::CglLandPSimplex::solver_ [private] |
Definition at line 249 of file CglLandPSimplex.hpp.
CglLandPSimplex::TabRow LAP::CglLandPSimplex::row_k_ [mutable, private] |
Source row for cut.
Definition at line 255 of file CglLandPSimplex.hpp.
Referenced by newRowCoefficient().
Row of leaving candidate.
Definition at line 259 of file CglLandPSimplex.hpp.
Referenced by newRowCoefficient().
double* LAP::CglLandPSimplex::rWk1_ [private] |
double* LAP::CglLandPSimplex::rWk2_ [private] |
double* LAP::CglLandPSimplex::rWk3_ [private] |
double* LAP::CglLandPSimplex::rWk4_ [private] |
int* LAP::CglLandPSimplex::rIntWork_ [private] |
bool* LAP::CglLandPSimplex::rowFlags_ [private] |
bool* LAP::CglLandPSimplex::colHasToComputeContrib_ [private] |
Flag columns for which contribution has to be computed in reduced cost(if in reduced space remove nonbasic structurals).
Definition at line 277 of file CglLandPSimplex.hpp.
bool* LAP::CglLandPSimplex::colCandidateToLeave_ [private] |
Flag columns which have to be considered for leaving the basis.
Definition at line 279 of file CglLandPSimplex.hpp.
int* LAP::CglLandPSimplex::basics_ [private] |
int* LAP::CglLandPSimplex::nonBasics_ [private] |
int* LAP::CglLandPSimplex::inM1_ [private] |
Stores the variables which are always in M1 for a given k.
Definition at line 285 of file CglLandPSimplex.hpp.
int* LAP::CglLandPSimplex::inM2_ [private] |
Stores the variables which are always in M2 for a given k.
Definition at line 287 of file CglLandPSimplex.hpp.
int* LAP::CglLandPSimplex::inM3_ [private] |
Stores the variables which could be either in M1 or M2.
Definition at line 289 of file CglLandPSimplex.hpp.
double LAP::CglLandPSimplex::tau_ [private] |
temporarily stores the value of thau for the current row
Definition at line 291 of file CglLandPSimplex.hpp.
double LAP::CglLandPSimplex::sigma_ [private] |
stores the cglp value of the normalized cut obtained from row k_
Definition at line 293 of file CglLandPSimplex.hpp.
double* LAP::CglLandPSimplex::colsolToCut_ [private] |
Pointer to the solution to cut (need to be modified after each pivot because we are only considering slacks).
Definition at line 297 of file CglLandPSimplex.hpp.
double* LAP::CglLandPSimplex::colsol_ [private] |
int LAP::CglLandPSimplex::numcols_ [private] |
int LAP::CglLandPSimplex::numrows_ [private] |
double* LAP::CglLandPSimplex::loBounds_ [private] |
double* LAP::CglLandPSimplex::upBounds_ [private] |
bool LAP::CglLandPSimplex::inDegenerateSequence_ [private] |
Say if we are in a sequence of degenerate pivots.
Definition at line 309 of file CglLandPSimplex.hpp.
double LAP::CglLandPSimplex::chosenReducedCostVal_ [private] |
const bool* LAP::CglLandPSimplex::integers_ [private] |
pointer to array of integer info for both structural and slacks
Definition at line 313 of file CglLandPSimplex.hpp.
Referenced by strengthenedIntersectionCutCoef().
OsiSolverInterface* LAP::CglLandPSimplex::si_ [private] |
bool LAP::CglLandPSimplex::own_ [private] |
int LAP::CglLandPSimplex::nNegativeRc_ [private] |
number of negative reduced costs in current iteration
Definition at line 325 of file CglLandPSimplex.hpp.
int LAP::CglLandPSimplex::nNegativeRcRows_ [private] |
number of rows with a <0 rc in current iteration
Definition at line 327 of file CglLandPSimplex.hpp.
CoinMessageHandler* LAP::CglLandPSimplex::handler_ [private] |
CoinMessages LAP::CglLandPSimplex::messages_ [private] |