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-2019 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 scip.zib.de. */
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 "GomoryHuTree.h"
28 #include "ProbDataTSP.h"
29 
30 namespace tsp
31 {
32 
33 /** C++ constraint handler for TSP subtour elimination constraints */
35 {
36 public:
37  /** default constructor */
39  SCIP* scip
40  )
41  : ObjConshdlr(scip, "subtour", "TSP subtour elimination constraints",
42  1000000, -2000000, -2000000, 1, -1, 1, 0,
44  {
45  }
46 
47  /** destructor */
48  virtual ~ConshdlrSubtour()
49  {
50  }
51 
52  /** frees specific constraint data
53  *
54  * WARNING! There may exist unprocessed events. For example, a variable's bound may have been already changed, but
55  * the corresponding bound change event was not yet processed.
56  */
57  virtual SCIP_DECL_CONSDELETE(scip_delete);
58 
59  /** transforms constraint data into data belonging to the transformed problem */
60  virtual SCIP_DECL_CONSTRANS(scip_trans);
61 
62  /** separation method of constraint handler for LP solution
63  *
64  * Separates all constraints of the constraint handler. The method is called in the LP solution loop,
65  * which means that a valid LP solution exists.
66  *
67  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation
68  * method should process only the useful constraints in most runs, and only occasionally the remaining
69  * nconss - nusefulconss constraints.
70  *
71  * possible return values for *result (if more than one applies, the first in the list should be used):
72  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
73  * - SCIP_CONSADDED : an additional constraint was generated
74  * - SCIP_REDUCEDDOM : a variable's domain was reduced
75  * - SCIP_SEPARATED : a cutting plane was generated
76  * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
77  * - SCIP_DIDNOTRUN : the separator was skipped
78  * - SCIP_DELAYED : the separator was skipped, but should be called again
79  */
80  virtual SCIP_DECL_CONSSEPALP(scip_sepalp);
81 
82  /** separation method of constraint handler for arbitrary primal solution
83  *
84  * Separates all constraints of the constraint handler. The method is called outside the LP solution loop (e.g., by
85  * a relaxator or a primal heuristic), which means that there is no valid LP solution.
86  * Instead, the method should produce cuts that separate the given solution.
87  *
88  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation
89  * method should process only the useful constraints in most runs, and only occasionally the remaining
90  * nconss - nusefulconss constraints.
91  *
92  * possible return values for *result (if more than one applies, the first in the list should be used):
93  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
94  * - SCIP_CONSADDED : an additional constraint was generated
95  * - SCIP_REDUCEDDOM : a variable's domain was reduced
96  * - SCIP_SEPARATED : a cutting plane was generated
97  * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
98  * - SCIP_DIDNOTRUN : the separator was skipped
99  * - SCIP_DELAYED : the separator was skipped, but should be called again
100  */
101  virtual SCIP_DECL_CONSSEPASOL(scip_sepasol);
102 
103  /** constraint enforcing method of constraint handler for LP solutions
104  *
105  * The method is called at the end of the node processing loop for a node where the LP was solved.
106  * The LP solution has to be checked for feasibility. If possible, an infeasibility should be resolved by
107  * branching, reducing a variable's domain to exclude the solution or separating the solution with a valid
108  * cutting plane.
109  *
110  * The enforcing methods of the active constraint handlers are called in decreasing order of their enforcing
111  * priorities until the first constraint handler returned with the value SCIP_CUTOFF, SCIP_SEPARATED,
112  * SCIP_REDUCEDDOM, SCIP_CONSADDED, or SCIP_BRANCHED.
113  * The integrality constraint handler has an enforcing priority of zero. A constraint handler which can
114  * (or wants) to enforce its constraints only for integral solutions should have a negative enforcing priority
115  * (e.g. the alldiff-constraint can only operate on integral solutions).
116  * A constraint handler which wants to incorporate its own branching strategy even on non-integral
117  * solutions must have an enforcing priority greater than zero (e.g. the SOS-constraint incorporates
118  * SOS-branching on non-integral solutions).
119  *
120  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing
121  * method should process the useful constraints first. The other nconss - nusefulconss constraints should only
122  * be enforced, if no violation was found in the useful constraints.
123  *
124  * possible return values for *result (if more than one applies, the first in the list should be used):
125  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
126  * - SCIP_CONSADDED : an additional constraint was generated
127  * - SCIP_REDUCEDDOM : a variable's domain was reduced
128  * - SCIP_SEPARATED : a cutting plane was generated
129  * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
130  * - SCIP_INFEASIBLE : at least one constraint is infeasible, but it was not resolved
131  * - SCIP_FEASIBLE : all constraints of the handler are feasible
132  */
133  virtual SCIP_DECL_CONSENFOLP(scip_enfolp);
134 
135  /** constraint enforcing method of constraint handler for pseudo solutions
136  *
137  * The method is called at the end of the node processing loop for a node where the LP was not solved.
138  * The pseudo solution has to be checked for feasibility. If possible, an infeasibility should be resolved by
139  * branching, reducing a variable's domain to exclude the solution or adding an additional constraint.
140  * Separation is not possible, since the LP is not processed at the current node. All LP informations like
141  * LP solution, slack values, or reduced costs are invalid and must not be accessed.
142  *
143  * Like in the enforcing method for LP solutions, the enforcing methods of the active constraint handlers are
144  * called in decreasing order of their enforcing priorities until the first constraint handler returned with
145  * the value SCIP_CUTOFF, SCIP_REDUCEDDOM, SCIP_CONSADDED, SCIP_BRANCHED, or SCIP_SOLVELP.
146  *
147  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing
148  * method should process the useful constraints first. The other nconss - nusefulconss constraints should only
149  * be enforced, if no violation was found in the useful constraints.
150  *
151  * If the pseudo solution's objective value is lower than the lower bound of the node, it cannot be feasible
152  * and the enforcing method may skip it's check and set *result to SCIP_DIDNOTRUN. However, it can also process
153  * its constraints and return any other possible result code.
154  *
155  * possible return values for *result (if more than one applies, the first in the list should be used):
156  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
157  * - SCIP_CONSADDED : an additional constraint was generated
158  * - SCIP_REDUCEDDOM : a variable's domain was reduced
159  * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
160  * - SCIP_SOLVELP : at least one constraint is infeasible, and this can only be resolved by solving the SCIP_LP
161  * - SCIP_INFEASIBLE : at least one constraint is infeasible, but it was not resolved
162  * - SCIP_FEASIBLE : all constraints of the handler are feasible
163  * - SCIP_DIDNOTRUN : the enforcement was skipped (only possible, if objinfeasible is true)
164  */
165  virtual SCIP_DECL_CONSENFOPS(scip_enfops);
166 
167  /** feasibility check method of constraint handler for primal solutions
168  *
169  * The given solution has to be checked for feasibility.
170  *
171  * The check methods of the active constraint handlers are called in decreasing order of their check
172  * priorities until the first constraint handler returned with the result SCIP_INFEASIBLE.
173  * The integrality constraint handler has a check priority of zero. A constraint handler which can
174  * (or wants) to check its constraints only for integral solutions should have a negative check priority
175  * (e.g. the alldiff-constraint can only operate on integral solutions).
176  * A constraint handler which wants to check feasibility even on non-integral solutions must have a
177  * check priority greater than zero (e.g. if the check is much faster than testing all variables for
178  * integrality).
179  *
180  * In some cases, integrality conditions or rows of the current LP don't have to be checked, because their
181  * feasibility is already checked or implicitly given. In these cases, 'checkintegrality' or
182  * 'checklprows' is FALSE.
183  *
184  * possible return values for *result:
185  * - SCIP_INFEASIBLE : at least one constraint of the handler is infeasible
186  * - SCIP_FEASIBLE : all constraints of the handler are feasible
187  */
188  virtual SCIP_DECL_CONSCHECK(scip_check);
189 
190  /** domain propagation method of constraint handler
191  *
192  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The propagation
193  * method should process only the useful constraints in most runs, and only occasionally the remaining
194  * nconss - nusefulconss constraints.
195  *
196  * possible return values for *result:
197  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
198  * - SCIP_REDUCEDDOM : at least one domain reduction was found
199  * - SCIP_DIDNOTFIND : the propagator searched, but did not find any domain reductions
200  * - SCIP_DIDNOTRUN : the propagator was skipped
201  * - SCIP_DELAYED : the propagator was skipped, but should be called again
202  */
203  virtual SCIP_DECL_CONSPROP(scip_prop);
204 
205  /** variable rounding lock method of constraint handler
206  *
207  * This method is called, after a constraint is added or removed from the transformed problem.
208  * It should update the rounding locks of all associated variables with calls to SCIPaddVarLocksType(),
209  * depending on the way, the variable is involved in the constraint:
210  * - If the constraint may get violated by decreasing the value of a variable, it should call
211  * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlockspos, nlocksneg), saying that rounding down is
212  * potentially rendering the (positive) constraint infeasible and rounding up is potentially rendering the
213  * negation of the constraint infeasible.
214  * - If the constraint may get violated by increasing the value of a variable, it should call
215  * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos), saying that rounding up is
216  * potentially rendering the constraint's negation infeasible and rounding up is potentially rendering the
217  * constraint itself infeasible.
218  * - If the constraint may get violated by changing the variable in any direction, it should call
219  * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg).
220  *
221  * Consider the linear constraint "3x -5y +2z <= 7" as an example. The variable rounding lock method of the
222  * linear constraint handler should call SCIPaddVarLocksType(scip, x, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos),
223  * SCIPaddVarLocksType(scip, y, SCIP_LOCKTYPE_MODEL, nlockspos, nlocksneg) and
224  * SCIPaddVarLocksType(scip, z, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos) to tell SCIP,
225  * that rounding up of x and z and rounding down of y can destroy the feasibility of the constraint, while rounding
226  * down of x and z and rounding up of y can destroy the feasibility of the constraint's negation "3x -5y +2z > 7".
227  * A linear constraint "2 <= 3x -5y +2z <= 7" should call
228  * SCIPaddVarLocksType(scip, ..., SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) on all variables,
229  * since rounding in both directions of each variable can destroy both the feasibility of the constraint and it's negation
230  * "3x -5y +2z < 2 or 3x -5y +2z > 7".
231  *
232  * If the constraint itself contains other constraints as sub constraints (e.g. the "or" constraint concatenation
233  * "c(x) or d(x)"), the rounding lock methods of these constraints should be called in a proper way.
234  * - If the constraint may get violated by the violation of the sub constraint c, it should call
235  * SCIPaddConsLocks(scip, c, nlockspos, nlocksneg), saying that infeasibility of c may lead to infeasibility of
236  * the (positive) constraint, and infeasibility of c's negation (i.e. feasibility of c) may lead to infeasibility
237  * of the constraint's negation (i.e. feasibility of the constraint).
238  * - If the constraint may get violated by the feasibility of the sub constraint c, it should call
239  * SCIPaddConsLocks(scip, c, nlocksneg, nlockspos), saying that infeasibility of c may lead to infeasibility of
240  * the constraint's negation (i.e. feasibility of the constraint), and infeasibility of c's negation (i.e. feasibility
241  * of c) may lead to infeasibility of the (positive) constraint.
242  * - If the constraint may get violated by any change in the feasibility of the sub constraint c, it should call
243  * SCIPaddConsLocks(scip, c, nlockspos + nlocksneg, nlockspos + nlocksneg).
244  *
245  * Consider the or concatenation "c(x) or d(x)". The variable rounding lock method of the or constraint handler
246  * should call SCIPaddConsLocks(scip, c, nlockspos, nlocksneg) and SCIPaddConsLocks(scip, d, nlockspos, nlocksneg)
247  * to tell SCIP, that infeasibility of c and d can lead to infeasibility of "c(x) or d(x)".
248  *
249  * As a second example, consider the equivalence constraint "y <-> c(x)" with variable y and constraint c. The
250  * constraint demands, that y == 1 if and only if c(x) is satisfied. The variable lock method of the corresponding
251  * constraint handler should call SCIPaddVarLocksType(scip, y, SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) and
252  * SCIPaddConsLocks(scip, c, nlockspos + nlocksneg, nlockspos + nlocksneg), because any modification to the
253  * value of y or to the feasibility of c can alter the feasibility of the equivalence constraint.
254  */
255  virtual SCIP_DECL_CONSLOCK(scip_lock);
256 
257  /** variable deletion method of constraint handler
258  *
259  * This method should iterate over all constraints of the constraint handler and delete all variables
260  * that were marked for deletion by SCIPdelVar().
261  *
262  * input:
263  * - scip : SCIP main data structure
264  * - conshdlr : the constraint handler itself
265  * - conss : array of constraints in transformed problem
266  * - nconss : number of constraints in transformed problem
267  */
268  virtual SCIP_DECL_CONSDELVARS(scip_delvars);
269 
270  /** constraint display method of constraint handler
271  *
272  * The constraint handler should store a representation of the constraint into the given text file.
273  */
274  virtual SCIP_DECL_CONSPRINT(scip_print);
275 
276  /** returns whether the objective plugin is copyable */
277  virtual SCIP_DECL_CONSHDLRISCLONEABLE(iscloneable)
278  {
279  return true;
280  }
281 
282  /** clone method which will be used to copy a objective plugin */
283  virtual SCIP_DECL_CONSHDLRCLONE(scip::ObjProbCloneable* clone); /*lint !e665*/
284 
285  /** constraint copying method of constraint handler
286  *
287  * The constraint handler can provide a copy method, which copies a constraint from one SCIP data structure into a other
288  * SCIP data structure.
289  */
290  virtual SCIP_DECL_CONSCOPY(scip_copy);
291 }; /*lint !e1712*/
292 
293 /** creates and captures a TSP subtour constraint */
295  SCIP* scip, /**< SCIP data structure */
296  SCIP_CONS** cons, /**< pointer to hold the created constraint */
297  const char* name, /**< name of constraint */
298  GRAPH* graph, /**< the underlying graph */
299  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? */
300  SCIP_Bool separate, /**< should the constraint be separated during LP processing? */
301  SCIP_Bool enforce, /**< should the constraint be enforced during node processing? */
302  SCIP_Bool check, /**< should the constraint be checked for feasibility? */
303  SCIP_Bool propagate, /**< should the constraint be propagated during node processing? */
304  SCIP_Bool local, /**< is constraint only valid locally? */
305  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? */
306  SCIP_Bool dynamic, /**< is constraint dynamic? */
307  SCIP_Bool removable /**< should the constraint be removed from the LP due to aging or cleanup? */
308  );
309 }
310 
311 #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:72
virtual SCIP_DECL_CONSCOPY(scip_copy)
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
generator for global cuts in undirected graphs
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:69
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)