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-2017 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 email to 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 
37 public:
38  /** default constructor */
40  SCIP* scip
41  )
42  : ObjConshdlr(scip, "subtour", "TSP subtour elimination constraints",
43  1000000, -2000000, -2000000, 1, -1, 1, 0,
45  {
46  }
47 
48  /** destructor */
49  virtual ~ConshdlrSubtour()
50  {
51  }
52 
53  /** frees specific constraint data
54  *
55  * WARNING! There may exist unprocessed events. For example, a variable's bound may have been already changed, but
56  * the corresponding bound change event was not yet processed.
57  */
58  virtual SCIP_DECL_CONSDELETE(scip_delete);
59 
60  /** transforms constraint data into data belonging to the transformed problem */
61  virtual SCIP_DECL_CONSTRANS(scip_trans);
62 
63  /** separation method of constraint handler for LP solution
64  *
65  * Separates all constraints of the constraint handler. The method is called in the LP solution loop,
66  * which means that a valid LP solution exists.
67  *
68  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation
69  * method should process only the useful constraints in most runs, and only occasionally the remaining
70  * nconss - nusefulconss constraints.
71  *
72  * possible return values for *result (if more than one applies, the first in the list should be used):
73  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
74  * - SCIP_CONSADDED : an additional constraint was generated
75  * - SCIP_REDUCEDDOM : a variable's domain was reduced
76  * - SCIP_SEPARATED : a cutting plane was generated
77  * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
78  * - SCIP_DIDNOTRUN : the separator was skipped
79  * - SCIP_DELAYED : the separator was skipped, but should be called again
80  */
81  virtual SCIP_DECL_CONSSEPALP(scip_sepalp);
82 
83  /** separation method of constraint handler for arbitrary primal solution
84  *
85  * Separates all constraints of the constraint handler. The method is called outside the LP solution loop (e.g., by
86  * a relaxator or a primal heuristic), which means that there is no valid LP solution.
87  * Instead, the method should produce cuts that separate the given solution.
88  *
89  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation
90  * method should process only the useful constraints in most runs, and only occasionally the remaining
91  * nconss - nusefulconss constraints.
92  *
93  * possible return values for *result (if more than one applies, the first in the list should be used):
94  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
95  * - SCIP_CONSADDED : an additional constraint was generated
96  * - SCIP_REDUCEDDOM : a variable's domain was reduced
97  * - SCIP_SEPARATED : a cutting plane was generated
98  * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
99  * - SCIP_DIDNOTRUN : the separator was skipped
100  * - SCIP_DELAYED : the separator was skipped, but should be called again
101  */
102  virtual SCIP_DECL_CONSSEPASOL(scip_sepasol);
103 
104  /** constraint enforcing method of constraint handler for LP solutions
105  *
106  * The method is called at the end of the node processing loop for a node where the LP was solved.
107  * The LP solution has to be checked for feasibility. If possible, an infeasibility should be resolved by
108  * branching, reducing a variable's domain to exclude the solution or separating the solution with a valid
109  * cutting plane.
110  *
111  * The enforcing methods of the active constraint handlers are called in decreasing order of their enforcing
112  * priorities until the first constraint handler returned with the value SCIP_CUTOFF, SCIP_SEPARATED,
113  * SCIP_REDUCEDDOM, SCIP_CONSADDED, or SCIP_BRANCHED.
114  * The integrality constraint handler has an enforcing priority of zero. A constraint handler which can
115  * (or wants) to enforce its constraints only for integral solutions should have a negative enforcing priority
116  * (e.g. the alldiff-constraint can only operate on integral solutions).
117  * A constraint handler which wants to incorporate its own branching strategy even on non-integral
118  * solutions must have an enforcing priority greater than zero (e.g. the SOS-constraint incorporates
119  * SOS-branching on non-integral solutions).
120  *
121  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing
122  * method should process the useful constraints first. The other nconss - nusefulconss constraints should only
123  * be enforced, if no violation was found in the useful constraints.
124  *
125  * possible return values for *result (if more than one applies, the first in the list should be used):
126  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
127  * - SCIP_CONSADDED : an additional constraint was generated
128  * - SCIP_REDUCEDDOM : a variable's domain was reduced
129  * - SCIP_SEPARATED : a cutting plane was generated
130  * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
131  * - SCIP_INFEASIBLE : at least one constraint is infeasible, but it was not resolved
132  * - SCIP_FEASIBLE : all constraints of the handler are feasible
133  */
134  virtual SCIP_DECL_CONSENFOLP(scip_enfolp);
135 
136  /** constraint enforcing method of constraint handler for pseudo solutions
137  *
138  * The method is called at the end of the node processing loop for a node where the LP was not solved.
139  * The pseudo solution has to be checked for feasibility. If possible, an infeasibility should be resolved by
140  * branching, reducing a variable's domain to exclude the solution or adding an additional constraint.
141  * Separation is not possible, since the LP is not processed at the current node. All LP informations like
142  * LP solution, slack values, or reduced costs are invalid and must not be accessed.
143  *
144  * Like in the enforcing method for LP solutions, the enforcing methods of the active constraint handlers are
145  * called in decreasing order of their enforcing priorities until the first constraint handler returned with
146  * the value SCIP_CUTOFF, SCIP_REDUCEDDOM, SCIP_CONSADDED, SCIP_BRANCHED, or SCIP_SOLVELP.
147  *
148  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing
149  * method should process the useful constraints first. The other nconss - nusefulconss constraints should only
150  * be enforced, if no violation was found in the useful constraints.
151  *
152  * If the pseudo solution's objective value is lower than the lower bound of the node, it cannot be feasible
153  * and the enforcing method may skip it's check and set *result to SCIP_DIDNOTRUN. However, it can also process
154  * its constraints and return any other possible result code.
155  *
156  * possible return values for *result (if more than one applies, the first in the list should be used):
157  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
158  * - SCIP_CONSADDED : an additional constraint was generated
159  * - SCIP_REDUCEDDOM : a variable's domain was reduced
160  * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
161  * - SCIP_SOLVELP : at least one constraint is infeasible, and this can only be resolved by solving the SCIP_LP
162  * - SCIP_INFEASIBLE : at least one constraint is infeasible, but it was not resolved
163  * - SCIP_FEASIBLE : all constraints of the handler are feasible
164  * - SCIP_DIDNOTRUN : the enforcement was skipped (only possible, if objinfeasible is true)
165  */
166  virtual SCIP_DECL_CONSENFOPS(scip_enfops);
167 
168  /** feasibility check method of constraint handler for primal solutions
169  *
170  * The given solution has to be checked for feasibility.
171  *
172  * The check methods of the active constraint handlers are called in decreasing order of their check
173  * priorities until the first constraint handler returned with the result SCIP_INFEASIBLE.
174  * The integrality constraint handler has a check priority of zero. A constraint handler which can
175  * (or wants) to check its constraints only for integral solutions should have a negative check priority
176  * (e.g. the alldiff-constraint can only operate on integral solutions).
177  * A constraint handler which wants to check feasibility even on non-integral solutions must have a
178  * check priority greater than zero (e.g. if the check is much faster than testing all variables for
179  * integrality).
180  *
181  * In some cases, integrality conditions or rows of the current LP don't have to be checked, because their
182  * feasibility is already checked or implicitly given. In these cases, 'checkintegrality' or
183  * 'checklprows' is FALSE.
184  *
185  * possible return values for *result:
186  * - SCIP_INFEASIBLE : at least one constraint of the handler is infeasible
187  * - SCIP_FEASIBLE : all constraints of the handler are feasible
188  */
189  virtual SCIP_DECL_CONSCHECK(scip_check);
190 
191  /** domain propagation method of constraint handler
192  *
193  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The propagation
194  * method should process only the useful constraints in most runs, and only occasionally the remaining
195  * nconss - nusefulconss constraints.
196  *
197  * possible return values for *result:
198  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
199  * - SCIP_REDUCEDDOM : at least one domain reduction was found
200  * - SCIP_DIDNOTFIND : the propagator searched, but did not find any domain reductions
201  * - SCIP_DIDNOTRUN : the propagator was skipped
202  * - SCIP_DELAYED : the propagator was skipped, but should be called again
203  */
204  virtual SCIP_DECL_CONSPROP(scip_prop);
205 
206  /** variable rounding lock method of constraint handler
207  *
208  * This method is called, after a constraint is added or removed from the transformed problem.
209  * It should update the rounding locks of all associated variables with calls to SCIPaddVarLocks(),
210  * depending on the way, the variable is involved in the constraint:
211  * - If the constraint may get violated by decreasing the value of a variable, it should call
212  * SCIPaddVarLocks(scip, var, nlockspos, nlocksneg), saying that rounding down is potentially rendering the
213  * (positive) constraint infeasible and rounding up is potentially rendering the negation of the constraint
214  * infeasible.
215  * - If the constraint may get violated by increasing the value of a variable, it should call
216  * SCIPaddVarLocks(scip, var, nlocksneg, nlockspos), saying that rounding down is potentially rendering the
217  * constraint's negation infeasible and rounding up is potentially rendering the constraint itself
218  * infeasible.
219  * - If the constraint may get violated by changing the variable in any direction, it should call
220  * SCIPaddVarLocks(scip, var, nlockspos + nlocksneg, nlockspos + nlocksneg).
221  *
222  * Consider the linear constraint "3x -5y +2z <= 7" as an example. The variable rounding lock method of the
223  * linear constraint handler should call SCIPaddVarLocks(scip, x, nlocksneg, nlockspos),
224  * SCIPaddVarLocks(scip, y, nlockspos, nlocksneg) and SCIPaddVarLocks(scip, z, 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  * SCIPaddVarLocks(scip, ..., nlockspos + nlocksneg, nlockspos + nlocksneg) on all variables, since rounding in both
229  * 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 SCIPaddVarLocks(scip, y, 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 
312 #endif
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:64
virtual SCIP_DECL_CONSCOPY(scip_copy)
#define TRUE
Definition: def.h:63
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:61
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)