pricer_gcg.h File Reference

Detailed Description

GCG variable pricer.

Author
Gerald Gamrath
Martin Bergner

Definition in file pricer_gcg.h.

#include "scip/scip.h"
#include "type_solver.h"

Go to the source code of this file.

Typedefs

typedef enum GCG_Pricetype GCG_PRICETYPE
 

Enumerations

enum  GCG_Pricetype { GCG_PRICETYPE_UNKNOWN = -1, GCG_PRICETYPE_INIT = 0, GCG_PRICETYPE_FARKAS = 1, GCG_PRICETYPE_REDCOST = 2 }
 

Functions

SCIP_RETCODE SCIPincludePricerGcg (SCIP *scip, SCIP *origprob)
 
SCIP * GCGmasterGetOrigprob (SCIP *scip)
 
SCIP_VAR ** GCGmasterGetPricedvars (SCIP *scip)
 
int GCGmasterGetNPricedvars (SCIP *scip)
 
SCIP_RETCODE GCGmasterAddMasterconsToHashmap (SCIP *scip, SCIP_CONS *cons, int pos)
 
SCIP_RETCODE GCGmasterSetRootLPSol (SCIP *scip, SCIP_SOL **sol)
 
SCIP_RETCODE GCGpricerIncludeSolver (SCIP *scip, const char *name, const char *desc, int priority, SCIP_Bool enabled, GCG_DECL_SOLVERUPDATE((*solverupdate)), GCG_DECL_SOLVERSOLVE((*solversolve)), GCG_DECL_SOLVERSOLVEHEUR((*solveheur)), GCG_DECL_SOLVERFREE((*solverfree)), GCG_DECL_SOLVERINIT((*solverinit)), GCG_DECL_SOLVEREXIT((*solverexit)), GCG_DECL_SOLVERINITSOL((*solverinitsol)), GCG_DECL_SOLVEREXITSOL((*solverexitsol)), GCG_SOLVERDATA *solverdata)
 
GCG_SOLVER ** GCGpricerGetSolvers (SCIP *scip)
 
int GCGpricerGetNSolvers (SCIP *scip)
 
void GCGpricerPrintListOfSolvers (SCIP *scip)
 
void GCGpricerPrintPricingStatistics (SCIP *scip, FILE *file)
 
void GCGpricerPrintStatistics (SCIP *scip, FILE *file)
 
SCIP_RETCODE GCGpricerExistRays (SCIP *scip, SCIP_Bool *exist)
 
int GCGpricerGetNPointsProb (SCIP *scip, int probnr)
 
int GCGpricerGetNRaysProb (SCIP *scip, int probnr)
 
int GCGpricerGetMaxColsRound (SCIP *scip)
 
int GCGpricerGetMaxColsProb (SCIP *scip)
 
SCIP_RETCODE GCGpricerAddCol (SCIP *scip, GCG_COL *col)
 
SCIP_RETCODE GCGmasterTransOrigSolToMasterVars (SCIP *scip, SCIP_SOL *origsol, SCIP_Bool *stored)
 
SCIP_RETCODE GCGmasterCreateInitialMastervars (SCIP *scip)
 
SCIP_Real GCGmasterGetDegeneracy (SCIP *scip)
 
SCIP_Bool GCGmasterIsCurrentSolValid (SCIP *scip)
 
SCIP_Bool GCGmasterIsBestsolValid (SCIP *scip)
 
SCIP_Bool GCGmasterIsSolValid (SCIP *scip, SCIP_SOL *mastersol)
 
SCIP_Longint GCGmasterGetPricingSimplexIters (SCIP *scip)
 
SCIP_RETCODE GCGmasterPrintSimplexIters (SCIP *scip, FILE *file)
 
SCIP_RETCODE GCGsetPricingObjs (SCIP *scip, SCIP_Real *dualsolconv)
 
SCIP_RETCODE GCGcreateNewMasterVarFromGcgCol (SCIP *scip, SCIP_Bool infarkas, GCG_COL *gcgcol, SCIP_Bool force, SCIP_Bool *added, SCIP_VAR **addedvar, SCIP_Real score)
 
SCIP_Real GCGcomputeRedCostGcgCol (SCIP *scip, SCIP_Bool infarkas, GCG_COL *gcgcol, SCIP_Real *objvalptr)
 
SCIP_RETCODE GCGcomputeColMastercoefs (SCIP *scip, GCG_COL *gcgcol)
 

Typedef Documentation

Definition at line 55 of file pricer_gcg.h.

Enumeration Type Documentation

Enumerator
GCG_PRICETYPE_UNKNOWN 

unknown pricing type

GCG_PRICETYPE_INIT 

initial pricing

GCG_PRICETYPE_FARKAS 

farkas pricing

GCG_PRICETYPE_REDCOST 

redcost pricing

Definition at line 48 of file pricer_gcg.h.

Function Documentation

SCIP_RETCODE GCGcomputeColMastercoefs ( SCIP *  scip,
GCG_COL gcgcol 
)

compute master and cut coefficients of column

Parameters
scipSCIP data structure
gcgcolGCG column data structure

Definition at line 3230 of file pricer_gcg.cpp.

References ObjPricerGcg::computeColMastercoefs(), ObjPricerGcg::computeColMastercuts(), GCGcomputeRedCostGcgCol(), and PRICER_NAME.

Referenced by GCGcolpoolUpdateRedcost(), and GCGcreateNewMasterVarFromGcgCol().

SCIP_Real GCGcomputeRedCostGcgCol ( SCIP *  scip,
SCIP_Bool  infarkas,
GCG_COL gcgcol,
SCIP_Real *  objvalptr 
)

computes the reduced cost of a column

Parameters
scipSCIP data structure
infarkasin Farkas pricing?
gcgcolgcg column to compute reduced cost for
objvalptrpointer to store the computed objective value

Definition at line 3250 of file pricer_gcg.cpp.

References ObjPricerGcg::computeRedCostGcgCol(), ObjPricerGcg::getFarkasPricingNonConst(), ObjPricerGcg::getReducedCostPricingNonConst(), ObjPricerGcg::priceNewVariables(), and PRICER_NAME.

Referenced by GCGcolpoolUpdateRedcost(), and GCGcomputeColMastercoefs().

SCIP_RETCODE GCGcreateNewMasterVarFromGcgCol ( SCIP *  scip,
SCIP_Bool  infarkas,
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
infarkasin Farkas 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 3199 of file pricer_gcg.cpp.

References ObjPricerGcg::createNewMasterVarFromGcgCol(), GCGcomputeColMastercoefs(), ObjPricerGcg::getFarkasPricingNonConst(), ObjPricerGcg::getReducedCostPricingNonConst(), and PRICER_NAME.

Referenced by GCGsetPricingObjs(), and pricestoreApplyCol().

SCIP_RETCODE GCGmasterAddMasterconsToHashmap ( SCIP *  scip,
SCIP_CONS *  cons,
int  pos 
)

adds the given constraint and the given position to the hashmap of the pricer

Parameters
scipSCIP data structure
consthe constraint that should be added
posthe position of the constraint in the relaxator's masterconss array

Definition at line 4239 of file pricer_gcg.cpp.

References GCGmasterSetRootLPSol(), GCGpricerIncludeSolver(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGmasterGetNPricedvars(), and GCGrelaxTransOrigToMasterCons().

SCIP_Real GCGmasterGetDegeneracy ( SCIP *  scip)

get root node degeneracy

Parameters
scipSCIP data structure

Definition at line 4992 of file pricer_gcg.cpp.

References GCGisRootNode(), GCGmasterIsCurrentSolValid(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGgetDegeneracy(), and GCGmasterCreateInitialMastervars().

int GCGmasterGetNPricedvars ( SCIP *  scip)

returns the number of variables that were priced in during the solving process

Parameters
scipSCIP data structure

Definition at line 4218 of file pricer_gcg.cpp.

References GCGmasterAddMasterconsToHashmap(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by applyGlobalBndchgsToPricedMastervars(), applyLocalBndchgsToPricedMastervars(), GCGmasterGetPricedvars(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_CONSDEACTIVE(), and SCIP_DECL_CONSPROP().

SCIP* GCGmasterGetOrigprob ( SCIP *  scip)

returns the pointer to the scip instance representing the original problem

Parameters
scipSCIP data structure

Definition at line 4182 of file pricer_gcg.cpp.

References GCGmasterGetPricedvars(), ObjPricerGcg::getOrigprob(), and PRICER_NAME.

Referenced by ReducedCostPricing::addParameters(), FarkasPricing::addParameters(), applyGlobalBndchgsToPricedMastervars(), applyGlobalBndchgsToPricingprobs(), applyLocalBndchgsToPricedMastervars(), applyLocalBndchgsToPricingprobs(), gcg::Pricingcontroller::canPricingloopBeAborted(), gcg::Pricingcontroller::collectResults(), gcg::Stabilization::consGetDual(), gcg::Stabilization::convGetDual(), ObjPricerGcg::createNewMasterVarFromGcgCol(), GCG_DECL_BRANCHACTIVEMASTER(), GCG_DECL_BRANCHDEACTIVEMASTER(), GCG_DECL_BRANCHPROPMASTER(), GCG_DECL_SOLVEREXITSOL(), GCG_DECL_SOLVERINITSOL(), GCGbranchGenericInitbranch(), GCGcolComputeDualObjPara(), GCGcreateConsMasterbranch(), GCGgetOriginalprob(), GCGincludeSolverCliquer(), GCGincludeSolverCplex(), GCGincludeSolverMip(), GCGpricerGetNPointsProb(), GCGpricerGetNRaysProb(), GCGpricestoreApplyCols(), GCGsepaBasisAddPricingCut(), GCGsolverCreate(), getBestMastervar(), initializeConsdata(), initializeStartsol(), gcg::Stabilization::linkingconsGetDual(), ObjPricerGcg::pricingLoop(), resetPricingVarBound(), SCIP_DECL_BRANCHEXECEXT(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), SCIP_DECL_BRANCHINIT(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSDEACTIVE(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_CONSINITSOL(), SCIP_DECL_CONSPROP(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINIT(), SCIP_DECL_NODESELSELECT(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXIT(), SCIP_DECL_SEPAEXITSOL(), SCIP_DECL_SEPAINIT(), SCIPgetRelpsprobBranchVar(), SCIPincludeBranchruleOrig(), SCIPincludeBranchruleRelpsprob(), SCIPincludeConshdlrMasterbranch(), SCIPincludeEventHdlrSolvingstats(), SCIPincludePricerGcg(), SCIPincludeSepaBasis(), SCIPincludeSepaMaster(), SCIPsepaBasisAddPPObjConss(), tightenPricingVarBound(), undoLocalBndchgsToPricingprobs(), gcg::Stabilization::updateAlpha(), gcg::Stabilization::updateStabilityCenter(), gcg::Pricingcontroller::~Pricingcontroller(), and gcg::Stabilization::~Stabilization().

SCIP_VAR** GCGmasterGetPricedvars ( SCIP *  scip)

returns the array of variables that were priced in during the solving process

Parameters
scipSCIP data structure

Definition at line 4198 of file pricer_gcg.cpp.

References GCGmasterGetNPricedvars(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by applyGlobalBndchgsToPricedMastervars(), applyLocalBndchgsToPricedMastervars(), and GCGmasterGetOrigprob().

SCIP_Longint GCGmasterGetPricingSimplexIters ( SCIP *  scip)

get number of iterations in pricing problems

Parameters
scipSCIP data structure

Definition at line 5136 of file pricer_gcg.cpp.

References GCGmasterPrintSimplexIters(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGmasterIsSolValid(), and SCIP_DECL_DISPOUTPUT().

SCIP_Bool GCGmasterIsCurrentSolValid ( SCIP *  scip)

return if artifical variables are used in current solution

check if current sol is valid

Parameters
scipSCIP data structure

Definition at line 5017 of file pricer_gcg.cpp.

References DEC_DECMODE_DANTZIGWOLFE, GCGgetMasterDecompMode(), GCGmasterIsBestsolValid(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGmasterGetDegeneracy(), relaxExecGcgDantzigWolfe(), SCIP_DECL_PRICERREDCOST(), solveMasterProblem(), and solveMasterProblemAndEvaluate().

SCIP_Bool GCGmasterIsSolValid ( SCIP *  scip,
SCIP_SOL *  mastersol 
)
Parameters
scipSCIP data structure
mastersolsolution of the master problem, or NULL for current LP solution

Definition at line 5100 of file pricer_gcg.cpp.

References DEC_DECMODE_DANTZIGWOLFE, GCGgetMasterDecompMode(), GCGmasterGetPricingSimplexIters(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGmasterIsBestsolValid(), GCGrelaxUpdateCurrentSol(), and GCGtransformMastersolToOrigsol().

SCIP_RETCODE GCGmasterPrintSimplexIters ( SCIP *  scip,
FILE *  file 
)

print simplex iteration statistics

Parameters
scipSCIP data structure
fileoutput file

Definition at line 5156 of file pricer_gcg.cpp.

References ObjPricerGcg::getOrigprob(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGmasterGetPricingSimplexIters(), and GCGprintStatistics().

SCIP_RETCODE GCGmasterSetRootLPSol ( SCIP *  scip,
SCIP_SOL **  sol 
)

sets the optimal LP solution in the pricerdata

Parameters
scipSCIP data structure
solpointer to optimal solution to root LP

Referenced by GCGmasterAddMasterconsToHashmap().

SCIP_RETCODE GCGmasterTransOrigSolToMasterVars ( SCIP *  scip,
SCIP_SOL *  origsol,
SCIP_Bool *  stored 
)

transfers a primal solution of the original problem into the master variable space, i.e. creates one master variable for each block and adds the solution to the master problem

Parameters
scipSCIP data structure
origsolthe solution that should be transferred
storedpointer to store if transferred solution is feasible (or NULL)

Definition at line 4721 of file pricer_gcg.cpp.

References ObjPricerGcg::createNewMasterVar(), DEC_DECMODE_DANTZIGWOLFE, GCGgetBlockRepresentative(), GCGgetDecompositionMode(), GCGgetOriginalprob(), GCGlinkingVarGetBlocks(), GCGlinkingVarGetNBlocks(), GCGlinkingVarGetPricingVars(), GCGmasterCreateInitialMastervars(), GCGoriginalVarGetMastervars(), GCGoriginalVarGetNMastervars(), GCGoriginalVarGetPricingVar(), GCGoriginalVarIsLinking(), GCGvarGetBlock(), GCGvarIsOriginal(), ObjPricerGcg::getPricerdata(), ObjPricerGcg::origprob, PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGpricerAddCol(), SCIP_DECL_EVENTEXEC(), and SCIP_DECL_PRICERFARKAS().

SCIP_RETCODE GCGpricerAddCol ( SCIP *  scip,
GCG_COL col 
)

add a new column to the pricing storage

Parameters
scipSCIP data structure
colpriced col

Definition at line 4703 of file pricer_gcg.cpp.

References ObjPricerGcg::addColToPricestore(), GCGmasterTransOrigSolToMasterVars(), and PRICER_NAME.

Referenced by GCGpricerGetMaxColsProb(), getColumnsFromPricingprob(), solveCliquer(), solveCplex(), solveKnapsack(), and solveProblem().

SCIP_RETCODE GCGpricerExistRays ( SCIP *  scip,
SCIP_Bool *  exist 
)

method to get existence of rays

Parameters
scipmaster SCIP data structure
existpointer to store if there exists any ray

Definition at line 4589 of file pricer_gcg.cpp.

References GCGpricerGetNPointsProb(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGbranchGenericInitbranch(), and GCGpricerPrintStatistics().

int GCGpricerGetMaxColsProb ( SCIP *  scip)

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

Parameters
scipmaster SCIP data structure

Definition at line 4687 of file pricer_gcg.cpp.

References GCGpricerAddCol(), ObjPricerGcg::getMaxColsProb(), and PRICER_NAME.

Referenced by GCGpricerGetMaxColsRound(), and GCGpricestoreApplyCols().

int GCGpricerGetMaxColsRound ( SCIP *  scip)

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

Parameters
scipmaster SCIP data structure

Definition at line 4671 of file pricer_gcg.cpp.

References GCGpricerGetMaxColsProb(), ObjPricerGcg::getMaxColsRound(), and PRICER_NAME.

Referenced by GCGpricerGetNRaysProb(), and GCGpricestoreApplyCols().

int GCGpricerGetNPointsProb ( SCIP *  scip,
int  probnr 
)

get the number of extreme points that a pricing problem has generated so far

Parameters
scipmaster SCIP data structure
probnrindex of pricing problem

Definition at line 4623 of file pricer_gcg.cpp.

References GCGisPricingprobRelevant(), GCGmasterGetOrigprob(), GCGpricerGetNRaysProb(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGpricerExistRays().

int GCGpricerGetNRaysProb ( SCIP *  scip,
int  probnr 
)

get the number of extreme rays that a pricing problem has generated so far

Parameters
scipmaster SCIP data structure
probnrindex of pricing problem

Definition at line 4647 of file pricer_gcg.cpp.

References GCGisPricingprobRelevant(), GCGmasterGetOrigprob(), GCGpricerGetMaxColsRound(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGpricerGetNPointsProb().

int GCGpricerGetNSolvers ( SCIP *  scip)

returns the number of available pricing solvers

Parameters
scipSCIP data structure

Definition at line 4386 of file pricer_gcg.cpp.

References GCGpricerPrintListOfSolvers(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGpricerGetSolvers().

GCG_SOLVER** GCGpricerGetSolvers ( SCIP *  scip)

returns the available pricing solvers

Parameters
scipSCIP data structure

Definition at line 4366 of file pricer_gcg.cpp.

References GCGpricerGetNSolvers(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGpricerIncludeSolver().

SCIP_RETCODE GCGpricerIncludeSolver ( SCIP *  scip,
const char *  name,
const char *  desc,
int  priority,
SCIP_Bool  enabled,
GCG_DECL_SOLVERUPDATE((*solverupdate))  ,
GCG_DECL_SOLVERSOLVE((*solversolve))  ,
GCG_DECL_SOLVERSOLVEHEUR((*solveheur))  ,
GCG_DECL_SOLVERFREE((*solverfree))  ,
GCG_DECL_SOLVERINIT((*solverinit))  ,
GCG_DECL_SOLVEREXIT((*solverexit))  ,
GCG_DECL_SOLVERINITSOL((*solverinitsol))  ,
GCG_DECL_SOLVEREXITSOL((*solverexitsol))  ,
GCG_SOLVERDATA solverdata 
)

includes a solver into the pricer data

Parameters
scipSCIP data structure
namename of solver
descdescription of solver
prioritypriority of solver
enabledflag to indicate whether the solver is enabled
solverdatapricing solver data
void GCGpricerPrintListOfSolvers ( SCIP *  scip)

writes out a list of all pricing problem solvers

Parameters
scipSCIP data structure

Definition at line 4406 of file pricer_gcg.cpp.

References GCGpricerPrintPricingStatistics(), GCGsolverGetDesc(), GCGsolverGetName(), GCGsolverGetPriority(), GCGsolverIsEnabled(), ObjPricerGcg::getPricerdata(), PRICER_NAME, and ObjPricerGcg::pricerdata.

Referenced by GCGpricerGetNSolvers(), and SCIP_DECL_DIALOGEXEC().

void GCGpricerPrintPricingStatistics ( SCIP *  scip,
FILE *  file 
)
void GCGpricerPrintStatistics ( SCIP *  scip,
FILE *  file 
)
SCIP_RETCODE GCGsetPricingObjs ( SCIP *  scip,
SCIP_Real *  dualsolconv 
)

set pricing objectives

Parameters
scipSCIP data structure
dualsolconvarray of dual solutions corresponding to convexity constraints

Definition at line 3152 of file pricer_gcg.cpp.

References GCGcreateNewMasterVarFromGcgCol(), GCGsolverUpdate(), ObjPricerGcg::getReducedCostPricingNonConst(), PRICER_NAME, ObjPricerGcg::pricerdata, and ObjPricerGcg::setPricingObjs().

Referenced by ObjPricerGcg::pricingLoop(), and SCIP_DECL_SEPAEXECLP().