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