cons_stp.c
Go to the documentation of this file.
22 * This file checks solutions for feasibility and separates violated model constraints. For more details see \ref STP_CONS page.
26 * In this file a constraint handler checking solutions for feasibility and separating violated model constraints is implemented.
27 * The separation problem for the cut inequalities described in \ref STP_PROBLEM can be solved by a max-flow algorithm in
28 * polynomial time. Regarding the variable values of a given LP solution as capacities on the edges, one can check for each
29 * \f$ t \in T \setminus \{r\} \f$, with \f$ r \f$ being the root, whether the minimal \f$ (r, t) \f$-cut is less than one. In this case,
30 * a violated cut inequality has been found, otherwise none exists. In order to calculate such a minimal cut an adaptation of Hao
31 * and Orlin's preflow-push algorithm (see A Faster Algorithm for Finding the Minimum Cut in a Directed Graph) is used. Furthermore, the file implements a dual ascent heuristic, based on a concept described
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
73 #define CONSHDLR_ENFOPRIORITY 0 /**< priority of the constraint handler for constraint enforcing */
74 #define CONSHDLR_CHECKPRIORITY 9999999 /**< priority of the constraint handler for checking feasibility */
75 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
76 #define CONSHDLR_PROPFREQ 0 /**< frequency for propagating domains; zero means only preprocessing propagation */
77 #define CONSHDLR_EAGERFREQ 1 /**< frequency for using all instead of only the useful constraints in separation,
79 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
80 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
81 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
83 #define DEFAULT_MAXROUNDS 10 /**< maximal number of separation rounds per node (-1: unlimited) */
84 #define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of separation rounds in the root node (-1: unlimited) */
85 #define DEFAULT_MAXSEPACUTS INT_MAX /**< maximal number of cuts separated per separation round */
86 #define DEFAULT_MAXSEPACUTSROOT INT_MAX /**< maximal number of cuts separated per separation round in the root node */
145 int maxsepacutsroot; /**< maximal number of cuts separated per separation round in the root node */
205 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "twocut", 1.0, SCIPinfinity(scip), local, FALSE, TRUE) );
664 /* we do not longer support any other flow as they slow everything down and are of little use anyway todo remove user parameter */
821 /* push as much as possible out of perpetually dormant nodes (possibly to other dormant nodes) */
947 graph_mincut_exec(g, root, i, nnodes, newnedges, rootcutsize, rootcut, capa, w, start, edgeflipped, headarr, rerun);
975 SCIP_CALL( cut_add(scip, conshdlr, g, xval, capa, nested_cut || disjunct_cut, ncuts, localcut, &addedcut) );
1037 SCIP_CALL( cut_add(scip, conshdlr, g, xval, capa, nested_cut || disjunct_cut, ncuts, &addedcut) );
1055 while( nested_cut ); /* Nested Cut is CONSTANT todo why not only one round? seems to make no sense whatsoever */
1221 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
1242 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
1289 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
1292 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1298 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1410 SCIP_CALL( SCIPStpValidateSol(scip, consdata->graph, SCIPprobdataGetXval(scip, NULL), &feasible) );
1435 SCIP_CALL( SCIPStpValidateSol(scip, consdata->graph, SCIPprobdataGetXval(scip, NULL), &feasible) );
1597 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropStp, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
1701 STP_Bool* RESTRICT nodearrchar /**< STP_Bool vertices array for internal computations or NULL */
1720 const SCIP_Real maxdeviation = (damaxdeviation > 0.0) ? damaxdeviation : DEFAULT_DAMAXDEVIATION;
1810 SCIP_CALL( dualascent_init(scip, g, start, edgearr, root, is_pseudoroot, ncsredges, gmark, active, pqueue,
1840 const SCIP_Real prio2 = (SCIPpqueueNElems(pqueue) > 0) ? ((GNODE*) SCIPpqueueFirst(pqueue))->dist : FARAWAY;
2246 SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, NULL, g, rescap, unsatarcs, cutverts, root, mynodearrchar, &success, TRUE) );
2380 else if( transgraph->tail[i] == pseudoroot && !Is_term(transgraph->term[transgraph->head[i]]) )
2517 if( SCIPisLE(scip, (currscore - prio1) / prio1, maxdeviation) || (SCIPpqueueNElems(pqueue) == 0) )
2570 SCIP_CALL(SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "da", 1.0, SCIPinfinity(scip), FALSE, FALSE, TRUE));
2672 SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, NULL, g, rescap, unsatarcs, cutverts, -1, active, &success, TRUE));
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4197
static int graph_next_term(const GRAPH *g, int terms, int *term, const int *w, const SCIP_Bool firstrun)
Definition: cons_stp.c:277
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_linear.c:17748
Definition: type_result.h:33
Definition: type_result.h:37
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:586
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
Definition: struct_scip.h:59
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:934
Constraint handler for Steiner problems.
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
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4263
Definition: struct_misc.h:69
Definition: type_set.h:37
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2152
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:18089
Definition: struct_var.h:198
SCIP_RETCODE SCIPStpDualAscentPcMw(SCIP *scip, GRAPH *g, SCIP_Real *redcost, SCIP_Real *objval, SCIP_Bool addcuts, SCIP_Bool ascendandprune, int nruns)
Definition: cons_stp.c:2268
static SCIP_RETCODE sep_flow(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSDATA *consdata, int maxcuts, int *ncuts)
Definition: cons_stp.c:392
reduction and dual-cost based primal heuristic for Steiner problems
void graph_mincut_exec(const GRAPH *, const int, const int, const int, const int, const int, const int *, const int *, int *RESTRICT, const int *, const int *, const int *, const SCIP_Bool)
void SCIPStpBranchruleInitNodeState(const GRAPH *g, int *nodestate)
Definition: branch_stp.c:683
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:862
Problem data for stp problem.
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:563
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
Definition: type_result.h:40
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1604
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:2357
SCIP_RETCODE SCIPStpDualAscent(SCIP *scip, const GRAPH *g, SCIP_Real *RESTRICT redcost, SCIP_Real *RESTRICT nodearrreal, SCIP_Real *objval, SCIP_Bool addcuts, SCIP_Bool ascendandprune, GNODE **gnodearrterms, const int *result, int *RESTRICT edgearrint, int *RESTRICT nodearrint, int root, SCIP_Bool is_pseudoroot, SCIP_Real damaxdeviation, STP_Bool *RESTRICT nodearrchar)
Definition: cons_stp.c:1687
SCIP_RETCODE SCIPStpHeurAscendPruneRun(SCIP *scip, SCIP_HEUR *heur, const GRAPH *g, const SCIP_Real *redcosts, int *edgearrint, int *nodearrint, int root, STP_Bool *nodearrchar, SCIP_Bool *solfound, SCIP_Bool addsol)
Definition: heur_ascendprune.c:290
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
static SCIP_Bool is_active(const int *active, int realtail, int dfsbase)
Definition: cons_stp.c:157
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1581
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1337
Definition: type_result.h:35
Definition: struct_cons.h:37
Definition: struct_cons.h:117
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:429
Definition: type_result.h:36
internal miscellaneous methods
Definition: type_set.h:43
Definition: type_retcode.h:33
static SCIP_RETCODE cut_add(SCIP *scip, SCIP_CONSHDLR *conshdlr, const GRAPH *g, const SCIP_Real *xval, int *capa, const int updatecapa, int *ncuts, SCIP_Bool local, SCIP_Bool *success)
Definition: cons_stp.c:177
reduction-based primal heuristic for Steiner problems
int GNODECmpByDist(void *first_arg, void *second_arg)
static SCIP_RETCODE dualascent_init(SCIP *scip, const GRAPH *g, const int *RESTRICT start, const int *RESTRICT edgearr, int root, SCIP_Bool is_pseudoroot, int ncsredges, int *gmark, int *RESTRICT active, SCIP_PQUEUE *pqueue, GNODE **gnodearr, SCIP_Real *RESTRICT rescap, SCIP_Real *dualobj, int *augmentingcomponent)
Definition: cons_stp.c:1081
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:220
static void set_capacity(const GRAPH *g, const SCIP_Bool creep_flow, const int flip, int *capa, const SCIP_Real *xval)
Definition: cons_stp.c:349
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:332
static SCIP_RETCODE sep_2cut(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSDATA *consdata, const int *termorg, int maxcuts, int *ncuts)
Definition: cons_stp.c:649
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4187
Definition: struct_lp.h:192
SCIP_RETCODE SCIPStpValidateSol(SCIP *, const GRAPH *, const double *, SCIP_Bool *)
Definition: validate.c:136
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:88
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
SCIP_RETCODE SCIPcreateConsStp(SCIP *scip, SCIP_CONS **cons, const char *name, GRAPH *graph)
Definition: cons_stp.c:1636
includes various files containing graph methods used for Steiner tree problems
Portable defintions.
Steiner vertex branching rule.
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:221
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1236
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:812
void graph_get_csr(const GRAPH *, int *RESTRICT, int *RESTRICT, int *RESTRICT, int *)
SCIP_RETCODE SCIPStpBranchruleApplyVertexChgs(SCIP *scip, int *vertexchgs, GRAPH *graph)
Definition: branch_stp.c:708
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:786
Definition: misc_stp.h:41
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1641
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4539
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
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
Definition: probdata_stp.c:2551
Definition: type_retcode.h:45
SCIP_RETCODE graph_pc_getSap(SCIP *, GRAPH *, GRAPH **, SCIP_Real *)
Definition: grphbase.c:1075
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
Definition: objbenders.h:33
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:266
Definition: type_result.h:39
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:609
SCIP callable library.
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1335
void SCIPStpConshdlrSetGraph(SCIP *scip, const GRAPH *g)
Definition: cons_stp.c:1666