probdata_rpa.c File Reference

Detailed Description

Problem data for ringpacking problem.

Author

Benjamin Mueller

This file handles the main problem data used in that project. For more details see Main problem data page.

Definition in file probdata_rpa.c.

#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "probdata_rpa.h"
#include "pricer_rpa.h"
#include <string.h>
#include <math.h>

Go to the source code of this file.

Macros
#define	TABLE_NAME_RPA   "ringpacking"
#define	TABLE_DESC_RPA   "ringpacking statistics"
#define	TABLE_POSITION_RPA   12500
#define	TABLE_EARLIEST_STAGE_RPA   SCIP_STAGE_TRANSFORMED
#define	M_PI   3.141592653589793238462643

Functions
Local methods
static SCIP_RETCODE	probdataCreate (SCIP *scip, SCIP_PROBDATA **probdata, SCIP_CONS **patternconss, SCIP_PATTERN **cpatterns, SCIP_VAR **cvars, int ncpatterns, SCIP_PATTERN **rpatterns, SCIP_VAR **rvars, int nrpatterns, int *demands, SCIP_Real *rints, SCIP_Real *rexts, int ntypes, SCIP_Real width, SCIP_Real height)
static SCIP_RETCODE	probdataFree (SCIP *scip, SCIP_PROBDATA **probdata)
static int	getNCPatterns (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PACKABLE status)
static SCIP_RETCODE	ensureSize (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERNTYPE type, int size)
static SCIP_RETCODE	createPatternVars (SCIP *scip, SCIP_PROBDATA *probdata)
static int	maxCircles (SCIP *scip, SCIP_PROBDATA *probdata, int type, int elemtype)
static int	isPatternDominating (SCIP_PATTERN *p, SCIP_PATTERN *q, int *count, int ntypes)
static SCIP_RETCODE	filterPatterns (SCIP *scip, SCIP_PROBDATA *probdata)
static SCIP_RETCODE	enumeratePatterns (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, int *ms, int *nselected, SCIP_Real nlptilim, SCIP_Real heurtilim, SCIP_Longint nlpnodelim, int heuriterlim, SCIP_Real *timeleft)
static SCIP_RETCODE	setupProblem (SCIP *scip, SCIP_PROBDATA *probdata)
static	SCIP_DECL_TABLEOUTPUT (tableOutputRpa)
static void	updateBestCandidate (SCIP *scip, SCIP_Real *xs, SCIP_Real *ys, SCIP_Real *rexts, SCIP_Real rext, SCIP_Real rbounding, SCIP_Real wbounding, SCIP_Real hbounding, SCIP_Real rmax, SCIP_PATTERNTYPE patterntype, SCIP_Bool *ispacked, int *elements, int nelements, SCIP_Real *bestx, SCIP_Real *besty, SCIP_Real x, SCIP_Real y, int ncalls)
static void	computePosRingCircle (SCIP *scip, int *elements, int nelements, SCIP_Real *rexts, SCIP_Real *xs, SCIP_Real *ys, int pos, SCIP_Bool *ispacked, SCIP_Real rmax, SCIP_Real rbound, SCIP_Real *bestx, SCIP_Real *besty, int ncalls)
static void	computePosTrivial (SCIP *scip, int *elements, int nelements, SCIP_Real *rexts, SCIP_Real *xs, SCIP_Real *ys, int pos, SCIP_Bool *ispacked, SCIP_Real rmax, SCIP_Real rbound, SCIP_Real width, SCIP_Real height, SCIP_PATTERNTYPE patterntype, SCIP_Real *bestx, SCIP_Real *besty, int ncalls)
static void	computePosRectangleCircle (SCIP *scip, int *elements, int nelements, SCIP_Real *rexts, SCIP_Real *xs, SCIP_Real *ys, int pos, SCIP_Bool *ispacked, SCIP_Real rmax, SCIP_Real width, SCIP_Real height, SCIP_Real *bestx, SCIP_Real *besty, int ncalls)
static void	computePosCircleCircle (SCIP *scip, int *elements, int nelements, SCIP_Real *rexts, SCIP_Real *xs, SCIP_Real *ys, int pos, SCIP_Bool *ispacked, SCIP_Real rmax, SCIP_Real rbound, SCIP_Real width, SCIP_Real height, SCIP_PATTERNTYPE patterntype, SCIP_Real *bestx, SCIP_Real *besty, int ncalls)
static void	computeScores (SCIP *scip, SCIP_PROBDATA *probdata, int *elements, int nelements, SCIP_Real *scores, int iter)
Callback methods of problem data
static	SCIP_DECL_PROBDELORIG (probdelorigRingpacking)
static	SCIP_DECL_PROBDELTRANS (probdeltransRingpacking)
static	SCIP_DECL_PROBTRANS (probtransRingpacking)
Interface methods
SCIP_RETCODE	SCIPprobdataCreate (SCIP *scip, const char *probname, int *demands, SCIP_Real *rints, SCIP_Real *rexts, int ntypes, SCIP_Real width, SCIP_Real height)
SCIP_RETCODE	SCIPprobdataSetupProblem (SCIP *scip)
SCIP_RETCODE	SCIPprobdataEnumeratePatterns (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real nlptilim, SCIP_Real heurtilim, SCIP_Real totaltilim, SCIP_Longint nlpnodelim, int heuriterlim)
int	SCIPprobdataGetNTypes (SCIP_PROBDATA *probdata)
SCIP_Real *	SCIPprobdataGetRexts (SCIP_PROBDATA *probdata)
SCIP_Real *	SCIPprobdataGetRints (SCIP_PROBDATA *probdata)
int *	SCIPprobdataGetDemands (SCIP_PROBDATA *probdata)
SCIP_Real	SCIPprobdataGetWidth (SCIP_PROBDATA *probdata)
SCIP_Real	SCIPprobdataGetHeight (SCIP_PROBDATA *probdata)
void	SCIPprobdataGetCInfos (SCIP_PROBDATA *probdata, SCIP_PATTERN ***cpatterns, SCIP_VAR ***cvars, int *ncpatterns)
void	SCIPprobdataGetRInfos (SCIP_PROBDATA *probdata, SCIP_PATTERN ***rpatterns, SCIP_VAR ***rvars, int *nrpatterns)
SCIP_CONS **	SCIPprobdataGetPatternConss (SCIP_PROBDATA *probdata)
SCIP_RETCODE	SCIPprobdataAddVar (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_VAR *var)
void	SCIPprobdataUpdateDualbound (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real dualbound)
void	SCIPprobdataInvalidateDualbound (SCIP *scip, SCIP_PROBDATA *probdata)
SCIP_Bool	SCIPprobdataIsDualboundInvalid (SCIP_PROBDATA *probdata)
void	SCIPpackCirclesGreedy (SCIP *scip, SCIP_Real *rexts, SCIP_Real *xs, SCIP_Real *ys, SCIP_Real rbounding, SCIP_Real width, SCIP_Real height, SCIP_Bool *ispacked, int *elements, int nelements, SCIP_PATTERNTYPE patterntype, int *npacked, int ncalls)
SCIP_RETCODE	SCIPverifyCircularPatternHeuristic (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, int iterlim)
SCIP_RETCODE	SCIPverifyCircularPatternNLP (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, SCIP_Longint nodelim)
void	SCIPcheckPattern (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)

Macro Definition Documentation

TABLE_NAME_RPA

#define TABLE_NAME_RPA   "ringpacking"

Definition at line 59 of file probdata_rpa.c.

Referenced by SCIPprobdataCreate().

TABLE_DESC_RPA

#define TABLE_DESC_RPA   "ringpacking statistics"

Definition at line 60 of file probdata_rpa.c.

Referenced by SCIPprobdataCreate().

TABLE_POSITION_RPA

#define TABLE_POSITION_RPA   12500

the position of the statistics table

Definition at line 61 of file probdata_rpa.c.

Referenced by SCIPprobdataCreate().

TABLE_EARLIEST_STAGE_RPA

#define TABLE_EARLIEST_STAGE_RPA   SCIP_STAGE_TRANSFORMED

output of the statistics table is only printed from this stage onwards

Definition at line 62 of file probdata_rpa.c.

Referenced by SCIPprobdataCreate().

M_PI

#define M_PI   3.141592653589793238462643

Definition at line 65 of file probdata_rpa.c.

Referenced by enumeratePatterns(), and setupProblem().

Function Documentation

probdataCreate()

static SCIP_RETCODE probdataCreate ( SCIP *  scip, SCIP_PROBDATA **  probdata, SCIP_CONS **  patternconss, SCIP_PATTERN **  cpatterns, SCIP_VAR **  cvars, int  ncpatterns, SCIP_PATTERN **  rpatterns, SCIP_VAR **  rvars, int  nrpatterns, int *  demands, SCIP_Real *  rints, SCIP_Real *  rexts, int  ntypes, SCIP_Real  width, SCIP_Real  height  )

static

auxiliary function to create problem data;

Note

captures patterns and corresponding variables

Parameters

scip	SCIP data structure
probdata	pointer to problem data
patternconss	pattern constraints
cpatterns	circular patterns
cvars	variables corresponding to circular patterns
ncpatterns	total number of circular patterns
rpatterns	rectangular patterns
rvars	variables corresponding to rectangular patterns
nrpatterns	total number of rectangular patterns
demands	array containing the demands
rints	interal radii of each ring
rexts	external radii of each ring
ntypes	number of different types
width	width of each rectangle
height	height of each rectangle

Definition at line 125 of file probdata_rpa.c.

References BMSclearMemory, BMSclearMemoryArray, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcreateRandom(), SCIPduplicateBlockMemoryArray, SCIPpatternCapture(), and TRUE.

Referenced by SCIP_DECL_PROBTRANS(), and SCIPprobdataCreate().

probdataFree()

static SCIP_RETCODE probdataFree ( SCIP *  scip, SCIP_PROBDATA **  probdata  )

static

auxiliary function to free problem data

Parameters

scip	SCIP data structure
probdata	pointer to release the probdata

Definition at line 208 of file probdata_rpa.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeRandom(), SCIPpatternRelease(), SCIPprobdataGetNTypes(), SCIPreleaseCons(), SCIPreleaseVar(), and SCIPsetProbData().

Referenced by SCIP_DECL_PROBDELORIG(), and SCIP_DECL_PROBDELTRANS().

getNCPatterns()

static int getNCPatterns ( SCIP *  scip, SCIP_PROBDATA *  probdata, SCIP_PACKABLE  status  )

static

counts the number of circular patterns with a given packable status

Parameters

scip	SCIP data structure
probdata	problem data
status	packable status

Definition at line 283 of file probdata_rpa.c.

References NULL, and SCIPpatternGetPackableStatus().

Referenced by SCIP_DECL_TABLEOUTPUT(), and setupProblem().

ensureSize()

static SCIP_RETCODE ensureSize ( SCIP *  scip, SCIP_PROBDATA *  probdata, SCIP_PATTERNTYPE  type, int  size  )

static

ensures a minimum size of the pattern and variable arrays

Parameters

scip	SCIP data structure
probdata	problem data
type	pattern type
size	required size

Definition at line 305 of file probdata_rpa.c.

References MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PATTERNTYPE_CIRCULAR, SCIP_PATTERNTYPE_RECTANGULAR, and SCIPreallocBlockMemoryArray.

Referenced by SCIPprobdataAddVar().

createPatternVars()

static SCIP_RETCODE createPatternVars ( SCIP *  scip, SCIP_PROBDATA *  probdata  )

static

create variables for all existing circular and rectangular patterns

Parameters

scip	SCIP data structure
probdata	problem data

Definition at line 339 of file probdata_rpa.c.

References NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_INTEGER, SCIPaddVar(), SCIPcreateVarBasic(), SCIPinfinity(), SCIPpatternGetCircleType(), SCIPpatternGetElementType(), SCIPpatternGetNElemens(), SCIPprobdataGetDemands(), and SCIPsnprintf().

Referenced by setupProblem().

maxCircles()

static int maxCircles ( SCIP *  scip, SCIP_PROBDATA *  probdata, int  type, int  elemtype  )

static

upper bound on the number of circles of a single type that fit into a circular pattern of a given type

Parameters

scip	SCIP data structure
probdata	problem data
type	type of the circular pattern
elemtype	type of element to pack

Definition at line 416 of file probdata_rpa.c.

References SCIP_Real, SCIPceil(), SCIPisLT(), SCIPprobdataGetDemands(), SCIPprobdataGetNTypes(), SCIPprobdataGetRexts(), and SCIPprobdataGetRints().

Referenced by SCIPprobdataEnumeratePatterns().

isPatternDominating()

static int isPatternDominating ( SCIP_PATTERN *  p, SCIP_PATTERN *  q, int *  count, int  ntypes  )

static

helper function to compare two patterns; returns

-1 if p dominates q +1 if q dominates p 0 otherwise

Parameters

p	pattern
q	pattern
count	array for counting elements of patterns
ntypes	total number of types

Definition at line 471 of file probdata_rpa.c.

References BMSclearMemoryArray, FALSE, SCIP_Bool, SCIP_PACKABLE_UNKNOWN, SCIP_PACKABLE_YES, SCIPpatternGetCircleType(), SCIPpatternGetElementType(), SCIPpatternGetNElemens(), SCIPpatternGetPackableStatus(), and TRUE.

Referenced by filterPatterns().

filterPatterns()

static SCIP_RETCODE filterPatterns ( SCIP *  scip, SCIP_PROBDATA *  probdata  )

static

filter dominated patterns

Parameters

scip	SCIP data structure
probdata	problem data

Definition at line 523 of file probdata_rpa.c.

References BMSclearMemoryArray, BMScopyMemoryArray, isPatternDominating(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPpatternRelease(), SCIPprobdataGetNTypes(), and TRUE.

Referenced by SCIPprobdataEnumeratePatterns().

enumeratePatterns()

static SCIP_RETCODE enumeratePatterns ( SCIP *  scip, SCIP_PROBDATA *  probdata, SCIP_PATTERN *  pattern, int *  ms, int *  nselected, SCIP_Real  nlptilim, SCIP_Real  heurtilim, SCIP_Longint  nlpnodelim, int  heuriterlim, SCIP_Real *  timeleft  )

static

enumerates all circular patterns for a given type

Parameters

scip	SCIP data structure
probdata	problem data
pattern	pattern (passed for performance reasons)
ms	maximum number of elements for each type (passed for performance reasons)
nselected	number of selected elements for each type (passed for performance reasons)
nlptilim	time limit for each NLP verification
heurtilim	time limit for each call of the heuristics
nlpnodelim	node limit for each NLP verification
heuriterlim	iteration limit for each call of the heuristics
timeleft	pointer to update the remaining time for the enumeration

Definition at line 594 of file probdata_rpa.c.

References M_PI, NULL, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_PACKABLE_NO, SCIP_PACKABLE_UNKNOWN, SCIP_Real, SCIPdebugMsg, SCIPdebugMsgPrint, SCIPgetTotalTime(), SCIPisGT(), SCIPisLE(), SCIPisZero(), SCIPpatternAddElement(), SCIPpatternGetCircleType(), SCIPpatternGetElementType(), SCIPpatternGetNElemens(), SCIPpatternGetPackableStatus(), SCIPpatternRemoveLastElements(), SCIPpatternSetPackableStatus(), SCIPprobdataAddVar(), SCIPprobdataGetNTypes(), SCIPprobdataGetRexts(), SCIPprobdataGetRints(), SCIPverifyCircularPatternHeuristic(), SCIPverifyCircularPatternNLP(), and TRUE.

Referenced by SCIPprobdataEnumeratePatterns().

setupProblem()

static SCIP_RETCODE setupProblem ( SCIP *  scip, SCIP_PROBDATA *  probdata  )

static

auxiliary function to setup the master problem

Parameters

scip	SCIP data structure
probdata	problem data

Definition at line 722 of file probdata_rpa.c.

References createPatternVars(), getNCPatterns(), M_PI, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OBJSENSE_MINIMIZE, SCIP_OKAY, SCIP_PACKABLE_UNKNOWN, SCIP_PACKABLE_YES, SCIP_PATTERNTYPE_CIRCULAR, SCIP_PATTERNTYPE_RECTANGULAR, SCIP_Real, SCIPaddCoefLinear(), SCIPaddCons(), SCIPcreateConsBasicLinear(), SCIPfeasCeil(), SCIPgetTotalTime(), SCIPinfinity(), SCIPinfoMessage(), SCIPisFeasLT(), SCIPpatternAddElement(), SCIPpatternCountElements(), SCIPpatternCreateRectangular(), SCIPpatternGetCircleType(), SCIPpatternGetPatternType(), SCIPpatternRelease(), SCIPpatternSetPackableStatus(), SCIPprobdataAddVar(), SCIPprobdataEnumeratePatterns(), SCIPprobdataGetDemands(), SCIPprobdataGetHeight(), SCIPprobdataGetNTypes(), SCIPprobdataGetRexts(), SCIPprobdataGetRints(), SCIPprobdataGetWidth(), SCIPprobdataUpdateDualbound(), SCIPreleaseCons(), SCIPsetConsModifiable(), SCIPsetObjIntegral(), SCIPsetObjsense(), SCIPsnprintf(), SCIPupdateLocalDualbound(), and TRUE.

Referenced by SCIPprobdataSetupProblem().

SCIP_DECL_TABLEOUTPUT()

static SCIP_DECL_TABLEOUTPUT ( tableOutputRpa  )

static

output method of statistics table to output file stream 'file'

Definition at line 901 of file probdata_rpa.c.

References getNCPatterns(), MAX, NULL, SCIP_OKAY, SCIP_PACKABLE_NO, SCIP_PACKABLE_UNKNOWN, SCIP_Real, SCIPgetDualbound(), SCIPgetProbData(), SCIPinfinity(), SCIPinfoMessage(), SCIPisGE(), SCIPprobdataGetDemands(), SCIPprobdataGetHeight(), SCIPprobdataGetNTypes(), SCIPprobdataGetRexts(), SCIPprobdataGetRints(), and SCIPprobdataGetWidth().

updateBestCandidate()

static void updateBestCandidate ( SCIP *  scip, SCIP_Real *  xs, SCIP_Real *  ys, SCIP_Real *  rexts, SCIP_Real  rext, SCIP_Real  rbounding, SCIP_Real  wbounding, SCIP_Real  hbounding, SCIP_Real  rmax, SCIP_PATTERNTYPE  patterntype, SCIP_Bool *  ispacked, int *  elements, int  nelements, SCIP_Real *  bestx, SCIP_Real *  besty, SCIP_Real  x, SCIP_Real  y, int  ncalls  )

static

auxiliary function to update the best known candidate

Parameters

scip	SCIP data structure
xs	x-coordinates of packed elements
ys	y-coordinates of packed elements
rexts	radii of packed elements
rext	radii of element that should be packed
rbounding	inner radius of bounding circle (ignored for rectangular patterns)
wbounding	width of bounding rectangular (ignored for circular patterns)
hbounding	height of bounding rectangular (ignored for circular patterns)
rmax	maximum radius of elements in the pattern
patterntype	pattern type
ispacked	array indicating which elements are already packed
elements	the order of the elements in the pattern
nelements	the total number of elements
bestx	buffer to update best x-coordinate
besty	buffer to update best y-coordinate
x	x-coordinate of a candidate point
y	y-coordinate of a candidate point
ncalls	total number of calls of the packing heuristic

Definition at line 965 of file probdata_rpa.c.

References SCIP_Bool, SCIP_INVALID, SCIP_PATTERNTYPE_CIRCULAR, SCIP_PATTERNTYPE_RECTANGULAR, SCIP_Real, SCIPisEQ(), SCIPisGT(), SCIPisLT(), x, and y.

Referenced by computePosCircleCircle(), computePosRectangleCircle(), computePosRingCircle(), and computePosTrivial().

computePosRingCircle()

static void computePosRingCircle ( SCIP *  scip, int *  elements, int  nelements, SCIP_Real *  rexts, SCIP_Real *  xs, SCIP_Real *  ys, int  pos, SCIP_Bool *  ispacked, SCIP_Real  rmax, SCIP_Real  rbound, SCIP_Real *  bestx, SCIP_Real *  besty, int  ncalls  )

static

auxiliary function for computing a candidate position between a circle and the outer ring

Parameters

scip	SCIP data structure
elements	types of elements that have been packed
nelements	the total number of elements
rexts	external radii
xs	x-coordinate of circle
ys	y-coordinate of circle
pos	position of element in the elements array
ispacked	array indicating whether an element has been packed already
rmax	maximum radius of elements in the pattern
rbound	radius of bounding circle
bestx	pointer to store the best x-coordinate
besty	pointer to store the best y-coordinate
ncalls	total number of calls of the packing heuristic

Definition at line 1038 of file probdata_rpa.c.

References a, b, h, MAX, SCIP_PATTERNTYPE_CIRCULAR, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisZero(), and updateBestCandidate().

Referenced by SCIPpackCirclesGreedy().

computePosTrivial()

static void computePosTrivial ( SCIP *  scip, int *  elements, int  nelements, SCIP_Real *  rexts, SCIP_Real *  xs, SCIP_Real *  ys, int  pos, SCIP_Bool *  ispacked, SCIP_Real  rmax, SCIP_Real  rbound, SCIP_Real  width, SCIP_Real  height, SCIP_PATTERNTYPE  patterntype, SCIP_Real *  bestx, SCIP_Real *  besty, int  ncalls  )

static

auxiliary function for computing trivial candidate positions

Parameters

scip	SCIP data structure
elements	types of elements that have been packed
nelements	the total number of elements
rexts	external radii
xs	x-coordinate of circle
ys	y-coordinate of circle
pos	position of element in the elements array
ispacked	array indicating whether an element has been packed already
rmax	maximum radius of elements in the pattern
rbound	radius of bounding circle
width	width of the rectangle
height	height of the rectangle
patterntype	the pattern type (rectangular or circular)
bestx	pointer to store the best x-coordinate
besty	pointer to store the best y-coordinate
ncalls	total number of calls of the packing heuristic

Definition at line 1108 of file probdata_rpa.c.

References SCIP_PATTERNTYPE_CIRCULAR, SCIP_Real, and updateBestCandidate().

Referenced by SCIPpackCirclesGreedy().

computePosRectangleCircle()

static void computePosRectangleCircle ( SCIP *  scip, int *  elements, int  nelements, SCIP_Real *  rexts, SCIP_Real *  xs, SCIP_Real *  ys, int  pos, SCIP_Bool *  ispacked, SCIP_Real  rmax, SCIP_Real  width, SCIP_Real  height, SCIP_Real *  bestx, SCIP_Real *  besty, int  ncalls  )

static

auxiliary function for computing a candidate position between a circle and the rectangle

Parameters

scip	SCIP data structure
elements	types of elements that have been packed
nelements	the total number of elements
rexts	external radii
xs	x-coordinate of circle
ys	y-coordinate of circle
pos	position of element in the elements array
ispacked	array indicating whether an element has been packed already
rmax	maximum radius of elements in the pattern
width	width of the rectangle
height	height of the rectangle
bestx	pointer to store the best x-coordinate
besty	pointer to store the best y-coordinate
ncalls	total number of calls of the packing heuristic

Definition at line 1152 of file probdata_rpa.c.

References SCIP_PATTERNTYPE_RECTANGULAR, SCIP_Real, and updateBestCandidate().

Referenced by SCIPpackCirclesGreedy().

computePosCircleCircle()

static void computePosCircleCircle ( SCIP *  scip, int *  elements, int  nelements, SCIP_Real *  rexts, SCIP_Real *  xs, SCIP_Real *  ys, int  pos, SCIP_Bool *  ispacked, SCIP_Real  rmax, SCIP_Real  rbound, SCIP_Real  width, SCIP_Real  height, SCIP_PATTERNTYPE  patterntype, SCIP_Real *  bestx, SCIP_Real *  besty, int  ncalls  )

static

auxiliary function for computing a candidate position between two circles

Parameters

scip	SCIP data structure
elements	types of elements that have been packed
nelements	the total number of elements
rexts	external radii
xs	x-coordinate of circle
ys	y-coordinate of circle
pos	position of element in the elements array
ispacked	array indicating whether an element has been packed already
rmax	maximum radius of elements in the pattern
rbound	radius of bounding circle
width	width of the rectangle
height	height of the rectangle
patterntype	the pattern type (rectangular or circular)
bestx	pointer to store the best x-coordinate
besty	pointer to store the best y-coordinate
ncalls	total number of calls of the packing heuristic

Definition at line 1220 of file probdata_rpa.c.

References a, b, h, MAX, SCIP_Real, SCIPisGE(), and updateBestCandidate().

Referenced by SCIPpackCirclesGreedy().

computeScores()

static void computeScores ( SCIP *  scip, SCIP_PROBDATA *  probdata, int *  elements, int  nelements, SCIP_Real *  scores, int  iter  )

static

array to compute the score of each element

Parameters

scip	SCIP data structure
probdata	problem data
elements	type of each element
nelements	total number of elements
scores	array to store the score of each element
iter	iteration round

Definition at line 1293 of file probdata_rpa.c.

References NULL, SCIP_Real, SCIPprobdataGetRexts(), and SCIPrandomGetReal().

Referenced by SCIPverifyCircularPatternHeuristic().

SCIP_DECL_PROBDELORIG()

static SCIP_DECL_PROBDELORIG ( probdelorigRingpacking  )

static

frees user data of original problem (called when the original problem is freed)

Definition at line 1342 of file probdata_rpa.c.

References probdataFree(), SCIP_CALL, SCIP_OKAY, and SCIPdebugMessage.

SCIP_DECL_PROBDELTRANS()

static SCIP_DECL_PROBDELTRANS ( probdeltransRingpacking  )

static

frees user data of transformed problem (called when the transformed problem is freed)

Definition at line 1352 of file probdata_rpa.c.

References probdataFree(), SCIP_CALL, SCIP_OKAY, and SCIPdebugMessage.

SCIP_DECL_PROBTRANS()

static SCIP_DECL_PROBTRANS ( probtransRingpacking  )

static

creates user data of transformed problem by transforming the original user problem data (called after problem was transformed)

Definition at line 1363 of file probdata_rpa.c.

References probdataCreate(), SCIP_CALL, SCIP_OKAY, SCIPtransformConss(), and SCIPtransformVars().

SCIPprobdataCreate()

SCIP_RETCODE SCIPprobdataCreate	(	SCIP *	scip,
		const char *	probname,
		int *	demands,
		SCIP_Real *	rints,
		SCIP_Real *	rexts,
		int	ntypes,
		SCIP_Real	width,
		SCIP_Real	height
	)

sets up the problem data

Parameters

scip	SCIP data structure
probname	problem name
demands	array containing the demands
rints	internal radii of each ring
rexts	external radii of each ring (assumed to be sorted)
ntypes	number of different types
width	width of each rectangle
height	height of each rectangle

Definition at line 1396 of file probdata_rpa.c.

References NULL, probdataCreate(), SCIP_CALL, SCIP_OKAY, SCIPcreateProbBasic(), SCIPfindTable(), SCIPincludeTable(), SCIPpricerRpaActivate(), SCIPsetProbData(), SCIPsetProbDelorig(), SCIPsetProbDeltrans(), SCIPsetProbTrans(), TABLE_DESC_RPA, TABLE_EARLIEST_STAGE_RPA, TABLE_NAME_RPA, TABLE_POSITION_RPA, and TRUE.

Referenced by SCIP_DECL_READERREAD().

SCIPprobdataSetupProblem()

SCIP_RETCODE SCIPprobdataSetupProblem

(

SCIP *

scip

)

enumerates circular patterns and creates restricted master problem

Parameters

scip	SCIP data structure

Definition at line 1443 of file probdata_rpa.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPgetIntParam(), SCIPgetLongintParam(), SCIPgetProbData(), SCIPgetRealParam(), and setupProblem().

Referenced by SCIP_DECL_READERREAD().

SCIPprobdataEnumeratePatterns()

SCIP_RETCODE SCIPprobdataEnumeratePatterns	(	SCIP *	scip,
		SCIP_PROBDATA *	probdata,
		SCIP_Real	nlptilim,
		SCIP_Real	heurtilim,
		SCIP_Real	totaltilim,
		SCIP_Longint	nlpnodelim,
		int	heuriterlim
	)

enumerate all non-dominated circular patterns

Parameters

scip	SCIP data structure
probdata	problem data
nlptilim	time limit for each NLP verification
heurtilim	time limit for each call of the heuristics
totaltilim	total time limit for enumeration
nlpnodelim	node limit for each NLP verification
heuriterlim	iteration limit for each call of the heuristics

Definition at line 1463 of file probdata_rpa.c.

References BMSclearMemoryArray, enumeratePatterns(), filterPatterns(), MAX, maxCircles(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetRealParam(), SCIPgetTotalTime(), SCIPpatternCreateCircular(), SCIPpatternRelease(), SCIPpatternSetType(), and SCIPprobdataGetNTypes().

Referenced by setupProblem().

SCIPprobdataGetNTypes()

int SCIPprobdataGetNTypes

(

SCIP_PROBDATA *

probdata

)

returns number of different types

Parameters

probdata

problem data

Definition at line 1520 of file probdata_rpa.c.

References NULL.

Referenced by addVariable(), enumeratePatterns(), filterPatterns(), maxCircles(), probdataFree(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_PRICERREDCOST(), SCIP_DECL_TABLEOUTPUT(), SCIPcheckPattern(), SCIPprobdataEnumeratePatterns(), SCIPverifyCircularPatternHeuristic(), SCIPverifyCircularPatternNLP(), setupProblem(), solvePricingHeuristic(), and solvePricingMINLP().

SCIPprobdataGetRexts()

SCIP_Real* SCIPprobdataGetRexts

(

SCIP_PROBDATA *

probdata

)

returns all external radii

Parameters

probdata

problem data

Definition at line 1530 of file probdata_rpa.c.

References NULL.

Referenced by computeScores(), enumeratePatterns(), maxCircles(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_TABLEOUTPUT(), SCIPcheckPattern(), SCIPverifyCircularPatternHeuristic(), SCIPverifyCircularPatternNLP(), setupProblem(), solvePricingHeuristic(), and solvePricingMINLP().

SCIPprobdataGetRints()

SCIP_Real* SCIPprobdataGetRints

(

SCIP_PROBDATA *

probdata

)

returns all internal radii

Parameters

probdata

problem data

Definition at line 1540 of file probdata_rpa.c.

References NULL.

Referenced by enumeratePatterns(), maxCircles(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_TABLEOUTPUT(), SCIPcheckPattern(), SCIPverifyCircularPatternHeuristic(), SCIPverifyCircularPatternNLP(), and setupProblem().

SCIPprobdataGetDemands()

int* SCIPprobdataGetDemands

(

SCIP_PROBDATA *

probdata

)

returns all demands

Parameters

probdata

problem data

Definition at line 1550 of file probdata_rpa.c.

References NULL.

Referenced by createPatternVars(), maxCircles(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_TABLEOUTPUT(), setupProblem(), solvePricingHeuristic(), and solvePricingMINLP().

SCIPprobdataGetWidth()

SCIP_Real SCIPprobdataGetWidth

(

SCIP_PROBDATA *

probdata

)

returns the width of each rectangle

Parameters

probdata

problem data

Definition at line 1560 of file probdata_rpa.c.

References NULL.

Referenced by SCIP_DECL_EVENTEXEC(), SCIP_DECL_TABLEOUTPUT(), SCIPcheckPattern(), SCIPverifyCircularPatternHeuristic(), setupProblem(), solvePricingHeuristic(), and solvePricingMINLP().

SCIPprobdataGetHeight()

SCIP_Real SCIPprobdataGetHeight

(

SCIP_PROBDATA *

probdata

)

returns the height of each rectangle

Parameters

probdata

problem data

Definition at line 1571 of file probdata_rpa.c.

References NULL.

Referenced by SCIP_DECL_EVENTEXEC(), SCIP_DECL_TABLEOUTPUT(), SCIPcheckPattern(), SCIPverifyCircularPatternHeuristic(), setupProblem(), solvePricingHeuristic(), and solvePricingMINLP().

SCIPprobdataGetCInfos()

void SCIPprobdataGetCInfos	(	SCIP_PROBDATA *	probdata,
		SCIP_PATTERN ***	cpatterns,
		SCIP_VAR ***	cvars,
		int *	ncpatterns
	)

returns all information about circular patterns

Parameters

probdata	problem data
cpatterns	pointer to store the circular patterns (might be NULL)
cvars	pointer to store the variables corresponding circular patterns (might be NULL)
ncpatterns	pointer to store the number of circular patterns (might be NULL)

Definition at line 1581 of file probdata_rpa.c.

References NULL.

Referenced by enforceSol(), isSolFeasible(), SCIP_DECL_CONSEXITSOL(), SCIP_DECL_CONSINITSOL(), SCIP_DECL_CONSLOCK(), and SCIP_DECL_EVENTEXEC().

SCIPprobdataGetRInfos()

void SCIPprobdataGetRInfos	(	SCIP_PROBDATA *	probdata,
		SCIP_PATTERN ***	rpatterns,
		SCIP_VAR ***	rvars,
		int *	nrpatterns
	)

returns all information about rectangular patterns

Parameters

probdata	problem data
rpatterns	pointer to store the rectangular patterns (might be NULL)
rvars	pointer to store the variables corresponding rectangular patterns (might be NULL)
nrpatterns	pointer to store the number of rectangular patterns (might be NULL)

Definition at line 1599 of file probdata_rpa.c.

References NULL.

Referenced by SCIP_DECL_EVENTEXEC().

SCIPprobdataGetPatternConss()

SCIP_CONS** SCIPprobdataGetPatternConss

(

SCIP_PROBDATA *

probdata

)

returns array of set pattern constraints

Parameters

probdata

problem data

Definition at line 1617 of file probdata_rpa.c.

References NULL.

Referenced by addVariable(), and SCIP_DECL_PRICERREDCOST().

SCIPprobdataAddVar()

SCIP_RETCODE SCIPprobdataAddVar	(	SCIP *	scip,
		SCIP_PROBDATA *	probdata,
		SCIP_PATTERN *	pattern,
		SCIP_VAR *	var
	)

adds given variable to the problem data

Parameters

scip	SCIP data structure
probdata	problem data
pattern	pattern
var	variables to add

Definition at line 1627 of file probdata_rpa.c.

References ensureSize(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_PACKABLE_NO, SCIP_PATTERNTYPE_CIRCULAR, SCIP_PATTERNTYPE_RECTANGULAR, SCIPcaptureVar(), SCIPcheckPattern(), SCIPpatternCopy(), SCIPpatternGetPackableStatus(), and SCIPpatternGetPatternType().

Referenced by addVariable(), enumeratePatterns(), and setupProblem().

SCIPprobdataUpdateDualbound()

void SCIPprobdataUpdateDualbound	(	SCIP *	scip,
		SCIP_PROBDATA *	probdata,
		SCIP_Real	dualbound
	)

updates the dual bound

Parameters

scip	SCIP data structure
probdata	problem data
dualbound	new dual bound

Definition at line 1669 of file probdata_rpa.c.

References NULL, SCIPinfoMessage(), and SCIPisFeasLT().

Referenced by SCIP_DECL_PRICERREDCOST(), and setupProblem().

SCIPprobdataInvalidateDualbound()

void SCIPprobdataInvalidateDualbound	(	SCIP *	scip,
		SCIP_PROBDATA *	probdata
	)

marks that further reported dual bounds are not valid

Parameters

scip	SCIP data structure
probdata	problem data

Definition at line 1685 of file probdata_rpa.c.

References NULL, SCIPinfoMessage(), and TRUE.

Referenced by enforceSol(), and SCIP_DECL_PRICERREDCOST().

SCIPprobdataIsDualboundInvalid()

SCIP_Bool SCIPprobdataIsDualboundInvalid

(

SCIP_PROBDATA *

probdata

)

returns whether dual bound is marked to be invalid

Parameters

probdata

problem data

Definition at line 1700 of file probdata_rpa.c.

References NULL.

Referenced by SCIP_DECL_PRICERREDCOST().

SCIPpackCirclesGreedy()

void SCIPpackCirclesGreedy	(	SCIP *	scip,
		SCIP_Real *	rexts,
		SCIP_Real *	xs,
		SCIP_Real *	ys,
		SCIP_Real	rbounding,
		SCIP_Real	width,
		SCIP_Real	height,
		SCIP_Bool *	ispacked,
		int *	elements,
		int	nelements,
		SCIP_PATTERNTYPE	patterntype,
		int *	npacked,
		int	ncalls
	)

Tries to pack a list of elements into a specified boundary circle by using a simple left-first bottom-second heuristic. Returns the number of elements that could be stored and indicated which ones these are in the buffer parameter ispacked. This auxiliary method can be used both to find such a packing or to verify a certain pattern.

Parameters

scip	SCIP data structure
rexts	outer radii of elements (in original order of probdata)
xs	buffer to store the resulting x-coordinates
ys	buffer to store the resulting y-coordinates
rbounding	inner radius of bounding circle (ignored for rectangular patterns)
width	width of the rectangle
height	height of the rectangle
ispacked	buffer to store which elements could be packed
elements	the order of the elements in the pattern
nelements	number of elements in the pattern
patterntype	the pattern type (rectangular or circular)
npacked	pointer to store the number of packed elements
ncalls	total number of calls of the packing heuristic

Definition at line 1713 of file probdata_rpa.c.

References BMSclearMemoryArray, computePosCircleCircle(), computePosRectangleCircle(), computePosRingCircle(), computePosTrivial(), FALSE, NULL, SCIP_Bool, SCIP_INVALID, SCIP_PATTERNTYPE_CIRCULAR, SCIP_Real, and TRUE.

Referenced by SCIPverifyCircularPatternHeuristic(), and solvePricingHeuristic().

SCIPverifyCircularPatternHeuristic()

SCIP_RETCODE SCIPverifyCircularPatternHeuristic	(	SCIP *	scip,
		SCIP_PROBDATA *	probdata,
		SCIP_PATTERN *	pattern,
		SCIP_Real	timelim,
		int	iterlim
	)

verifies a circular pattern heuristically

Parameters

scip	SCIP data structure
probdata	problem data
pattern	pattern
timelim	time limit
iterlim	iteration limit

Definition at line 1819 of file probdata_rpa.c.

References computeScores(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PACKABLE_NO, SCIP_PACKABLE_UNKNOWN, SCIP_PACKABLE_YES, SCIP_PATTERNTYPE_CIRCULAR, SCIP_Real, SCIPallocBufferArray, SCIPcheckPattern(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetTotalTime(), SCIPisGE(), SCIPpackCirclesGreedy(), SCIPpatternGetCircleType(), SCIPpatternGetElementType(), SCIPpatternGetNElemens(), SCIPpatternGetPackableStatus(), SCIPpatternGetPatternType(), SCIPpatternSetElementPos(), SCIPpatternSetPackableStatus(), SCIPprobdataGetHeight(), SCIPprobdataGetNTypes(), SCIPprobdataGetRexts(), SCIPprobdataGetRints(), SCIPprobdataGetWidth(), and SCIPsortDownRealIntInt().

Referenced by enumeratePatterns(), and verifyCircularPattern().

SCIPverifyCircularPatternNLP()

SCIP_RETCODE SCIPverifyCircularPatternNLP	(	SCIP *	scip,
		SCIP_PROBDATA *	probdata,
		SCIP_PATTERN *	pattern,
		SCIP_Real	timelim,
		SCIP_Longint	nodelim
	)

verifies a circular pattern via a verification NLP

Parameters

scip	SCIP data structure
probdata	problem data
pattern	pattern
timelim	time limit
nodelim	node limit

Definition at line 1951 of file probdata_rpa.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PACKABLE_NO, SCIP_PACKABLE_UNKNOWN, SCIP_PACKABLE_YES, SCIP_PARAMEMPHASIS_FEASIBILITY, SCIP_PATTERNTYPE_CIRCULAR, SCIP_Real, SCIP_STATUS_INFEASIBLE, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcheckPattern(), SCIPcreate(), SCIPcreateConsBasicLinear(), SCIPcreateConsQuadraticNonlinear(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPfree(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNSols(), SCIPgetSolVal(), SCIPgetStatus(), SCIPincludeDefaultPlugins(), SCIPinfinity(), SCIPpatternGetCircleType(), SCIPpatternGetElementType(), SCIPpatternGetNElemens(), SCIPpatternGetPackableStatus(), SCIPpatternGetPatternType(), SCIPpatternSetElementPos(), SCIPpatternSetPackableStatus(), SCIPprobdataGetNTypes(), SCIPprobdataGetRexts(), SCIPprobdataGetRints(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetEmphasis(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetMessagehdlrQuiet(), SCIPsetRealParam(), SCIPsnprintf(), SCIPsolve(), and TRUE.

Referenced by enumeratePatterns(), and verifyCircularPattern().

SCIPcheckPattern()

void SCIPcheckPattern	(	SCIP *	scip,
		SCIP_PROBDATA *	probdata,
		SCIP_PATTERN *	pattern
	)

check a pattern for consistency

Parameters

scip	SCIP data structure
probdata	problem data
pattern	pattern

Definition at line 2151 of file probdata_rpa.c.

References NULL, SCIP_PACKABLE_YES, SCIP_PATTERNTYPE_CIRCULAR, SCIP_Real, SCIPisFeasGE(), SCIPisFeasLE(), SCIPpatternGetCircleType(), SCIPpatternGetElementPosX(), SCIPpatternGetElementPosY(), SCIPpatternGetElementType(), SCIPpatternGetNElemens(), SCIPpatternGetPackableStatus(), SCIPpatternGetPatternType(), SCIPprobdataGetHeight(), SCIPprobdataGetNTypes(), SCIPprobdataGetRexts(), SCIPprobdataGetRints(), and SCIPprobdataGetWidth().

Referenced by SCIP_DECL_EVENTEXEC(), SCIPprobdataAddVar(), SCIPverifyCircularPatternHeuristic(), SCIPverifyCircularPatternNLP(), and verifyCircularPattern().