Scippy

GCG

Branch-and-Price & Column Generation for Everyone

Detailed Description

Definition at line 55 of file objpricer_gcg.h.

#include <objpricer_gcg.h>

Public Member Functions

 ObjPricerGcg (SCIP *scip, SCIP *origscip, const char *name, const char *desc, int priority, unsigned int delay, SCIP_PRICERDATA *pricerdata)
 
virtual ~ObjPricerGcg ()
 
virtual SCIP_DECL_PRICERFREE (scip_free)
 
virtual SCIP_DECL_PRICERINIT (scip_init)
 
virtual SCIP_DECL_PRICEREXIT (scip_exit)
 
virtual SCIP_DECL_PRICERINITSOL (scip_initsol)
 
virtual SCIP_DECL_PRICEREXITSOL (scip_exitsol)
 
virtual SCIP_DECL_PRICERREDCOST (scip_redcost)
 
virtual SCIP_DECL_PRICERFARKAS (scip_farkas)
 
SCIP_PRICERDATA * getPricerdata ()
 
SCIP_Real getConvconsDualsol (PricingType *pricetype, int probnr)
 
SCIP_RETCODE setPricingObjs (PricingType *pricetype, SCIP_Bool stabilize)
 
void updateRedcostColumnPool (PricingType *pricetype)
 
SCIP_RETCODE priceColumnPoolOld (PricingType *pricetype, int *pnfoundvars)
 
SCIP_RETCODE priceNewVariables (PricingType *pricetype, SCIP_RESULT *result, double *lowerbound)
 
SCIP_RETCODE createNewMasterVar (SCIP *scip, PricingType *pricetype, SCIP_SOL *sol, SCIP_VAR **solvars, double *solvals, int nsolvars, unsigned int solisray, int prob, unsigned int force, unsigned int *added, SCIP_VAR **addedvar)
 
SCIP_RETCODE createNewMasterVarFromGcgCol (SCIP *scip, PricingType *pricetype, GCG_COL *gcgcol, SCIP_Bool force, SCIP_Bool *added, SCIP_VAR **addedvar, SCIP_Real score)
 
SCIP_RETCODE computeDualDiff (SCIP_Real **dualvals1, SCIP_Real *dualconv1, SCIP_Real **dualvals2, SCIP_Real *dualconv2, SCIP_Real *dualdiff)
 
SCIP_RETCODE pricingLoop (PricingType *pricetype, SCIP_RESULT *result, int *nfoundvars, SCIP_Real *lowerbound, SCIP_Bool *bestredcostvalid)
 
const FarkasPricinggetFarkasPricing () const
 
FarkasPricinggetFarkasPricingNonConst ()
 
const ReducedCostPricinggetReducedCostPricing () const
 
ReducedCostPricinggetReducedCostPricingNonConst ()
 
SCIP * getOrigprob ()
 
int getMaxColsRound () const
 
int getMaxColsProb () const
 
SCIP_RETCODE addArtificialVars ()
 
SCIP_RETCODE addTrivialsols ()
 
SCIP_RETCODE createPricingTypes ()
 
SCIP_RETCODE createPricingcontroller ()
 
void createStabilization ()
 
SCIP_RETCODE createColpool ()
 
SCIP_RETCODE createPricestore ()
 
void updateRedcosts (PricingType *pricetype, GCG_COL **cols, int ncols, int *nimpcols)
 
SCIP_RETCODE addColToPricestore (GCG_COL *col)
 
void getBestCols (GCG_COL **pricingprobcols)
 
SCIP_Real getDualconvsum (GCG_COL **bestcols)
 
SCIP_RETCODE getStabilizedDualObjectiveValue (PricingType *pricetype, SCIP_Real *stabdualval, SCIP_Bool stabilize)
 
SCIP_Real computeRedCostGcgCol (PricingType *pricetype, GCG_Col *gcgcol, SCIP_Real *objvalptr) const
 
SCIP_RETCODE computeColMastercoefs (GCG_COL *gcgcol)
 
SCIP_RETCODE computeColMastercuts (GCG_COL *gcgcol)
 

Data Fields

SCIP * origprob
 
SCIP_PRICERDATA * pricerdata
 
GCG_COLPOOLcolpool
 
GCG_PRICESTOREpricestore
 

Static Public Attributes

static int threads
 

Constructor & Destructor Documentation

◆ ObjPricerGcg()

ObjPricerGcg::ObjPricerGcg ( SCIP *  scip,
SCIP *  origscip,
const char *  name,
const char *  desc,
int  priority,
unsigned int  delay,
SCIP_PRICERDATA *  pricerdata 
)

default constructor

Parameters
scipSCIP data structure
origscipSCIP data structure of original problem
namename of variable pricer
descdescription of variable pricer
prioritypriority of the variable pricer
delayshould the pricer be delayed until no other pricers or already existing
pricerdatapricerdata data structure

Definition at line 3399 of file pricer_gcg.cpp.

References origprob, and pricerdata.

◆ ~ObjPricerGcg()

virtual ObjPricerGcg::~ObjPricerGcg ( )
inlinevirtual

destructor

Definition at line 77 of file objpricer_gcg.h.

Member Function Documentation

◆ SCIP_DECL_PRICERFREE()

virtual ObjPricerGcg::SCIP_DECL_PRICERFREE ( scip_free  )
virtual

destructor of variable pricer to free user data (called when SCIP is exiting)

◆ SCIP_DECL_PRICERINIT()

virtual ObjPricerGcg::SCIP_DECL_PRICERINIT ( scip_init  )
virtual

initialization method of variable pricer (called after problem was transformed)

◆ SCIP_DECL_PRICEREXIT()

virtual ObjPricerGcg::SCIP_DECL_PRICEREXIT ( scip_exit  )
virtual

deinitialization method of variable pricer (called before transformed problem is freed)

◆ SCIP_DECL_PRICERINITSOL()

virtual ObjPricerGcg::SCIP_DECL_PRICERINITSOL ( scip_initsol  )
virtual

solving process initialization method of variable pricer (called when branch and bound process is about to begin)

◆ SCIP_DECL_PRICEREXITSOL()

virtual ObjPricerGcg::SCIP_DECL_PRICEREXITSOL ( scip_exitsol  )
virtual

solving process deinitialization method of variable pricer (called before branch and bound process data is freed)

◆ SCIP_DECL_PRICERREDCOST()

virtual ObjPricerGcg::SCIP_DECL_PRICERREDCOST ( scip_redcost  )
virtual

reduced cost pricing method of variable pricer for feasible LPs

◆ SCIP_DECL_PRICERFARKAS()

virtual ObjPricerGcg::SCIP_DECL_PRICERFARKAS ( scip_farkas  )
virtual

farkas pricing method of variable pricer for infeasible LPs

◆ getPricerdata()

◆ getConvconsDualsol()

SCIP_Real ObjPricerGcg::getConvconsDualsol ( PricingType pricetype,
int  probnr 
)

for a pricing problem, get the dual solution value or Farkas value of the convexity constraint

Parameters
pricetypeFarkas or Reduced cost pricing
probnrindex of corresponding pricing problem

Definition at line 690 of file pricer_gcg.cpp.

References PricingType::consGetDual(), GCGgetConvCons(), and GCGisPricingprobRelevant().

◆ setPricingObjs()

◆ updateRedcostColumnPool()

void ObjPricerGcg::updateRedcostColumnPool ( PricingType pricetype)

update reduced cost of columns in column pool

Parameters
pricetypetype of pricing: reduced cost or Farkas

◆ priceColumnPoolOld()

SCIP_RETCODE ObjPricerGcg::priceColumnPoolOld ( PricingType pricetype,
int *  pnfoundvars 
)

method to price new columns from Column Pool

Parameters
pricetypetype of pricing: reduced cost or Farkas
pnfoundvarspointer to store number of priced variables

◆ priceNewVariables()

SCIP_RETCODE ObjPricerGcg::priceNewVariables ( PricingType pricetype,
SCIP_RESULT *  result,
double *  lowerbound 
)

performs the pricing routine, gets the type of pricing that should be done: farkas or redcost pricing

Parameters
pricetypetype of the pricing
resultresult pointer
lowerboundlower bound of pricingproblems

Definition at line 3293 of file pricer_gcg.cpp.

References GCG_PRICETYPE_FARKAS, GCG_PRICETYPE_REDCOST, GCGisRootNode(), GCGpricerPrintInfo, GCGsolverUpdate(), PricingType::getCalls(), PricingType::getType(), and PricingType::incCalls().

◆ createNewMasterVar()

SCIP_RETCODE ObjPricerGcg::createNewMasterVar ( SCIP *  scip,
PricingType pricetype,
SCIP_SOL *  sol,
SCIP_VAR **  solvars,
double *  solvals,
int  nsolvars,
unsigned int  solisray,
int  prob,
unsigned int  force,
unsigned int *  added,
SCIP_VAR **  addedvar 
)

creates a new master variable corresponding to the given solution and problem

Parameters
scipSCIP data structure
pricetypetype of the pricing
solsolution to compute reduced cost for
solvarsarray of variables with non-zero value in the solution of the pricing problem
solvalsarray of values in the solution of the pricing problem for variables in array solvars
nsolvarsnumber of variables in array solvars
solisrayis the solution a ray?
probnumber of the pricing problem the solution belongs to
forceshould the given variable be added also if it has non-negative reduced cost?
addedpointer to store whether the variable was successfully added
addedvarpointer to store the created variable

Definition at line 2051 of file pricer_gcg.cpp.

References GCG_PRICETYPE_REDCOST, GCGcreateMasterVar(), GCGgetConvCons(), GCGoriginalVarIsLinking(), GCGpricingVarGetOrigvars(), GCGsetRootRedcostCall(), GCGupdateVarStatistics(), GCGvarIsPricing(), and PricingType::getType().

Referenced by GCGmasterTransOrigSolToMasterVars().

◆ createNewMasterVarFromGcgCol()

SCIP_RETCODE ObjPricerGcg::createNewMasterVarFromGcgCol ( SCIP *  scip,
PricingType pricetype,
GCG_COL gcgcol,
SCIP_Bool  force,
SCIP_Bool *  added,
SCIP_VAR **  addedvar,
SCIP_Real  score 
)

creates a new master variable corresponding to the given gcg column

Parameters
scipSCIP data structure
pricetypetype of pricing
gcgcolGCG column data structure
forceshould the given variable be added also if it has non-negative reduced cost?
addedpointer to store whether the variable was successfully added
addedvarpointer to store the created variable
scorescore of column (or -1.0 if not specified)

Definition at line 2205 of file pricer_gcg.cpp.

References GCG_PRICETYPE_REDCOST, GCGcolGetNVars(), GCGcolGetProbNr(), GCGcolGetRedcost(), GCGcolGetVals(), GCGcolGetVars(), GCGcolIsRay(), GCGcreateMasterVar(), GCGgetConvCons(), GCGmasterGetOrigprob(), GCGoriginalVarIsLinking(), GCGpricingVarGetOrigvars(), GCGsetRootRedcostCall(), GCGupdateVarStatistics(), GCGvarIsPricing(), and PricingType::getType().

Referenced by GCGcreateNewMasterVarFromGcgCol().

◆ computeDualDiff()

SCIP_RETCODE ObjPricerGcg::computeDualDiff ( SCIP_Real **  dualvals1,
SCIP_Real *  dualconv1,
SCIP_Real **  dualvals2,
SCIP_Real *  dualconv2,
SCIP_Real *  dualdiff 
)
Parameters
dualvals1array of dual values for each pricing problem
dualconv1array of dual solutions for the convexity constraints
dualvals2array of dual values for each pricing problem
dualconv2array of dual solutions for the convexity constraints
dualdiffpointer to store difference of duals solutions

Definition at line 2641 of file pricer_gcg.cpp.

Referenced by GCGpricerPrintStatistics().

◆ pricingLoop()

SCIP_RETCODE ObjPricerGcg::pricingLoop ( PricingType pricetype,
SCIP_RESULT *  result,
int *  pnfoundvars,
SCIP_Real *  lowerbound,
SCIP_Bool *  bestredcostvalid 
)

◆ getFarkasPricing()

const FarkasPricing* ObjPricerGcg::getFarkasPricing ( ) const
inline

Definition at line 172 of file objpricer_gcg.h.

Referenced by GCGpricerPrintStatistics().

◆ getFarkasPricingNonConst()

FarkasPricing* ObjPricerGcg::getFarkasPricingNonConst ( )
inline

Definition at line 177 of file objpricer_gcg.h.

Referenced by GCGcomputeRedCostGcgCol(), and GCGcreateNewMasterVarFromGcgCol().

◆ getReducedCostPricing()

const ReducedCostPricing* ObjPricerGcg::getReducedCostPricing ( ) const
inline

Definition at line 182 of file objpricer_gcg.h.

Referenced by GCGpricerPrintStatistics().

◆ getReducedCostPricingNonConst()

ReducedCostPricing* ObjPricerGcg::getReducedCostPricingNonConst ( )
inline

◆ getOrigprob()

SCIP* ObjPricerGcg::getOrigprob ( )
inline

Definition at line 192 of file objpricer_gcg.h.

References origprob.

Referenced by GCGmasterGetOrigprob(), and GCGmasterPrintSimplexIters().

◆ getMaxColsRound()

int ObjPricerGcg::getMaxColsRound ( ) const

get the number of columns to be added to the master LP in the current pricing round

Definition at line 367 of file pricer_gcg.cpp.

Referenced by GCGpricerGetMaxColsRound().

◆ getMaxColsProb()

int ObjPricerGcg::getMaxColsProb ( ) const

get the number of columns per pricing problem to be added to the master LP in the current pricing round

Definition at line 375 of file pricer_gcg.cpp.

Referenced by GCGpricerGetMaxColsProb().

◆ addArtificialVars()

SCIP_RETCODE ObjPricerGcg::addArtificialVars ( )

◆ addTrivialsols()

SCIP_RETCODE ObjPricerGcg::addTrivialsols ( )

add trivial sols

◆ createPricingTypes()

SCIP_RETCODE ObjPricerGcg::createPricingTypes ( )

create the pointers for the pricing types

Definition at line 4052 of file pricer_gcg.cpp.

References ReducedCostPricing::addParameters(), and FarkasPricing::addParameters().

Referenced by SCIPincludePricerGcg().

◆ createPricingcontroller()

SCIP_RETCODE ObjPricerGcg::createPricingcontroller ( )

create the pricing controller

Definition at line 4066 of file pricer_gcg.cpp.

References gcg::Pricingcontroller::addParameters().

Referenced by SCIPincludePricerGcg().

◆ createStabilization()

void ObjPricerGcg::createStabilization ( )

create the pointers for the stabilization

Definition at line 4075 of file pricer_gcg.cpp.

References GCGgetNPricingprobs(), GCGgetNRelPricingprobs(), origprob, and pricerdata.

◆ createColpool()

SCIP_RETCODE ObjPricerGcg::createColpool ( )

create the pointers for the colpool

Definition at line 4086 of file pricer_gcg.cpp.

References colpool, GCGcolpoolCreate(), and pricerdata.

◆ createPricestore()

SCIP_RETCODE ObjPricerGcg::createPricestore ( )

create the pointers for the pricestore

Definition at line 4097 of file pricer_gcg.cpp.

References GCGpricestoreCreate(), pricerdata, and pricestore.

◆ updateRedcosts()

void ObjPricerGcg::updateRedcosts ( PricingType pricetype,
GCG_COL **  cols,
int  ncols,
int *  nimpcols 
)

for given columns, (re-)compute and update their reduced costs

Parameters
pricetypetype of pricing
colscolumns to compute reduced costs for
ncolsnumber of columns
nimpcolspointer to store number of improving columns

◆ addColToPricestore()

SCIP_RETCODE ObjPricerGcg::addColToPricestore ( GCG_COL col)

add a new column to the pricing storage

Parameters
colpriced col

Definition at line 1647 of file pricer_gcg.cpp.

References GCGcolUpdateRedcost(), and GCGpricestoreAddCol().

Referenced by GCGpricerAddCol().

◆ getBestCols()

void ObjPricerGcg::getBestCols ( GCG_COL **  pricingprobcols)

for each pricing problem, get the best found column from the pricing storage

Parameters
pricingprobcolsarray to be filled with best column per pricing problem

Definition at line 1671 of file pricer_gcg.cpp.

References GCGcolGetProbNr(), GCGcolGetRedcost(), GCGpricestoreGetCols(), and GCGpricestoreGetNCols().

◆ getDualconvsum()

SCIP_Real ObjPricerGcg::getDualconvsum ( GCG_COL **  bestcols)

get the sum over the dual values of convexity constraints

Parameters
bestcolsbest columns found per pricing problem

Definition at line 1699 of file pricer_gcg.cpp.

References GCGcolIsRay(), GCGgetConvCons(), GCGgetNIdenticalBlocks(), and GCGisPricingprobRelevant().

◆ getStabilizedDualObjectiveValue()

◆ computeRedCostGcgCol()

SCIP_Real ObjPricerGcg::computeRedCostGcgCol ( PricingType pricetype,
GCG_Col gcgcol,
SCIP_Real *  objvalptr 
) const
Parameters
pricetypetype of pricing
gcgcolgcg column to compute reduced cost for
objvalptrpointer to store the computed objective value

Definition at line 1566 of file pricer_gcg.cpp.

References GCGcolGetNVars(), GCGcolGetProbNr(), GCGcolGetVals(), GCGcolGetVars(), GCGcolIsRay(), GCGcolUpdateRedcost(), and GCGpricingprobGetGenericBranchData().

Referenced by GCGcomputeRedCostGcgCol().

◆ computeColMastercoefs()

◆ computeColMastercuts()

SCIP_RETCODE ObjPricerGcg::computeColMastercuts ( GCG_COL gcgcol)

Field Documentation

◆ origprob

SCIP* ObjPricerGcg::origprob

the original program

Definition at line 60 of file objpricer_gcg.h.

Referenced by addArtificialVars(), createStabilization(), getOrigprob(), and ObjPricerGcg().

◆ pricerdata

SCIP_PRICERDATA* ObjPricerGcg::pricerdata

◆ colpool

GCG_COLPOOL* ObjPricerGcg::colpool

column pool

Definition at line 62 of file objpricer_gcg.h.

Referenced by createColpool().

◆ pricestore

GCG_PRICESTORE* ObjPricerGcg::pricestore

price storage

Definition at line 63 of file objpricer_gcg.h.

Referenced by createPricestore().

◆ threads

int ObjPricerGcg::threads
static

Definition at line 64 of file objpricer_gcg.h.

Referenced by SCIPincludePricerGcg().