Ringpacking variable pricer.
This file implements the variable pricer which checks if variables negative reduced cost exist. See Pricing new variables for more details.
Definition in file pricer_rpa.c.
#include <assert.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include "scip/scipdefplugins.h"
#include "scip/scip.h"
#include "pricer_rpa.h"
#include "probdata_rpa.h"
#include "pattern.h"
Go to the source code of this file.
Macros | |
#define | M_PI 3.141592653589793238462643 |
Pricer properties | |
#define | PRICER_NAME "ringpacking" |
#define | PRICER_DESC "pricer for ringpacking" |
#define | PRICER_PRIORITY 0 |
#define | PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */ |
#define | DEFAULT_PRICING_NLPTILIM 1e+20 |
#define | DEFAULT_PRICING_NLPNODELIM 1000L |
#define | DEFAULT_PRICING_HEURTILIM 1e+20 |
#define | DEFAULT_PRICING_HEURITERLIM 1000 |
#define | DEFAULT_PRICING_TOTALTILIM 1e+20 |
Functions | |
Local methods | |
static SCIP_Real | getDensityUb (int n) |
static int | getNCircles (SCIP *scip, SCIP_Real rext, int demand, SCIP_Real width, SCIP_Real height, SCIP_Real lambda) |
static SCIP_RETCODE | addVariable (SCIP *scip, SCIP_PROBDATA *probdata, int *types, SCIP_Real *xs, SCIP_Real *ys, SCIP_Bool *ispacked, int nelems) |
static SCIP_RETCODE | extractVariablesMINLP (SCIP *scip, SCIP_PROBDATA *probdata, SCIP *subscip, SCIP_VAR **x, SCIP_VAR **y, SCIP_VAR **w, int *types, int nvars, SCIP_Bool *success) |
static void | computeScores (SCIP *scip, SCIP_Real *rexts, SCIP_RANDNUMGEN *randnumgen, int *elements, int nelements, SCIP_Real *lambdas, SCIP_Real *scores, int iter, int iterlim) |
static SCIP_RETCODE | solvePricingHeuristic (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PRICERDATA *pricerdata, SCIP_Real *lambdas, SCIP_Real timelim, int iterlim, SCIP_Bool *addedvar) |
static SCIP_RETCODE | solvePricingMINLP (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real *lambdas, SCIP_Real timelim, SCIP_Longint nodelim, SCIP_Bool *addedvar, SCIP_STATUS *solstat, SCIP_Real *dualbound) |
static | SCIP_DECL_PRICERFREE (pricerFreeRingpacking) |
static | SCIP_DECL_PRICERINIT (pricerInitRingpacking) |
static | SCIP_DECL_PRICEREXIT (pricerExitRingpacking) |
static | SCIP_DECL_PRICERREDCOST (pricerRedcostRingpacking) |
static | SCIP_DECL_PRICERFARKAS (pricerFarkasRingpacking) |
Interface methods | |
SCIP_RETCODE | SCIPincludePricerRpa (SCIP *scip) |
SCIP_RETCODE | SCIPpricerRpaActivate (SCIP *scip) |
#define PRICER_NAME "ringpacking" |
Definition at line 82 of file pricer_rpa.c.
#define PRICER_DESC "pricer for ringpacking" |
Definition at line 83 of file pricer_rpa.c.
#define PRICER_PRIORITY 0 |
Definition at line 84 of file pricer_rpa.c.
#define PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */ |
Definition at line 85 of file pricer_rpa.c.
#define DEFAULT_PRICING_NLPTILIM 1e+20 |
time limit for each pricing NLP
Definition at line 88 of file pricer_rpa.c.
Referenced by SCIPincludePricerRpa().
#define DEFAULT_PRICING_NLPNODELIM 1000L |
node limit for each pricing NLP
Definition at line 89 of file pricer_rpa.c.
Referenced by SCIPincludePricerRpa().
#define DEFAULT_PRICING_HEURTILIM 1e+20 |
time limit for each heuristic pricing
Definition at line 90 of file pricer_rpa.c.
Referenced by SCIPincludePricerRpa().
#define DEFAULT_PRICING_HEURITERLIM 1000 |
iteration limit for each heuristic pricing
Definition at line 91 of file pricer_rpa.c.
Referenced by SCIPincludePricerRpa().
#define DEFAULT_PRICING_TOTALTILIM 1e+20 |
total time limit for all pricing NLPs and heuristic calls
Definition at line 92 of file pricer_rpa.c.
Referenced by SCIPincludePricerRpa().
#define M_PI 3.141592653589793238462643 |
Definition at line 97 of file pricer_rpa.c.
Referenced by computeCurvatureSin(), computeLeftSecantSin(), computeRevPropIntervalSin(), computeRightSecantSin(), computeSecantSin(), computeSolTangentSin(), enumeratePatterns(), getDensityUb(), getNCircles(), readExpression(), SCIP_DECL_EXPRMONOTONICITY(), SCIP_DECL_EXPRMONOTONICITY(), setupProblem(), setupProblem(), and solvePricingMINLP().
|
static |
returns an upper bound on the density for n equal circles in a square (holds also for rectangles); this is a result of Groemer's formula (see, 'Ueber die Einlagerung von Kreisen in einen konvexen Bereich')
Definition at line 127 of file pricer_rpa.c.
References assert(), M_PI, SCIP_Real, and SQR.
Referenced by getNCircles().
|
static |
helper function to count how many circles of a given type are needed
scip | SCIP data structure |
rext | external radius |
demand | demand |
width | width of the rectangle |
height | height of the rectangle |
lambda | objective coefficient of each circle of the given type |
Definition at line 137 of file pricer_rpa.c.
References assert(), c, getDensityUb(), M_PI, MIN, ncircles, SCIP_Real, SCIPfeasFloor(), SCIPfloor(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisGT(), SCIPisLE(), and SQR.
Referenced by solvePricingHeuristic(), and solvePricingMINLP().
|
static |
adds a variable to the restricted master problem
scip | SCIP data structure |
probdata | problem data |
types | types of elements |
xs | x coordinate of each element |
ys | y coordinate of each element |
ispacked | checks whether an element has been packed (might be NULL) |
nelems | total number of elements |
Definition at line 183 of file pricer_rpa.c.
References assert(), i, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PACKABLE_YES, SCIP_Real, SCIP_VARTYPE_INTEGER, SCIPaddCoefLinear(), SCIPaddPricedVar(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPinfinity(), SCIPpatternAddElement(), SCIPpatternCreateRectangular(), SCIPpatternRelease(), SCIPpatternSetPackableStatus(), SCIPprobdataAddVar(), SCIPprobdataGetNTypes(), SCIPprobdataGetPatternConss(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarMarkDeletable(), SCIPvarSetInitial(), SCIPvarSetRemovable(), TRUE, and var.
Referenced by extractVariablesMINLP(), and solvePricingHeuristic().
|
static |
scip | SCIP data structure |
probdata | problem data |
subscip | sub-SCIP data structure |
x | x variables of sub-SCIP |
y | y variables of sub-SCIP |
w | w variables of sub-SCIP |
types | type corresponding to each variable |
nvars | number of variables |
success | pointer to store if we could add at least one variable with negative reduced costs |
Definition at line 257 of file pricer_rpa.c.
References addVariable(), assert(), FALSE, i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNSols(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPisFeasGE(), sol, TRUE, w, x, and y.
Referenced by solvePricingMINLP().
|
static |
array to compute the score of each element
scip | SCIP data structure |
rexts | external radii for each type |
randnumgen | random number generator |
elements | type of each element |
nelements | total number of elements |
lambdas | dual multipliers for each type |
scores | array to store the score of each element |
iter | iteration round |
iterlim | total iteration limit |
Definition at line 331 of file pricer_rpa.c.
References assert(), i, SCIP_Real, and SCIPrandomGetReal().
Referenced by solvePricingHeuristic().
|
static |
tries to find a column with negative reduced cost by using a greedy packing heuristic
scip | SCIP data structure |
probdata | problem data |
pricerdata | pricer data |
lambdas | dual multipliers for pattern constraints |
timelim | time limit |
iterlim | iteration limit |
addedvar | pointer to store whether a variable with negative reduced cost has been added |
Definition at line 384 of file pricer_rpa.c.
References addVariable(), assert(), computeScores(), FALSE, getNCircles(), i, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PATTERNTYPE_RECTANGULAR, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetTotalTime(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisGT(), SCIPisStopped(), SCIPpackCirclesGreedy(), SCIPprobdataGetDemands(), SCIPprobdataGetHeight(), SCIPprobdataGetNTypes(), SCIPprobdataGetRexts(), SCIPprobdataGetWidth(), SCIPsortDownRealInt(), and TRUE.
Referenced by SCIP_DECL_PRICERREDCOST().
|
static |
auxiliary function for solving the pricing problem exactly
scip | SCIP data structure |
probdata | problem data |
lambdas | dual multipliers for pattern constraints |
timelim | time limit |
nodelim | node limit |
addedvar | pointer to store whether a variable with negative reduced cost has been added |
solstat | pointer to store the solution status |
dualbound | pointer to store the dual bound |
Definition at line 511 of file pricer_rpa.c.
References assert(), c, extractVariablesMINLP(), FALSE, getNCircles(), i, M_PI, ncircles, NULL, nvars, obj, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PARAMSETTING_AGGRESSIVE, SCIP_Real, SCIP_STATUS_UNKNOWN, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPallocBlockMemoryArray, SCIPcreate(), SCIPcreateConsBasicLinear(), SCIPcreateConsQuadraticNonlinear(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPfree(), SCIPfreeBlockMemoryArray, SCIPgetDualbound(), SCIPgetStatus(), SCIPincludeDefaultPlugins(), SCIPinfinity(), SCIPprobdataGetDemands(), SCIPprobdataGetHeight(), SCIPprobdataGetNTypes(), SCIPprobdataGetRexts(), SCIPprobdataGetWidth(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetHeuristics(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetMessagehdlrQuiet(), SCIPsetRealParam(), SCIPsnprintf(), SCIPsolve(), SQR, TRUE, w, x, and y.
Referenced by SCIP_DECL_PRICERREDCOST().
|
static |
name Callback methods destructor of variable pricer to free user data (called when SCIP is exiting)
Definition at line 762 of file pricer_rpa.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemoryNull, and SCIPpricerGetData().
|
static |
initialization method of variable pricer (called after problem was transformed and pricer is active)
Definition at line 776 of file pricer_rpa.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPpricerGetData(), and TRUE.
|
static |
deinitialization method of variable pricer (called before transformed problem is freed and pricer is active)
Definition at line 790 of file pricer_rpa.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeRandom(), and SCIPpricerGetData().
|
static |
reduced cost pricing method of variable pricer for feasible LPs
Definition at line 803 of file pricer_rpa.c.
References assert(), MIN, MIN3, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_STATUS_OPTIMAL, SCIP_SUCCESS, SCIPallocBufferArray, SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfeasCeil(), SCIPfreeBufferArray, SCIPgetDepth(), SCIPgetDualsolLinear(), SCIPgetLPObjval(), SCIPgetProbData(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPinfoMessage(), SCIPisFeasGE(), SCIPpricerGetData(), SCIPprobdataGetNTypes(), SCIPprobdataGetPatternConss(), SCIPprobdataInvalidateDualbound(), SCIPprobdataIsDualboundInvalid(), SCIPprobdataUpdateDualbound(), solvePricingHeuristic(), and solvePricingMINLP().
|
static |
farkas pricing method of variable pricer for infeasible LPs
Definition at line 902 of file pricer_rpa.c.
SCIP_RETCODE SCIPincludePricerRpa | ( | SCIP * | scip | ) |
creates the ringpacking variable pricer and includes it in SCIP
scip | SCIP data structure |
Definition at line 920 of file pricer_rpa.c.
References BMSclearMemory, DEFAULT_PRICING_HEURITERLIM, DEFAULT_PRICING_HEURTILIM, DEFAULT_PRICING_NLPNODELIM, DEFAULT_PRICING_NLPTILIM, DEFAULT_PRICING_TOTALTILIM, FALSE, NULL, PRICER_DELAY, PRICER_DESC, PRICER_NAME, PRICER_PRIORITY, SCIP_CALL, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddIntParam(), SCIPaddLongintParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPincludePricerBasic(), SCIPsetPricerExit(), SCIPsetPricerFree(), and SCIPsetPricerInit().
Referenced by runShell().
SCIP_RETCODE SCIPpricerRpaActivate | ( | SCIP * | scip | ) |
added problem specific data to pricer and activates pricer
scip | SCIP data structure |
Definition at line 969 of file pricer_rpa.c.
References assert(), NULL, PRICER_NAME, SCIP_CALL, SCIP_OKAY, SCIPactivatePricer(), and SCIPfindPricer().
Referenced by SCIPprobdataCreate().