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 subscip, SCIP_VAR *vars)


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

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

Definition at line 92 of file pricer_binpacking.c.

Referenced by SCIPincludePricerBinpacking().

#define PRICER_DESC "pricer for binpacking tours"

Definition at line 90 of file pricer_binpacking.c.

Referenced by SCIPincludePricerBinpacking().

#define PRICER_NAME "binpacking"

Definition at line 89 of file pricer_binpacking.c.

Referenced by SCIPincludePricerBinpacking(), and SCIPpricerBinpackingActivate().

#define PRICER_PRIORITY 0

Definition at line 91 of file pricer_binpacking.c.

Referenced by SCIPincludePricerBinpacking().

Function Documentation

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 121 of file pricer_binpacking.c.

References SCIP_PricerData::conss, DIFFER, SAME, SCIPgetItemid1Samediff(), SCIPgetItemid2Samediff(), SCIPgetTypeSamediff(), and SCIPprobdataGetIds().

Referenced by initPricing().

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 217 of file pricer_binpacking.c.

References SCIPvardataGetConsids(), and SCIPvardataGetNConsids().

Referenced by initPricing().

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

static

initializes the pricing problem for the given capacity

Parameters

scip	SCIP data structure
pricerdata	pricer data
subscip	pricing SCIP data structure
vars	variable array for the items

Definition at line 329 of file pricer_binpacking.c.

References addBranchingDecisionConss(), addFixedVarsConss(), SCIP_PricerData::capacity, SCIP_PricerData::conss, SCIP_PricerData::nitems, and SCIP_PricerData::weights.

Referenced by SCIP_DECL_PRICERREDCOST().

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 479 of file pricer_binpacking.c.

static SCIP_DECL_PRICERFARKAS ( pricerFarkasBinpacking )

static

farkas pricing method of variable pricer for infeasible LPs

Note

In case of this binpacking example, the master LP should not get infeasible after branching, because of the way branching is performed. Therefore, the Farkas pricing is not implemented.

In case of Ryan/Foster branching, the two items are selected in a way such that the sum of the LP values of all columns/packings containing both items is fractional. Hence, it exists at least one column/packing which contains both items and also at least one column/packing for each item containing this but not the other item. That means, branching in the "same" direction stays LP feasible since there exists at least one column/packing with both items and branching in the "differ" direction stays LP feasible since there exists at least one column/packing containing one item, but not the other.
In case of variable branching, we only branch on fractional variables. If a variable is fixed to one, there is no issue. If a variable is fixed to zero, then we know that for each item which is part of that column/packing, there exists at least one other column/packing containing this particular item due to the covering constraints.

Definition at line 686 of file pricer_binpacking.c.

static SCIP_DECL_PRICERFREE ( pricerFreeBinpacking )

static

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

Definition at line 421 of file pricer_binpacking.c.

static SCIP_DECL_PRICERINIT ( pricerInitBinpacking )

static

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

Definition at line 446 of file pricer_binpacking.c.

static SCIP_DECL_PRICERREDCOST ( pricerRedcostBinpacking )

static

reduced cost pricing method of variable pricer for feasible LPs

Definition at line 503 of file pricer_binpacking.c.

References SCIP_PricerData::capacity, SCIP_PricerData::conss, SCIP_PricerData::ids, initPricing(), SCIP_PricerData::nitems, SCIPcreateVarBinpacking(), and SCIPvardataCreateBinpacking().

SCIP_RETCODE SCIPincludePricerBinpacking ( SCIP * scip )

creates the binpacking variable pricer and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 717 of file pricer_binpacking.c.

References PRICER_DELAY, PRICER_DESC, PRICER_NAME, and PRICER_PRIORITY.

Referenced by runShell().

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 752 of file pricer_binpacking.c.

References SCIP_PricerData::capacity, SCIP_PricerData::nitems, and PRICER_NAME.

Referenced by SCIPprobdataCreate().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

Function Documentation