Detailed Description
C++ constraint handler for TSP subtour elimination constraints
Definition at line 33 of file ConshdlrSubtour.h.
#include <ConshdlrSubtour.h>
Public Member Functions  
ConshdlrSubtour (SCIP *scip)  
virtual  ~ConshdlrSubtour () 
virtual  SCIP_DECL_CONSDELETE (scip_delete) 
virtual  SCIP_DECL_CONSTRANS (scip_trans) 
virtual  SCIP_DECL_CONSSEPALP (scip_sepalp) 
virtual  SCIP_DECL_CONSSEPASOL (scip_sepasol) 
virtual  SCIP_DECL_CONSENFOLP (scip_enfolp) 
virtual  SCIP_DECL_CONSENFOPS (scip_enfops) 
virtual  SCIP_DECL_CONSCHECK (scip_check) 
virtual  SCIP_DECL_CONSPROP (scip_prop) 
virtual  SCIP_DECL_CONSLOCK (scip_lock) 
virtual  SCIP_DECL_CONSDELVARS (scip_delvars) 
virtual  SCIP_DECL_CONSPRINT (scip_print) 
virtual  SCIP_DECL_CONSHDLRISCLONEABLE (iscloneable) 
virtual  SCIP_DECL_CONSHDLRCLONE (scip::ObjProbCloneable *clone) 
virtual  SCIP_DECL_CONSCOPY (scip_copy) 
Public Member Functions inherited from scip::ObjConshdlr  
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)  
virtual  ~ObjConshdlr () 
virtual  SCIP_DECL_CONSFREE (scip_free) 
virtual  SCIP_DECL_CONSINIT (scip_init) 
virtual  SCIP_DECL_CONSEXIT (scip_exit) 
virtual  SCIP_DECL_CONSINITPRE (scip_initpre) 
virtual  SCIP_DECL_CONSEXITPRE (scip_exitpre) 
virtual  SCIP_DECL_CONSINITSOL (scip_initsol) 
virtual  SCIP_DECL_CONSEXITSOL (scip_exitsol) 
virtual  SCIP_DECL_CONSINITLP (scip_initlp) 
virtual  SCIP_DECL_CONSENFORELAX (scip_enforelax) 
virtual  SCIP_DECL_CONSPRESOL (scip_presol) 
virtual  SCIP_DECL_CONSRESPROP (scip_resprop) 
virtual  SCIP_DECL_CONSACTIVE (scip_active) 
virtual  SCIP_DECL_CONSDEACTIVE (scip_deactive) 
virtual  SCIP_DECL_CONSENABLE (scip_enable) 
virtual  SCIP_DECL_CONSDISABLE (scip_disable) 
virtual  SCIP_DECL_CONSPARSE (scip_parse) 
virtual  SCIP_DECL_CONSGETVARS (scip_getvars) 
virtual  SCIP_DECL_CONSGETNVARS (scip_getnvars) 
virtual  SCIP_DECL_CONSGETDIVEBDCHGS (scip_getdivebdchgs) 
Public Member Functions inherited from scip::ObjProbCloneable  
virtual  ~ObjProbCloneable () 
virtual  SCIP_DECL_OBJPROBCLONE (ObjProbCloneable *clone) 
virtual  SCIP_DECL_OBJPROBISCLONEABLE (iscloneable) 
Additional Inherited Members  
Data Fields inherited from scip::ObjConshdlr  
SCIP *  scip_ 
char *  scip_name_ 
char *  scip_desc_ 
const int  scip_sepapriority_ 
const int  scip_enfopriority_ 
const int  scip_checkpriority_ 
const int  scip_sepafreq_ 
const int  scip_propfreq_ 
const int  scip_eagerfreq_ 
const int  scip_maxprerounds_ 
const SCIP_Bool  scip_delaysepa_ 
const SCIP_Bool  scip_delayprop_ 
const SCIP_Bool  scip_needscons_ 
const SCIP_PROPTIMING  scip_proptiming_ 
const SCIP_PRESOLTIMING  scip_presoltiming_ 
Constructor & Destructor Documentation
◆ ConshdlrSubtour()

inline 
default constructor
Definition at line 37 of file ConshdlrSubtour.h.
◆ ~ConshdlrSubtour()

inlinevirtual 
destructor
Definition at line 47 of file ConshdlrSubtour.h.
References SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSDELVARS(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_CONSLOCK(), SCIP_DECL_CONSPRINT(), SCIP_DECL_CONSPROP(), SCIP_DECL_CONSSEPALP(), SCIP_DECL_CONSSEPASOL(), and SCIP_DECL_CONSTRANS().
Member Function Documentation
◆ SCIP_DECL_CONSDELETE()

virtual 
frees specific constraint data
Reimplemented from scip::ObjConshdlr.
Referenced by ~ConshdlrSubtour().
◆ SCIP_DECL_CONSTRANS()

virtual 
transforms constraint data into data belonging to the transformed problem
Implements scip::ObjConshdlr.
Referenced by ~ConshdlrSubtour().
◆ SCIP_DECL_CONSSEPALP()

virtual 
separation method of constraint handler for LP solution
Separates all constraints of the constraint handler. The method is called in the LP solution loop, which means that a valid LP solution exists.
The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation method should process only the useful constraints in most runs, and only occasionally the remaining nconss  nusefulconss constraints.
possible return values for *result (if more than one applies, the first in the list should be used):
 SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
 SCIP_CONSADDED : an additional constraint was generated
 SCIP_REDUCEDDOM : a variable's domain was reduced
 SCIP_SEPARATED : a cutting plane was generated
 SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
 SCIP_DIDNOTRUN : the separator was skipped
 SCIP_DELAYED : the separator was skipped, but should be called again
Reimplemented from scip::ObjConshdlr.
Referenced by ~ConshdlrSubtour().
◆ SCIP_DECL_CONSSEPASOL()

virtual 
separation method of constraint handler for arbitrary primal solution
Separates all constraints of the constraint handler. The method is called outside the LP solution loop (e.g., by a relaxator or a primal heuristic), which means that there is no valid LP solution. Instead, the method should produce cuts that separate the given solution.
The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation method should process only the useful constraints in most runs, and only occasionally the remaining nconss  nusefulconss constraints.
possible return values for *result (if more than one applies, the first in the list should be used):
 SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
 SCIP_CONSADDED : an additional constraint was generated
 SCIP_REDUCEDDOM : a variable's domain was reduced
 SCIP_SEPARATED : a cutting plane was generated
 SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
 SCIP_DIDNOTRUN : the separator was skipped
 SCIP_DELAYED : the separator was skipped, but should be called again
Reimplemented from scip::ObjConshdlr.
Referenced by ~ConshdlrSubtour().
◆ SCIP_DECL_CONSENFOLP()

virtual 
constraint enforcing method of constraint handler for LP solutions
The method is called at the end of the node processing loop for a node where the LP was solved. The LP solution has to be checked for feasibility. If possible, an infeasibility should be resolved by branching, reducing a variable's domain to exclude the solution or separating the solution with a valid cutting plane.
The enforcing methods of the active constraint handlers are called in decreasing order of their enforcing priorities until the first constraint handler returned with the value SCIP_CUTOFF, SCIP_SEPARATED, SCIP_REDUCEDDOM, SCIP_CONSADDED, or SCIP_BRANCHED. The integrality constraint handler has an enforcing priority of zero. A constraint handler which can (or wants) to enforce its constraints only for integral solutions should have a negative enforcing priority (e.g. the alldiffconstraint can only operate on integral solutions). A constraint handler which wants to incorporate its own branching strategy even on nonintegral solutions must have an enforcing priority greater than zero (e.g. the SOSconstraint incorporates SOSbranching on nonintegral solutions).
The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing method should process the useful constraints first. The other nconss  nusefulconss constraints should only be enforced, if no violation was found in the useful constraints.
possible return values for *result (if more than one applies, the first in the list should be used):
 SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
 SCIP_CONSADDED : an additional constraint was generated
 SCIP_REDUCEDDOM : a variable's domain was reduced
 SCIP_SEPARATED : a cutting plane was generated
 SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
 SCIP_INFEASIBLE : at least one constraint is infeasible, but it was not resolved
 SCIP_FEASIBLE : all constraints of the handler are feasible
Implements scip::ObjConshdlr.
Referenced by ~ConshdlrSubtour().
◆ SCIP_DECL_CONSENFOPS()

virtual 
constraint enforcing method of constraint handler for pseudo solutions
The method is called at the end of the node processing loop for a node where the LP was not solved. The pseudo solution has to be checked for feasibility. If possible, an infeasibility should be resolved by branching, reducing a variable's domain to exclude the solution or adding an additional constraint. Separation is not possible, since the LP is not processed at the current node. All LP informations like LP solution, slack values, or reduced costs are invalid and must not be accessed.
Like in the enforcing method for LP solutions, the enforcing methods of the active constraint handlers are called in decreasing order of their enforcing priorities until the first constraint handler returned with the value SCIP_CUTOFF, SCIP_REDUCEDDOM, SCIP_CONSADDED, SCIP_BRANCHED, or SCIP_SOLVELP.
The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing method should process the useful constraints first. The other nconss  nusefulconss constraints should only be enforced, if no violation was found in the useful constraints.
If the pseudo solution's objective value is lower than the lower bound of the node, it cannot be feasible and the enforcing method may skip it's check and set *result to SCIP_DIDNOTRUN. However, it can also process its constraints and return any other possible result code.
possible return values for *result (if more than one applies, the first in the list should be used):
 SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
 SCIP_CONSADDED : an additional constraint was generated
 SCIP_REDUCEDDOM : a variable's domain was reduced
 SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
 SCIP_SOLVELP : at least one constraint is infeasible, and this can only be resolved by solving the SCIP_LP
 SCIP_INFEASIBLE : at least one constraint is infeasible, but it was not resolved
 SCIP_FEASIBLE : all constraints of the handler are feasible
 SCIP_DIDNOTRUN : the enforcement was skipped (only possible, if objinfeasible is true)
Implements scip::ObjConshdlr.
Referenced by ~ConshdlrSubtour().
◆ SCIP_DECL_CONSCHECK()

virtual 
feasibility check method of constraint handler for primal solutions
The given solution has to be checked for feasibility.
The check methods of the active constraint handlers are called in decreasing order of their check priorities until the first constraint handler returned with the result SCIP_INFEASIBLE. The integrality constraint handler has a check priority of zero. A constraint handler which can (or wants) to check its constraints only for integral solutions should have a negative check priority (e.g. the alldiffconstraint can only operate on integral solutions). A constraint handler which wants to check feasibility even on nonintegral solutions must have a check priority greater than zero (e.g. if the check is much faster than testing all variables for integrality).
In some cases, integrality conditions or rows of the current LP don't have to be checked, because their feasibility is already checked or implicitly given. In these cases, 'checkintegrality' or 'checklprows' is FALSE.
possible return values for *result:
 SCIP_INFEASIBLE : at least one constraint of the handler is infeasible
 SCIP_FEASIBLE : all constraints of the handler are feasible
Implements scip::ObjConshdlr.
Referenced by ~ConshdlrSubtour().
◆ SCIP_DECL_CONSPROP()

virtual 
domain propagation method of constraint handler
The first nusefulconss constraints are the ones, that are identified to likely be violated. The propagation method should process only the useful constraints in most runs, and only occasionally the remaining nconss  nusefulconss constraints.
possible return values for *result:
 SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
 SCIP_REDUCEDDOM : at least one domain reduction was found
 SCIP_DIDNOTFIND : the propagator searched, but did not find any domain reductions
 SCIP_DIDNOTRUN : the propagator was skipped
 SCIP_DELAYED : the propagator was skipped, but should be called again
Reimplemented from scip::ObjConshdlr.
Referenced by ~ConshdlrSubtour().
◆ SCIP_DECL_CONSLOCK()

virtual 
variable rounding lock method of constraint handler
This method is called, after a constraint is added or removed from the transformed problem. It should update the rounding locks of all associated variables with calls to SCIPaddVarLocksType(), depending on the way, the variable is involved in the constraint:
 If the constraint may get violated by decreasing the value of a variable, it should call SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlockspos, nlocksneg), saying that rounding down is potentially rendering the (positive) constraint infeasible and rounding up is potentially rendering the negation of the constraint infeasible.
 If the constraint may get violated by increasing the value of a variable, it should call SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos), saying that rounding up is potentially rendering the constraint's negation infeasible and rounding up is potentially rendering the constraint itself infeasible.
 If the constraint may get violated by changing the variable in any direction, it should call SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg).
Consider the linear constraint "3x 5y +2z <= 7" as an example. The variable rounding lock method of the linear constraint handler should call SCIPaddVarLocksType(scip, x, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos), SCIPaddVarLocksType(scip, y, SCIP_LOCKTYPE_MODEL, nlockspos, nlocksneg) and SCIPaddVarLocksType(scip, z, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos) to tell SCIP, that rounding up of x and z and rounding down of y can destroy the feasibility of the constraint, while rounding down of x and z and rounding up of y can destroy the feasibility of the constraint's negation "3x 5y +2z > 7". A linear constraint "2 <= 3x 5y +2z <= 7" should call SCIPaddVarLocksType(scip, ..., SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) on all variables, since rounding in both directions of each variable can destroy both the feasibility of the constraint and it's negation "3x 5y +2z < 2 or 3x 5y +2z > 7".
If the constraint itself contains other constraints as sub constraints (e.g. the "or" constraint concatenation "c(x) or d(x)"), the rounding lock methods of these constraints should be called in a proper way.
 If the constraint may get violated by the violation of the sub constraint c, it should call SCIPaddConsLocks(scip, c, nlockspos, nlocksneg), saying that infeasibility of c may lead to infeasibility of the (positive) constraint, and infeasibility of c's negation (i.e. feasibility of c) may lead to infeasibility of the constraint's negation (i.e. feasibility of the constraint).
 If the constraint may get violated by the feasibility of the sub constraint c, it should call SCIPaddConsLocks(scip, c, nlocksneg, nlockspos), saying that infeasibility of c may lead to infeasibility of the constraint's negation (i.e. feasibility of the constraint), and infeasibility of c's negation (i.e. feasibility of c) may lead to infeasibility of the (positive) constraint.
 If the constraint may get violated by any change in the feasibility of the sub constraint c, it should call SCIPaddConsLocks(scip, c, nlockspos + nlocksneg, nlockspos + nlocksneg).
Consider the or concatenation "c(x) or d(x)". The variable rounding lock method of the or constraint handler should call SCIPaddConsLocks(scip, c, nlockspos, nlocksneg) and SCIPaddConsLocks(scip, d, nlockspos, nlocksneg) to tell SCIP, that infeasibility of c and d can lead to infeasibility of "c(x) or d(x)".
As a second example, consider the equivalence constraint "y <> c(x)" with variable y and constraint c. The constraint demands, that y == 1 if and only if c(x) is satisfied. The variable lock method of the corresponding constraint handler should call SCIPaddVarLocksType(scip, y, SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) and SCIPaddConsLocks(scip, c, nlockspos + nlocksneg, nlockspos + nlocksneg), because any modification to the value of y or to the feasibility of c can alter the feasibility of the equivalence constraint.
Implements scip::ObjConshdlr.
Referenced by ~ConshdlrSubtour().
◆ SCIP_DECL_CONSDELVARS()

virtual 
variable deletion method of constraint handler
This method should iterate over all constraints of the constraint handler and delete all variables that were marked for deletion by SCIPdelVar().
input:
 scip : SCIP main data structure
 conshdlr : the constraint handler itself
 conss : array of constraints in transformed problem
 nconss : number of constraints in transformed problem
Reimplemented from scip::ObjConshdlr.
Referenced by ~ConshdlrSubtour().
◆ SCIP_DECL_CONSPRINT()

virtual 
constraint display method of constraint handler
The constraint handler should store a representation of the constraint into the given text file.
Reimplemented from scip::ObjConshdlr.
Referenced by ~ConshdlrSubtour().
◆ SCIP_DECL_CONSHDLRISCLONEABLE()

inlinevirtual 
returns whether the objective plugin is copyable
Definition at line 272 of file ConshdlrSubtour.h.
References SCIP_Bool, SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSHDLRCLONE(), tsp::SCIPcreateConsSubtour(), and TRUE.
◆ SCIP_DECL_CONSHDLRCLONE()

virtual 
clone method which will be used to copy a objective plugin
Referenced by SCIP_DECL_CONSHDLRISCLONEABLE().
◆ SCIP_DECL_CONSCOPY()

virtual 
constraint copying method of constraint handler
The constraint handler can provide a copy method, which copies a constraint from one SCIP data structure into a other SCIP data structure.
Reimplemented from scip::ObjConshdlr.
Referenced by SCIP_DECL_CONSHDLRISCLONEABLE().