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 51 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.

Referenced by SCIPincludeConshdlrRpa().

◆ DEFAULT_VERIFICATION_NLPNODELIM

#define DEFAULT_VERIFICATION_NLPNODELIM 10000L

node limit for each verification NLP

Definition at line 61 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 62 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 63 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 64 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

Function Documentation

◆ isSolFeasible()

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 assert(), FALSE, NULL, SCIP_Bool, SCIP_PACKABLE_YES, SCIP_Real, SCIPdebugMsg, SCIPgetProbData(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPpatternGetPackableStatus(), SCIPprobdataGetCInfos(), sol, and TRUE.

Referenced by enforceSol(), and SCIP_DECL_CONSCHECK().

◆ verifyCircularPattern()

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 assert(), 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()

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

the solution is feasible; if yes -> skip
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
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 assert(), isSolFeasible(), NULL, result, 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(), sol, TRUE, and verifyCircularPattern().

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

◆ getShadingVal()

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 assert(), MAX, and MIN.

Referenced by SCIP_DECL_EVENTEXEC().

◆ SCIP_DECL_EVENTEXEC()

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 assert(), getShadingVal(), i, 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(), sol, vars, x, and y.

◆ SCIP_DECL_CONSFREE()

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 assert(), NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

◆ SCIP_DECL_CONSINITSOL()

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 assert(), BMSclearMemoryArray, NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcatchEvent(), SCIPconshdlrGetData(), SCIPgetProbData(), and SCIPprobdataGetCInfos().

◆ SCIP_DECL_CONSEXITSOL()

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 assert(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, SCIPconshdlrGetData(), SCIPdropEvent(), SCIPfreeBlockMemoryArray, SCIPgetProbData(), and SCIPprobdataGetCInfos().

◆ SCIP_DECL_CONSENFOLP()

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, result, SCIP_CALL, and SCIP_OKAY.

◆ SCIP_DECL_CONSENFORELAX()

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(), result, SCIP_CALL, SCIP_OKAY, and sol.

◆ SCIP_DECL_CONSENFOPS()

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, result, SCIP_CALL, and SCIP_OKAY.

◆ SCIP_DECL_CONSCHECK()

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(), result, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, and sol.

◆ SCIP_DECL_CONSLOCK()

SCIP_DECL_CONSLOCK ( consLockRpa )

static

variable rounding lock method of constraint handler

Definition at line 599 of file cons_rpa.c.

References assert(), 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.

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

◆ CONSHDLR_ENFOPRIORITY

◆ CONSHDLR_CHECKPRIORITY

◆ CONSHDLR_EAGERFREQ

◆ CONSHDLR_NEEDSCONS

◆ EVENTHDLR_NAME

◆ EVENTHDLR_DESC

◆ DEFAULT_VERIFICATION_NLPTILIM

◆ DEFAULT_VERIFICATION_NLPNODELIM

◆ DEFAULT_VERIFICATION_HEURTILIM

◆ DEFAULT_VERIFICATION_HEURITERLIM

◆ DEFAULT_VERIFICATION_TOTALTILIM

Function Documentation

◆ isSolFeasible()

◆ verifyCircularPattern()

◆ enforceSol()

◆ getShadingVal()

◆ SCIP_DECL_EVENTEXEC()

◆ SCIP_DECL_CONSFREE()

◆ SCIP_DECL_CONSINITSOL()

◆ SCIP_DECL_CONSEXITSOL()

◆ SCIP_DECL_CONSENFOLP()

◆ SCIP_DECL_CONSENFORELAX()

◆ SCIP_DECL_CONSENFOPS()

◆ SCIP_DECL_CONSCHECK()

◆ SCIP_DECL_CONSLOCK()