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_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) |
#define PRICER_NAME "binpacking" |
Definition at line 86 of file pricer_binpacking.c.
#define PRICER_DESC "pricer for binpacking tours" |
Definition at line 87 of file pricer_binpacking.c.
#define PRICER_PRIORITY 0 |
Definition at line 88 of file pricer_binpacking.c.
#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.
|
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 118 of file pricer_binpacking.c.
References assert(), c, 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(), SCIPreleaseCons(), and vars.
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 214 of file pricer_binpacking.c.
References assert(), c, FALSE, NULL, nvars, 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(), TRUE, var, and vars.
Referenced by initPricing().
|
static |
initializes the pricing problem for the given capacity
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(), assert(), c, NULL, nvars, SCIP_Bool, 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(), SCIPreleaseVar(), var, and vars.
Referenced by doPricing().
|
static |
perform packing pricing
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 assert(), FALSE, initPricing(), NULL, result, 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(), sol, TRUE, var, and vars.
Referenced by SCIP_DECL_PRICERFARKAS(), and SCIP_DECL_PRICERREDCOST().
|
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 assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, and SCIPpricerGetData().
|
static |
initialization method of variable pricer (called after problem was transformed)
Definition at line 634 of file pricer_binpacking.c.
References assert(), c, 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 667 of file pricer_binpacking.c.
References assert(), c, NULL, SCIP_CALL, SCIP_OKAY, SCIPpricerGetData(), and SCIPreleaseCons().
|
static |
reduced cost pricing method of variable pricer for feasible LPs
Definition at line 690 of file pricer_binpacking.c.
References doPricing(), FALSE, result, SCIP_CALL, and SCIP_OKAY.
|
static |
farkas pricing method of variable pricer for infeasible LPs
Definition at line 699 of file pricer_binpacking.c.
References doPricing(), result, SCIP_CALL, SCIP_OKAY, and TRUE.
SCIP_RETCODE SCIPincludePricerBinpacking | ( | SCIP * | scip | ) |
creates the binpacking variable pricer and includes it in SCIP
scip | SCIP data structure |
Definition at line 715 of file pricer_binpacking.c.
References assert(), 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 750 of file pricer_binpacking.c.
References assert(), c, NULL, PRICER_NAME, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPactivatePricer(), SCIPcaptureCons(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPduplicateBlockMemoryArray, SCIPfindPricer(), and SCIPpricerGetData().
Referenced by SCIPprobdataCreate().