Scippy

SCIP

Solving Constraint Integer Programs

ConshdlrSubtour.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License. */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file ConshdlrSubtour.h
17  * @brief C++ constraint handler for TSP subtour elimination constraints
18  * @author Timo Berthold
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #ifndef __TSPCONSHDLRSUBTOUR_H__
24 #define __TSPCONSHDLRSUBTOUR_H__
25 
26 #include "objscip/objscip.h"
27 #include "ProbDataTSP.h"
28 
29 namespace tsp
30 {
31 
32 /** C++ constraint handler for TSP subtour elimination constraints */
34 {
35 public:
36  /** default constructor */
38  SCIP* scip
39  )
40  : ObjConshdlr(scip, "subtour", "TSP subtour elimination constraints",
41  1000000, -2000000, -2000000, 1, -1, 1, 0,
43  {
44  }
45 
46  /** destructor */
47  virtual ~ConshdlrSubtour()
48  {
49  }
50 
51  /** frees specific constraint data */
52  virtual SCIP_DECL_CONSDELETE(scip_delete);
53 
54  /** transforms constraint data into data belonging to the transformed problem */
55  virtual SCIP_DECL_CONSTRANS(scip_trans);
56 
57  /** separation method of constraint handler for LP solution
58  *
59  * Separates all constraints of the constraint handler. The method is called in the LP solution loop,
60  * which means that a valid LP solution exists.
61  *
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
64  * nconss - nusefulconss constraints.
65  *
66  * possible return values for *result (if more than one applies, the first in the list should be used):
67  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
68  * - SCIP_CONSADDED : an additional constraint was generated
69  * - SCIP_REDUCEDDOM : a variable's domain was reduced
70  * - SCIP_SEPARATED : a cutting plane was generated
71  * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
72  * - SCIP_DIDNOTRUN : the separator was skipped
73  * - SCIP_DELAYED : the separator was skipped, but should be called again
74  */
75  virtual SCIP_DECL_CONSSEPALP(scip_sepalp);
76 
77  /** separation method of constraint handler for arbitrary primal solution
78  *
79  * Separates all constraints of the constraint handler. The method is called outside the LP solution loop (e.g., by
80  * a relaxator or a primal heuristic), which means that there is no valid LP solution.
81  * Instead, the method should produce cuts that separate the given solution.
82  *
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
85  * nconss - nusefulconss constraints.
86  *
87  * possible return values for *result (if more than one applies, the first in the list should be used):
88  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
89  * - SCIP_CONSADDED : an additional constraint was generated
90  * - SCIP_REDUCEDDOM : a variable's domain was reduced
91  * - SCIP_SEPARATED : a cutting plane was generated
92  * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
93  * - SCIP_DIDNOTRUN : the separator was skipped
94  * - SCIP_DELAYED : the separator was skipped, but should be called again
95  */
96  virtual SCIP_DECL_CONSSEPASOL(scip_sepasol);
97 
98  /** constraint enforcing method of constraint handler for LP solutions
99  *
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
103  * cutting plane.
104  *
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,
107  * SCIP_REDUCEDDOM, SCIP_CONSADDED, or SCIP_BRANCHED.
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
110  * (e.g. the alldiff-constraint can only operate on integral solutions).
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
113  * SOS-branching on non-integral solutions).
114  *
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
117  * be enforced, if no violation was found in the useful constraints.
118  *
119  * possible return values for *result (if more than one applies, the first in the list should be used):
120  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
121  * - SCIP_CONSADDED : an additional constraint was generated
122  * - SCIP_REDUCEDDOM : a variable's domain was reduced
123  * - SCIP_SEPARATED : a cutting plane was generated
124  * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
125  * - SCIP_INFEASIBLE : at least one constraint is infeasible, but it was not resolved
126  * - SCIP_FEASIBLE : all constraints of the handler are feasible
127  */
128  virtual SCIP_DECL_CONSENFOLP(scip_enfolp);
129 
130  /** constraint enforcing method of constraint handler for pseudo solutions
131  *
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
136  * LP solution, slack values, or reduced costs are invalid and must not be accessed.
137  *
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
140  * the value SCIP_CUTOFF, SCIP_REDUCEDDOM, SCIP_CONSADDED, SCIP_BRANCHED, or SCIP_SOLVELP.
141  *
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
144  * be enforced, if no violation was found in the useful constraints.
145  *
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
148  * its constraints and return any other possible result code.
149  *
150  * possible return values for *result (if more than one applies, the first in the list should be used):
151  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
152  * - SCIP_CONSADDED : an additional constraint was generated
153  * - SCIP_REDUCEDDOM : a variable's domain was reduced
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
156  * - SCIP_INFEASIBLE : at least one constraint is infeasible, but it was not resolved
157  * - SCIP_FEASIBLE : all constraints of the handler are feasible
158  * - SCIP_DIDNOTRUN : the enforcement was skipped (only possible, if objinfeasible is true)
159  */
160  virtual SCIP_DECL_CONSENFOPS(scip_enfops);
161 
162  /** feasibility check method of constraint handler for primal solutions
163  *
164  * The given solution has to be checked for feasibility.
165  *
166  * The check methods of the active constraint handlers are called in decreasing order of their check
167  * priorities until the first constraint handler returned with the result SCIP_INFEASIBLE.
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
170  * (e.g. the alldiff-constraint can only operate on integral solutions).
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
173  * integrality).
174  *
175  * In some cases, integrality conditions or rows of the current LP don't have to be checked, because their
176  * feasibility is already checked or implicitly given. In these cases, 'checkintegrality' or
177  * 'checklprows' is FALSE.
178  *
179  * possible return values for *result:
180  * - SCIP_INFEASIBLE : at least one constraint of the handler is infeasible
181  * - SCIP_FEASIBLE : all constraints of the handler are feasible
182  */
183  virtual SCIP_DECL_CONSCHECK(scip_check);
184 
185  /** domain propagation method of constraint handler
186  *
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
189  * nconss - nusefulconss constraints.
190  *
191  * possible return values for *result:
192  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
193  * - SCIP_REDUCEDDOM : at least one domain reduction was found
194  * - SCIP_DIDNOTFIND : the propagator searched, but did not find any domain reductions
195  * - SCIP_DIDNOTRUN : the propagator was skipped
196  * - SCIP_DELAYED : the propagator was skipped, but should be called again
197  */
198  virtual SCIP_DECL_CONSPROP(scip_prop);
199 
200  /** variable rounding lock method of constraint handler
201  *
202  * This method is called, after a constraint is added or removed from the transformed problem.
203  * It should update the rounding locks of all associated variables with calls to SCIPaddVarLocksType(),
204  * depending on the way, the variable is involved in the constraint:
205  * - If the constraint may get violated by decreasing the value of a variable, it should call
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
208  * negation of the constraint infeasible.
209  * - If the constraint may get violated by increasing the value of a variable, it should call
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
212  * constraint itself infeasible.
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).
215  *
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),
218  * SCIPaddVarLocksType(scip, y, SCIP_LOCKTYPE_MODEL, nlockspos, nlocksneg) and
219  * SCIPaddVarLocksType(scip, z, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos) to tell SCIP,
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".
222  * A linear constraint "2 <= 3x -5y +2z <= 7" should call
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
225  * "3x -5y +2z < 2 or 3x -5y +2z > 7".
226  *
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.
229  * - If the constraint may get violated by the violation of the sub constraint c, it should call
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
232  * of the constraint's negation (i.e. feasibility of the constraint).
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
236  * of c) may lead to infeasibility of the (positive) constraint.
237  * - If the constraint may get violated by any change in the feasibility of the sub constraint c, it should call
238  * SCIPaddConsLocks(scip, c, nlockspos + nlocksneg, nlockspos + nlocksneg).
239  *
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)
242  * to tell SCIP, that infeasibility of c and d can lead to infeasibility of "c(x) or d(x)".
243  *
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.
249  */
250  virtual SCIP_DECL_CONSLOCK(scip_lock);
251 
252  /** variable deletion method of constraint handler
253  *
254  * This method should iterate over all constraints of the constraint handler and delete all variables
255  * that were marked for deletion by SCIPdelVar().
256  *
257  * input:
258  * - scip : SCIP main data structure
259  * - conshdlr : the constraint handler itself
260  * - conss : array of constraints in transformed problem
261  * - nconss : number of constraints in transformed problem
262  */
263  virtual SCIP_DECL_CONSDELVARS(scip_delvars);
264 
265  /** constraint display method of constraint handler
266  *
267  * The constraint handler should store a representation of the constraint into the given text file.
268  */
269  virtual SCIP_DECL_CONSPRINT(scip_print);
270 
271  /** returns whether the objective plugin is copyable */
272  virtual SCIP_DECL_CONSHDLRISCLONEABLE(iscloneable)
273  {
274  return true;
275  }
276 
277  /** clone method which will be used to copy a objective plugin */
278  virtual SCIP_DECL_CONSHDLRCLONE(scip::ObjProbCloneable* clone); /*lint !e665*/
279 
280  /** constraint copying method of constraint handler
281  *
282  * The constraint handler can provide a copy method, which copies a constraint from one SCIP data structure into a other
283  * SCIP data structure.
284  */
285  virtual SCIP_DECL_CONSCOPY(scip_copy);
286 }; /*lint !e1712*/
287 
288 /** creates and captures a TSP subtour constraint */
290  SCIP* scip, /**< SCIP data structure */
291  SCIP_CONS** cons, /**< pointer to hold the created constraint */
292  const char* name, /**< name of constraint */
293  GRAPH* graph, /**< the underlying graph */
294  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? */
295  SCIP_Bool separate, /**< should the constraint be separated during LP processing? */
296  SCIP_Bool enforce, /**< should the constraint be enforced during node processing? */
297  SCIP_Bool check, /**< should the constraint be checked for feasibility? */
298  SCIP_Bool propagate, /**< should the constraint be propagated during node processing? */
299  SCIP_Bool local, /**< is constraint only valid locally? */
300  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? */
301  SCIP_Bool dynamic, /**< is constraint dynamic? */
302  SCIP_Bool removable /**< should the constraint be removed from the LP due to aging or cleanup? */
303  );
304 }
305 
306 #endif
Definition: grph.h:57
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)
#define FALSE
Definition: def.h:73
virtual SCIP_DECL_CONSCOPY(scip_copy)
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
virtual SCIP_DECL_CONSSEPALP(scip_sepalp)
#define SCIP_PRESOLTIMING_FAST
Definition: type_timing.h:43
virtual SCIP_DECL_CONSHDLRISCLONEABLE(iscloneable)
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)
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.
#define SCIP_Bool
Definition: def.h:70
virtual SCIP_DECL_CONSTRANS(scip_trans)
ConshdlrSubtour(SCIP *scip)
virtual SCIP_DECL_CONSLOCK(scip_lock)
virtual SCIP_DECL_CONSCHECK(scip_check)
#define SCIP_PROPTIMING_BEFORELP
Definition: type_timing.h:56
C++ wrapper for constraint handlers.
Definition: objconshdlr.h:47
Definition of base class for all clonable classes which define problem data.
virtual SCIP_DECL_CONSPRINT(scip_print)
virtual SCIP_DECL_CONSHDLRCLONE(scip::ObjProbCloneable *clone)
virtual SCIP_DECL_CONSSEPASOL(scip_sepasol)