constraint handler for recursive circle packing
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) |
#define CONSHDLR_NAME "rpa" |
Definition at line 47 of file cons_rpa.c.
#define CONSHDLR_DESC "ringpacking constraint handler" |
Definition at line 48 of file cons_rpa.c.
#define CONSHDLR_ENFOPRIORITY 1 |
priority of the constraint handler for constraint enforcing
Definition at line 49 of file cons_rpa.c.
#define CONSHDLR_CHECKPRIORITY -1 |
priority of the constraint handler for checking feasibility
Definition at line 50 of file cons_rpa.c.
#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.
#define CONSHDLR_NEEDSCONS FALSE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 53 of file cons_rpa.c.
#define CONSHDLR_SEPAPRIORITY 0 |
priority of the constraint handler for separation
Definition at line 57 of file cons_rpa.c.
#define CONSHDLR_SEPAFREQ -1 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 58 of file cons_rpa.c.
#define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 59 of file cons_rpa.c.
#define CONSHDLR_PROPFREQ -1 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 61 of file cons_rpa.c.
#define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 62 of file cons_rpa.c.
#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
propagation timing mask of the constraint handler
Definition at line 63 of file cons_rpa.c.
#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM |
presolving timing of the constraint handler (fast, medium, or exhaustive)
Definition at line 65 of file cons_rpa.c.
#define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 66 of file cons_rpa.c.
#define EVENTHDLR_NAME "bestsol" |
Definition at line 69 of file cons_rpa.c.
#define EVENTHDLR_DESC "best solution event handler" |
Definition at line 70 of file cons_rpa.c.
#define DEFAULT_VERIFICATION_NLPTILIM 10.0 |
time limit for each verification NLP
Definition at line 73 of file cons_rpa.c.
Referenced by SCIPincludeConshdlrRpa().
#define DEFAULT_VERIFICATION_NLPNODELIM 10000L |
node limit for each verification NLP
Definition at line 74 of file cons_rpa.c.
Referenced by SCIPincludeConshdlrRpa().
#define DEFAULT_VERIFICATION_HEURTILIM 10.0 |
time limit for heuristic verification
Definition at line 75 of file cons_rpa.c.
Referenced by SCIPincludeConshdlrRpa().
#define DEFAULT_VERIFICATION_HEURITERLIM 1000 |
iteration limit for each heuristic verification
Definition at line 76 of file cons_rpa.c.
Referenced by SCIPincludeConshdlrRpa().
#define DEFAULT_VERIFICATION_TOTALTILIM 3600.0 |
total time limit for all verification problems during the solving process
Definition at line 77 of file cons_rpa.c.
Referenced by SCIPincludeConshdlrRpa().
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
scip | SCIP data structure |
sol | solution (NULL for LP solution) |
Definition at line 108 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().
|
static |
tries to verify a circular pattern; it first tries to call heuristic(s) and afterwards uses a verification NLP
scip | SCIP data structure |
conshdlrdata | constraint handler data |
probdata | problem data |
pattern | circular pattern |
Definition at line 150 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().
|
static |
auxiliary function for enforcing ringpacking constraint; the function checks whether
Note that after step 3. the dual bound is not valid anymore.
scip | SCIP data structure |
conshdlr | constraint handler |
sol | solution (NULL for LP solution) |
result | pointer to store the result |
Definition at line 205 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().
|
static |
get shading of a given pattern type
type | pattern type |
ntypes | total number of patterns |
Definition at line 316 of file cons_rpa.c.
References assert(), MAX, and MIN.
Referenced by SCIP_DECL_EVENTEXEC().
|
static |
processes the event that a new primal solution has been found
Definition at line 333 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.
|
static |
destructor of constraint handler to free constraint handler data (called when SCIP is exiting)
Definition at line 498 of file cons_rpa.c.
References assert(), NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.
|
static |
solving process initialization method of constraint handler (called when branch and bound process is about to begin)
Definition at line 517 of file cons_rpa.c.
References assert(), BMSclearMemoryArray, NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcatchEvent(), SCIPconshdlrGetData(), SCIPgetProbData(), and SCIPprobdataGetCInfos().
|
static |
solving process deinitialization method of constraint handler (called before branch and bound process data is freed)
Definition at line 546 of file cons_rpa.c.
References assert(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, SCIPconshdlrGetData(), SCIPdropEvent(), SCIPfreeBlockMemoryArray, SCIPgetProbData(), and SCIPprobdataGetCInfos().
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 573 of file cons_rpa.c.
References enforceSol(), NULL, result, SCIP_CALL, and SCIP_OKAY.
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 583 of file cons_rpa.c.
References enforceSol(), result, SCIP_CALL, SCIP_OKAY, and sol.
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 593 of file cons_rpa.c.
References enforceSol(), NULL, result, SCIP_CALL, and SCIP_OKAY.
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 603 of file cons_rpa.c.
References isSolFeasible(), result, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, and sol.
|
static |
variable rounding lock method of constraint handler
Definition at line 612 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.