ConshdlrSubtour.cpp
Go to the documentation of this file.
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
177 // create a new cutting plane for every suitable arc (representing a cut with value < 2) of the Gomory Hu Tree
181 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "subtour", 2.0, SCIPinfinity(scip), FALSE, FALSE, TRUE) );
206 // Add violated cut. The cuts produced by ghc_tree are violated by at least the feasibility tolerance. If we
207 // are enforcing, then this is enough to add the cut. Otherwise (we are separating), we check whether the
260 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons),
269 * Separates all constraints of the constraint handler. The method is called in the LP solution loop,
272 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation
273 * method should process only the useful constraints in most runs, and only occasionally the remaining
276 * possible return values for *result (if more than one applies, the first in the list should be used):
281 * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
295 * Separates all constraints of the constraint handler. The method is called outside the LP solution loop (e.g., by
299 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation
300 * method should process only the useful constraints in most runs, and only occasionally the remaining
303 * possible return values for *result (if more than one applies, the first in the list should be used):
308 * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
322 * The method is called at the end of the node processing loop for a node where the LP was solved.
323 * The LP solution has to be checked for feasibility. If possible, an infeasibility should be resolved by
324 * branching, reducing a variable's domain to exclude the solution or separating the solution with a valid
327 * The enforcing methods of the active constraint handlers are called in decreasing order of their enforcing
328 * priorities until the first constraint handler returned with the value SCIP_CUTOFF, SCIP_SEPARATED,
330 * The integrality constraint handler has an enforcing priority of zero. A constraint handler which can
331 * (or wants) to enforce its constraints only for integral solutions should have a negative enforcing priority
333 * A constraint handler which wants to incorporate its own branching strategy even on non-integral
334 * solutions must have an enforcing priority greater than zero (e.g. the SOS-constraint incorporates
337 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing
338 * method should process the useful constraints first. The other nconss - nusefulconss constraints should only
341 * possible return values for *result (if more than one applies, the first in the list should be used):
346 * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
366 * The method is called at the end of the node processing loop for a node where the LP was not solved.
367 * The pseudo solution has to be checked for feasibility. If possible, an infeasibility should be resolved by
368 * branching, reducing a variable's domain to exclude the solution or adding an additional constraint.
369 * Separation is not possible, since the LP is not processed at the current node. All LP informations like
372 * Like in the enforcing method for LP solutions, the enforcing methods of the active constraint handlers are
373 * called in decreasing order of their enforcing priorities until the first constraint handler returned with
376 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing
377 * method should process the useful constraints first. The other nconss - nusefulconss constraints should only
380 * If the pseudo solution's objective value is lower than the lower bound of the node, it cannot be feasible
381 * and the enforcing method may skip it's check and set *result to SCIP_DIDNOTRUN. However, it can also process
384 * possible return values for *result (if more than one applies, the first in the list should be used):
388 * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
389 * - SCIP_SOLVELP : at least one constraint is infeasible, and this can only be resolved by solving the SCIP_LP
412 * The check methods of the active constraint handlers are called in decreasing order of their check
414 * The integrality constraint handler has a check priority of zero. A constraint handler which can
415 * (or wants) to check its constraints only for integral solutions should have a negative check priority
417 * A constraint handler which wants to check feasibility even on non-integral solutions must have a
418 * check priority greater than zero (e.g. if the check is much faster than testing all variables for
421 * In some cases, integrality conditions or rows of the current LP don't have to be checked, because their
465 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The propagation
466 * method should process only the useful constraints in most runs, and only occasionally the remaining
487 * It should update the rounding locks of all associated variables with calls to SCIPaddVarLocksType(),
490 * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlockspos, nlocksneg), saying that rounding down is
491 * potentially rendering the (positive) constraint infeasible and rounding up is potentially rendering the
494 * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos), saying that rounding up is
495 * potentially rendering the constraint's negation infeasible and rounding up is potentially rendering the
497 * - If the constraint may get violated by changing the variable in any direction, it should call
498 * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg).
500 * Consider the linear constraint "3x -5y +2z <= 7" as an example. The variable rounding lock method of the
501 * linear constraint handler should call SCIPaddVarLocksType(scip, x, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos),
504 * that rounding up of x and z and rounding down of y can destroy the feasibility of the constraint, while rounding
505 * down of x and z and rounding up of y can destroy the feasibility of the constraint's negation "3x -5y +2z > 7".
507 * SCIPaddVarLocksType(scip, ..., SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) on all variables,
508 * since rounding in both directions of each variable can destroy both the feasibility of the constraint and it's negation
511 * If the constraint itself contains other constraints as sub constraints (e.g. the "or" constraint concatenation
512 * "c(x) or d(x)"), the rounding lock methods of these constraints should be called in a proper way.
514 * SCIPaddConsLocks(scip, c, nlockspos, nlocksneg), saying that infeasibility of c may lead to infeasibility of
515 * the (positive) constraint, and infeasibility of c's negation (i.e. feasibility of c) may lead to infeasibility
517 * - If the constraint may get violated by the feasibility of the sub constraint c, it should call
518 * SCIPaddConsLocks(scip, c, nlocksneg, nlockspos), saying that infeasibility of c may lead to infeasibility of
519 * the constraint's negation (i.e. feasibility of the constraint), and infeasibility of c's negation (i.e. feasibility
521 * - If the constraint may get violated by any change in the feasibility of the sub constraint c, it should call
524 * Consider the or concatenation "c(x) or d(x)". The variable rounding lock method of the or constraint handler
525 * should call SCIPaddConsLocks(scip, c, nlockspos, nlocksneg) and SCIPaddConsLocks(scip, d, nlockspos, nlocksneg)
528 * As a second example, consider the equivalence constraint "y <-> c(x)" with variable y and constraint c. The
529 * constraint demands, that y == 1 if and only if c(x) is satisfied. The variable lock method of the corresponding
530 * constraint handler should call SCIPaddVarLocksType(scip, y, SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) and
531 * SCIPaddConsLocks(scip, c, nlockspos + nlocksneg, nlockspos + nlocksneg), because any modification to the
532 * value of y or to the feasibility of c can alter the feasibility of the equivalence constraint.
547 SCIP_CALL( SCIPaddVarLocksType(scip, g->edges[i].var, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos) );
555 * This method should iterate over all constraints of the constraint handler and delete all variables
572 * The constraint handler should store a representation of the constraint into the given text file.
585 SCIPinfoMessage(scip, file, "subtour of Graph G with %d nodes and %d edges\n", g->nnodes, g->nedges);
600 * The constraint handler can provide a copy method, which copies a constraint from one SCIP data structure into a other
652 SCIP_Bool removable /**< should the constraint be removed from the LP due to aging or cleanup? */
672 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
Definition: type_result.h:42
Definition: type_result.h:46
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
Definition: struct_scip.h:68
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:886
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIP_DECL_CONSSEPALP(ConshdlrSubtour::scip_sepalp)
Definition: ConshdlrSubtour.cpp:285
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1695
SCIP_DECL_CONSENFOPS(ConshdlrSubtour::scip_enfops)
Definition: ConshdlrSubtour.cpp:394
generator for global cuts in undirected graphs
Definition: type_result.h:49
SCIP_DECL_CONSSEPASOL(ConshdlrSubtour::scip_sepasol)
Definition: ConshdlrSubtour.cpp:312
SCIP_DECL_CONSDELETE(ConshdlrSubtour::scip_delete)
Definition: ConshdlrSubtour.cpp:232
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
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:943
SCIP_DECL_CONSENFOLP(ConshdlrSubtour::scip_enfolp)
Definition: ConshdlrSubtour.cpp:350
static SCIP_RETCODE sepaSubtour(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_Bool enforce, SCIP_RESULT *result)
Definition: ConshdlrSubtour.cpp:128
Definition: struct_sol.h:73
SCIP_DECL_CONSCHECK(ConshdlrSubtour::scip_check)
Definition: ConshdlrSubtour.cpp:429
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4265
Definition: ProbDataTSP.h:42
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:117
SCIP_RETCODE SCIPcreateConsSubtour(SCIP *scip, SCIP_CONS **cons, const char *name, GRAPH *graph, 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)
Definition: ConshdlrSubtour.cpp:639
Definition: type_result.h:44
Definition: struct_cons.h:46
Definition: struct_cons.h:126
Definition: pqueue.h:37
Definition: type_result.h:45
SCIP_DECL_CONSTRANS(ConshdlrSubtour::scip_trans)
Definition: ConshdlrSubtour.cpp:244
C++ wrapper classes for SCIP.
Definition: type_retcode.h:42
SCIP_DECL_CONSDELVARS(ConshdlrSubtour::scip_delvars)
Definition: ConshdlrSubtour.cpp:564
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
C++ constraint handler for TSP subtour elimination constraints.
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2482
Definition: struct_lp.h:201
Constraint handler for linear constraints in their most general form, .
Definition: ConshdlrSubtour.h:42
Definition: GomoryHuTree.h:40
Definition of base class for all clonable classes which define problem data.
Definition: objprobcloneable.h:51
SCIP_DECL_CONSHDLRCLONE(ObjProbCloneable *ConshdlrSubtour::clone)
Definition: ConshdlrSubtour.cpp:591
SCIP_Bool ghc_tree(GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)
Definition: GomoryHuTree.cpp:632
Definition: GomoryHuTree.h:63
Definition: ConshdlrSubtour.h:38
Definition: type_var.h:93
SCIP_DECL_CONSPRINT(ConshdlrSubtour::scip_print)
Definition: ConshdlrSubtour.cpp:574
Definition: type_retcode.h:54
static SCIP_Bool findSubtour(SCIP *scip, GRAPH *graph, SCIP_SOL *sol)
Definition: ConshdlrSubtour.cpp:60
Definition: GomoryHuTree.h:79
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:1391
Definition: objbenders.h:43
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
Definition: type_result.h:48