ConshdlrSubtour.h
Go to the documentation of this file.
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
68 * Separates all constraints of the constraint handler. The method is called in the LP solution loop,
71 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation
72 * method should process only the useful constraints in most runs, and only occasionally the remaining
75 * possible return values for *result (if more than one applies, the first in the list should be used):
80 * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
88 * Separates all constraints of the constraint handler. The method is called outside the LP solution loop (e.g., by
92 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation
93 * method should process only the useful constraints in most runs, and only occasionally the remaining
96 * possible return values for *result (if more than one applies, the first in the list should be used):
101 * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
109 * The method is called at the end of the node processing loop for a node where the LP was solved.
110 * The LP solution has to be checked for feasibility. If possible, an infeasibility should be resolved by
111 * branching, reducing a variable's domain to exclude the solution or separating the solution with a valid
114 * The enforcing methods of the active constraint handlers are called in decreasing order of their enforcing
115 * priorities until the first constraint handler returned with the value SCIP_CUTOFF, SCIP_SEPARATED,
117 * The integrality constraint handler has an enforcing priority of zero. A constraint handler which can
118 * (or wants) to enforce its constraints only for integral solutions should have a negative enforcing priority
120 * A constraint handler which wants to incorporate its own branching strategy even on non-integral
121 * solutions must have an enforcing priority greater than zero (e.g. the SOS-constraint incorporates
124 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing
125 * method should process the useful constraints first. The other nconss - nusefulconss constraints should only
128 * possible return values for *result (if more than one applies, the first in the list should be used):
133 * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
141 * The method is called at the end of the node processing loop for a node where the LP was not solved.
142 * The pseudo solution has to be checked for feasibility. If possible, an infeasibility should be resolved by
143 * branching, reducing a variable's domain to exclude the solution or adding an additional constraint.
144 * Separation is not possible, since the LP is not processed at the current node. All LP informations like
147 * Like in the enforcing method for LP solutions, the enforcing methods of the active constraint handlers are
148 * called in decreasing order of their enforcing priorities until the first constraint handler returned with
151 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing
152 * method should process the useful constraints first. The other nconss - nusefulconss constraints should only
155 * If the pseudo solution's objective value is lower than the lower bound of the node, it cannot be feasible
156 * and the enforcing method may skip it's check and set *result to SCIP_DIDNOTRUN. However, it can also process
159 * possible return values for *result (if more than one applies, the first in the list should be used):
163 * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
164 * - SCIP_SOLVELP : at least one constraint is infeasible, and this can only be resolved by solving the SCIP_LP
175 * The check methods of the active constraint handlers are called in decreasing order of their check
177 * The integrality constraint handler has a check priority of zero. A constraint handler which can
178 * (or wants) to check its constraints only for integral solutions should have a negative check priority
180 * A constraint handler which wants to check feasibility even on non-integral solutions must have a
181 * check priority greater than zero (e.g. if the check is much faster than testing all variables for
184 * In some cases, integrality conditions or rows of the current LP don't have to be checked, because their
196 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The propagation
197 * method should process only the useful constraints in most runs, and only occasionally the remaining
212 * It should update the rounding locks of all associated variables with calls to SCIPaddVarLocksType(),
215 * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlockspos, nlocksneg), saying that rounding down is
216 * potentially rendering the (positive) constraint infeasible and rounding up is potentially rendering the
219 * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos), saying that rounding up is
220 * potentially rendering the constraint's negation infeasible and rounding up is potentially rendering the
222 * - If the constraint may get violated by changing the variable in any direction, it should call
223 * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg).
225 * Consider the linear constraint "3x -5y +2z <= 7" as an example. The variable rounding lock method of the
226 * linear constraint handler should call SCIPaddVarLocksType(scip, x, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos),
229 * that rounding up of x and z and rounding down of y can destroy the feasibility of the constraint, while rounding
230 * down of x and z and rounding up of y can destroy the feasibility of the constraint's negation "3x -5y +2z > 7".
232 * SCIPaddVarLocksType(scip, ..., SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) on all variables,
233 * since rounding in both directions of each variable can destroy both the feasibility of the constraint and it's negation
236 * If the constraint itself contains other constraints as sub constraints (e.g. the "or" constraint concatenation
237 * "c(x) or d(x)"), the rounding lock methods of these constraints should be called in a proper way.
239 * SCIPaddConsLocks(scip, c, nlockspos, nlocksneg), saying that infeasibility of c may lead to infeasibility of
240 * the (positive) constraint, and infeasibility of c's negation (i.e. feasibility of c) may lead to infeasibility
242 * - If the constraint may get violated by the feasibility of the sub constraint c, it should call
243 * SCIPaddConsLocks(scip, c, nlocksneg, nlockspos), saying that infeasibility of c may lead to infeasibility of
244 * the constraint's negation (i.e. feasibility of the constraint), and infeasibility of c's negation (i.e. feasibility
246 * - If the constraint may get violated by any change in the feasibility of the sub constraint c, it should call
249 * Consider the or concatenation "c(x) or d(x)". The variable rounding lock method of the or constraint handler
250 * should call SCIPaddConsLocks(scip, c, nlockspos, nlocksneg) and SCIPaddConsLocks(scip, d, nlockspos, nlocksneg)
253 * As a second example, consider the equivalence constraint "y <-> c(x)" with variable y and constraint c. The
254 * constraint demands, that y == 1 if and only if c(x) is satisfied. The variable lock method of the corresponding
255 * constraint handler should call SCIPaddVarLocksType(scip, y, SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) and
256 * SCIPaddConsLocks(scip, c, nlockspos + nlocksneg, nlockspos + nlocksneg), because any modification to the
257 * value of y or to the feasibility of c can alter the feasibility of the equivalence constraint.
263 * This method should iterate over all constraints of the constraint handler and delete all variables
276 * The constraint handler should store a representation of the constraint into the given text file.
291 * The constraint handler can provide a copy method, which copies a constraint from one SCIP data structure into a other
311 SCIP_Bool removable /**< should the constraint be removed from the LP due to aging or cleanup? */
Definition: struct_scip.h:68
ObjConshdlr(SCIP *scip, const char *name, const char *desc, int sepapriority, int enfopriority, int checkpriority, int sepafreq, int propfreq, int eagerfreq, int maxprerounds, SCIP_Bool delaysepa, SCIP_Bool delayprop, SCIP_Bool needscons, SCIP_PROPTIMING proptiming, SCIP_PRESOLTIMING presoltiming)
Definition: objconshdlr.h:108
virtual SCIP_DECL_CONSDELETE(scip_delete)
virtual SCIP_DECL_CONSCOPY(scip_copy)
virtual SCIP_DECL_CONSSEPALP(scip_sepalp)
virtual SCIP_DECL_CONSHDLRISCLONEABLE(iscloneable)
Definition: ConshdlrSubtour.h:281
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: struct_cons.h:46
virtual SCIP_DECL_CONSENFOPS(scip_enfops)
virtual SCIP_DECL_CONSENFOLP(scip_enfolp)
C++ wrapper classes for SCIP.
virtual SCIP_DECL_CONSPROP(scip_prop)
virtual SCIP_DECL_CONSDELVARS(scip_delvars)
C++ problem data for TSP.
virtual SCIP_DECL_CONSTRANS(scip_trans)
virtual SCIP_DECL_CONSLOCK(scip_lock)
virtual SCIP_DECL_CONSCHECK(scip_check)
Definition: ConshdlrSubtour.h:42
Definition of base class for all clonable classes which define problem data.
Definition: objprobcloneable.h:51
virtual SCIP_DECL_CONSPRINT(scip_print)
Definition: ConshdlrSubtour.h:38
virtual SCIP_DECL_CONSHDLRCLONE(scip::ObjProbCloneable *clone)
Definition: GomoryHuTree.h:79
virtual SCIP_DECL_CONSSEPASOL(scip_sepasol)
Definition: objbenders.h:43