cons_rpa.c
Go to the documentation of this file.
20 * This constraint handler is used to store information about which (not verified) rectangular patterns have been locked
23 * @todo Is it enough the lock the unverified circular pattern variables only in the positive direction?
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40 #define CONSHDLR_ENFOPRIORITY 1 /**< priority of the constraint handler for constraint enforcing */
41 #define CONSHDLR_CHECKPRIORITY -1 /**< priority of the constraint handler for checking feasibility */
42 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
44 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
47 /* TODO: remove properties which are never used because the corresponding routines are not supported */
49 #define CONSHDLR_SEPAFREQ -1 /**< frequency for separating cuts; zero means to separate only in the root node */
50 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
52 #define CONSHDLR_PROPFREQ -1 /**< frequency for propagating domains; zero means only preprocessing propagation */
53 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
54 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler*/
56 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
57 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
67 #define DEFAULT_VERIFICATION_HEURITERLIM 1000 /**< iteration limit for each heuristic verification */
68 #define DEFAULT_VERIFICATION_TOTALTILIM 3600.0 /**< total time limit for all verification problems during the solving process */
84 SCIP_Real timeleft; /**< time left for solving verification problem during the solving process */
95 /** auxiliary function to decide whether a proposed solution is feasible; a solution is called feasible if and only if
96 * z*_C = 0 holds for all circular patterns that are either not packable, i.e., SCIP_PACKABLE_NO or SCIP_PACKABLE_UNKNOWN
129 SCIPdebugMsg(scip, "solution might be infeasible because of circular pattern %d = (%g,%d)\n", p,
139 /** tries to verify a circular pattern; it first tries to call heuristic(s) and afterwards uses a verification NLP */
161 heurtimelimit = MIN(timelimit - SCIPgetSolvingTime(scip), conshdlrdata->heurtilim); /*lint !e666*/
163 SCIPdebugMsg(scip, "call verification heuristic (%g,%d)\n", heurtimelimit, conshdlrdata->heuriterlim);
165 SCIP_CALL( SCIPverifyCircularPatternHeuristic(scip, probdata, pattern, heurtimelimit, conshdlrdata->heuriterlim) );
171 nlptimelimit = MIN3(conshdlrdata->timeleft, timelimit - SCIPgetSolvingTime(scip), conshdlrdata->nlptilim); /*lint !e666*/
173 SCIPdebugMsg(scip, "call verification NLP (%g,%lld)\n", nlptimelimit, conshdlrdata->nlpnodelim);
175 SCIP_CALL( SCIPverifyCircularPatternNLP(scip, probdata, pattern, nlptimelimit, conshdlrdata->nlpnodelim) );
249 if( SCIPpatternGetPackableStatus(cpatterns[p]) == SCIP_PACKABLE_UNKNOWN && !conshdlrdata->tried[p] )
286 SCIPdebugMsg(scip, "fix unknown pattern %d in [%g,%g] (success=%u)\n", p, SCIPvarGetLbLocal(cvars[p]),
359 assert(SCIPisFeasZero(scip, val) || SCIPpatternGetPackableStatus(patterns[p]) == SCIP_PACKABLE_YES);
420 SCIPinfoMessage(scip, file, "\\draw[draw=none,fill=white] (%g,%g) circle (%g);\n", 0.0, 0.0, rints[type]);
432 SCIPinfoMessage(scip, file, "\\draw[draw=none,fill=white] (%g,%g) circle (%g);\n", x, y, _rint);
450 SCIPinfoMessage(scip, file, "\\subsection*{\\texttt{\\pname} = %g}\n", SCIPgetSolVal(scip, sol, vars[p]));
463 /* SCIPinfoMessage(scip, file, "\\draw[draw=none,fill=white] (%g,%g) circle (%g);\n", x, y, _rint); */
487 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
506 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
529 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, conshdlrdata->eventhdlr, NULL, NULL) );
535 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
556 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, conshdlrdata->eventhdlr, NULL, -1) );
637 * A pattern might change its status during a later verification step and we only need to lock patterns with a
638 * SCIP_PACKABLE_UNKNOWN status. For this reason, we keep track of patterns that have been locked. The CONSLOCK
639 * callback should only be called twice because the constraint handler does not have constraints.
701 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &conshdlrdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
708 &conshdlrdata->nlptilim, FALSE, DEFAULT_VERIFICATION_NLPTILIM, -1.0, SCIP_REAL_MAX, NULL, NULL) );
713 &conshdlrdata->nlpnodelim, FALSE, DEFAULT_VERIFICATION_NLPNODELIM, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
718 &conshdlrdata->heurtilim, FALSE, DEFAULT_VERIFICATION_HEURTILIM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
728 &conshdlrdata->timeleft, FALSE, DEFAULT_VERIFICATION_TOTALTILIM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
SCIP_RETCODE SCIPgetStringParam(SCIP *scip, const char *name, char **value)
Definition: scip_param.c:336
Definition: type_result.h:37
Definition: pattern.h:47
Definition: pattern.h:36
static SCIP_RETCODE verifyCircularPattern(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)
Definition: cons_rpa.c:142
Definition: struct_scip.h:59
Definition: pattern.h:42
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
void SCIPcheckPattern(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)
Definition: probdata_rpa.c:2141
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:308
Problem data for ringpacking problem.
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
Definition: struct_var.h:198
int * SCIPprobdataGetDemands(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1540
void SCIPprobdataInvalidateDualbound(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1675
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:102
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:166
int SCIPpatternGetCircleType(SCIP_PATTERN *pattern)
Definition: pattern.c:300
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
Definition: struct_sol.h:64
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4256
Definition: pattern.h:34
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:429
SCIP_PACKABLE SCIPpatternGetPackableStatus(SCIP_PATTERN *pattern)
Definition: pattern.c:326
void SCIPprobdataGetRInfos(SCIP_PROBDATA *probdata, SCIP_PATTERN ***rpatterns, SCIP_VAR ***rvars, int *nrpatterns)
Definition: probdata_rpa.c:1589
int SCIPprobdataGetNTypes(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1510
SCIP_Real SCIPprobdataGetHeight(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1561
Definition: struct_cons.h:117
SCIP_RETCODE SCIPverifyCircularPatternHeuristic(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, int iterlim)
Definition: probdata_rpa.c:1809
Definition: type_result.h:36
pattern data for ringpacking problem
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4195
Definition: type_retcode.h:33
int SCIPpatternGetElementType(SCIP_PATTERN *pattern, int i)
Definition: pattern.c:216
Definition: type_result.h:42
Definition: pattern.h:35
constraint handler for ringpacking
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:277
SCIP_Real * SCIPprobdataGetRexts(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1520
static SCIP_RETCODE enforceSol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: cons_rpa.c:197
SCIP_Real SCIPpatternGetElementPosX(SCIP_PATTERN *pattern, int elem)
Definition: pattern.c:248
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:311
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8273
SCIP_Real SCIPprobdataGetWidth(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1550
SCIP_PATTERNTYPE SCIPpatternGetPatternType(SCIP_PATTERN *pattern)
Definition: pattern.c:287
void SCIPprobdataGetCInfos(SCIP_PROBDATA *probdata, SCIP_PATTERN ***cpatterns, SCIP_VAR ***cvars, int *ncpatterns)
Definition: probdata_rpa.c:1571
SCIP_Real SCIPpatternGetElementPosY(SCIP_PATTERN *pattern, int elem)
Definition: pattern.c:260
SCIP_RETCODE SCIPverifyCircularPatternNLP(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, SCIP_Longint nodelim)
Definition: probdata_rpa.c:1941
Definition: type_var.h:84
SCIPallocBlockMemory(scip, subsol))
Definition: objbenders.h:33
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:453
SCIP_Real * SCIPprobdataGetRints(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1530
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
Definition: type_result.h:39
Definition: struct_event.h:195
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1766