probdata_rpa.h File Reference

Detailed Description

Problem data for ringpacking problem.

Author

Benjamin Mueller

Definition in file probdata_rpa.h.

#include "scip/scip.h"
#include "pattern.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPprobdataCreate (SCIP *scip, const char *probname, int *demands, SCIP_Real *rints, SCIP_Real *rexts, int nitems, 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)

Function Documentation

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(), MIN, 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 solving a verification NLP

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

Referenced by enumeratePatterns(), and verifyCircularPattern().

SCIPcheckPattern()

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

check whether a pattern for consistency

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(), SCIPprobdataGetWidth(), and SQR.

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