cons_rpa.c
Go to the documentation of this file.
29 * This constraint handler is used to store information about which (not verified) rectangular patterns have been locked
32 * @todo Is it enough the lock the unverified circular pattern variables only in the positive direction?
36/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
49#define CONSHDLR_ENFOPRIORITY 1 /**< priority of the constraint handler for constraint enforcing */
50#define CONSHDLR_CHECKPRIORITY -1 /**< priority of the constraint handler for checking feasibility */
51#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
53#define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
56/* TODO: remove properties which are never used because the corresponding routines are not supported */
58#define CONSHDLR_SEPAFREQ -1 /**< frequency for separating cuts; zero means to separate only in the root node */
59#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
61#define CONSHDLR_PROPFREQ -1 /**< frequency for propagating domains; zero means only preprocessing propagation */
62#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
63#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler*/
65#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
66#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
76#define DEFAULT_VERIFICATION_HEURITERLIM 1000 /**< iteration limit for each heuristic verification */
77#define DEFAULT_VERIFICATION_TOTALTILIM 3600.0 /**< total time limit for all verification problems during the solving process */
93 SCIP_Real timeleft; /**< time left for solving verification problem during the solving process */
104/** auxiliary function to decide whether a proposed solution is feasible; a solution is called feasible if and only if
105 * z*_C = 0 holds for all circular patterns that are either not packable, i.e., SCIP_PACKABLE_NO or SCIP_PACKABLE_UNKNOWN
138 SCIPdebugMsg(scip, "solution might be infeasible because of circular pattern %d = (%g,%d)\n", p,
148/** tries to verify a circular pattern; it first tries to call heuristic(s) and afterwards uses a verification NLP */
170 heurtimelimit = MIN(timelimit - SCIPgetSolvingTime(scip), conshdlrdata->heurtilim); /*lint !e666*/
172 SCIPdebugMsg(scip, "call verification heuristic (%g,%d)\n", heurtimelimit, conshdlrdata->heuriterlim);
174 SCIP_CALL( SCIPverifyCircularPatternHeuristic(scip, probdata, pattern, heurtimelimit, conshdlrdata->heuriterlim) );
180 nlptimelimit = MIN3(conshdlrdata->timeleft, timelimit - SCIPgetSolvingTime(scip), conshdlrdata->nlptilim); /*lint !e666*/
182 SCIPdebugMsg(scip, "call verification NLP (%g,%lld)\n", nlptimelimit, conshdlrdata->nlpnodelim);
184 SCIP_CALL( SCIPverifyCircularPatternNLP(scip, probdata, pattern, nlptimelimit, conshdlrdata->nlpnodelim) );
258 if( SCIPpatternGetPackableStatus(cpatterns[p]) == SCIP_PACKABLE_UNKNOWN && !conshdlrdata->tried[p] )
295 SCIPdebugMsg(scip, "fix unknown pattern %d in [%g,%g] (success=%u)\n", p, SCIPvarGetLbLocal(cvars[p]),
368 assert(SCIPisFeasZero(scip, val) || SCIPpatternGetPackableStatus(patterns[p]) == SCIP_PACKABLE_YES);
429 SCIPinfoMessage(scip, file, "\\draw[draw=none,fill=white] (%g,%g) circle (%g);\n", 0.0, 0.0, rints[type]);
441 SCIPinfoMessage(scip, file, "\\draw[draw=none,fill=white] (%g,%g) circle (%g);\n", x, y, _rint);
459 SCIPinfoMessage(scip, file, "\\subsection*{\\texttt{\\pname} = %g}\n", SCIPgetSolVal(scip, sol, vars[p]));
472 /* SCIPinfoMessage(scip, file, "\\draw[draw=none,fill=white] (%g,%g) circle (%g);\n", x, y, _rint); */
496/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
515/** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
538 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, conshdlrdata->eventhdlr, NULL, NULL) );
544/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
565 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, conshdlrdata->eventhdlr, NULL, -1) );
646 * A pattern might change its status during a later verification step and we only need to lock patterns with a
647 * SCIP_PACKABLE_UNKNOWN status. For this reason, we keep track of patterns that have been locked. The CONSLOCK
648 * callback should only be called twice because the constraint handler does not have constraints.
710 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &conshdlrdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
717 &conshdlrdata->nlptilim, FALSE, DEFAULT_VERIFICATION_NLPTILIM, -1.0, SCIP_REAL_MAX, NULL, NULL) );
722 &conshdlrdata->nlpnodelim, FALSE, DEFAULT_VERIFICATION_NLPNODELIM, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
727 &conshdlrdata->heurtilim, FALSE, DEFAULT_VERIFICATION_HEURTILIM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
737 &conshdlrdata->timeleft, FALSE, DEFAULT_VERIFICATION_TOTALTILIM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
static SCIP_RETCODE verifyCircularPattern(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)
Definition: cons_rpa.c:150
static SCIP_RETCODE enforceSol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: cons_rpa.c:205
constraint handler for ringpacking
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
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:111
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:83
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:139
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
SCIP_RETCODE SCIPgetStringParam(SCIP *scip, const char *name, char **value)
Definition: scip_param.c:345
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:181
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
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:104
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:286
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:320
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1631
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
Definition: objbenders.h:44
SCIP_Real SCIPpatternGetElementPosY(SCIP_PATTERN *pattern, int elem)
Definition: pattern.c:269
SCIP_Real SCIPpatternGetElementPosX(SCIP_PATTERN *pattern, int elem)
Definition: pattern.c:257
SCIP_PATTERNTYPE SCIPpatternGetPatternType(SCIP_PATTERN *pattern)
Definition: pattern.c:296
SCIP_PACKABLE SCIPpatternGetPackableStatus(SCIP_PATTERN *pattern)
Definition: pattern.c:335
int SCIPpatternGetElementType(SCIP_PATTERN *pattern, int i)
Definition: pattern.c:225
int SCIPpatternGetCircleType(SCIP_PATTERN *pattern)
Definition: pattern.c:309
pattern data for ringpacking problem
SCIP_Real SCIPprobdataGetHeight(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1571
SCIP_RETCODE SCIPverifyCircularPatternNLP(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, SCIP_Longint nodelim)
Definition: probdata_rpa.c:1951
int * SCIPprobdataGetDemands(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1550
void SCIPprobdataGetRInfos(SCIP_PROBDATA *probdata, SCIP_PATTERN ***rpatterns, SCIP_VAR ***rvars, int *nrpatterns)
Definition: probdata_rpa.c:1599
int SCIPprobdataGetNTypes(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1520
void SCIPprobdataGetCInfos(SCIP_PROBDATA *probdata, SCIP_PATTERN ***cpatterns, SCIP_VAR ***cvars, int *ncpatterns)
Definition: probdata_rpa.c:1581
SCIP_Real * SCIPprobdataGetRexts(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1530
SCIP_RETCODE SCIPverifyCircularPatternHeuristic(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, int iterlim)
Definition: probdata_rpa.c:1819
SCIP_Real * SCIPprobdataGetRints(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1540
void SCIPprobdataInvalidateDualbound(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1685
void SCIPcheckPattern(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)
Definition: probdata_rpa.c:2151
SCIP_Real SCIPprobdataGetWidth(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1560
Problem data for ringpacking problem.
Definition: struct_cons.h:127
Definition: struct_event.h:205
Definition: pattern.h:57
Definition: struct_sol.h:74
Definition: struct_var.h:208
Definition: struct_scip.h:70