Scippy

SCIP

Solving Constraint Integer Programs

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_RealSCIPprobdataGetRexts (SCIP_PROBDATA *probdata)
 
SCIP_RealSCIPprobdataGetRints (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 50 of file probdata_rpa.c.

Referenced by SCIPprobdataCreate().

◆ TABLE_DESC_RPA

#define TABLE_DESC_RPA   "ringpacking statistics"

Definition at line 51 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 52 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 53 of file probdata_rpa.c.

Referenced by SCIPprobdataCreate().

◆ M_PI

#define M_PI   3.141592653589793238462643

Definition at line 56 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
scipSCIP data structure
probdatapointer to problem data
patternconsspattern constraints
cpatternscircular patterns
cvarsvariables corresponding to circular patterns
ncpatternstotal number of circular patterns
rpatternsrectangular patterns
rvarsvariables corresponding to rectangular patterns
nrpatternstotal number of rectangular patterns
demandsarray containing the demands
rintsinteral radii of each ring
rextsexternal radii of each ring
ntypesnumber of different types
widthwidth of each rectangle
heightheight of each rectangle

Definition at line 116 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
scipSCIP data structure
probdatapointer to release the probdata

Definition at line 199 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
scipSCIP data structure
probdataproblem data
statuspackable status

Definition at line 274 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
scipSCIP data structure
probdataproblem data
typepattern type
sizerequired size

Definition at line 296 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
scipSCIP data structure
probdataproblem data

Definition at line 330 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
scipSCIP data structure
probdataproblem data
typetype of the circular pattern
elemtypetype of element to pack

Definition at line 407 of file probdata_rpa.c.

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

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
ppattern
qpattern
countarray for counting elements of patterns
ntypestotal number of types

Definition at line 462 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
scipSCIP data structure
probdataproblem data

Definition at line 514 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
scipSCIP data structure
probdataproblem data
patternpattern (passed for performance reasons)
msmaximum number of elements for each type (passed for performance reasons)
nselectednumber of selected elements for each type (passed for performance reasons)
nlptilimtime limit for each NLP verification
heurtilimtime limit for each call of the heuristics
nlpnodelimnode limit for each NLP verification
heuriterlimiteration limit for each call of the heuristics
timeleftpointer to update the remaining time for the enumeration

Definition at line 585 of file probdata_rpa.c.

References M_PI, MIN, 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(), SQR, and TRUE.

Referenced by SCIPprobdataEnumeratePatterns().

◆ setupProblem()

◆ SCIP_DECL_TABLEOUTPUT()

◆ 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
scipSCIP data structure
xsx-coordinates of packed elements
ysy-coordinates of packed elements
rextsradii of packed elements
rextradii of element that should be packed
rboundinginner radius of bounding circle (ignored for rectangular patterns)
wboundingwidth of bounding rectangular (ignored for circular patterns)
hboundingheight of bounding rectangular (ignored for circular patterns)
rmaxmaximum radius of elements in the pattern
patterntypepattern type
ispackedarray indicating which elements are already packed
elementsthe order of the elements in the pattern
nelementsthe total number of elements
bestxbuffer to update best x-coordinate
bestybuffer to update best y-coordinate
xx-coordinate of a candidate point
yy-coordinate of a candidate point
ncallstotal number of calls of the packing heuristic

Definition at line 957 of file probdata_rpa.c.

References SCIP_Bool, SCIP_INVALID, SCIP_PATTERNTYPE_CIRCULAR, SCIP_PATTERNTYPE_RECTANGULAR, SCIP_Real, SCIPisEQ(), SCIPisGT(), SCIPisLT(), SQR, 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
scipSCIP data structure
elementstypes of elements that have been packed
nelementsthe total number of elements
rextsexternal radii
xsx-coordinate of circle
ysy-coordinate of circle
posposition of element in the elements array
ispackedarray indicating whether an element has been packed already
rmaxmaximum radius of elements in the pattern
rboundradius of bounding circle
bestxpointer to store the best x-coordinate
bestypointer to store the best y-coordinate
ncallstotal number of calls of the packing heuristic

Definition at line 1030 of file probdata_rpa.c.

References a, b, h, SCIP_PATTERNTYPE_CIRCULAR, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisZero(), SQRT, 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
scipSCIP data structure
elementstypes of elements that have been packed
nelementsthe total number of elements
rextsexternal radii
xsx-coordinate of circle
ysy-coordinate of circle
posposition of element in the elements array
ispackedarray indicating whether an element has been packed already
rmaxmaximum radius of elements in the pattern
rboundradius of bounding circle
widthwidth of the rectangle
heightheight of the rectangle
patterntypethe pattern type (rectangular or circular)
bestxpointer to store the best x-coordinate
bestypointer to store the best y-coordinate
ncallstotal number of calls of the packing heuristic

Definition at line 1100 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
scipSCIP data structure
elementstypes of elements that have been packed
nelementsthe total number of elements
rextsexternal radii
xsx-coordinate of circle
ysy-coordinate of circle
posposition of element in the elements array
ispackedarray indicating whether an element has been packed already
rmaxmaximum radius of elements in the pattern
widthwidth of the rectangle
heightheight of the rectangle
bestxpointer to store the best x-coordinate
bestypointer to store the best y-coordinate
ncallstotal number of calls of the packing heuristic

Definition at line 1144 of file probdata_rpa.c.

References SCIP_PATTERNTYPE_RECTANGULAR, SCIP_Real, SQR, SQRT, 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
scipSCIP data structure
elementstypes of elements that have been packed
nelementsthe total number of elements
rextsexternal radii
xsx-coordinate of circle
ysy-coordinate of circle
posposition of element in the elements array
ispackedarray indicating whether an element has been packed already
rmaxmaximum radius of elements in the pattern
rboundradius of bounding circle
widthwidth of the rectangle
heightheight of the rectangle
patterntypethe pattern type (rectangular or circular)
bestxpointer to store the best x-coordinate
bestypointer to store the best y-coordinate
ncallstotal number of calls of the packing heuristic

Definition at line 1212 of file probdata_rpa.c.

References a, b, h, SCIP_Real, SCIPisGE(), SQR, SQRT, 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
scipSCIP data structure
probdataproblem data
elementstype of each element
nelementstotal number of elements
scoresarray to store the score of each element
iteriteration round

Definition at line 1284 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 1333 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 1343 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 1354 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
scipSCIP data structure
probnameproblem name
demandsarray containing the demands
rintsinternal radii of each ring
rextsexternal radii of each ring (assumed to be sorted)
ntypesnumber of different types
widthwidth of each rectangle
heightheight of each rectangle

Definition at line 1387 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
scipSCIP data structure

Definition at line 1434 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
scipSCIP data structure
probdataproblem data
nlptilimtime limit for each NLP verification
heurtilimtime limit for each call of the heuristics
totaltilimtotal time limit for enumeration
nlpnodelimnode limit for each NLP verification
heuriterlimiteration limit for each call of the heuristics

Definition at line 1454 of file probdata_rpa.c.

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

Referenced by setupProblem().

◆ SCIPprobdataGetNTypes()

◆ SCIPprobdataGetRexts()

SCIP_Real* SCIPprobdataGetRexts ( SCIP_PROBDATA probdata)

◆ SCIPprobdataGetRints()

SCIP_Real* SCIPprobdataGetRints ( SCIP_PROBDATA probdata)

returns all internal radii

Parameters
probdataproblem data

Definition at line 1531 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
probdataproblem data

Definition at line 1541 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
probdataproblem data

Definition at line 1551 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
probdataproblem data

Definition at line 1562 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
probdataproblem data
cpatternspointer to store the circular patterns (might be NULL)
cvarspointer to store the variables corresponding circular patterns (might be NULL)
ncpatternspointer to store the number of circular patterns (might be NULL)

Definition at line 1572 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
probdataproblem data
rpatternspointer to store the rectangular patterns (might be NULL)
rvarspointer to store the variables corresponding rectangular patterns (might be NULL)
nrpatternspointer to store the number of rectangular patterns (might be NULL)

Definition at line 1590 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
probdataproblem data

Definition at line 1608 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
scipSCIP data structure
probdataproblem data
patternpattern
varvariables to add

Definition at line 1618 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
scipSCIP data structure
probdataproblem data
dualboundnew dual bound

Definition at line 1660 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
scipSCIP data structure
probdataproblem data

Definition at line 1676 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
probdataproblem data

Definition at line 1691 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
scipSCIP data structure
rextsouter radii of elements (in original order of probdata)
xsbuffer to store the resulting x-coordinates
ysbuffer to store the resulting y-coordinates
rboundinginner radius of bounding circle (ignored for rectangular patterns)
widthwidth of the rectangle
heightheight of the rectangle
ispackedbuffer to store which elements could be packed
elementsthe order of the elements in the pattern
nelementsnumber of elements in the pattern
patterntypethe pattern type (rectangular or circular)
npackedpointer to store the number of packed elements
ncallstotal number of calls of the packing heuristic

Definition at line 1704 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()

◆ SCIPverifyCircularPatternNLP()

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

◆ SCIPcheckPattern()