Scippy

GCG

Branch-and-Price & Column Generation for Everyone

pricer_gcg.cpp File Reference

Detailed Description

pricer for generic column generation

Author
Gerald Gamrath
Martin Bergner
Alexander Gross
Christian Puchert
Michael Bastubbe
Jonas Witt

Definition in file pricer_gcg.cpp.

#include <cassert>
#include <cstring>
#include "scip/scip.h"
#include "gcg.h"
#include "scip/cons_linear.h"
#include "scip/cons_knapsack.h"
#include "pricer_gcg.h"
#include "objpricer_gcg.h"
#include "sepa_master.h"
#include "sepa_basis.h"
#include "relax_gcg.h"
#include "scip_misc.h"
#include "pub_gcgvar.h"
#include "pub_gcgcol.h"
#include "pub_pricingjob.h"
#include "pub_pricingprob.h"
#include "pub_solver.h"
#include "solver.h"
#include "cons_masterbranch.h"
#include "objscip/objscip.h"
#include "class_pricingtype.h"
#include "class_pricingcontroller.h"
#include "class_stabilization.h"
#include "branch_generic.h"
#include "event_display.h"
#include "pub_colpool.h"

Go to the source code of this file.

Data Structures

struct  SCIP_PricerData
 

Macros

#define PRICER_NAME   "gcg"
 
#define PRICER_DESC   "pricer for gcg"
 
#define PRICER_PRIORITY   5000000
 
#define PRICER_DELAY   TRUE /* only call pricer if all problem variables have non-negative reduced costs */
 
#define DEFAULT_ABORTPRICINGINT   TRUE
 
#define DEFAULT_ABORTPRICINGGAP   0.00
 
#define DEFAULT_DISPINFOS   FALSE
 
#define DEFAULT_DISABLECUTOFF   2
 
#define DEFAULT_THREADS   0
 
#define DEFAULT_STABILIZATION   TRUE
 
#define DEFAULT_STABILIZATIONTREE   FALSE
 
#define DEFAULT_HYBRIDASCENT   FALSE
 
#define DEFAULT_HYBRIDASCENT_NOAGG   FALSE
 
#define DEFAULT_USECOLPOOL   TRUE
 
#define DEFAULT_COLPOOL_AGELIMIT   100
 
#define DEFAULT_PRICE_ORTHOFAC   0.0
 
#define DEFAULT_PRICE_OBJPARALFAC   0.0
 
#define DEFAULT_PRICE_REDCOSTFAC   1.0
 
#define DEFAULT_PRICE_MINCOLORTH   0.0
 
#define DEFAULT_PRICE_EFFICIACYCHOICE   0
 
#define DEFAULT_USEARTIFICIALVARS   FALSE
 
#define DEFAULT_USEMAXOBJ   TRUE
 
#define DEFAULT_ONLYRELIABLEBIGM   TRUE
 
#define DEFAULT_FACTORUNRELIABLE   1000
 
#define DEFAULT_BIGMARTIFICIAL   1000
 
#define EVENTHDLR_NAME   "probdatavardeleted"
 
#define EVENTHDLR_DESC   "event handler for variable deleted event"
 
#define GCGpricerPrintInfo(scip, pricerdata, ...)
 
#define PRICER_STAT_ARRAYLEN_TIME   1024
 
#define PRICER_STAT_BUCKETSIZE_TIME   10
 
#define PRICER_STAT_ARRAYLEN_VARS   1024
 
#define PRICER_STAT_BUCKETSIZE_VARS   1
 
#define eventFreeVardeleted   NULL
 
#define eventInitVardeleted   NULL
 
#define eventExitVardeleted   NULL
 
#define eventInitsolVardeleted   NULL
 
#define eventExitsolVardeleted   NULL
 
#define eventDeleteVardeleted   NULL
 

Functions

static SCIP_DECL_PARAMCHGD (paramChgdDisablecutoff)
 
static SCIP_DECL_EVENTEXEC (eventExecVardeleted)
 
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_RETCODE GCGcomputeColMastercoefs (SCIP *scip, GCG_COL *gcgcol)
 
SCIP_Real GCGcomputeRedCostGcgCol (SCIP *scip, SCIP_Bool infarkas, GCG_COL *gcgcol, SCIP_Real *objvalptr)
 
 SCIP_DECL_PRICERFREE (ObjPricerGcg::scip_free)
 
 SCIP_DECL_PRICERINIT (ObjPricerGcg::scip_init)
 
 SCIP_DECL_PRICEREXIT (ObjPricerGcg::scip_exit)
 
 SCIP_DECL_PRICERINITSOL (ObjPricerGcg::scip_initsol)
 
 SCIP_DECL_PRICEREXITSOL (ObjPricerGcg::scip_exitsol)
 
 SCIP_DECL_PRICERREDCOST (ObjPricerGcg::scip_redcost)
 
 SCIP_DECL_PRICERFARKAS (ObjPricerGcg::scip_farkas)
 
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 GCGpricerIncludeSolver (SCIP *scip, const char *name, const char *desc, int priority, SCIP_Bool heurenabled, SCIP_Bool exactenabled, GCG_DECL_SOLVERUPDATE((*solverupdate)), GCG_DECL_SOLVERSOLVE((*solversolve)), GCG_DECL_SOLVERSOLVEHEUR((*solversolveheur)), 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)
 

Macro Definition Documentation

◆ PRICER_NAME

#define PRICER_NAME   "gcg"

Definition at line 92 of file pricer_gcg.cpp.

◆ PRICER_DESC

#define PRICER_DESC   "pricer for gcg"

Definition at line 93 of file pricer_gcg.cpp.

◆ PRICER_PRIORITY

#define PRICER_PRIORITY   5000000

Definition at line 94 of file pricer_gcg.cpp.

◆ PRICER_DELAY

#define PRICER_DELAY   TRUE /* only call pricer if all problem variables have non-negative reduced costs */

Definition at line 95 of file pricer_gcg.cpp.

◆ DEFAULT_ABORTPRICINGINT

#define DEFAULT_ABORTPRICINGINT   TRUE

should the pricing be aborted when integral

Definition at line 97 of file pricer_gcg.cpp.

◆ DEFAULT_ABORTPRICINGGAP

#define DEFAULT_ABORTPRICINGGAP   0.00

gap between dual bound and RMP objective at which pricing is aborted

Definition at line 98 of file pricer_gcg.cpp.

◆ DEFAULT_DISPINFOS

#define DEFAULT_DISPINFOS   FALSE

should additional information be displayed

Definition at line 99 of file pricer_gcg.cpp.

◆ DEFAULT_DISABLECUTOFF

#define DEFAULT_DISABLECUTOFF   2

should the cutoffbound be applied in master LP solving? (0: on, 1:off, 2:auto)

Definition at line 100 of file pricer_gcg.cpp.

◆ DEFAULT_THREADS

#define DEFAULT_THREADS   0

number of threads (0 is OpenMP default)

Definition at line 101 of file pricer_gcg.cpp.

◆ DEFAULT_STABILIZATION

#define DEFAULT_STABILIZATION   TRUE

should stabilization be used

Definition at line 102 of file pricer_gcg.cpp.

◆ DEFAULT_STABILIZATIONTREE

#define DEFAULT_STABILIZATIONTREE   FALSE

should stabilization be used in nodes other than the root node

Definition at line 103 of file pricer_gcg.cpp.

◆ DEFAULT_HYBRIDASCENT

#define DEFAULT_HYBRIDASCENT   FALSE

should hybridization of smoothing with an ascent method be enabled

Definition at line 104 of file pricer_gcg.cpp.

◆ DEFAULT_HYBRIDASCENT_NOAGG

#define DEFAULT_HYBRIDASCENT_NOAGG   FALSE

should hybridization of smoothing with an ascent method be enabled if pricing problems cannot be aggregation

Definition at line 105 of file pricer_gcg.cpp.

◆ DEFAULT_USECOLPOOL

#define DEFAULT_USECOLPOOL   TRUE

should the colpool be checked for negative redcost cols before solving the pricing problems?

Definition at line 108 of file pricer_gcg.cpp.

◆ DEFAULT_COLPOOL_AGELIMIT

#define DEFAULT_COLPOOL_AGELIMIT   100

default age limit for columns in column pool

Definition at line 109 of file pricer_gcg.cpp.

◆ DEFAULT_PRICE_ORTHOFAC

#define DEFAULT_PRICE_ORTHOFAC   0.0

Definition at line 111 of file pricer_gcg.cpp.

◆ DEFAULT_PRICE_OBJPARALFAC

#define DEFAULT_PRICE_OBJPARALFAC   0.0

Definition at line 112 of file pricer_gcg.cpp.

◆ DEFAULT_PRICE_REDCOSTFAC

#define DEFAULT_PRICE_REDCOSTFAC   1.0

Definition at line 113 of file pricer_gcg.cpp.

◆ DEFAULT_PRICE_MINCOLORTH

#define DEFAULT_PRICE_MINCOLORTH   0.0

Definition at line 114 of file pricer_gcg.cpp.

◆ DEFAULT_PRICE_EFFICIACYCHOICE

#define DEFAULT_PRICE_EFFICIACYCHOICE   0

Definition at line 115 of file pricer_gcg.cpp.

◆ DEFAULT_USEARTIFICIALVARS

#define DEFAULT_USEARTIFICIALVARS   FALSE

add artificial vars to master (instead of using Farkas pricing)

Definition at line 117 of file pricer_gcg.cpp.

◆ DEFAULT_USEMAXOBJ

#define DEFAULT_USEMAXOBJ   TRUE

default value for using maxobj for big M objective of artificial variables

Definition at line 118 of file pricer_gcg.cpp.

◆ DEFAULT_ONLYRELIABLEBIGM

#define DEFAULT_ONLYRELIABLEBIGM   TRUE

default value for only using maxobj for big M objective of artificial variables if it is reliable

Definition at line 119 of file pricer_gcg.cpp.

◆ DEFAULT_FACTORUNRELIABLE

#define DEFAULT_FACTORUNRELIABLE   1000

default factor to use for objective of unbounded variables

Definition at line 120 of file pricer_gcg.cpp.

◆ DEFAULT_BIGMARTIFICIAL

#define DEFAULT_BIGMARTIFICIAL   1000

default value for big M objective of artificial variables (if maxobj is not used)

Definition at line 121 of file pricer_gcg.cpp.

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "probdatavardeleted"

Definition at line 123 of file pricer_gcg.cpp.

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC   "event handler for variable deleted event"

Definition at line 124 of file pricer_gcg.cpp.

◆ GCGpricerPrintInfo

#define GCGpricerPrintInfo (   scip,
  pricerdata,
  ... 
)
Value:
do { \
if( pricerdata->dispinfos ) { \
SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, __VA_ARGS__);\
} else {\
SCIPdebugMessage(__VA_ARGS__); \
}\
}while( FALSE )

small macro to simplify printing pricer information

Definition at line 127 of file pricer_gcg.cpp.

◆ PRICER_STAT_ARRAYLEN_TIME

#define PRICER_STAT_ARRAYLEN_TIME   1024

length of the array for Time histogram representation

Definition at line 135 of file pricer_gcg.cpp.

◆ PRICER_STAT_BUCKETSIZE_TIME

#define PRICER_STAT_BUCKETSIZE_TIME   10

size of the buckets for Time histogram representation

Definition at line 136 of file pricer_gcg.cpp.

◆ PRICER_STAT_ARRAYLEN_VARS

#define PRICER_STAT_ARRAYLEN_VARS   1024

length of the array for foundVars histogram representation

Definition at line 137 of file pricer_gcg.cpp.

◆ PRICER_STAT_BUCKETSIZE_VARS

#define PRICER_STAT_BUCKETSIZE_VARS   1

size of the buckets for foundVars histogram representation

Definition at line 138 of file pricer_gcg.cpp.

◆ eventFreeVardeleted

#define eventFreeVardeleted   NULL

destructor of event handler to free user data (called when SCIP is exiting)

Definition at line 273 of file pricer_gcg.cpp.

◆ eventInitVardeleted

#define eventInitVardeleted   NULL

initialization method of event handler (called after problem was transformed)

Definition at line 276 of file pricer_gcg.cpp.

◆ eventExitVardeleted

#define eventExitVardeleted   NULL

deinitialization method of event handler (called before transformed problem is freed)

Definition at line 279 of file pricer_gcg.cpp.

◆ eventInitsolVardeleted

#define eventInitsolVardeleted   NULL

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

Definition at line 282 of file pricer_gcg.cpp.

◆ eventExitsolVardeleted

#define eventExitsolVardeleted   NULL

solving process deinitialization method of event handler (called before branch and bound process data is freed)

Definition at line 285 of file pricer_gcg.cpp.

◆ eventDeleteVardeleted

#define eventDeleteVardeleted   NULL

frees specific event data

Definition at line 288 of file pricer_gcg.cpp.

Function Documentation

◆ SCIP_DECL_PARAMCHGD()

static SCIP_DECL_PARAMCHGD ( paramChgdDisablecutoff  )
static

information method for a parameter change of disablecutoff

Definition at line 254 of file pricer_gcg.cpp.

References GCGgetMasterprob().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecVardeleted  )
static

◆ SCIP_DECL_PRICERFREE()

SCIP_DECL_PRICERFREE ( ObjPricerGcg::scip_free  )

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

Definition at line 3416 of file pricer_gcg.cpp.

◆ SCIP_DECL_PRICERINIT()

SCIP_DECL_PRICERINIT ( ObjPricerGcg::scip_init  )

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

Definition at line 3443 of file pricer_gcg.cpp.

◆ SCIP_DECL_PRICEREXIT()

SCIP_DECL_PRICEREXIT ( ObjPricerGcg::scip_exit  )

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

Definition at line 3459 of file pricer_gcg.cpp.

◆ SCIP_DECL_PRICERINITSOL()

SCIP_DECL_PRICERINITSOL ( ObjPricerGcg::scip_initsol  )

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

Definition at line 3469 of file pricer_gcg.cpp.

References GCGgetMasterConss(), GCGgetNMasterConss(), GCGgetNPricingprobs(), GCGgetNVarLinkingconss(), GCGgetPricingprob(), GCGisPricingprobRelevant(), PRICER_STAT_ARRAYLEN_TIME, PRICER_STAT_ARRAYLEN_VARS, and SCIPactivateEventHdlrDisplay().

◆ SCIP_DECL_PRICEREXITSOL()

SCIP_DECL_PRICEREXITSOL ( ObjPricerGcg::scip_exitsol  )

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

Definition at line 3677 of file pricer_gcg.cpp.

References GCGcolpoolFree(), and GCGpricestoreFree().

◆ SCIP_DECL_PRICERREDCOST()

SCIP_DECL_PRICERREDCOST ( ObjPricerGcg::scip_redcost  )

reduced cost pricing method of variable pricer for feasible LPs

Definition at line 3774 of file pricer_gcg.cpp.

References GCGcolpoolEndFarkas(), GCGconsMasterbranchAddRootCons(), GCGmasterIsCurrentSolValid(), GCGpricestoreEndFarkas(), and GCGsepaGetNCuts().

◆ SCIP_DECL_PRICERFARKAS()

SCIP_DECL_PRICERFARKAS ( ObjPricerGcg::scip_farkas  )

farcas pricing method of variable pricer for infeasible LPs

Definition at line 3961 of file pricer_gcg.cpp.

References GCGcolpoolStartFarkas(), GCGconsMasterbranchAddRootCons(), GCGmasterTransOrigSolToMasterVars(), and GCGpricestoreStartFarkas().

◆ GCGpricerIncludeSolver()

SCIP_RETCODE GCGpricerIncludeSolver ( SCIP *  scip,
const char *  name,
const char *  desc,
int  priority,
SCIP_Bool  heurenabled,
SCIP_Bool  exactenabled,
GCG_DECL_SOLVERUPDATE((*solverupdate))  ,
GCG_DECL_SOLVERSOLVE((*solversolve))  ,
GCG_DECL_SOLVERSOLVEHEUR((*solversolveheur))  ,
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
heurenabledflag to indicate whether heuristic solving method of the solver is enabled
exactenabledflag to indicate whether exact solving method of the solver is enabled
solverdatapricing solver data

Definition at line 4370 of file pricer_gcg.cpp.

References GCGsolverCreate(), ObjPricerGcg::getPricerdata(), and PRICER_NAME.

Referenced by GCGincludeSolverCliquer(), GCGincludeSolverCplex(), GCGincludeSolverKnapsack(), and GCGincludeSolverMip().