Scippy

SCIP

Solving Constraint Integer Programs

pricer_binpacking.c File Reference

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

◆ PRICER_NAME

#define PRICER_NAME   "binpacking"

◆ PRICER_DESC

#define PRICER_DESC   "pricer for binpacking tours"

Definition at line 90 of file pricer_binpacking.c.

Referenced by SCIPincludePricerBinpacking().

◆ PRICER_PRIORITY

#define PRICER_PRIORITY   0

Definition at line 91 of file pricer_binpacking.c.

Referenced by SCIPincludePricerBinpacking().

◆ PRICER_DELAY

#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().

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
scipSCIP data structure
subscippricing SCIP data structure
varsvariable array of the subscuip oder variables
conshdlrconstraint handler for branching data

Definition at line 121 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
scipSCIP data structure
subscippricing SCIP data structure
varsvariable array of the subscuip
conssarray of setppc constraint for each item one
nitemsnumber of items

Definition at line 217 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 subscip,
SCIP_VAR **  vars 
)
static

◆ SCIP_DECL_PRICERFREE()

static SCIP_DECL_PRICERFREE ( pricerFreeBinpacking  )
static

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

Definition at line 420 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 445 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 478 of file pricer_binpacking.c.

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

◆ SCIP_DECL_PRICERREDCOST()

◆ SCIP_DECL_PRICERFARKAS()

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.
  1. 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.
  2. 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.

References SCIP_OKAY, SCIPABORT, and SCIPwarningMessage().

◆ SCIPincludePricerBinpacking()

SCIP_RETCODE SCIPincludePricerBinpacking ( SCIP scip)

creates the binpacking variable pricer and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 716 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
scipSCIP data structure
conssset covering constraints for the items
weightsweight of the items
idsarray of item ids
nitemsnumber of items to be packed
capacitycapacity of the bins

Definition at line 751 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().