Detailed Description
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) |
Macro Definition Documentation
◆ PRICER_NAME
#define PRICER_NAME "binpacking" |
Definition at line 98 of file pricer_binpacking.c.
Referenced by SCIPincludePricerBinpacking(), and SCIPpricerBinpackingActivate().
◆ PRICER_DESC
#define PRICER_DESC "pricer for binpacking tours" |
Definition at line 99 of file pricer_binpacking.c.
Referenced by SCIPincludePricerBinpacking().
◆ PRICER_PRIORITY
#define PRICER_PRIORITY 0 |
Definition at line 100 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 101 of file pricer_binpacking.c.
Referenced by SCIPincludePricerBinpacking().
Function Documentation
◆ addBranchingDecisionConss()
|
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 130 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 |
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 226 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 |
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 338 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().
◆ SCIP_DECL_PRICERFREE()
|
static |
name Callback methodsdestructor of variable pricer to free user data (called when SCIP is exiting)
Definition at line 429 of file pricer_binpacking.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, and SCIPpricerGetData().
◆ SCIP_DECL_PRICERINIT()
|
static |
initialization method of variable pricer (called after problem was transformed)
Definition at line 454 of file pricer_binpacking.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPcaptureCons(), SCIPgetTransformedCons(), SCIPpricerGetData(), and SCIPreleaseCons().
◆ SCIP_DECL_PRICEREXITSOL()
|
static |
solving process deinitialization method of variable pricer (called before branch and bound process data is freed)
Definition at line 487 of file pricer_binpacking.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPpricerGetData(), and SCIPreleaseCons().
◆ SCIP_DECL_PRICERREDCOST()
|
static |
reduced cost pricing method of variable pricer for feasible LPs
Definition at line 511 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.
◆ SCIP_DECL_PRICERFARKAS()
|
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 695 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
-
scip SCIP data structure
Definition at line 725 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 760 of file pricer_binpacking.c.
References NULL, PRICER_NAME, SCIP_CALL, SCIP_OKAY, SCIPactivatePricer(), SCIPcaptureCons(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPduplicateBlockMemoryArray, SCIPfindPricer(), and SCIPpricerGetData().
Referenced by SCIPprobdataCreate().