Binpacking variable pricer.
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) |
#define PRICER_NAME "binpacking" |
Definition at line 89 of file pricer_binpacking.c.
Referenced by SCIPincludePricerBinpacking(), and SCIPpricerBinpackingActivate().
#define PRICER_DESC "pricer for binpacking tours" |
Definition at line 90 of file pricer_binpacking.c.
Referenced by SCIPincludePricerBinpacking().
#define PRICER_PRIORITY 0 |
Definition at line 91 of file pricer_binpacking.c.
Referenced by SCIPincludePricerBinpacking().
#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().
|
static |
add branching decisions constraints to the sub SCIP
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 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().
|
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
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 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().
|
static |
initializes the pricing problem for the given capacity
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(), 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, SCIPgetDualsolSetppc(), SCIPgetNFixedonesSetppc(), SCIPgetStage(), SCIPreleaseCons(), and SCIPreleaseVar().
Referenced by SCIP_DECL_PRICERREDCOST().
|
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().
|
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().
|
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().
|
static |
reduced cost pricing method of variable pricer for feasible LPs
Definition at line 502 of file pricer_binpacking.c.
References FALSE, initPricing(), NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_Longint, 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.
|
static |
farkas pricing method of variable pricer for infeasible LPs
Definition at line 686 of file pricer_binpacking.c.
References SCIP_OKAY, SCIPABORT, and SCIPwarningMessage().
SCIP_RETCODE SCIPincludePricerBinpacking | ( | SCIP * | scip | ) |
creates the binpacking variable pricer and includes it in SCIP
scip | SCIP data structure |
Definition at line 717 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().
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
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 NULL, PRICER_NAME, SCIP_CALL, SCIP_OKAY, SCIPactivatePricer(), SCIPcaptureCons(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPduplicateBlockMemoryArray, SCIPfindPricer(), and SCIPpricerGetData().
Referenced by SCIPprobdataCreate().