cons_rpa.c File Reference

Detailed Description

constraint handler for recursive circle packing

Author

Benjamin Mueller

This constraint handler is used to store information about which (not verified) rectangular patterns have been locked and which circular patterns have not been tried to be verified yet.

Definition in file cons_rpa.c.

#include <assert.h>
#include <string.h>
#include "cons_rpa.h"
#include "probdata_rpa.h"
#include "pattern.h"

Go to the source code of this file.

Macros
#define	CONSHDLR_NAME   "rpa"
#define	CONSHDLR_DESC   "ringpacking constraint handler"
#define	CONSHDLR_ENFOPRIORITY   1
#define	CONSHDLR_CHECKPRIORITY   -1
#define	CONSHDLR_EAGERFREQ   100
#define	CONSHDLR_NEEDSCONS   FALSE
#define	EVENTHDLR_NAME   "bestsol"
#define	EVENTHDLR_DESC   "best solution event handler"
#define	DEFAULT_VERIFICATION_NLPTILIM   10.0
#define	DEFAULT_VERIFICATION_NLPNODELIM   10000L
#define	DEFAULT_VERIFICATION_HEURTILIM   10.0
#define	DEFAULT_VERIFICATION_HEURITERLIM   1000
#define	DEFAULT_VERIFICATION_TOTALTILIM   3600.0

Functions
static SCIP_Bool	isSolFeasible (SCIP *scip, SCIP_SOL *sol)
static SCIP_RETCODE	verifyCircularPattern (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)
static SCIP_RETCODE	enforceSol (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_RESULT *result)
static int	getShadingVal (int type, int ntypes)
static	SCIP_DECL_EVENTEXEC (processNewSolutionEvent)
static	SCIP_DECL_CONSFREE (consFreeRpa)
static	SCIP_DECL_CONSINITSOL (consInitsolRpa)
static	SCIP_DECL_CONSEXITSOL (consExitsolRpa)
static	SCIP_DECL_CONSENFOLP (consEnfolpRpa)
static	SCIP_DECL_CONSENFORELAX (consEnforelaxRpa)
static	SCIP_DECL_CONSENFOPS (consEnfopsRpa)
static	SCIP_DECL_CONSCHECK (consCheckRpa)
static	SCIP_DECL_CONSLOCK (consLockRpa)
SCIP_RETCODE	SCIPincludeConshdlrRpa (SCIP *scip)

Macro Definition Documentation

CONSHDLR_NAME

#define CONSHDLR_NAME   "rpa"

Definition at line 47 of file cons_rpa.c.

CONSHDLR_DESC

#define CONSHDLR_DESC   "ringpacking constraint handler"

Definition at line 48 of file cons_rpa.c.

CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   1

priority of the constraint handler for constraint enforcing

Definition at line 49 of file cons_rpa.c.

CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -1

priority of the constraint handler for checking feasibility

Definition at line 50 of file cons_rpa.c.

CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ   100

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 52 of file cons_rpa.c.

CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   FALSE

should the constraint handler be skipped, if no constraints are available?

Definition at line 53 of file cons_rpa.c.

EVENTHDLR_NAME

#define EVENTHDLR_NAME   "bestsol"

Definition at line 56 of file cons_rpa.c.

EVENTHDLR_DESC

#define EVENTHDLR_DESC   "best solution event handler"

Definition at line 57 of file cons_rpa.c.

DEFAULT_VERIFICATION_NLPTILIM

#define DEFAULT_VERIFICATION_NLPTILIM   10.0

time limit for each verification NLP

Definition at line 60 of file cons_rpa.c.

DEFAULT_VERIFICATION_NLPNODELIM

#define DEFAULT_VERIFICATION_NLPNODELIM   10000L

node limit for each verification NLP

Definition at line 61 of file cons_rpa.c.

DEFAULT_VERIFICATION_HEURTILIM

#define DEFAULT_VERIFICATION_HEURTILIM   10.0

time limit for heuristic verification

Definition at line 62 of file cons_rpa.c.

DEFAULT_VERIFICATION_HEURITERLIM

#define DEFAULT_VERIFICATION_HEURITERLIM   1000

iteration limit for each heuristic verification

Definition at line 63 of file cons_rpa.c.

DEFAULT_VERIFICATION_TOTALTILIM

#define DEFAULT_VERIFICATION_TOTALTILIM   3600.0

total time limit for all verification problems during the solving process

Definition at line 64 of file cons_rpa.c.

Function Documentation

isSolFeasible()

static SCIP_Bool isSolFeasible ( SCIP *  scip, SCIP_SOL *  sol  )

static

auxiliary function to decide whether a proposed solution is feasible; a solution is called feasible if and only if z*_C = 0 holds for all circular patterns that are either not packable, i.e., SCIP_PACKABLE_NO or SCIP_PACKABLE_UNKNOWN

Parameters

scip	SCIP data structure
sol	solution (NULL for LP solution)

Definition at line 95 of file cons_rpa.c.

References FALSE, NULL, SCIP_PACKABLE_YES, SCIP_Real, SCIPdebugMsg, SCIPgetProbData(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPpatternGetPackableStatus(), SCIPprobdataGetCInfos(), and TRUE.

Referenced by enforceSol(), and SCIP_DECL_CONSCHECK().

verifyCircularPattern()

static SCIP_RETCODE verifyCircularPattern ( SCIP *  scip, SCIP_CONSHDLRDATA *  conshdlrdata, SCIP_PROBDATA *  probdata, SCIP_PATTERN *  pattern  )

static

tries to verify a circular pattern; it first tries to call heuristic(s) and afterwards uses a verification NLP

Parameters

scip	SCIP data structure
conshdlrdata	constraint handler data
probdata	problem data
pattern	circular pattern

Definition at line 137 of file cons_rpa.c.

References MIN, MIN3, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PACKABLE_UNKNOWN, SCIP_PATTERNTYPE_CIRCULAR, SCIP_Real, SCIPcheckPattern(), SCIPdebugMsg, SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPpatternGetPackableStatus(), SCIPpatternGetPatternType(), SCIPverifyCircularPatternHeuristic(), and SCIPverifyCircularPatternNLP().

Referenced by enforceSol().

enforceSol()

static SCIP_RETCODE enforceSol ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, SCIP_SOL *  sol, SCIP_RESULT *  result  )

static

auxiliary function for enforcing ringpacking constraint; the function checks whether

1. the solution is feasible; if yes -> skip
2. tries to verify an unverified circular pattern C with z*_c > 0 2a. case packable or unknown: go to 2. 2b. case not packable: fix z_C to 0 -> skip
3. fix all unverified circular patterns to 0

Note that after step 3. the dual bound is not valid anymore.

Parameters

scip	SCIP data structure
conshdlr	constraint handler
sol	solution (NULL for LP solution)
result	pointer to store the result

Definition at line 192 of file cons_rpa.c.

References isSolFeasible(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIP_PACKABLE_NO, SCIP_PACKABLE_UNKNOWN, SCIP_Real, SCIP_REDUCEDDOM, SCIPconshdlrGetData(), SCIPdebugMsg, SCIPfixVar(), SCIPgetProbData(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPpatternGetPackableStatus(), SCIPprintSol(), SCIPprobdataGetCInfos(), SCIPprobdataInvalidateDualbound(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and verifyCircularPattern().

Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), and SCIP_DECL_CONSENFORELAX().

getShadingVal()

static int getShadingVal ( int  type, int  ntypes  )

static

get shading of a given pattern type

Parameters

type	pattern type
ntypes	total number of patterns

Definition at line 303 of file cons_rpa.c.

References MAX, and MIN.

Referenced by SCIP_DECL_EVENTEXEC().

SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( processNewSolutionEvent  )

static

processes the event that a new primal solution has been found

Definition at line 320 of file cons_rpa.c.

References getShadingVal(), NULL, SCIP_CALL, SCIP_EVENTTYPE_SOLFOUND, SCIP_OKAY, SCIP_PACKABLE_YES, SCIP_Real, SCIPcheckPattern(), SCIPdebugMsg, SCIPeventGetSol(), SCIPeventGetType(), SCIPgetProbData(), SCIPgetSolVal(), SCIPgetStringParam(), SCIPinfoMessage(), SCIPisFeasZero(), SCIPpatternGetCircleType(), SCIPpatternGetElementPosX(), SCIPpatternGetElementPosY(), SCIPpatternGetElementType(), SCIPpatternGetNElemens(), SCIPpatternGetPackableStatus(), SCIPprobdataGetCInfos(), SCIPprobdataGetDemands(), SCIPprobdataGetHeight(), SCIPprobdataGetNTypes(), SCIPprobdataGetRexts(), SCIPprobdataGetRInfos(), SCIPprobdataGetRints(), SCIPprobdataGetWidth(), SCIPvarGetName(), x, and y.

SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeRpa  )

static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 485 of file cons_rpa.c.

References NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

SCIP_DECL_CONSINITSOL()

static SCIP_DECL_CONSINITSOL ( consInitsolRpa  )

static

solving process initialization method of constraint handler (called when branch and bound process is about to begin)

Definition at line 504 of file cons_rpa.c.

References BMSclearMemoryArray, NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcatchEvent(), SCIPconshdlrGetData(), SCIPgetProbData(), and SCIPprobdataGetCInfos().

SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolRpa  )

static

solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

Definition at line 533 of file cons_rpa.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, SCIPconshdlrGetData(), SCIPdropEvent(), SCIPfreeBlockMemoryArray, SCIPgetProbData(), and SCIPprobdataGetCInfos().

SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpRpa  )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 560 of file cons_rpa.c.

References enforceSol(), NULL, SCIP_CALL, and SCIP_OKAY.

SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxRpa  )

static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 570 of file cons_rpa.c.

References enforceSol(), SCIP_CALL, and SCIP_OKAY.

SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsRpa  )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 580 of file cons_rpa.c.

References enforceSol(), NULL, SCIP_CALL, and SCIP_OKAY.

SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckRpa  )

static

feasibility check method of constraint handler for integral solutions

Definition at line 590 of file cons_rpa.c.

References isSolFeasible(), SCIP_FEASIBLE, SCIP_INFEASIBLE, and SCIP_OKAY.

SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockRpa  )

static

variable rounding lock method of constraint handler

Definition at line 599 of file cons_rpa.c.

References BMSclearMemoryArray, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_PACKABLE_UNKNOWN, SCIPaddVarLocksType(), SCIPallocBlockMemoryArray, SCIPconshdlrGetData(), SCIPdebugMsg, SCIPgetProbData(), SCIPpatternGetPackableStatus(), SCIPprobdataGetCInfos(), SCIPvarGetName(), and TRUE.