Detailed Description

Binpacking variable pricer.

Author: Timo Berthold; Stefan Heinz

This file implements the variable pricer which check if variables exist with negative reduced cost. See Pricing new variables for more details.

Definition in file pricer_binpacking.c.

#include <assert.h>
#include <string.h>
#include "scip/cons_knapsack.h"
#include "scip/cons_logicor.h"
#include "scip/cons_setppc.h"
#include "scip/cons_varbound.h"
#include "scip/scipdefplugins.h"
#include "cons_samediff.h"
#include "pricer_binpacking.h"
#include "probdata_binpacking.h"
#include "vardata_binpacking.h"

Go to the source code of this file.

Macros
Pricer properties
#define	PRICER_NAME "binpacking"

#define	PRICER_DESC "pricer for binpacking tours"

#define	PRICER_PRIORITY 0

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

Functions
Local methods
static SCIP_RETCODE	addBranchingDecisionConss (SCIP scip, SCIP subscip, SCIP_VAR *vars, SCIP_CONSHDLR conshdlr)

static SCIP_RETCODE	addFixedVarsConss (SCIP scip, SCIP subscip, SCIP_VAR vars, SCIP_CONS conss, int nitems)

static SCIP_RETCODE	initPricing (SCIP scip, SCIP_PRICERDATA pricerdata, SCIP_Bool isfarkas, SCIP subscip, SCIP_VAR *vars)

static SCIP_RETCODE	doPricing (SCIP scip, SCIP_PRICER pricer, SCIP_Bool isfarkas, SCIP_RESULT *result)


static	SCIP_DECL_PRICERFREE (pricerFreeBinpacking)

static	SCIP_DECL_PRICERINIT (pricerInitBinpacking)

static	SCIP_DECL_PRICEREXITSOL (pricerExitsolBinpacking)

static	SCIP_DECL_PRICERREDCOST (pricerRedcostBinpacking)

static	SCIP_DECL_PRICERFARKAS (pricerFarkasBinpacking)

Interface methods
SCIP_RETCODE	SCIPincludePricerBinpacking (SCIP *scip)

SCIP_RETCODE	SCIPpricerBinpackingActivate (SCIP scip, SCIP_CONS conss, SCIP_Longint weights, int *ids, int nitems, SCIP_Longint capacity)

Macro Definition Documentation

◆ PRICER_NAME

#define PRICER_NAME "binpacking"

Definition at line 86 of file pricer_binpacking.c.

◆ PRICER_DESC

#define PRICER_DESC "pricer for binpacking tours"

Definition at line 87 of file pricer_binpacking.c.

◆ PRICER_PRIORITY

#define PRICER_PRIORITY 0

Definition at line 88 of file pricer_binpacking.c.

◆ PRICER_DELAY

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

Definition at line 89 of file pricer_binpacking.c.

Function Documentation

◆ addBranchingDecisionConss()

static SCIP_RETCODE addBranchingDecisionConss	(	SCIP *	scip,
		SCIP *	subscip,
		SCIP_VAR **	vars,
		SCIP_CONSHDLR *	conshdlr
	)

static

add branching decisions constraints to the sub SCIP

Parameters

scip	SCIP data structure
subscip	pricing SCIP data structure
vars	variable array of the subscuip oder variables
conshdlr	constraint handler for branching data

Definition at line 118 of file pricer_binpacking.c.

References DIFFER, NULL, SAME, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPconsIsActive(), SCIPcreateConsBasicVarbound(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPerrorMessage, SCIPgetItemid1Samediff(), SCIPgetItemid2Samediff(), SCIPgetProbData(), SCIPgetTypeSamediff(), SCIPinfinity(), SCIPprobdataGetIds(), and SCIPreleaseCons().

Referenced by initPricing().

◆ addFixedVarsConss()

static SCIP_RETCODE addFixedVarsConss	(	SCIP *	scip,
		SCIP *	subscip,
		SCIP_VAR **	vars,
		SCIP_CONS **	conss,
		int	nitems
	)

static

avoid to generate columns which are fixed to zero; therefore add for each variable which is fixed to zero a corresponding logicor constraint to forbid this column

Note: variable which are fixed locally to zero should not be generated again by the pricing MIP

Parameters

scip	SCIP data structure
subscip	pricing SCIP data structure
vars	variable array of the subscuip
conss	array of setppc constraint for each item one
nitems	number of items

Definition at line 214 of file pricer_binpacking.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPallocBufferArray, SCIPconsIsEnabled(), SCIPcreateConsBasicLogicor(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNegatedVar(), SCIPgetNFixedonesSetppc(), SCIPgetNVars(), SCIPgetVars(), SCIPreleaseCons(), SCIPsetConsInitial(), SCIPvardataGetConsids(), SCIPvardataGetNConsids(), SCIPvarGetData(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by initPricing().

◆ initPricing()

static SCIP_RETCODE initPricing	(	SCIP *	scip,
		SCIP_PRICERDATA *	pricerdata,
		SCIP_Bool	isfarkas,
		SCIP *	subscip,
		SCIP_VAR **	vars
	)

static

initializes the pricing problem for the given capacity

Parameters

scip	SCIP data structure
pricerdata	pricer data
isfarkas	whether we perform Farkas pricing
subscip	pricing SCIP data structure
vars	variable array for the items

Definition at line 326 of file pricer_binpacking.c.

References addBranchingDecisionConss(), addFixedVarsConss(), NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PROBLEM, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPconsIsEnabled(), SCIPcreateConsBasicKnapsack(), SCIPcreateVarBasic(), SCIPdelConsLocal(), SCIPfreeBufferArray, SCIPgetDualfarkasSetppc(), SCIPgetDualsolSetppc(), SCIPgetNFixedonesSetppc(), SCIPgetStage(), SCIPreleaseCons(), and SCIPreleaseVar().

Referenced by doPricing().

◆ doPricing()

static SCIP_RETCODE doPricing	(	SCIP *	scip,
		SCIP_PRICER *	pricer,
		SCIP_Bool	isfarkas,
		SCIP_RESULT *	result
	)

static

perform packing pricing

Parameters

scip	SCIP data structure
pricer	variable pricer structure
isfarkas	whether we perform Farkas pricing
result	pointer to store the result

Definition at line 411 of file pricer_binpacking.c.

References FALSE, initPricing(), NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OBJSENSE_MAXIMIZE, SCIP_OKAY, SCIP_Real, SCIP_STATUS_OPTIMAL, SCIP_SUCCESS, SCIPaddCoefSetppc(), SCIPaddPricedVar(), SCIPallocBufferArray, SCIPcheckSolOrig(), SCIPchgVarUbLazy(), SCIPconsIsEnabled(), SCIPcreate(), SCIPcreateProbBasic(), SCIPcreateVarBinpacking(), SCIPdebug, SCIPdebugMsg, SCIPfree(), SCIPfreeBufferArray, SCIPgetMemUsed(), SCIPgetNFixedonesSetppc(), SCIPgetNSols(), SCIPgetRealParam(), SCIPgetSolOrigObj(), SCIPgetSols(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPgetStatus(), SCIPincludeDefaultPlugins(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisInfinity(), SCIPpricerGetData(), SCIPprintSol(), SCIPprintVar(), SCIPreleaseVar(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetObjsense(), SCIPsetRealParam(), SCIPsnprintf(), SCIPsolve(), SCIPvardataCreateBinpacking(), SCIPwarningMessage(), and TRUE.

Referenced by SCIP_DECL_PRICERFARKAS(), and SCIP_DECL_PRICERREDCOST().

◆ SCIP_DECL_PRICERFREE()

static SCIP_DECL_PRICERFREE ( pricerFreeBinpacking )

static

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

Definition at line 609 of file pricer_binpacking.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, and SCIPpricerGetData().

◆ SCIP_DECL_PRICERINIT()

static SCIP_DECL_PRICERINIT ( pricerInitBinpacking )

static

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

Definition at line 634 of file pricer_binpacking.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcaptureCons(), SCIPgetTransformedCons(), SCIPpricerGetData(), and SCIPreleaseCons().

◆ SCIP_DECL_PRICEREXITSOL()

static SCIP_DECL_PRICEREXITSOL ( pricerExitsolBinpacking )

static

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

Definition at line 667 of file pricer_binpacking.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPpricerGetData(), and SCIPreleaseCons().

◆ SCIP_DECL_PRICERREDCOST()

static SCIP_DECL_PRICERREDCOST ( pricerRedcostBinpacking )

static

reduced cost pricing method of variable pricer for feasible LPs

Definition at line 690 of file pricer_binpacking.c.

References doPricing(), FALSE, SCIP_CALL, and SCIP_OKAY.

◆ SCIP_DECL_PRICERFARKAS()

static SCIP_DECL_PRICERFARKAS ( pricerFarkasBinpacking )

static

farkas pricing method of variable pricer for infeasible LPs

Definition at line 699 of file pricer_binpacking.c.

References doPricing(), SCIP_CALL, SCIP_OKAY, and TRUE.

◆ SCIPincludePricerBinpacking()

SCIP_RETCODE SCIPincludePricerBinpacking ( SCIP * scip )

creates the binpacking variable pricer and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 715 of file pricer_binpacking.c.

References NULL, PRICER_DELAY, PRICER_DESC, PRICER_NAME, PRICER_PRIORITY, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPfindConshdlr(), SCIPincludePricerBasic(), SCIPsetPricerExitsol(), SCIPsetPricerFree(), and SCIPsetPricerInit().

Referenced by runShell().

◆ SCIPpricerBinpackingActivate()

SCIP_RETCODE SCIPpricerBinpackingActivate	(	SCIP *	scip,
		SCIP_CONS **	conss,
		SCIP_Longint *	weights,
		int *	ids,
		int	nitems,
		SCIP_Longint	capacity
	)

added problem specific data to pricer and activates pricer

Parameters

scip	SCIP data structure
conss	set covering constraints for the items
weights	weight of the items
ids	array of item ids
nitems	number of items to be packed
capacity	capacity of the bins

Definition at line 750 of file pricer_binpacking.c.

References NULL, PRICER_NAME, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPactivatePricer(), SCIPcaptureCons(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPduplicateBlockMemoryArray, SCIPfindPricer(), and SCIPpricerGetData().

Referenced by SCIPprobdataCreate().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PRICER_NAME

◆ PRICER_DESC

◆ PRICER_PRIORITY

◆ PRICER_DELAY

Function Documentation

◆ addBranchingDecisionConss()

◆ addFixedVarsConss()

◆ initPricing()

◆ doPricing()

◆ SCIP_DECL_PRICERFREE()

◆ SCIP_DECL_PRICERINIT()

◆ SCIP_DECL_PRICEREXITSOL()

◆ SCIP_DECL_PRICERREDCOST()

◆ SCIP_DECL_PRICERFARKAS()

◆ SCIPincludePricerBinpacking()

◆ SCIPpricerBinpackingActivate()