Detailed Description

Ringpacking variable pricer.

Author: Benjamin Mueller

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)

Macro Definition Documentation

◆ PRICER_NAME

#define PRICER_NAME "ringpacking"

Definition at line 82 of file pricer_rpa.c.

◆ PRICER_DESC

#define PRICER_DESC "pricer for ringpacking"

Definition at line 83 of file pricer_rpa.c.

◆ PRICER_PRIORITY

#define PRICER_PRIORITY 0

Definition at line 84 of file pricer_rpa.c.

◆ PRICER_DELAY

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

◆ DEFAULT_PRICING_NLPTILIM

#define DEFAULT_PRICING_NLPTILIM 1e+20

time limit for each pricing NLP

Definition at line 88 of file pricer_rpa.c.

◆ DEFAULT_PRICING_NLPNODELIM

#define DEFAULT_PRICING_NLPNODELIM 1000L

node limit for each pricing NLP

Definition at line 89 of file pricer_rpa.c.

◆ DEFAULT_PRICING_HEURTILIM

#define DEFAULT_PRICING_HEURTILIM 1e+20

time limit for each heuristic pricing

Definition at line 90 of file pricer_rpa.c.

◆ DEFAULT_PRICING_HEURITERLIM

#define DEFAULT_PRICING_HEURITERLIM 1000

iteration limit for each heuristic pricing

Definition at line 91 of file pricer_rpa.c.

◆ DEFAULT_PRICING_TOTALTILIM

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

◆ M_PI

#define M_PI 3.141592653589793238462643

Definition at line 97 of file pricer_rpa.c.

Function Documentation

◆ getDensityUb()

static SCIP_Real getDensityUb ( int n )

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 M_PI, and SQR.

Referenced by getNCircles().

◆ getNCircles()

static int getNCircles	(	SCIP *	scip,
		SCIP_Real	rext,
		int	demand,
		SCIP_Real	width,
		SCIP_Real	height,
		SCIP_Real	lambda
	)

static

helper function to count how many circles of a given type are needed

Parameters

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 getDensityUb(), M_PI, MIN, ncircles, SCIP_Real, SCIPfeasFloor(), SCIPfloor(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisGT(), SCIPisLE(), and SQR.

Referenced by solvePricingHeuristic(), and solvePricingMINLP().

◆ addVariable()

static SCIP_RETCODE addVariable	(	SCIP *	scip,
		SCIP_PROBDATA *	probdata,
		int *	types,
		SCIP_Real *	xs,
		SCIP_Real *	ys,
		SCIP_Bool *	ispacked,
		int	nelems
	)

static

adds a variable to the restricted master problem

Parameters

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 NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PACKABLE_YES, SCIP_VARTYPE_INTEGER, SCIPaddCoefLinear(), SCIPaddPricedVar(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPinfinity(), SCIPpatternAddElement(), SCIPpatternCreateRectangular(), SCIPpatternRelease(), SCIPpatternSetPackableStatus(), SCIPprobdataAddVar(), SCIPprobdataGetNTypes(), SCIPprobdataGetPatternConss(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarMarkDeletable(), SCIPvarSetInitial(), SCIPvarSetRemovable(), and TRUE.

Referenced by extractVariablesMINLP(), and solvePricingHeuristic().

◆ extractVariablesMINLP()

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

Parameters

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(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNSols(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPisFeasGE(), TRUE, w, x, and y.

Referenced by solvePricingMINLP().

◆ computeScores()

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

array to compute the score of each element

Parameters

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 SCIP_Real, and SCIPrandomGetReal().

Referenced by solvePricingHeuristic().

◆ solvePricingHeuristic()

static SCIP_RETCODE solvePricingHeuristic	(	SCIP *	scip,
		SCIP_PROBDATA *	probdata,
		SCIP_PRICERDATA *	pricerdata,
		SCIP_Real *	lambdas,
		SCIP_Real	timelim,
		int	iterlim,
		SCIP_Bool *	addedvar
	)

static

tries to find a column with negative reduced cost by using a greedy packing heuristic

Parameters

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(), computeScores(), FALSE, getNCircles(), 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().

◆ solvePricingMINLP()

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

auxiliary function for solving the pricing problem exactly

Parameters

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 extractVariablesMINLP(), FALSE, getNCircles(), M_PI, ncircles, NULL, SCIP_CALL, 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().

◆ SCIP_DECL_PRICERFREE()

static SCIP_DECL_PRICERFREE ( pricerFreeRingpacking )

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 NULL, SCIP_OKAY, SCIPfreeBlockMemoryNull, and SCIPpricerGetData().

◆ SCIP_DECL_PRICERINIT()

static SCIP_DECL_PRICERINIT ( pricerInitRingpacking )

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 NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPpricerGetData(), and TRUE.

◆ SCIP_DECL_PRICEREXIT()

static SCIP_DECL_PRICEREXIT ( pricerExitRingpacking )

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 NULL, SCIP_OKAY, SCIPfreeRandom(), and SCIPpricerGetData().

◆ SCIP_DECL_PRICERREDCOST()

static SCIP_DECL_PRICERREDCOST ( pricerRedcostRingpacking )

static

reduced cost pricing method of variable pricer for feasible LPs

Definition at line 803 of file pricer_rpa.c.

References MIN, MIN3, NULL, 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().

◆ SCIP_DECL_PRICERFARKAS()

static SCIP_DECL_PRICERFARKAS ( pricerFarkasRingpacking )

static

farkas pricing method of variable pricer for infeasible LPs

Definition at line 902 of file pricer_rpa.c.

References SCIP_OKAY, and SCIPABORT.

◆ SCIPincludePricerRpa()

SCIP_RETCODE SCIPincludePricerRpa ( SCIP * scip )

creates the ringpacking variable pricer and includes it in SCIP

Parameters

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

◆ SCIPpricerRpaActivate()

SCIP_RETCODE SCIPpricerRpaActivate ( SCIP * scip )

added problem specific data to pricer and activates pricer

Parameters

scip	SCIP data structure

Definition at line 969 of file pricer_rpa.c.

References NULL, PRICER_NAME, SCIP_CALL, SCIP_OKAY, SCIPactivatePricer(), and SCIPfindPricer().

Referenced by SCIPprobdataCreate().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PRICER_NAME

◆ PRICER_DESC

◆ PRICER_PRIORITY

◆ PRICER_DELAY

◆ DEFAULT_PRICING_NLPTILIM

◆ DEFAULT_PRICING_NLPNODELIM

◆ DEFAULT_PRICING_HEURTILIM

◆ DEFAULT_PRICING_HEURITERLIM

◆ DEFAULT_PRICING_TOTALTILIM

◆ M_PI

Function Documentation

◆ getDensityUb()

◆ getNCircles()

◆ addVariable()

◆ extractVariablesMINLP()

◆ computeScores()

◆ solvePricingHeuristic()

◆ solvePricingMINLP()

◆ SCIP_DECL_PRICERFREE()

◆ SCIP_DECL_PRICERINIT()

◆ SCIP_DECL_PRICEREXIT()

◆ SCIP_DECL_PRICERREDCOST()

◆ SCIP_DECL_PRICERFARKAS()

◆ SCIPincludePricerRpa()

◆ SCIPpricerRpaActivate()