Detailed Description

methods for storing priced cols (based on SCIP's separation storage)

Author: Jonas Witt; Christian Puchert

#include <assert.h>
#include "scip/def.h"
#include "scip/set.h"
#include "scip/stat.h"
#include "scip/clock.h"
#include "scip/lp.h"
#include "scip/var.h"
#include "scip/tree.h"
#include "scip/reopt.h"
#include "scip/event.h"
#include "scip/cons.h"
#include "scip/debug.h"
#include "gcg.h"
#include "pricestore_gcg.h"
#include "struct_pricestore_gcg.h"
#include "pricer_gcg.h"

Go to the source code of this file.

Functions
static SCIP_RETCODE	pricestoreEnsureColsMem (GCG_PRICESTORE *pricestore, int num)

SCIP_RETCODE	GCGpricestoreCreate (SCIP scip, GCG_PRICESTORE *pricestore, SCIP_Real efficiacyfac, SCIP_Real objparalfac, SCIP_Real orthofac, SCIP_Real mincolorth, GCG_EFFICIACYCHOICE efficiacychoice)

SCIP_RETCODE	GCGpricestoreFree (SCIP scip, GCG_PRICESTORE *pricestore)

void	GCGpricestoreStartFarkas (GCG_PRICESTORE *pricestore)

void	GCGpricestoreEndFarkas (GCG_PRICESTORE *pricestore)

void	GCGpricestoreStartForceCols (GCG_PRICESTORE *pricestore)

void	GCGpricestoreEndForceCols (GCG_PRICESTORE *pricestore)

static void	pricestoreDelCol (GCG_PRICESTORE *pricestore, int pos, SCIP_Bool freecol)

static int	pricestoreFindEqualCol (GCG_PRICESTORE pricestore, GCG_COL col)

SCIP_RETCODE	GCGpricestoreAddCol (SCIP scip, GCG_PRICESTORE pricestore, GCG_COL *col, SCIP_Bool forcecol)

static SCIP_RETCODE	pricestoreUpdateOrthogonalities (GCG_PRICESTORE pricestore, GCG_COL col, SCIP_Real mincolorthogonality)

static SCIP_RETCODE	pricestoreApplyCol (GCG_PRICESTORE pricestore, GCG_COL col, SCIP_Bool force, SCIP_Real mincolorthogonality, SCIP_Real score, SCIP_Bool *added)

static int	pricestoreGetBestCol (GCG_PRICESTORE *pricestore)

static SCIP_RETCODE	computeScore (GCG_PRICESTORE *pricestore, int pos)

SCIP_RETCODE	GCGpricestoreApplyCols (GCG_PRICESTORE pricestore, GCG_COLPOOL colpool, SCIP_Bool usecolpool, int *nfoundvars)

void	GCGpricestoreClearCols (GCG_PRICESTORE *pricestore)

void	GCGpricestoreRemoveInefficaciousCols (GCG_PRICESTORE *pricestore)

GCG_COL **	GCGpricestoreGetCols (GCG_PRICESTORE *pricestore)

int	GCGpricestoreGetNCols (GCG_PRICESTORE *pricestore)

int	GCGpricestoreGetNEfficaciousCols (GCG_PRICESTORE *pricestore)

int	GCGpricestoreGetNColsFound (GCG_PRICESTORE *pricestore)

int	GCGpricestoreGetNColsFoundRound (GCG_PRICESTORE *pricestore)

int	GCGpricestoreGetNColsApplied (GCG_PRICESTORE *pricestore)

SCIP_Real	GCGpricestoreGetTime (GCG_PRICESTORE *pricestore)

Function Documentation

◆ pricestoreEnsureColsMem()

static SCIP_RETCODE pricestoreEnsureColsMem	(	GCG_PRICESTORE *	pricestore,
		int	num
	)

static

resizes cols and score arrays to be able to store at least num entries

Parameters

pricestore	price storage
num	minimal number of slots in array

Definition at line 60 of file pricestore_gcg.c.

References GCG_PriceStore::cols, GCG_PriceStore::colssize, GCG_PriceStore::objparallelisms, GCG_PriceStore::orthogonalities, GCG_PriceStore::scip, and GCG_PriceStore::scores.

Referenced by GCGpricestoreAddCol().

◆ GCGpricestoreCreate()

SCIP_RETCODE GCGpricestoreCreate	(	SCIP *	scip,
		GCG_PRICESTORE **	pricestore,
		SCIP_Real	efficiacyfac,
		SCIP_Real	objparalfac,
		SCIP_Real	orthofac,
		SCIP_Real	mincolorth,
		GCG_EFFICIACYCHOICE	efficiacychoice
	)

creates price storage

Parameters

scip	SCIP data structure
pricestore	pointer to store price storage
efficiacyfac	factor of -redcost/norm in score function
objparalfac	factor of objective parallelism in score function
orthofac	factor of orthogonalities in score function
mincolorth	minimal orthogonality of columns to add (with respect to columns added in the current round)
efficiacychoice	choice to base efficiacy on

Definition at line 85 of file pricestore_gcg.c.

Referenced by ObjPricerGcg::createPricestore().

◆ GCGpricestoreFree()

SCIP_RETCODE GCGpricestoreFree	(	SCIP *	scip,
		GCG_PRICESTORE **	pricestore
	)

frees price storage

Parameters

scip	SCIP data structure
pricestore	pointer to store price storage

Definition at line 127 of file pricestore_gcg.c.

References GCGpricestoreGetTime().

Referenced by SCIP_DECL_PRICEREXITSOL().

◆ GCGpricestoreStartFarkas()

void GCGpricestoreStartFarkas ( GCG_PRICESTORE * pricestore )

informs price storage, that Farkas pricing starts now

Parameters

pricestore price storage

Definition at line 152 of file pricestore_gcg.c.

References GCG_PriceStore::infarkas, and GCG_PriceStore::ncols.

Referenced by SCIP_DECL_PRICERFARKAS().

◆ GCGpricestoreEndFarkas()

void GCGpricestoreEndFarkas ( GCG_PRICESTORE * pricestore )

informs price storage, that Farkas pricing is now finished

Parameters

pricestore price storage

Definition at line 163 of file pricestore_gcg.c.

References GCG_PriceStore::infarkas, and GCG_PriceStore::ncols.

Referenced by SCIP_DECL_PRICERREDCOST().

◆ GCGpricestoreStartForceCols()

void GCGpricestoreStartForceCols ( GCG_PRICESTORE * pricestore )

informs price storage, that the following cols should be used in any case

Parameters

pricestore price storage

Definition at line 174 of file pricestore_gcg.c.

References GCG_PriceStore::forcecols.

◆ GCGpricestoreEndForceCols()

void GCGpricestoreEndForceCols ( GCG_PRICESTORE * pricestore )

informs price storage, that the following cols should no longer be used in any case

Parameters

pricestore price storage

Definition at line 185 of file pricestore_gcg.c.

References GCG_PriceStore::forcecols.

◆ pricestoreDelCol()

static void pricestoreDelCol	(	GCG_PRICESTORE *	pricestore,
		int	pos,
		SCIP_Bool	freecol
	)

static

removes a non-forced col from the price storage

Parameters

pricestore	price storage
pos	position of col to delete
freecol	should col be freed

Definition at line 197 of file pricestore_gcg.c.

References GCG_PriceStore::cols, GCGcolGetRedcost(), GCGfreeGcgCol(), GCG_PriceStore::ncols, GCG_PriceStore::nefficaciouscols, GCG_PriceStore::nforcedcols, GCG_PriceStore::objparallelisms, GCG_PriceStore::orthogonalities, GCG_PriceStore::scip, and GCG_PriceStore::scores.

Referenced by GCGpricestoreApplyCols(), GCGpricestoreRemoveInefficaciousCols(), and pricestoreUpdateOrthogonalities().

◆ pricestoreFindEqualCol()

static int pricestoreFindEqualCol	(	GCG_PRICESTORE *	pricestore,
		GCG_COL *	col
	)

static

for a given column, check if an identical column already exists in the price storage; if one exists, return its position, otherwise, return -1

Parameters

pricestore	price storage
col	column to be checked

Definition at line 226 of file pricestore_gcg.c.

References GCG_PriceStore::cols, GCGcolIsEq(), and GCG_PriceStore::ncols.

Referenced by GCGpricestoreAddCol().

◆ GCGpricestoreAddCol()

SCIP_RETCODE GCGpricestoreAddCol	(	SCIP *	scip,
		GCG_PRICESTORE *	pricestore,
		GCG_COL *	col,
		SCIP_Bool	forcecol
	)

adds col to price storage; if the col should be forced to enter the LP, an infinite score will be used

Parameters

scip	SCIP data structure
pricestore	price storage
col	priced col
forcecol	should the col be forced to enter the LP?

Definition at line 243 of file pricestore_gcg.c.

References GCG_PriceStore::cols, GCG_PriceStore::colssize, GCG_PriceStore::forcecols, GCGcolComputeDualObjPara(), GCGcolComputeNorm(), GCGcolGetRedcost(), GCGfreeGcgCol(), GCG_PriceStore::ncols, GCG_PriceStore::ncolsfound, GCG_PriceStore::ncolsfoundround, GCG_PriceStore::nefficaciouscols, GCG_PriceStore::nforcedcols, GCG_PriceStore::objparalfac, GCG_PriceStore::objparallelisms, GCG_PriceStore::orthogonalities, GCG_PriceStore::priceclock, pricestoreEnsureColsMem(), pricestoreFindEqualCol(), GCG_PriceStore::scip, and GCG_PriceStore::scores.

Referenced by ObjPricerGcg::addColToPricestore(), and GCGcolpoolPrice().

◆ pricestoreUpdateOrthogonalities()

static SCIP_RETCODE pricestoreUpdateOrthogonalities	(	GCG_PRICESTORE *	pricestore,
		GCG_COL *	col,
		SCIP_Real	mincolorthogonality
	)

static

updates the orthogonalities and scores of the non-forced cols after the given col was added to the LP

Parameters

pricestore	price storage
col	col that was applied
mincolorthogonality	minimal orthogonality of cols to apply to LP

Definition at line 361 of file pricestore_gcg.c.

References GCG_PriceStore::cols, GCG_PriceStore::efficiacychoice, GCG_PriceStore::efficiacyfac, GCG_EFFICIACYCHOICE_DANTZIG, GCG_EFFICIACYCHOICE_LAMBDA, GCG_EFFICIACYCHOICE_STEEPESTEDGE, GCGcolComputeOrth(), GCGcolGetNorm(), GCGcolGetRedcost(), GCG_PriceStore::nforcedcols, GCG_PriceStore::objparalfac, GCG_PriceStore::objparallelisms, GCG_PriceStore::orthofac, GCG_PriceStore::orthogonalities, pricestoreDelCol(), GCG_PriceStore::scip, and GCG_PriceStore::scores.

Referenced by pricestoreApplyCol().

◆ pricestoreApplyCol()

static SCIP_RETCODE pricestoreApplyCol	(	GCG_PRICESTORE *	pricestore,
		GCG_COL *	col,
		SCIP_Bool	force,
		SCIP_Real	mincolorthogonality,
		SCIP_Real	score,
		SCIP_Bool *	added
	)

static

adds the given col to priced vars and updates the orthogonalities and scores of remaining cols

Parameters

pricestore	price storage
col	col to apply to the LP
force	force column
mincolorthogonality	minimal orthogonality of cols to apply to LP
score	score of column (or -1.0 if not specified)
added	pointer to store whether the column was added