ConshdlrSubtour.h
Go to the documentation of this file.
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
59 * Separates all constraints of the constraint handler. The method is called in the LP solution loop,
62 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation
63 * method should process only the useful constraints in most runs, and only occasionally the remaining
66 * possible return values for *result (if more than one applies, the first in the list should be used):
71 * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
79 * Separates all constraints of the constraint handler. The method is called outside the LP solution loop (e.g., by
83 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation
84 * method should process only the useful constraints in most runs, and only occasionally the remaining
87 * possible return values for *result (if more than one applies, the first in the list should be used):
92 * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
100 * The method is called at the end of the node processing loop for a node where the LP was solved.
101 * The LP solution has to be checked for feasibility. If possible, an infeasibility should be resolved by
102 * branching, reducing a variable's domain to exclude the solution or separating the solution with a valid
105 * The enforcing methods of the active constraint handlers are called in decreasing order of their enforcing
106 * priorities until the first constraint handler returned with the value SCIP_CUTOFF, SCIP_SEPARATED,
108 * The integrality constraint handler has an enforcing priority of zero. A constraint handler which can
109 * (or wants) to enforce its constraints only for integral solutions should have a negative enforcing priority
111 * A constraint handler which wants to incorporate its own branching strategy even on non-integral
112 * solutions must have an enforcing priority greater than zero (e.g. the SOS-constraint incorporates
115 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing
116 * method should process the useful constraints first. The other nconss - nusefulconss constraints should only
119 * possible return values for *result (if more than one applies, the first in the list should be used):
124 * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
132 * The method is called at the end of the node processing loop for a node where the LP was not solved.
133 * The pseudo solution has to be checked for feasibility. If possible, an infeasibility should be resolved by
134 * branching, reducing a variable's domain to exclude the solution or adding an additional constraint.
135 * Separation is not possible, since the LP is not processed at the current node. All LP informations like
138 * Like in the enforcing method for LP solutions, the enforcing methods of the active constraint handlers are
139 * called in decreasing order of their enforcing priorities until the first constraint handler returned with
142 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing
143 * method should process the useful constraints first. The other nconss - nusefulconss constraints should only
146 * If the pseudo solution's objective value is lower than the lower bound of the node, it cannot be feasible
147 * and the enforcing method may skip it's check and set *result to SCIP_DIDNOTRUN. However, it can also process
150 * possible return values for *result (if more than one applies, the first in the list should be used):
154 * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
155 * - SCIP_SOLVELP : at least one constraint is infeasible, and this can only be resolved by solving the SCIP_LP
166 * The check methods of the active constraint handlers are called in decreasing order of their check
168 * The integrality constraint handler has a check priority of zero. A constraint handler which can
169 * (or wants) to check its constraints only for integral solutions should have a negative check priority
171 * A constraint handler which wants to check feasibility even on non-integral solutions must have a
172 * check priority greater than zero (e.g. if the check is much faster than testing all variables for
175 * In some cases, integrality conditions or rows of the current LP don't have to be checked, because their
187 * The first nusefulconss constraints are the ones, that are identified to likely be violated. The propagation
188 * method should process only the useful constraints in most runs, and only occasionally the remaining
203 * It should update the rounding locks of all associated variables with calls to SCIPaddVarLocksType(),
206 * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlockspos, nlocksneg), saying that rounding down is
207 * potentially rendering the (positive) constraint infeasible and rounding up is potentially rendering the
210 * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos), saying that rounding up is
211 * potentially rendering the constraint's negation infeasible and rounding up is potentially rendering the
213 * - If the constraint may get violated by changing the variable in any direction, it should call
214 * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg).
216 * Consider the linear constraint "3x -5y +2z <= 7" as an example. The variable rounding lock method of the
217 * linear constraint handler should call SCIPaddVarLocksType(scip, x, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos),
220 * that rounding up of x and z and rounding down of y can destroy the feasibility of the constraint, while rounding
221 * down of x and z and rounding up of y can destroy the feasibility of the constraint's negation "3x -5y +2z > 7".
223 * SCIPaddVarLocksType(scip, ..., SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) on all variables,
224 * since rounding in both directions of each variable can destroy both the feasibility of the constraint and it's negation
227 * If the constraint itself contains other constraints as sub constraints (e.g. the "or" constraint concatenation
228 * "c(x) or d(x)"), the rounding lock methods of these constraints should be called in a proper way.
230 * SCIPaddConsLocks(scip, c, nlockspos, nlocksneg), saying that infeasibility of c may lead to infeasibility of
231 * the (positive) constraint, and infeasibility of c's negation (i.e. feasibility of c) may lead to infeasibility
233 * - If the constraint may get violated by the feasibility of the sub constraint c, it should call
234 * SCIPaddConsLocks(scip, c, nlocksneg, nlockspos), saying that infeasibility of c may lead to infeasibility of
235 * the constraint's negation (i.e. feasibility of the constraint), and infeasibility of c's negation (i.e. feasibility
237 * - If the constraint may get violated by any change in the feasibility of the sub constraint c, it should call
240 * Consider the or concatenation "c(x) or d(x)". The variable rounding lock method of the or constraint handler
241 * should call SCIPaddConsLocks(scip, c, nlockspos, nlocksneg) and SCIPaddConsLocks(scip, d, nlockspos, nlocksneg)
244 * As a second example, consider the equivalence constraint "y <-> c(x)" with variable y and constraint c. The
245 * constraint demands, that y == 1 if and only if c(x) is satisfied. The variable lock method of the corresponding
246 * constraint handler should call SCIPaddVarLocksType(scip, y, SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) and
247 * SCIPaddConsLocks(scip, c, nlockspos + nlocksneg, nlockspos + nlocksneg), because any modification to the
248 * value of y or to the feasibility of c can alter the feasibility of the equivalence constraint.
254 * This method should iterate over all constraints of the constraint handler and delete all variables
267 * The constraint handler should store a representation of the constraint into the given text file.
282 * The constraint handler can provide a copy method, which copies a constraint from one SCIP data structure into a other
302 SCIP_Bool removable /**< should the constraint be removed from the LP due to aging or cleanup? */
Definition: struct_scip.h:59
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:98
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:272
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:656
Definition: struct_cons.h:37
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:33
Definition of base class for all clonable classes which define problem data.
Definition: objprobcloneable.h:42
virtual SCIP_DECL_CONSPRINT(scip_print)
Definition: ConshdlrSubtour.h:29
virtual SCIP_DECL_CONSHDLRCLONE(scip::ObjProbCloneable *clone)
virtual SCIP_DECL_CONSSEPASOL(scip_sepasol)
Definition: objbenders.h:33