- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- Alphabetical List
- Class List
- Class Hierarchy
- Class Members

# LAP::CglLandPSimplex Class Reference

`#include <CglLandPSimplex.hpp>`

Collaboration diagram for LAP::CglLandPSimplex:

[legend]
List of all members.

## 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 &params)
| Perfom pivots to find the best cuts.
bool | generateMig (int row, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters &params) 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 &params)
| 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

## Detailed Description

Definition at line 53 of file CglLandPSimplex.hpp.

## Member Enumeration Documentation

enum LAP::CglLandPSimplex::lpSolver`[private]`

Enumerator:

  clp |
  cplex |
  xpress |

Definition at line 248 of file CglLandPSimplex.hpp.

## Constructor & Destructor Documentation

LAP::CglLandPSimplex::CglLandPSimplex | ( | const OsiSolverInterface & | si,
|  | const CglLandP::CachedData & | cached,
|  | bool | reducedSpace,
|  | int | numPivots |
| ) |  |  |

Usefull onstructor.

LAP::CglLandPSimplex::~CglLandPSimplex | ( |  | ) |

Destructor.

LAP::CglLandPSimplex::CglLandPSimplex | ( |  | ) | `[inline]`

No default constructor.

Definition at line 115 of file CglLandPSimplex.hpp.

## Member Function Documentation

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]`

Definition at line 127 of file CglLandPSimplex.hpp.

References si_.

void LAP::CglLandPSimplex::freeSi | ( |  | ) | `[inline]`

Definition at line 129 of file CglLandPSimplex.hpp.

References si_.

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).

Returns:
  index of the cut or -1 if none exists.

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.

Remarks:
  At this point reduced costs should be already computed.

Returns:
  incoming variable variable,

Parameters:

  | 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 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

Bug:
  not the same as in Ionut's pseudo code, it is not the same

Definition at line 440 of file CglLandPSimplex.hpp.

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.

void LAP::CglLandPSimplex::createMIG | ( | TabRow & | row,
|  | OsiRowCut & | cut |
| ) |  |  | const`[protected]`

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]`

## Member Data Documentation

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().

CglLandPSimplex::TabRow LAP::CglLandPSimplex::perturbed_row_k_`[private]`

Perturbed source row.

Definition at line 257 of file CglLandPSimplex.hpp.

CglLandPSimplex::TabRow LAP::CglLandPSimplex::row_i_`[private]`

Row of leaving candidate.

Definition at line 259 of file CglLandPSimplex.hpp.

Referenced by newRowCoefficient().

CglLandPSimplex::TabRow LAP::CglLandPSimplex::newRow_`[private]`

Stores the new row.

Definition at line 261 of file CglLandPSimplex.hpp.

CoinPackedVector LAP::CglLandPSimplex::gammas_`[private]`

vector to sort the gammas

Definition at line 263 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::rWk1_`[private]`

first work vector in row space.

Definition at line 265 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::rWk2_`[private]`

scond work vector in row space.

Definition at line 267 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::rWk3_`[private]`

third work vector in row space.

Definition at line 269 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::rWk4_`[private]`

fourth work vector in row space.

Definition at line 271 of file CglLandPSimplex.hpp.

int* LAP::CglLandPSimplex::rIntWork_`[private]`

integer valued work vector on the rows

Definition at line 273 of file CglLandPSimplex.hpp.

bool* LAP::CglLandPSimplex::rowFlags_`[private]`

Flag rows which we don't want to try anymore.

Definition at line 275 of file CglLandPSimplex.hpp.

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]`

Store the basics variable.

Definition at line 281 of file CglLandPSimplex.hpp.

int* LAP::CglLandPSimplex::nonBasics_`[private]`

Stores the nonBasicVariables.

Definition at line 283 of file CglLandPSimplex.hpp.

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.

CoinWarmStartBasis LAP::CglLandPSimplex::basis_`[private]`

Keep track of basis status.

Definition at line 295 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]`

Pointer to the current basic solution.

Definition at line 299 of file CglLandPSimplex.hpp.

int LAP::CglLandPSimplex::numcols_`[private]`

cached numcols

Definition at line 301 of file CglLandPSimplex.hpp.

int LAP::CglLandPSimplex::numrows_`[private]`

cached numrows

Definition at line 303 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::loBounds_`[private]`

Source row for cut.

Definition at line 305 of file CglLandPSimplex.hpp.

Referenced by getLoBound().

double* LAP::CglLandPSimplex::upBounds_`[private]`

Source row for cut.

Definition at line 307 of file CglLandPSimplex.hpp.

Referenced by getUpBound().

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]`

Value for the reduced cost chosen for pivoting.

Definition at line 311 of file CglLandPSimplex.hpp.

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]`

Pointer to the solver interface.

Definition at line 318 of file CglLandPSimplex.hpp.

Referenced by freeSi(), and setSi().

bool LAP::CglLandPSimplex::own_`[private]`

Own the data or not?

Definition at line 321 of file CglLandPSimplex.hpp.

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]`

Message handler.

Definition at line 400 of file CglLandPSimplex.hpp.

Referenced by setLogLevel().

CoinMessages LAP::CglLandPSimplex::messages_`[private]`

Messages.

Definition at line 402 of file CglLandPSimplex.hpp.

The documentation for this class was generated from the following file:

- /home/coin/SVN-release/Cgl-0.53.1/Cgl/src/CglLandP/CglLandPSimplex.hpp