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	CONSHDLR_SEPAPRIORITY   0
#define	CONSHDLR_SEPAFREQ   -1
#define	CONSHDLR_DELAYSEPA   FALSE
#define	CONSHDLR_PROPFREQ   -1
#define	CONSHDLR_DELAYPROP   FALSE
#define	CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
#define	CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM
#define	CONSHDLR_MAXPREROUNDS   -1
#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 38 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

CONSHDLR_DESC

#define CONSHDLR_DESC   "ringpacking constraint handler"

Definition at line 39 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   1

priority of the constraint handler for constraint enforcing

Definition at line 40 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -1

priority of the constraint handler for checking feasibility

Definition at line 41 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

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 42 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   FALSE

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

Definition at line 45 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   0

priority of the constraint handler for separation

Definition at line 49 of file cons_rpa.c.

CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ   -1

frequency for separating cuts; zero means to separate only in the root node

Definition at line 50 of file cons_rpa.c.

CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 51 of file cons_rpa.c.

CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   -1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 53 of file cons_rpa.c.

CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 54 of file cons_rpa.c.

CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

propagation timing mask of the constraint handler

Definition at line 55 of file cons_rpa.c.

CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM

presolving timing of the constraint handler (fast, medium, or exhaustive)

Definition at line 57 of file cons_rpa.c.

CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS   -1

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 58 of file cons_rpa.c.

EVENTHDLR_NAME

#define EVENTHDLR_NAME   "bestsol"

Definition at line 61 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

EVENTHDLR_DESC

#define EVENTHDLR_DESC   "best solution event handler"

Definition at line 62 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

DEFAULT_VERIFICATION_NLPTILIM

#define DEFAULT_VERIFICATION_NLPTILIM   10.0

time limit for each verification NLP

Definition at line 65 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

DEFAULT_VERIFICATION_NLPNODELIM

#define DEFAULT_VERIFICATION_NLPNODELIM   10000L

node limit for each verification NLP

Definition at line 66 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

DEFAULT_VERIFICATION_HEURTILIM

#define DEFAULT_VERIFICATION_HEURTILIM   10.0

time limit for heuristic verification

Definition at line 67 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

DEFAULT_VERIFICATION_HEURITERLIM

#define DEFAULT_VERIFICATION_HEURITERLIM   1000

iteration limit for each heuristic verification

Definition at line 68 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

DEFAULT_VERIFICATION_TOTALTILIM

#define DEFAULT_VERIFICATION_TOTALTILIM   3600.0

total time limit for all verification problems during the solving process

Definition at line 69 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

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 100 of file cons_rpa.c.

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

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 142 of file cons_rpa.c.

References enforceSol(), 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(), and isSolFeasible().

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 197 of file cons_rpa.c.

References getShadingVal(), 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(), SCIP_DECL_CONSENFORELAX(), and verifyCircularPattern().

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 308 of file cons_rpa.c.

References MAX, MIN, and SCIP_DECL_EVENTEXEC().

Referenced by enforceSol(), and 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 325 of file cons_rpa.c.

References getShadingVal(), NULL, SCIP_CALL, SCIP_DECL_CONSFREE(), 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.

Referenced by getShadingVal().

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 490 of file cons_rpa.c.

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

Referenced by SCIP_DECL_EVENTEXEC().

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 509 of file cons_rpa.c.

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

Referenced by SCIP_DECL_CONSFREE().

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 538 of file cons_rpa.c.

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

Referenced by SCIP_DECL_CONSINITSOL().

SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpRpa  )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 565 of file cons_rpa.c.

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

Referenced by SCIP_DECL_CONSEXITSOL().

SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxRpa  )

static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 575 of file cons_rpa.c.

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

Referenced by SCIP_DECL_CONSENFOLP().

SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsRpa  )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 585 of file cons_rpa.c.

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

Referenced by SCIP_DECL_CONSENFORELAX().

SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckRpa  )

static

feasibility check method of constraint handler for integral solutions

Definition at line 595 of file cons_rpa.c.

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

Referenced by SCIP_DECL_CONSENFOPS().

SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockRpa  )

static

variable rounding lock method of constraint handler

Definition at line 604 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(), SCIPincludeConshdlrRpa(), SCIPpatternGetPackableStatus(), SCIPprobdataGetCInfos(), SCIPvarGetName(), and TRUE.

Referenced by SCIP_DECL_CONSCHECK().