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