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