Scippy

SCIP

Solving Constraint Integer Programs

ConshdlrSubtour.cpp
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-2023 Zuse Institute Berlin (ZIB) */
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.cpp
26  * @brief Subtour elimination constraint handler for TSP problems, written in C++
27  * @author Timo Berthold
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #include <cassert>
33 #include <string>
34 #include <iostream>
35 #include "ConshdlrSubtour.h"
36 #include "GomoryHuTree.h"
37 
38 #include "objscip/objscip.h"
39 
40 #include "scip/cons_linear.h"
41 
42 #include "GomoryHuTree.h"
43 
44 using namespace tsp;
45 using namespace scip;
46 using namespace std;
47 
48 /** data structure for subtour elimination constraints */
49 struct SCIP_ConsData
50 {
51  GRAPH* graph;
52 };
53 
54 
55 /** checks whether proposed solution contains a subtour
56  *
57  * We assume that the solution is binary.
58  */
59 static
61  SCIP* scip, /**< SCIP data structure */
62  GRAPH* graph, /**< underlying graph */
63  SCIP_SOL* sol /**< proposed solution */
64  )
65 {
66  GRAPHNODE* node;
67  GRAPHNODE* startnode;
68  GRAPHEDGE* edge;
69  GRAPHEDGE* nextedge;
70  GRAPHEDGE* lastedge = NULL;
71  int tourlength = 0;
72 
73  assert(scip != NULL);
74  assert(graph != NULL);
75 
76  if( graph->nnodes <= 1 )
77  return FALSE;
78 
79  startnode = &graph->nodes[0];
80  node = startnode;
81 
82  /* follow the (sub?)tour until you come back to the startnode */
83  do
84  {
85  edge = node->first_edge;
86  nextedge = NULL;
87 
88  /* look for an outgoing edge to proceed */
89  while( edge != NULL )
90  {
91  /* if a new edge with value 1 is found, we proceed */
92  if( edge->back != lastedge && SCIPgetSolVal(scip, sol, edge->var) > 0.5 )
93  {
94  ++tourlength;
95 
96  /* if we found a subtour without the starting node, e.g. 0 - 1 - 2 - 3 - 1 - 2 - ...;
97  * this can only happen, if the degree constraints are violated; */
98  if( nextedge != NULL || tourlength > graph->nnodes )
99  return TRUE;
100 
101  nextedge = edge;
102 
103  /* only use the first edge for the start node */
104  if( node == startnode )
105  break;
106  }
107 
108  edge = edge->next;
109  }
110 
111  /* no outgoing edge found in the solution: the degree constraints must be violated; abort! */
112  if( nextedge == NULL )
113  return TRUE;
114 
115  node = nextedge->adjac;
116  lastedge = nextedge;
117  }
118  while( node != startnode );
119 
120  assert(tourlength <= graph->nnodes);
121 
122  return ( graph->nnodes != tourlength );
123 }
124 
125 
126 /** separates subtour elemination cuts */
127 static
129  SCIP* scip, /**< SCIP data structure */
130  SCIP_CONSHDLR* conshdlr, /**< the constraint handler itself */
131  SCIP_CONS** conss, /**< array of constraints to process */
132  int nconss, /**< number of constraints to process */
133  int nusefulconss, /**< number of useful (non-obsolete) constraints to process */
134  SCIP_SOL* sol, /**< primal solution that should be separated */
135  SCIP_Bool enforce, /**< whether we are in enforcing */
136  SCIP_RESULT* result /**< pointer to store the result of the separation call */
137  )
138 { /*lint --e{715}*/
139  assert(result != NULL);
140 
141  *result = SCIP_DIDNOTFIND;
142 
143  for(int c = 0; c < nusefulconss && *result != SCIP_CUTOFF; ++c)
144  {
145  // get all required structures
146  SCIP_CONSDATA* consdata;
147  GRAPH* graph;
148 
149  consdata = SCIPconsGetData(conss[c]);
150  assert(consdata != NULL);
151 
152  graph = consdata->graph;
153  assert(graph != NULL);
154 
155  // store the suggested, but infeasible solution into the capacity of the edges
156  for(int i = 0; i < graph->nedges; i++)
157  {
158  double cap = SCIPgetSolVal(scip, sol, graph->edges[i].var);
159  graph->edges[i].rcap = cap;
160  graph->edges[i].cap = cap;
161  graph->edges[i].back->rcap = cap;
162  graph->edges[i].back->cap = cap;
163  }
164 
165  SCIP_Bool** cuts = NULL;
166  int ncuts;
167 
168  SCIP_CALL( SCIPallocBufferArray(scip, &cuts, graph->nnodes) );
169  for(int i = 0; i < graph->nnodes; i++)
170  {
171  SCIP_CALL( SCIPallocBufferArray(scip, &cuts[i], graph->nnodes) ); /*lint !e866*/
172  }
173 
174  // try to find cuts
175  if( ghc_tree(graph, cuts, &ncuts, SCIPfeastol(scip)) )
176  {
177  // create a new cutting plane for every suitable arc (representing a cut with value < 2) of the Gomory Hu Tree
178  for(int i = 0; i < ncuts && *result != SCIP_CUTOFF; ++i)
179  {
180  SCIP_ROW* row;
181  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "subtour", 2.0, SCIPinfinity(scip), FALSE, FALSE, TRUE) );
182 
183  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
184 
185  for(int j = 0; j < graph->nnodes; j++)
186  {
187  // in gmincut the graph has been partitioned into two parts, represented by bools
188  if( cuts[i][j] )
189  {
190  GRAPHEDGE* edge = graph->nodes[j].first_edge;
191 
192  // take every edge with nodes in different parts into account
193  while( edge != NULL )
194  {
195  if( ! cuts[i][edge->adjac->id] )
196  {
197  SCIP_CALL( SCIPaddVarToRow(scip, row, edge->var, 1.0) );
198  }
199  edge = edge->next;
200  }
201  }
202  }
203 
204  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
205 
206  // Add violated cut. The cuts produced by ghc_tree are violated by at least the feasibility tolerance. If we
207  // are enforcing, then this is enough to add the cut. Otherwise (we are separating), we check whether the
208  // cut is efficacious.
209  if( enforce || SCIPisCutEfficacious(scip, sol, row) )
210  {
211  SCIP_Bool infeasible;
212  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
213  if ( infeasible )
214  *result = SCIP_CUTOFF;
215  else
216  *result = SCIP_SEPARATED;
217  }
218  SCIP_CALL( SCIPreleaseRow(scip, &row) );
219  }
220  }
221 
222  for(int i = graph->nnodes - 1; i >= 0; i--)
223  SCIPfreeBufferArray(scip, &cuts[i]);
224  SCIPfreeBufferArray(scip, &cuts);
225  }
226 
227  return SCIP_OKAY;
228 }
229 
230 
231 /** frees specific constraint data */
232 SCIP_DECL_CONSDELETE(ConshdlrSubtour::scip_delete)
233 { /*lint --e{715}*/
234  assert(consdata != NULL);
235 
236  release_graph(&(*consdata)->graph);
237  SCIPfreeBlockMemory(scip, consdata);
238 
239  return SCIP_OKAY;
240 }
241 
242 
243 /** transforms constraint data into data belonging to the transformed problem */
244 SCIP_DECL_CONSTRANS(ConshdlrSubtour::scip_trans)
245 {
246  SCIP_CONSDATA* sourcedata;
247  SCIP_CONSDATA* targetdata = NULL;
248 
249  sourcedata = SCIPconsGetData(sourcecons);
250  assert( sourcedata != NULL );
251 
252  SCIP_CALL( SCIPallocBlockMemory(scip, &targetdata) );
253  targetdata->graph = sourcedata->graph;
254  capture_graph(targetdata->graph);
255 
256  /* create target constraint */
257  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
258  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
259  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
260  SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons),
261  SCIPconsIsStickingAtNode(sourcecons)) );
262 
263  return SCIP_OKAY;
264 }
265 
266 
267 /** separation method of constraint handler for LP solution
268  *
269  * Separates all constraints of the constraint handler. The method is called in the LP solution loop,
270  * which means that a valid LP solution exists.
271  *
272  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation
273  * method should process only the useful constraints in most runs, and only occasionally the remaining
274  * nconss - nusefulconss constraints.
275  *
276  * possible return values for *result (if more than one applies, the first in the list should be used):
277  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
278  * - SCIP_CONSADDED : an additional constraint was generated
279  * - SCIP_REDUCEDDOM : a variable's domain was reduced
280  * - SCIP_SEPARATED : a cutting plane was generated
281  * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
282  * - SCIP_DIDNOTRUN : the separator was skipped
283  * - SCIP_DELAYED : the separator was skipped, but should be called again
284  */
285 SCIP_DECL_CONSSEPALP(ConshdlrSubtour::scip_sepalp)
286 {
287  SCIP_CALL( sepaSubtour(scip, conshdlr, conss, nconss, nusefulconss, NULL, FALSE, result) );
288 
289  return SCIP_OKAY;
290 }
291 
292 
293 /** separation method of constraint handler for arbitrary primal solution
294  *
295  * Separates all constraints of the constraint handler. The method is called outside the LP solution loop (e.g., by
296  * a relaxator or a primal heuristic), which means that there is no valid LP solution.
297  * Instead, the method should produce cuts that separate the given solution.
298  *
299  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The separation
300  * method should process only the useful constraints in most runs, and only occasionally the remaining
301  * nconss - nusefulconss constraints.
302  *
303  * possible return values for *result (if more than one applies, the first in the list should be used):
304  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
305  * - SCIP_CONSADDED : an additional constraint was generated
306  * - SCIP_REDUCEDDOM : a variable's domain was reduced
307  * - SCIP_SEPARATED : a cutting plane was generated
308  * - SCIP_DIDNOTFIND : the separator searched, but did not find domain reductions, cutting planes, or cut constraints
309  * - SCIP_DIDNOTRUN : the separator was skipped
310  * - SCIP_DELAYED : the separator was skipped, but should be called again
311  */
312 SCIP_DECL_CONSSEPASOL(ConshdlrSubtour::scip_sepasol)
313 {
314  SCIP_CALL( sepaSubtour(scip, conshdlr, conss, nconss, nusefulconss, sol, FALSE, result) );
315 
316  return SCIP_OKAY;
317 }
318 
319 
320 /** constraint enforcing method of constraint handler for LP solutions
321  *
322  * The method is called at the end of the node processing loop for a node where the LP was solved.
323  * The LP solution has to be checked for feasibility. If possible, an infeasibility should be resolved by
324  * branching, reducing a variable's domain to exclude the solution or separating the solution with a valid
325  * cutting plane.
326  *
327  * The enforcing methods of the active constraint handlers are called in decreasing order of their enforcing
328  * priorities until the first constraint handler returned with the value SCIP_CUTOFF, SCIP_SEPARATED,
329  * SCIP_REDUCEDDOM, SCIP_CONSADDED, or SCIP_BRANCHED.
330  * The integrality constraint handler has an enforcing priority of zero. A constraint handler which can
331  * (or wants) to enforce its constraints only for integral solutions should have a negative enforcing priority
332  * (e.g. the alldiff-constraint can only operate on integral solutions).
333  * A constraint handler which wants to incorporate its own branching strategy even on non-integral
334  * solutions must have an enforcing priority greater than zero (e.g. the SOS-constraint incorporates
335  * SOS-branching on non-integral solutions).
336  *
337  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing
338  * method should process the useful constraints first. The other nconss - nusefulconss constraints should only
339  * be enforced, if no violation was found in the useful constraints.
340  *
341  * possible return values for *result (if more than one applies, the first in the list should be used):
342  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
343  * - SCIP_CONSADDED : an additional constraint was generated
344  * - SCIP_REDUCEDDOM : a variable's domain was reduced
345  * - SCIP_SEPARATED : a cutting plane was generated
346  * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
347  * - SCIP_INFEASIBLE : at least one constraint is infeasible, but it was not resolved
348  * - SCIP_FEASIBLE : all constraints of the handler are feasible
349  */
350 SCIP_DECL_CONSENFOLP(ConshdlrSubtour::scip_enfolp)
351 { /*lint --e{715}*/
352  assert(result != NULL);
353 
354  // search for subtour elimination cuts
355  SCIP_CALL( sepaSubtour(scip, conshdlr, conss, nconss, nusefulconss, NULL, TRUE, result) );
356 
357  // if separation could not find a subtour, then the solution is feasible for this constraint
358  if( *result == SCIP_DIDNOTFIND )
359  *result = SCIP_FEASIBLE;
360 
361  return SCIP_OKAY;
362 }
363 
364 /** constraint enforcing method of constraint handler for pseudo solutions
365  *
366  * The method is called at the end of the node processing loop for a node where the LP was not solved.
367  * The pseudo solution has to be checked for feasibility. If possible, an infeasibility should be resolved by
368  * branching, reducing a variable's domain to exclude the solution or adding an additional constraint.
369  * Separation is not possible, since the LP is not processed at the current node. All LP informations like
370  * LP solution, slack values, or reduced costs are invalid and must not be accessed.
371  *
372  * Like in the enforcing method for LP solutions, the enforcing methods of the active constraint handlers are
373  * called in decreasing order of their enforcing priorities until the first constraint handler returned with
374  * the value SCIP_CUTOFF, SCIP_REDUCEDDOM, SCIP_CONSADDED, SCIP_BRANCHED, or SCIP_SOLVELP.
375  *
376  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The enforcing
377  * method should process the useful constraints first. The other nconss - nusefulconss constraints should only
378  * be enforced, if no violation was found in the useful constraints.
379  *
380  * If the pseudo solution's objective value is lower than the lower bound of the node, it cannot be feasible
381  * and the enforcing method may skip it's check and set *result to SCIP_DIDNOTRUN. However, it can also process
382  * its constraints and return any other possible result code.
383  *
384  * possible return values for *result (if more than one applies, the first in the list should be used):
385  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
386  * - SCIP_CONSADDED : an additional constraint was generated
387  * - SCIP_REDUCEDDOM : a variable's domain was reduced
388  * - SCIP_BRANCHED : no changes were made to the problem, but a branching was applied to resolve an infeasibility
389  * - SCIP_SOLVELP : at least one constraint is infeasible, and this can only be resolved by solving the SCIP_LP
390  * - SCIP_INFEASIBLE : at least one constraint is infeasible, but it was not resolved
391  * - SCIP_FEASIBLE : all constraints of the handler are feasible
392  * - SCIP_DIDNOTRUN : the enforcement was skipped (only possible, if objinfeasible is true)
393  */
394 SCIP_DECL_CONSENFOPS(ConshdlrSubtour::scip_enfops)
395 { /*lint --e{715}*/
396  assert(result != NULL);
397 
398  // search for subtour elimination cuts
399  SCIP_CALL( sepaSubtour(scip, conshdlr, conss, nconss, nusefulconss, NULL, TRUE, result) );
400 
401  // if separation could not find a subtour, then the solution is feasible for this constraint
402  if( *result == SCIP_DIDNOTFIND )
403  *result = SCIP_FEASIBLE;
404 
405  return SCIP_OKAY;
406 }
407 
408 /** feasibility check method of constraint handler for primal solutions
409  *
410  * The given solution has to be checked for feasibility.
411  *
412  * The check methods of the active constraint handlers are called in decreasing order of their check
413  * priorities until the first constraint handler returned with the result SCIP_INFEASIBLE.
414  * The integrality constraint handler has a check priority of zero. A constraint handler which can
415  * (or wants) to check its constraints only for integral solutions should have a negative check priority
416  * (e.g. the alldiff-constraint can only operate on integral solutions).
417  * A constraint handler which wants to check feasibility even on non-integral solutions must have a
418  * check priority greater than zero (e.g. if the check is much faster than testing all variables for
419  * integrality).
420  *
421  * In some cases, integrality conditions or rows of the current LP don't have to be checked, because their
422  * feasibility is already checked or implicitly given. In these cases, 'checkintegrality' or
423  * 'checklprows' is FALSE.
424  *
425  * possible return values for *result:
426  * - SCIP_INFEASIBLE : at least one constraint of the handler is infeasible
427  * - SCIP_FEASIBLE : all constraints of the handler are feasible
428  */
429 SCIP_DECL_CONSCHECK(ConshdlrSubtour::scip_check)
430 { /*lint --e{715}*/
431  assert(result != NULL);
432  *result = SCIP_FEASIBLE;
433 
434  for( int i = 0; i < nconss; ++i )
435  {
436  SCIP_CONSDATA* consdata;
437  GRAPH* graph;
438  SCIP_Bool found;
439 
440  assert(conss != NULL);
441  assert(conss[i] != NULL);
442  consdata = SCIPconsGetData(conss[i]);
443  assert(consdata != NULL);
444  graph = consdata->graph;
445  assert(graph != NULL);
446 
447  // if a subtour is found, the solution must be infeasible
448  found = findSubtour(scip, graph, sol);
449  if( found )
450  {
451  *result = SCIP_INFEASIBLE;
452  if( printreason )
453  {
454  SCIP_CALL( SCIPprintCons(scip, conss[i], NULL) );
455  SCIPinfoMessage(scip, NULL, "violation: graph has a subtour\n");
456  }
457  }
458  }
459 
460  return SCIP_OKAY;
461 }
462 
463 /** domain propagation method of constraint handler
464  *
465  * The first nusefulconss constraints are the ones, that are identified to likely be violated. The propagation
466  * method should process only the useful constraints in most runs, and only occasionally the remaining
467  * nconss - nusefulconss constraints.
468  *
469  * possible return values for *result:
470  * - SCIP_CUTOFF : the node is infeasible in the variable's bounds and can be cut off
471  * - SCIP_REDUCEDDOM : at least one domain reduction was found
472  * - SCIP_DIDNOTFIND : the propagator searched, but did not find any domain reductions
473  * - SCIP_DIDNOTRUN : the propagator was skipped
474  * - SCIP_DELAYED : the propagator was skipped, but should be called again
475  */
476 SCIP_DECL_CONSPROP(ConshdlrSubtour::scip_prop)
477 { /*lint --e{715}*/
478  assert(result != NULL);
479 
480  *result = SCIP_DIDNOTRUN;
481  return SCIP_OKAY;
482 }
483 
484 /** variable rounding lock method of constraint handler
485  *
486  * This method is called, after a constraint is added or removed from the transformed problem.
487  * It should update the rounding locks of all associated variables with calls to SCIPaddVarLocksType(),
488  * depending on the way, the variable is involved in the constraint:
489  * - If the constraint may get violated by decreasing the value of a variable, it should call
490  * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlockspos, nlocksneg), saying that rounding down is
491  * potentially rendering the (positive) constraint infeasible and rounding up is potentially rendering the
492  * negation of the constraint infeasible.
493  * - If the constraint may get violated by increasing the value of a variable, it should call
494  * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos), saying that rounding up is
495  * potentially rendering the constraint's negation infeasible and rounding up is potentially rendering the
496  * constraint itself infeasible.
497  * - If the constraint may get violated by changing the variable in any direction, it should call
498  * SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg).
499  *
500  * Consider the linear constraint "3x -5y +2z <= 7" as an example. The variable rounding lock method of the
501  * linear constraint handler should call SCIPaddVarLocksType(scip, x, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos),
502  * SCIPaddVarLocksType(scip, y, SCIP_LOCKTYPE_MODEL, nlockspos, nlocksneg) and
503  * SCIPaddVarLocksType(scip, z, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos) to tell SCIP,
504  * that rounding up of x and z and rounding down of y can destroy the feasibility of the constraint, while rounding
505  * down of x and z and rounding up of y can destroy the feasibility of the constraint's negation "3x -5y +2z > 7".
506  * A linear constraint "2 <= 3x -5y +2z <= 7" should call
507  * SCIPaddVarLocksType(scip, ..., SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) on all variables,
508  * since rounding in both directions of each variable can destroy both the feasibility of the constraint and it's negation
509  * "3x -5y +2z < 2 or 3x -5y +2z > 7".
510  *
511  * If the constraint itself contains other constraints as sub constraints (e.g. the "or" constraint concatenation
512  * "c(x) or d(x)"), the rounding lock methods of these constraints should be called in a proper way.
513  * - If the constraint may get violated by the violation of the sub constraint c, it should call
514  * SCIPaddConsLocks(scip, c, nlockspos, nlocksneg), saying that infeasibility of c may lead to infeasibility of
515  * the (positive) constraint, and infeasibility of c's negation (i.e. feasibility of c) may lead to infeasibility
516  * of the constraint's negation (i.e. feasibility of the constraint).
517  * - If the constraint may get violated by the feasibility of the sub constraint c, it should call
518  * SCIPaddConsLocks(scip, c, nlocksneg, nlockspos), saying that infeasibility of c may lead to infeasibility of
519  * the constraint's negation (i.e. feasibility of the constraint), and infeasibility of c's negation (i.e. feasibility
520  * of c) may lead to infeasibility of the (positive) constraint.
521  * - If the constraint may get violated by any change in the feasibility of the sub constraint c, it should call
522  * SCIPaddConsLocks(scip, c, nlockspos + nlocksneg, nlockspos + nlocksneg).
523  *
524  * Consider the or concatenation "c(x) or d(x)". The variable rounding lock method of the or constraint handler
525  * should call SCIPaddConsLocks(scip, c, nlockspos, nlocksneg) and SCIPaddConsLocks(scip, d, nlockspos, nlocksneg)
526  * to tell SCIP, that infeasibility of c and d can lead to infeasibility of "c(x) or d(x)".
527  *
528  * As a second example, consider the equivalence constraint "y <-> c(x)" with variable y and constraint c. The
529  * constraint demands, that y == 1 if and only if c(x) is satisfied. The variable lock method of the corresponding
530  * constraint handler should call SCIPaddVarLocksType(scip, y, SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) and
531  * SCIPaddConsLocks(scip, c, nlockspos + nlocksneg, nlockspos + nlocksneg), because any modification to the
532  * value of y or to the feasibility of c can alter the feasibility of the equivalence constraint.
533  */
534 SCIP_DECL_CONSLOCK(ConshdlrSubtour::scip_lock)
535 { /*lint --e{715}*/
536  SCIP_CONSDATA* consdata;
537  GRAPH* g;
538 
539  consdata = SCIPconsGetData(cons);
540  assert(consdata != NULL);
541 
542  g = consdata->graph;
543  assert(g != NULL);
544 
545  for( int i = 0; i < g->nedges; ++i )
546  {
547  SCIP_CALL( SCIPaddVarLocksType(scip, g->edges[i].var, SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos) );
548  }
549 
550  return SCIP_OKAY;
551 }
552 
553 /** variable deletion method of constraint handler
554  *
555  * This method should iterate over all constraints of the constraint handler and delete all variables
556  * that were marked for deletion by SCIPdelVar().
557  *
558  * input:
559  * - scip : SCIP main data structure
560  * - conshdlr : the constraint handler itself
561  * - conss : array of constraints in transformed problem
562  * - nconss : number of constraints in transformed problem
563  */
564 SCIP_DECL_CONSDELVARS(ConshdlrSubtour::scip_delvars)
565 { /*lint --e{715}*/
566  return SCIP_OKAY;
567 }
568 
569 
570 /** constraint display method of constraint handler
571  *
572  * The constraint handler should store a representation of the constraint into the given text file.
573  */
574 SCIP_DECL_CONSPRINT(ConshdlrSubtour::scip_print)
575 { /*lint --e{715}*/
576  SCIP_CONSDATA* consdata;
577  GRAPH* g;
578 
579  consdata = SCIPconsGetData(cons);
580  assert(consdata != NULL);
581 
582  g = consdata->graph;
583  assert(g != NULL);
584 
585  SCIPinfoMessage(scip, file, "subtour of Graph G with %d nodes and %d edges\n", g->nnodes, g->nedges);
586 
587  return SCIP_OKAY;
588 }
589 
590 /** clone method which will be used to copy a objective plugin */
591 SCIP_DECL_CONSHDLRCLONE(ObjProbCloneable* ConshdlrSubtour::clone) /*lint !e665*/
592 {
593  assert(valid != NULL);
594  *valid = TRUE;
595  return new ConshdlrSubtour(scip);
596 }
597 
598 /** constraint copying method of constraint handler
599  *
600  * The constraint handler can provide a copy method, which copies a constraint from one SCIP data structure into a other
601  * SCIP data structure.
602  */
603 SCIP_DECL_CONSCOPY(ConshdlrSubtour::scip_copy)
604 { /*lint --e{715}*/
605  SCIP_CONSHDLR* conshdlr;
606  SCIP_CONSDATA* consdata = NULL;
607 
608  assert(valid != NULL);
609 
610  /* find the subtour constraint handler */
611  conshdlr = SCIPfindConshdlr(scip, "subtour");
612  if( conshdlr == NULL )
613  {
614  SCIPerrorMessage("subtour constraint handler not found\n");
615  return SCIP_PLUGINNOTFOUND;
616  }
617 
618  /* create constraint data */
619  SCIP_CALL( SCIPallocBlockMemory( scip, &consdata) );
620  ProbDataTSP* probdatatsp;
621  probdatatsp = dynamic_cast<ProbDataTSP*>(SCIPgetObjProbData(scip));
622  assert( probdatatsp != NULL );
623 
624  GRAPH * graph = probdatatsp->getGraph();
625  consdata->graph = graph;
626  capture_graph( consdata->graph );
627 
628  /* create constraint */
629  SCIP_CALL( SCIPcreateCons(scip, cons, (name == NULL) ? SCIPconsGetName(sourcecons) : name,
630  conshdlr, consdata, initial, separate, enforce, check,
631  propagate, local, modifiable, dynamic, removable, FALSE) );
632 
633  *valid = TRUE;
634 
635  return SCIP_OKAY;
636 }
637 
638 /** creates and captures a TSP subtour constraint */
640  SCIP* scip, /**< SCIP data structure */
641  SCIP_CONS** cons, /**< pointer to hold the created constraint */
642  const char* name, /**< name of constraint */
643  GRAPH* graph, /**< the underlying graph */
644  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? */
645  SCIP_Bool separate, /**< should the constraint be separated during LP processing? */
646  SCIP_Bool enforce, /**< should the constraint be enforced during node processing? */
647  SCIP_Bool check, /**< should the constraint be checked for feasibility? */
648  SCIP_Bool propagate, /**< should the constraint be propagated during node processing? */
649  SCIP_Bool local, /**< is constraint only valid locally? */
650  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? */
651  SCIP_Bool dynamic, /**< is constraint dynamic? */
652  SCIP_Bool removable /**< should the constraint be removed from the LP due to aging or cleanup? */
653  )
654 {
655  SCIP_CONSHDLR* conshdlr;
656  SCIP_CONSDATA* consdata;
657 
658  /* find the subtour constraint handler */
659  conshdlr = SCIPfindConshdlr(scip, "subtour");
660  if( conshdlr == NULL )
661  {
662  SCIPerrorMessage("subtour constraint handler not found\n");
663  return SCIP_PLUGINNOTFOUND;
664  }
665 
666  /* create constraint data */
667  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) ); /*lint !e530*/
668  consdata->graph = graph;
669  capture_graph(consdata->graph);
670 
671  /* create constraint */
672  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
673  local, modifiable, dynamic, removable, FALSE) );
674 
675  return SCIP_OKAY;
676 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
struct GraphEdge * next
Definition: GomoryHuTree.h:69
int nnodes
Definition: GomoryHuTree.h:82
SCIP_Real SCIPfeastol(SCIP *scip)
GRAPHNODE * nodes
Definition: GomoryHuTree.h:86
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8349
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:886
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIP_DECL_CONSSEPALP(ConshdlrSubtour::scip_sepalp)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIP_DECL_CONSENFOPS(ConshdlrSubtour::scip_enfops)
#define FALSE
Definition: def.h:96
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8369
generator for global cuts in undirected graphs
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
SCIP_DECL_CONSSEPASOL(ConshdlrSubtour::scip_sepasol)
SCIP_DECL_CONSDELETE(ConshdlrSubtour::scip_delete)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8359
int nedges
Definition: GomoryHuTree.h:83
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, 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, SCIP_Bool stickingatnode)
Definition: scip_cons.c:943
SCIP_DECL_CONSENFOLP(ConshdlrSubtour::scip_enfolp)
static SCIP_RETCODE sepaSubtour(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_Bool enforce, SCIP_RESULT *result)
SCIP_DECL_CONSCHECK(ConshdlrSubtour::scip_check)
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
SCIP_VAR * var
Definition: GomoryHuTree.h:74
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:117
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)
#define SCIPerrorMessage
Definition: pub_message.h:64
double cap
Definition: GomoryHuTree.h:65
Definition: pqueue.h:37
GRAPHNODE * adjac
Definition: GomoryHuTree.h:72
struct GraphEdge * back
Definition: GomoryHuTree.h:70
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8090
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8309
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:53
GRAPHEDGE * edges
Definition: GomoryHuTree.h:87
SCIP_DECL_CONSTRANS(ConshdlrSubtour::scip_trans)
#define NULL
Definition: lpi_spx1.cpp:164
C++ wrapper classes for SCIP.
SCIP_DECL_CONSDELVARS(ConshdlrSubtour::scip_delvars)
#define SCIP_CALL(x)
Definition: def.h:394
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8329
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:65
GRAPH * getGraph()
Definition: ProbDataTSP.h:97
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIP_Bool
Definition: def.h:93
SCIP_DECL_CONSPROP(ConshdlrSubtour::scip_prop)
C++ constraint handler for TSP subtour elimination constraints.
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2482
double rcap
Definition: GomoryHuTree.h:66
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8289
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8259
Constraint handler for linear constraints in their most general form, .
scip::ObjProbData * SCIPgetObjProbData(SCIP *scip)
Definition of base class for all clonable classes which define problem data.
SCIP_DECL_CONSHDLRCLONE(ObjProbCloneable *ConshdlrSubtour::clone)
SCIP_Bool ghc_tree(GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8120
SCIP_DECL_CONSLOCK(ConshdlrSubtour::scip_lock)
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8339
SCIP_DECL_CONSPRINT(ConshdlrSubtour::scip_print)
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8279
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8269
static SCIP_Bool findSubtour(SCIP *scip, GRAPH *graph, SCIP_SOL *sol)
void capture_graph(GRAPH *gr)
SCIP_DECL_CONSCOPY(ConshdlrSubtour::scip_copy)
void release_graph(GRAPH **gr)
#define nnodes
Definition: gastrans.c:74
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1391
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361