Scippy

GCG

Branch-and-Price & Column Generation for Everyone

colpool.c File Reference

Detailed Description

methods for storing cols in a col pool (based on SCIP's cut pool)

Author
Jonas Witt

Definition in file colpool.c.

#include <assert.h>
#include "scip/clock.h"
#include "pub_gcgcol.h"
#include "colpool.h"
#include "struct_colpool.h"
#include "pricestore_gcg.h"
#include "struct_pricestore_gcg.h"
#include "pricer_gcg.h"

Go to the source code of this file.

Macros

#define GCG_USESMALLTABLES   FALSE
 
#define GCG_HASHSIZE_COLPOOLS_SMALL   100
 
#define GCG_HASHSIZE_COLPOOLS   500
 

Functions

static SCIP_DECL_HASHGETKEY (hashGetKeyCol)
 
static SCIP_DECL_HASHKEYEQ (hashKeyEqCol)
 
static SCIP_DECL_HASHKEYVAL (hashKeyValCol)
 
static SCIP_RETCODE colpoolEnsureColsMem (GCG_COLPOOL *colpool, int num)
 
SCIP_RETCODE GCGcolpoolCreate (SCIP *scip, GCG_COLPOOL **colpool, int agelimit)
 
SCIP_RETCODE GCGcolpoolFree (SCIP *scip, GCG_COLPOOL **colpool)
 
static SCIP_RETCODE colpoolDelCol (GCG_COLPOOL *colpool, GCG_COL *col, SCIP_Bool freecol)
 
SCIP_RETCODE GCGcolpoolClear (GCG_COLPOOL *colpool)
 
SCIP_RETCODE GCGcolpoolAddCol (GCG_COLPOOL *colpool, GCG_COL *col, SCIP_Bool *success)
 
SCIP_RETCODE GCGcolpoolAddNewCol (GCG_COLPOOL *colpool, GCG_COL *col)
 
SCIP_RETCODE GCGcolpoolDelCol (GCG_COLPOOL *colpool, GCG_COL *col, SCIP_Bool freecol)
 
SCIP_RETCODE GCGcolpoolPrice (SCIP *scip, GCG_COLPOOL *colpool, GCG_PRICESTORE *pricestore, SCIP_SOL *sol, SCIP_Bool *foundvars)
 
SCIP_RETCODE GCGcolpoolUpdateNode (GCG_COLPOOL *colpool)
 
SCIP_RETCODE GCGcolpoolUpdateRedcost (GCG_COLPOOL *colpool)
 
void GCGcolpoolStartFarkas (GCG_COLPOOL *colpool)
 
void GCGcolpoolEndFarkas (GCG_COLPOOL *colpool)
 
GCG_COL ** GCGcolpoolGetCols (GCG_COLPOOL *colpool)
 
int GCGcolpoolGetNCols (GCG_COLPOOL *colpool)
 
int GCGcolpoolGetMaxNCols (GCG_COLPOOL *colpool)
 
SCIP_Real GCGcolpoolGetTime (GCG_COLPOOL *colpool)
 
SCIP_Longint GCGcolpoolGetNCalls (GCG_COLPOOL *colpool)
 
SCIP_Longint GCGcolpoolGetNColsFound (GCG_COLPOOL *colpool)
 

Macro Definition Documentation

◆ GCG_USESMALLTABLES

#define GCG_USESMALLTABLES   FALSE

Definition at line 46 of file colpool.c.

◆ GCG_HASHSIZE_COLPOOLS_SMALL

#define GCG_HASHSIZE_COLPOOLS_SMALL   100

size of hash table in col pools for small problems

Definition at line 47 of file colpool.c.

◆ GCG_HASHSIZE_COLPOOLS

#define GCG_HASHSIZE_COLPOOLS   500

size of hash table in col pools

Definition at line 48 of file colpool.c.

Function Documentation

◆ SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( hashGetKeyCol  )
static

gets the hash key of a col

Definition at line 56 of file colpool.c.

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( hashKeyEqCol  )
static

returns TRUE iff both cols are identical

Definition at line 69 of file colpool.c.

References GCG_Col::isray, GCG_Col::nvars, GCG_Col::probnr, GCG_Col::vals, and GCG_Col::vars.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( hashKeyValCol  )
static

Definition at line 107 of file colpool.c.

References GCG_Col::isray, GCG_Col::nvars, GCG_Col::probnr, and GCG_Col::vals.

◆ colpoolEnsureColsMem()

static SCIP_RETCODE colpoolEnsureColsMem ( GCG_COLPOOL colpool,
int  num 
)
static

resizes cols array to be able to store at least num entries

Parameters
colpoolcol pool
numminimal number of slots in array

Definition at line 130 of file colpool.c.

References GCG_Colpool::cols, GCG_Colpool::colssize, and GCG_Colpool::scip.

Referenced by GCGcolpoolAddNewCol().

◆ GCGcolpoolCreate()

SCIP_RETCODE GCGcolpoolCreate ( SCIP *  scip,
GCG_COLPOOL **  colpool,
int  agelimit 
)

creates col pool

Parameters
scipSCIP data structure
colpoolpointer to store col pool
agelimitmaximum age a col can reach before it is deleted from the pool (-1 fpr no limit)

Definition at line 159 of file colpool.c.

References GCG_HASHSIZE_COLPOOLS, GCG_HASHSIZE_COLPOOLS_SMALL, and GCG_USESMALLTABLES.

Referenced by ObjPricerGcg::createColpool().

◆ GCGcolpoolFree()

SCIP_RETCODE GCGcolpoolFree ( SCIP *  scip,
GCG_COLPOOL **  colpool 
)

frees col pool

Parameters
scipSCIP data structure
colpoolpointer to store col pool

Definition at line 195 of file colpool.c.

References GCGcolpoolClear(), and GCGcolpoolGetTime().

Referenced by SCIP_DECL_PRICEREXITSOL().

◆ colpoolDelCol()

static SCIP_RETCODE colpoolDelCol ( GCG_COLPOOL colpool,
GCG_COL col,
SCIP_Bool  freecol 
)
static

removes the col from the col pool

Parameters
colpoolcol pool
colcol to remove
freecolshould the col be freed?

Definition at line 223 of file colpool.c.

References GCG_Colpool::cols, GCG_Colpool::firstunprocessed, GCG_Colpool::firstunprocessedsol, GCGfreeGcgCol(), GCG_Colpool::hashtable, GCG_Colpool::ncols, and GCG_Col::pos.

Referenced by GCGcolpoolClear(), GCGcolpoolDelCol(), and GCGcolpoolPrice().

◆ GCGcolpoolClear()

SCIP_RETCODE GCGcolpoolClear ( GCG_COLPOOL colpool)

removes all rows from the col pool

Parameters
colpoolcol pool

Definition at line 262 of file colpool.c.

References colpoolDelCol(), GCG_Colpool::cols, and GCG_Colpool::ncols.

Referenced by GCGcolpoolFree(), and GCGcolpoolUpdateNode().

◆ GCGcolpoolAddCol()

SCIP_RETCODE GCGcolpoolAddCol ( GCG_COLPOOL colpool,
GCG_COL col,
SCIP_Bool *  success 
)

if not already existing, adds col to col pool and captures it

Parameters
colpoolcol pool
colcolumn to add
successpointer to store if col was added

Definition at line 281 of file colpool.c.

References GCGcolpoolAddNewCol(), and GCG_Colpool::hashtable.

Referenced by GCGpricestoreApplyCols().

◆ GCGcolpoolAddNewCol()

SCIP_RETCODE GCGcolpoolAddNewCol ( GCG_COLPOOL colpool,
GCG_COL col 
)

adds row to col pool and captures it; doesn't check for multiple cols

Parameters
colpoolcol pool
colcolumn to add

Definition at line 304 of file colpool.c.

References colpoolEnsureColsMem(), GCG_Colpool::cols, GCG_Colpool::hashtable, GCG_Colpool::maxncols, GCG_Colpool::ncols, and GCG_Col::pos.

Referenced by GCGcolpoolAddCol().

◆ GCGcolpoolDelCol()

SCIP_RETCODE GCGcolpoolDelCol ( GCG_COLPOOL colpool,
GCG_COL col,
SCIP_Bool  freecol 
)

removes the LP row from the col pool

Parameters
colpoolcol pool
colcol to remove
freecolshould the col be freed?

Definition at line 328 of file colpool.c.

References colpoolDelCol(), and GCG_Colpool::hashtable.

◆ GCGcolpoolPrice()

SCIP_RETCODE GCGcolpoolPrice ( SCIP *  scip,
GCG_COLPOOL colpool,
GCG_PRICESTORE pricestore,
SCIP_SOL *  sol,
SCIP_Bool *  foundvars 
)

prices cols of the col pool

Parameters
scipSCIP data structure
colpoolcol pool
pricestoreGCG price storage
solsolution to be separated (or NULL for LP-solution)
foundvarspointer to store the result of the separation call

Definition at line 352 of file colpool.c.

References GCG_Col::age, colpoolDelCol(), GCG_Colpool::firstunprocessed, GCG_Colpool::firstunprocessedsol, GCGcolGetRedcost(), GCGcolIsAged(), GCGpricestoreAddCol(), GCGpricestoreGetNCols(), GCG_Colpool::ncalls, GCG_Colpool::ncols, GCG_Col::pos, and GCG_Colpool::scip.

Referenced by ObjPricerGcg::pricingLoop().

◆ GCGcolpoolUpdateNode()

SCIP_RETCODE GCGcolpoolUpdateNode ( GCG_COLPOOL colpool)

update node at which columns of column pool are feasible

Parameters
colpoolcol pool

Definition at line 429 of file colpool.c.

References GCGcolpoolClear(), GCG_Colpool::nodenr, and GCG_Colpool::scip.

Referenced by ObjPricerGcg::pricingLoop().

◆ GCGcolpoolUpdateRedcost()

SCIP_RETCODE GCGcolpoolUpdateRedcost ( GCG_COLPOOL colpool)

update reduced cost and compute master coefs of columns in column pool

Parameters
colpoolcol pool

Definition at line 451 of file colpool.c.

References GCGcolpoolGetCols(), GCGcolpoolGetNCols(), GCGcolUpdateRedcost(), GCGcomputeColMastercoefs(), GCGcomputeRedCostGcgCol(), GCG_Colpool::infarkas, and GCG_Colpool::scip.

Referenced by ObjPricerGcg::pricingLoop().

◆ GCGcolpoolStartFarkas()

void GCGcolpoolStartFarkas ( GCG_COLPOOL colpool)

gets number of cols in the col pool

Parameters
colpoolcol pool

Definition at line 481 of file colpool.c.

References GCG_Colpool::infarkas.

Referenced by SCIP_DECL_PRICERFARKAS().

◆ GCGcolpoolEndFarkas()

void GCGcolpoolEndFarkas ( GCG_COLPOOL colpool)

gets number of cols in the col pool

Parameters
colpoolcol pool

Definition at line 489 of file colpool.c.

References GCG_Colpool::infarkas.

Referenced by SCIP_DECL_PRICERREDCOST().

◆ GCGcolpoolGetNCols()

int GCGcolpoolGetNCols ( GCG_COLPOOL colpool)

gets number of cols in the col pool

Parameters
colpoolcol pool

Definition at line 508 of file colpool.c.

References GCG_Colpool::ncols.

Referenced by GCGcolpoolUpdateRedcost().

◆ GCGcolpoolGetMaxNCols()

int GCGcolpoolGetMaxNCols ( GCG_COLPOOL colpool)

gets maximum number of cols that were stored in the col pool at the same time

Parameters
colpoolcol pool

Definition at line 518 of file colpool.c.

References GCG_Colpool::maxncols.

◆ GCGcolpoolGetTime()

SCIP_Real GCGcolpoolGetTime ( GCG_COLPOOL colpool)

gets time in seconds used for separating cols from the pool

Parameters
colpoolcol pool

Definition at line 528 of file colpool.c.

References GCG_Colpool::poolclock, and GCG_Colpool::scip.

Referenced by GCGcolpoolFree().

◆ GCGcolpoolGetNCalls()

SCIP_Longint GCGcolpoolGetNCalls ( GCG_COLPOOL colpool)

get number of times, the col pool was separated

Parameters
colpoolcol pool

Definition at line 538 of file colpool.c.

References GCG_Colpool::ncalls.

◆ GCGcolpoolGetNColsFound()

SCIP_Longint GCGcolpoolGetNColsFound ( GCG_COLPOOL colpool)

get total number of cols that were separated from the col pool

Parameters
colpoolcol pool

Definition at line 548 of file colpool.c.

References GCG_Colpool::ncolsfound.