# SCIP

Solving Constraint Integer Programs

cons_stp.c
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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file cons_stp.c
17  * @brief Constraint handler for Steiner problems
18  * @author Gerald Gamrath
19  * @author Daniel Rehfeldt
20  * @author Michael Winkler
21  *
22  * This file checks solutions for feasibility and separates violated model constraints. For more details see \ref STP_CONS page.
23  *
24  * @page STP_CONS Separating violated constraints
25  *
26  * In this file a constraint handler checking solutions for feasibility and separating violated model constraints is implemented.
27  * The separation problem for the cut inequalities described in \ref STP_PROBLEM can be solved by a max-flow algorithm in
28  * polynomial time. Regarding the variable values of a given LP solution as capacities on the edges, one can check for each
29  * \f$t \in T \setminus \{r\} \f$, with \f$r \f$ being the root, whether the minimal \f$(r, t) \f$-cut is less than one. In this case,
30  * a violated cut inequality has been found, otherwise none exists. In order to calculate such a minimal cut an adaptation of Hao
31  * and Orlin's preflow-push algorithm (see A Faster Algorithm for Finding the Minimum Cut in a Directed Graph) is used. Furthermore, the file implements a dual ascent heuristic, based on a concept described
32  * in "A dual ascent approach for Steiner tree problems on a directed graph." by R. Wong.
33  *
34  */
35
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37
38 #include <assert.h>
39 #include <string.h>
40
41 #include "cons_stp.h"
42 #include "probdata_stp.h"
43 #include "graph.h"
44 #include "portab.h"
45 #include "branch_stp.h"
46 #include "prop_stp.h"
47 #include "sepaspecial.h"
48 #include "mincut.h"
49 #include "scip/scip.h"
50 #include "scip/misc.h"
51 #include "scip/cons_linear.h"
52 #include <time.h>
53 #if 0
54 #ifdef WITH_UG
56 #else
58 #endif
59 #endif
60
62 #define STP_SEPASPECIAL_USECLIQUE FALSE
63 #define STP_SEPASPECIAL_USECVTIMP FALSE
64
65 /**@name Constraint handler properties
66  *
67  * @{
68  */
69
70 #define CONSHDLR_NAME "stp"
71 #define CONSHDLR_DESC "steiner tree constraint handler"
72 #define CONSHDLR_SEPAPRIORITY 9999999 /**< priority of the constraint handler for separation */
73 #define CONSHDLR_ENFOPRIORITY 0 /**< priority of the constraint handler for constraint enforcing */
74 #define CONSHDLR_CHECKPRIORITY 9999999 /**< priority of the constraint handler for checking feasibility */
75 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
76 #define CONSHDLR_PROPFREQ 0 /**< frequency for propagating domains; zero means only preprocessing propagation */
77 #define CONSHDLR_EAGERFREQ 1 /**< frequency for using all instead of only the useful constraints in separation,
78  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
79 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
80 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
81 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
83 #define DEFAULT_MAXROUNDS 20 /**< maximal number of separation rounds per node (-1: unlimited) */
84 #define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of separation rounds in the root node (-1: unlimited) */
85 #define DEFAULT_MAXSEPACUTS INT_MAX /**< maximal number of cuts separated per separation round */
86 #define DEFAULT_MAXSEPACUTSROOT INT_MAX /**< maximal number of cuts separated per separation round in the root node */
88 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
90 #define DEFAULT_BACKCUT FALSE /**< Try Back-Cuts FALSE*/
91 #define DEFAULT_CREEPFLOW TRUE /**< Use Creep-Flow */
92 #define DEFAULT_DISJUNCTCUT FALSE /**< Only disjunct Cuts FALSE */
93 #define DEFAULT_NESTEDCUT FALSE /**< Try Nested-Cuts FALSE*/
94 #define DEFAULT_FLOWSEP TRUE /**< Try Flow-Cuts */
95 #define DEFAULT_INFLOWSEP TRUE /**< Try in-flow Cuts */
96 #define DEFAULT_INFLOWTERMSEP TRUE /**< Try terminal in-flow Cuts */
97 #define DEFAULT_OUTFLOWSEP TRUE
98 #define DEFAULT_BALANCEFLOWSEP TRUE
100
101 /**@} */
102
103 /*
104  * Data structures
105  */
106
107 /** @brief Constraint data for \ref cons_stp.c "Stp" constraints */
108 struct SCIP_ConsData
109 {
110  GRAPH* graph; /**< graph data structure */
111 };
112
113
114 /** @brief Constraint handler data for \ref cons_stp.c "Stp" constraint handler */
115 struct SCIP_ConshdlrData
116 {
117  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
118  PACLIQUES* pacliques; /**< pseudo ancestor cliques */
119  PCIMPLICATION* pcimplications; /**< prize-collecting implications */
120  VTIMPLICATION* vtimplications; /**< vertex-terminal implications */
121  SCIP_Bool backcut; /**< should backcuts be applied? */
122  SCIP_Bool creepflow; /**< should creepflow cuts be applied? */
123  SCIP_Bool disjunctcut; /**< should disjunction cuts be applied? */
124  SCIP_Bool nestedcut; /**< should nested cuts be applied? */
125  SCIP_Bool flowsep; /**< should flow separation be applied? */
126  SCIP_Bool inflowsep; /**< should unit in-flow separation be applied? */
127  SCIP_Bool intermflowsep; /**< should unit terminal in-flow separation be applied? */
128  SCIP_Bool outflowsep; /**< should single-edge out-flow separation be applied? */
129  SCIP_Bool balanceflowsep; /**< should flow-balance separation be applied? */
130  int maxrounds; /**< maximal number of separation rounds per node (-1: unlimited) */
131  int maxroundsroot; /**< maximal number of separation rounds in the root node (-1: unlimited) */
132  int maxsepacuts; /**< maximal number of cuts separated per separation round */
133  int maxsepacutsroot; /**< maximal number of cuts separated per separation round in the root node */
134 };
135
136
137
138 /**@name Local methods
139  *
140  * @{
141  */
142
143
144
145 #if 0
146 /** separate degree-2 cuts */
147 static
148 SCIP_RETCODE sep_deg2(
149  SCIP* scip, /**< SCIP data structure */
150  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
151  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
152  SCIP_CONSDATA* consdata, /**< constraint data */
153  int maxcuts, /**< maximal number of cuts */
154  int* ncuts /**< pointer to store number of cuts */
155  )
156 {
157  GRAPH* g;
158  SCIP_VAR** vars;
159  SCIP_ROW* row = NULL;
160  SCIP_Real* xval;
161  int cutscount = 0;
162  int nnodes;
163  const SCIP_Bool* deg2bounded = SCIPStpPropGet2BoundedArr(scip);
164
165  assert(scip != NULL);
166  assert(conshdlr != NULL);
167  assert(conshdlrdata != NULL);
168  assert(deg2bounded != NULL);
169
170  vars = SCIPprobdataGetVars(scip);
171  g = consdata->graph;
172  assert(g != NULL);
173
174  xval = SCIPprobdataGetXval(scip, NULL);
175  assert(xval != NULL);
176
177  nnodes = g->knots;
178
179  for( int i = 0; i < nnodes; i++ )
180  {
181  double inoutsum;
182
183  if( Is_term(g->term[i]) )
184  continue;
185
186  if( !deg2bounded[i] )
187  continue;
188
189  inoutsum = 0.0;
190
191  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
192  {
193  inoutsum += xval[e] + xval[flipedge_Uint(e)];
194  assert(flipedge_Uint(e) == (unsigned) flipedge(e));
195  }
196
197  if( SCIPisFeasGT(scip, inoutsum, 2.0) )
198  {
199  SCIP_Bool infeasible;
200
201  SCIP_CALL(SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "deg2", -SCIPinfinity(scip), 2.0, FALSE, FALSE, TRUE));
202
203  SCIP_CALL(SCIPcacheRowExtensions(scip, row));
204
205  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
206  {
209  assert(flipedge_Uint(e) == (unsigned) flipedge(e));
210  }
211
212  SCIP_CALL(SCIPflushRowExtensions(scip, row));
213
215
217  /* add cut to pool */
218  if( !infeasible )
220 #endif
221
222  cutscount++;
223
224  SCIP_CALL(SCIPreleaseRow(scip, &row));
225
226  if( *ncuts + cutscount >= maxcuts )
227  break;
228  }
229  }
230
231  printf("Deg2 Separator: %d Inequalities added\n", cutscount);
232  *ncuts += cutscount;
233
234  return SCIP_OKAY;
235 }
236 #endif
237
238
239
240 /** separate in-flow cuts:
241  * input of a non-terminal vertex has to be <= 1.0 */
242 static
244  SCIP* scip, /**< SCIP data structure */
245  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
246  const SCIP_Real* nodes_inflow, /**< incoming flow per node */
247  const GRAPH* g, /**< graph data structure */
248  const SCIP_Real* xval, /**< LP-solution values */
249  int vertex, /**< vertex */
250  SCIP_VAR** vars, /**< variables */
251  int* cutcount /**< counts cuts */
252 )
253 {
254  assert(xval && cutcount && vars);
255  assert(!Is_term(g->term[vertex]));
256
257 #ifndef NDEBUG
258  {
259  SCIP_Real sum = 0.0;
260
261  for( int k = g->inpbeg[vertex]; k != EAT_LAST; k = g->ieat[k] )
262  sum += xval[k];
263
264  assert(SCIPisEQ(scip, sum, nodes_inflow[vertex]));
265  }
266 #endif
267
268  if( SCIPisFeasGT(scip, nodes_inflow[vertex], 1.0) )
269  {
270  SCIP_ROW* row = NULL;
271  SCIP_Bool infeasible;
272
273  SCIP_CALL(SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "inflow", -SCIPinfinity(scip), 1.0, FALSE, FALSE, TRUE));
274  SCIP_CALL(SCIPcacheRowExtensions(scip, row));
275
276  for( int k = g->inpbeg[vertex]; k != EAT_LAST; k = g->ieat[k] )
278
279  SCIP_CALL(SCIPflushRowExtensions(scip, row));
281  assert(!infeasible);
282
284  /* if at root node, add cut to pool */
285  if( !infeasible )
287 #endif
288
289  (*cutcount)++;
290
291  SCIP_CALL(SCIPreleaseRow(scip, &row));
292  }
293
294  return SCIP_OKAY;
295 }
296
297
298 /** separate terminal in-flow cuts
299  * at terminal input sum == 1
300  * basically a cut (starcut) */
301 static
303  SCIP* scip, /**< SCIP data structure */
304  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
305  const SCIP_Real* nodes_inflow, /**< incoming flow per node */
306  const GRAPH* g, /**< graph data structure */
307  const SCIP_Real* xval, /**< LP-solution values */
308  const int* termorg, /**< original terminals or NULL */
309  int vertex, /**< vertex */
310  SCIP_VAR** vars, /**< variables */
311  int* cutcount /**< counts cuts */
312 )
313 {
314 #ifndef NDEBUG
315  SCIP_Real sum = 0.0;
316
317  for( int k = g->inpbeg[vertex]; k != EAT_LAST; k = g->ieat[k] )
318  sum += xval[k];
319
320  assert(SCIPisEQ(scip, sum, nodes_inflow[vertex]));
321 #endif
322
323  assert(Is_term(g->term[vertex]));
324
325  if( !SCIPisFeasEQ(scip, nodes_inflow[vertex], 1.0) )
326  {
327  SCIP_ROW* row = NULL;
328  SCIP_Bool infeasible;
329  const SCIP_Bool isLocal = (termorg != NULL && termorg[vertex] != g->term[vertex]);
330
331  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "term", 1.0, 1.0, isLocal, FALSE, TRUE) );
332
333  SCIP_CALL(SCIPcacheRowExtensions(scip, row));
334
335  for( int k = g->inpbeg[vertex]; k != EAT_LAST; k = g->ieat[k] )
337
338  SCIP_CALL(SCIPflushRowExtensions(scip, row));
340
341  if( infeasible )
342  {
343  assert(isLocal);
344  }
345  else
346  {
347  (*cutcount)++;
348  }
349
351  /* add cut to pool */
352  if( !infeasible )
354 #endif
355
356
357  SCIP_CALL(SCIPreleaseRow(scip, &row));
358  }
359
360  return SCIP_OKAY;
361 }
362
363
364 /** separate flow-balance constraints
365  * incoming flow <= outgoing flow */
366 static
368  SCIP* scip, /**< SCIP data structure */
369  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
370  const SCIP_Real* nodes_inflow, /**< incoming flow per node */
371  const GRAPH* g, /**< graph data structure */
372  const SCIP_Real* xval, /**< LP-solution values */
373  int vertex, /**< vertex */
374  SCIP_VAR** vars, /**< variables */
375  int* cutcount /**< counts cuts */
376 )
377 {
378  SCIP_ROW* row = NULL;
379  SCIP_Real sum = -nodes_inflow[vertex];
380
381  assert(!Is_term(g->term[vertex]));
382
383  for( int k = g->outbeg[vertex]; k != EAT_LAST; k = g->oeat[k] )
384  sum += xval[k];
385
386 #ifndef NDEBUG
387  {
388  SCIP_Real sum_debug = 0.0;
389  for( int k = g->inpbeg[vertex]; k != EAT_LAST; k = g->ieat[k] )
390  sum_debug -= xval[k];
391
392  for( int k = g->outbeg[vertex]; k != EAT_LAST; k = g->oeat[k] )
393  sum_debug += xval[k];
394
395  assert(SCIPisEQ(scip, sum_debug, sum));
396  }
397 #endif
398
399  if( SCIPisFeasNegative(scip, sum) )
400  {
401  SCIP_Bool infeasible;
402
403  SCIP_CALL(SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "flowbalance", 0.0, (g->terms == 2) ? 0.0 : SCIPinfinity(scip), FALSE, FALSE, TRUE));
404  SCIP_CALL(SCIPcacheRowExtensions(scip, row));
405
406  for( int k = g->inpbeg[vertex]; k != EAT_LAST; k = g->ieat[k] )
408
409  for( int k = g->outbeg[vertex]; k != EAT_LAST; k = g->oeat[k] )
411
412  SCIP_CALL(SCIPflushRowExtensions(scip, row));
414  assert(!infeasible);
415
417  /* if at root node, add cut to pool */
418  if( !infeasible )
420 #endif
421
422  (*cutcount)++;
423
424  SCIP_CALL(SCIPreleaseRow(scip, &row));
425  }
426
427  return SCIP_OKAY;
428 }
429
430
431 /** separate
432  * the value of each outgoing edge needs to be smaller than the sum of the in-going edges */
433 static
435  SCIP* scip, /**< SCIP data structure */
436  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
437  const SCIP_Real* nodes_inflow, /**< incoming flow per node */
438  const GRAPH* g, /**< graph data structure */
439  const SCIP_Real* xval, /**< LP-solution values */
440  int vertex, /**< vertex */
441  SCIP_VAR** vars, /**< variables */
442  int* cutcount /**< counts cuts */
443 )
444 {
445  const int i = vertex;
446
447  for( int ijedge = g->outbeg[i]; ijedge != EAT_LAST; ijedge = g->oeat[ijedge] )
448  {
449  const int j = g->head[ijedge];
450  const SCIP_Real sum = nodes_inflow[i] - xval[ijedge] - xval[flipedge(ijedge)];
451
452 #ifndef NDEBUG
453  SCIP_Real sum_debug = -xval[ijedge];
454
455  for( int e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
456  if( g->tail[e] != j )
457  sum_debug += xval[e];
458
459  assert(SCIPisEQ(scip, sum, sum_debug));
460 #endif
461
462  if( SCIPisFeasNegative(scip, sum) )
463  {
464  SCIP_Bool infeasible;
465  SCIP_ROW* row = NULL;
466
467  SCIP_CALL(SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "edgeflow", 0.0, SCIPinfinity(scip), FALSE, FALSE, TRUE));
468  SCIP_CALL(SCIPcacheRowExtensions(scip, row));
469
471
472  for( int e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
473  {
474  if( g->tail[e] != j )
476  }
477
478  SCIP_CALL(SCIPflushRowExtensions(scip, row));
480  assert(!infeasible);
481
483  /* add cut to pool */
484  if( !infeasible )
486 #endif
487
488  (*cutcount)++;
489  SCIP_CALL(SCIPreleaseRow(scip, &row));
490  }
491  }
492
493  return SCIP_OKAY;
494 }
495
496
497 /** separate flow-cuts */
498 static
500  SCIP* scip, /**< SCIP data structure */
501  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
502  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
503  SCIP_CONSDATA* consdata, /**< constraint data */
504  const int* termorg, /**< original terminals or NULL */
505  int maxcuts, /**< maximal number of cuts */
506  int* ncuts /**< pointer to store number of cuts */
507  )
508 {
509  const GRAPH* const g = consdata->graph;
510  SCIP_VAR** vars = SCIPprobdataGetVars(scip);
511  const SCIP_Real* xval =SCIPprobdataGetXval(scip, NULL);
512  SCIP_Real* nodes_inflow;
513  int count = 0;
514  const int nnodes = graph_get_nNodes(g);
515  const int maxcuts_local = maxcuts - *ncuts;
516  const SCIP_Bool flowsep = conshdlrdata->flowsep;
517  const SCIP_Bool inflowsep = conshdlrdata->inflowsep;
518  const SCIP_Bool intermflowsep = conshdlrdata->intermflowsep;
519  const SCIP_Bool outflowsep = conshdlrdata->outflowsep;
520  const SCIP_Bool balanceflowsep = conshdlrdata->balanceflowsep;
521
522  assert(conshdlr && xval && ncuts && vars);
523
524  SCIP_CALL( SCIPallocBufferArray(scip, &nodes_inflow, nnodes) );
525
526  for( int i = 0; i < nnodes; i++ )
527  {
528  SCIP_Real sum = 0;
529
530  for( int e = g->inpbeg[i]; e >= 0; e = g->ieat[e] )
531  sum += xval[e];
532
533  nodes_inflow[i] = sum;
534  }
535
536  for( int i = 0; i < nnodes; i++ )
537  {
538  if( i == g->source )
539  continue;
540
541  if( intermflowsep && Is_term(g->term[i]) )
542  {
543  SCIP_CALL( sep_flowTermIn(scip, conshdlr, nodes_inflow, g, xval, termorg, i, vars, &count) );
544
545  if( count >= maxcuts_local )
546  break;
547  }
548
549  /* flow cuts disabled? */
550  if( !flowsep )
551  continue;
552
553  if( outflowsep )
554  {
555  SCIP_CALL( sep_flowEdgeOut(scip, conshdlr, nodes_inflow, g, xval, i, vars, &count) );
556
557  if( count >= maxcuts_local )
558  break;
559  }
560
561  /* from here on consider only non terminals */
562  if( Is_term(g->term[i]) )
563  continue;
564
565  if( inflowsep )
566  {
567  SCIP_CALL( sep_flowIn(scip, conshdlr, nodes_inflow, g, xval, i, vars, &count) );
568
569  if( count >= maxcuts_local )
570  break;
571  }
572
573  if( balanceflowsep )
574  {
575  SCIP_CALL( sep_flowBalance(scip, conshdlr, nodes_inflow, g, xval, i, vars, &count) );
576
577  if( count >= maxcuts_local )
578  break;
579  }
580  }
581
582  SCIPdebugMessage("Flow Separator: %d Inequalities added\n", count);
583
584  *ncuts += count;
585
586  SCIPfreeBufferArray(scip, &nodes_inflow);
587
588  return SCIP_OKAY;
589 }
590
591
592 /**@} */
593
594
595 /**@name Callback methods
596  *
597  * @{
598  */
599
600 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
601 static
602 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyStp)
603 { /*lint --e{715}*/
604  assert(scip != NULL);
605  assert(conshdlr != NULL);
606  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
607
608  /* call inclusion method of constraint handler */
610
611  *valid = TRUE;
612
613  return SCIP_OKAY;
614 }
615
616 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
617 static
618 SCIP_DECL_CONSFREE(consFreeStp)
619 { /*lint --e{715}*/
620  SCIP_CONSHDLRDATA* conshdlrdata;
621
622  assert(scip != NULL);
623  assert(conshdlr != NULL);
624  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
625
626  /* free constraint handler data */
627  conshdlrdata = SCIPconshdlrGetData(conshdlr);
628  assert(conshdlrdata != NULL);
629
630  SCIPfreeRandom(scip, &conshdlrdata->randnumgen);
631
632  SCIPfreeMemory(scip, &conshdlrdata);
633
634  SCIPconshdlrSetData(conshdlr, NULL);
635
636  return SCIP_OKAY;
637 }
638
639 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
640 static
641 SCIP_DECL_CONSINITSOL(consInitsolStp)
642 { /*lint --e{715}*/
643 #ifdef WITH_UG
645 #endif
646  return SCIP_OKAY;
647 }
648
649 static
650 SCIP_DECL_CONSEXITSOL(consExitsolStp)
651 { /*lint --e{715}*/
652  SCIP_CONSHDLRDATA* conshdlrdata;
653
654  conshdlrdata = SCIPconshdlrGetData(conshdlr);
655  assert(conshdlrdata);
656
657  if( conshdlrdata->pcimplications )
658  sepaspecial_pcimplicationsFree(scip, &(conshdlrdata->pcimplications));
659
660  if( conshdlrdata->pacliques )
661  sepaspecial_pacliquesFree(scip, &(conshdlrdata->pacliques));
662
663  if( conshdlrdata->vtimplications )
664  sepaspecial_vtimplicationsFree(scip, &(conshdlrdata->vtimplications));
665
666  return SCIP_OKAY;
667 }
668
669 /** frees specific constraint data */
670 static
671 SCIP_DECL_CONSDELETE(consDeleteStp)
672 { /*lint --e{715}*/
673  assert(conshdlr != NULL);
674  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
675  assert(consdata != NULL);
676  assert(*consdata != NULL);
677
678  SCIPfreeBlockMemory(scip, consdata);
679
680  return SCIP_OKAY;
681 }
682
683 /** transforms constraint data into data belonging to the transformed problem */
684 static
685 SCIP_DECL_CONSTRANS(consTransStp)
686 { /*lint --e{715}*/
687  SCIP_CONSDATA* sourcedata;
688  SCIP_CONSDATA* targetdata;
689
690  assert(conshdlr != NULL);
691  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
692  assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
693  assert(sourcecons != NULL);
694  assert(targetcons != NULL);
695
696  sourcedata = SCIPconsGetData(sourcecons);
697  assert(sourcedata != NULL);
698
699  /* create constraint data for target constraint */
700  SCIP_CALL( SCIPallocBlockMemory(scip, &targetdata) );
701
702  targetdata->graph = sourcedata->graph;
703
704  /* create target constraint */
705  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
706  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
707  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
708  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
709  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
710
711  return SCIP_OKAY;
712 }
713
714 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
715 static
716 SCIP_DECL_CONSINITLP(consInitlpStp)
717 { /*lint --e{715}*/
718 #if 0
719  SCIP_PROBDATA* probdata;
720  GRAPH* graph;
721
722  SCIP_Real lpobjval;
723
724  probdata = SCIPgetProbData(scip);
725  assert(probdata != NULL);
726
727  graph = SCIPprobdataGetGraph(probdata);
728  assert(graph != NULL);
729
730  SCIP_CALL( SCIPdualAscentPcStp(scip, graph, NULL, &lpobjval, TRUE, 1) );
731 #endif
732
733  return SCIP_OKAY;
734 }
735
736 /** separation method of constraint handler for LP solutions */
737 static
738 SCIP_DECL_CONSSEPALP(consSepalpStp)
739 { /*lint --e{715}*/
740  SCIP_CONSHDLRDATA* conshdlrdata;
741  SCIP_CONSDATA* consdata;
742  GRAPH* g;
743  int* termorg = NULL;
744  int* nodestatenew = NULL;
745  int maxcuts;
746  int ncuts = 0;
747  const SCIP_Bool atrootnode = (SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0);
748  SCIP_Bool chgterms = FALSE;
749 #ifndef NDEBUG
750  int nterms;
751 #endif
752
753  *result = SCIP_DIDNOTRUN;
754
755  conshdlrdata = SCIPconshdlrGetData(conshdlr);
756  assert(conshdlrdata != NULL);
757
758  maxcuts = atrootnode ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts;
759
760  assert(nconss == 1);
761  consdata = SCIPconsGetData(conss[0]);
762
763  assert(consdata != NULL);
764
765  g = consdata->graph;
766  assert(g != NULL);
767
768 #ifndef NDEBUG
769  nterms = g->terms;
770 #endif
771
772  /* vertex branching possible? */
774  {
775  chgterms = (!atrootnode && SCIPStpBranchruleIsActive(scip));
776
777  if( chgterms )
778  {
779  SCIPdebugMessage("adapting branched on vertices for separation \n");
780  }
781  }
782
783  if( graph_pc_isPcMw(g) && g->stp_type != STP_BRMWCSP )
784  {
785  if( conshdlrdata->pcimplications == NULL )
786  {
787  graph_pc_2org(scip, g);
788  SCIP_CALL( sepaspecial_pcimplicationsInit(scip, g, &(conshdlrdata->pcimplications)) );
789  graph_pc_2trans(scip, g);
790  }
791
792  SCIP_CALL( sepaspecial_pcimplicationsSeparate(scip, conshdlr, conshdlrdata->pcimplications, maxcuts, &ncuts) );
793  }
794
795 #if STP_SEPASPECIAL_USECLIQUE
796  if( conshdlrdata->pacliques == NULL )
797  {
798  SCIP_CALL( sepaspecial_pacliquesInit(scip, g, &(conshdlrdata->pacliques)) );
799  }
800
801  SCIP_CALL( sepaspecial_pacliquesSeparate(scip, conshdlr, conshdlrdata->pacliques, maxcuts, &ncuts) );
802 #endif
803
804
805 #if STP_SEPASPECIAL_USECVTIMP
806  if( conshdlrdata->vtimplications == NULL )
807  {
808  SCIP_CALL( sepaspecial_vtimplicationsInit(scip, g, &(conshdlrdata->vtimplications)) );
809  }
810
811  SCIP_CALL( sepaspecial_vtimplicationsSeparate(scip, conshdlr, conshdlrdata->vtimplications, maxcuts, &ncuts) );
812 #endif
813
814  /* change graph according to branch-and-bound terminal changes */
815  if( chgterms )
816  {
817  SCIP_Bool conflict = FALSE;
818  const int nnodes = g->knots;
819
820  SCIP_CALL(SCIPallocBufferArray(scip, &nodestatenew, nnodes));
821  SCIP_CALL(SCIPallocBufferArray(scip, &termorg, nnodes));
822  BMScopyMemoryArray(termorg, g->term, nnodes);
823
824  SCIPStpBranchruleInitNodeState(g, nodestatenew);
825  SCIP_CALL( SCIPStpBranchruleGetVertexChgs(scip, nodestatenew, &conflict) );
826
827  assert(!conflict);
828
829  for( int k = 0; k < nnodes; k++ )
830  {
831  if( nodestatenew[k] == BRANCH_STP_VERTEX_TERM && !Is_term(g->term[k]) )
832  graph_knot_chg(g, k, STP_TERM);
833  }
834  }
835
836  SCIP_CALL( sep_flow(scip, conshdlr, conshdlrdata, consdata, termorg, maxcuts, &ncuts) );
837
838  /* NOTE: for 2-terminal problems no cuts are necessary if flows are given */
839  if( !conshdlrdata->flowsep || g->terms != 2 )
840  {
841  SCIP_CALL( mincut_separateLp(scip, conshdlr, NULL, termorg, consdata->graph, maxcuts, &ncuts) );
842  }
843
844  if( ncuts > 0 )
845  *result = SCIP_SEPARATED;
846
847  /* restore graph */
848  if( chgterms )
849  {
850  const int nnodes = g->knots;
851
852  for( int k = 0; k < nnodes; k++ )
853  {
854  if( g->term[k] != termorg[k] )
855  graph_knot_chg(g, k, termorg[k]);
856  }
857  }
858
859 #ifndef NDEBUG
860  assert(g->terms == nterms);
861 #endif
862
863  SCIPfreeBufferArrayNull(scip, &termorg);
864  SCIPfreeBufferArrayNull(scip, &nodestatenew);
865
866  return SCIP_OKAY;
867 }
868
869
870 /** constraint enforcing method of constraint handler for LP solutions */
871 static
872 SCIP_DECL_CONSENFOLP(consEnfolpStp)
873 { /*lint --e{715}*/
874  SCIP_Bool feasible;
875  SCIP_CONSDATA* consdata;
876
877  // todo
878  assert(nconss == 1);
879
880  for( int i = 0; i < nconss; i++ )
881  {
882  consdata = SCIPconsGetData(conss[i]);
883
884  SCIP_CALL( SCIPStpValidateSol(scip, consdata->graph, SCIPprobdataGetXval(scip, NULL), FALSE, &feasible) );
885
886  if( !feasible )
887  {
888  *result = SCIP_INFEASIBLE;
889  return SCIP_OKAY;
890  }
891  }
892
893  *result = SCIP_FEASIBLE;
894
895  return SCIP_OKAY;
896 }
897
898 /** constraint enforcing method of constraint handler for pseudo solutions */
899 static
900 SCIP_DECL_CONSENFOPS(consEnfopsStp)
901 { /*lint --e{715}*/
902  SCIP_Bool feasible;
903
904  // todo
905  assert(nconss == 1);
906
907  for( int i = 0; i < nconss; i++ )
908  {
909  const SCIP_CONSDATA* consdata = SCIPconsGetData(conss[i]);
910
911  SCIP_CALL( SCIPStpValidateSol(scip, consdata->graph, SCIPprobdataGetXval(scip, NULL), FALSE, &feasible) );
912
913  if( !feasible )
914  {
915  *result = SCIP_INFEASIBLE;
916  return SCIP_OKAY;
917  }
918  }
919  *result = SCIP_FEASIBLE;
920
921  return SCIP_OKAY;
922 }
923
924 /** feasibility check method of constraint handler for integral solutions */
925 static
926 SCIP_DECL_CONSCHECK(consCheckStp)
927 { /*lint --e{715}*/
928  const GRAPH* g = SCIPprobdataGetGraph2(scip);
929  SCIP_Bool feasible;
930
931  assert(g != NULL);
932
933  SCIP_CALL(SCIPStpValidateSol(scip, g, SCIPprobdataGetXval(scip, sol), FALSE, &feasible));
934
935  if( !feasible )
936  {
937  *result = SCIP_INFEASIBLE;
938  return SCIP_OKAY;
939  }
940
941  *result = SCIP_FEASIBLE;
942
943  return SCIP_OKAY;
944 }
945
946 /** domain propagation method of constraint handler */
947 static
948 SCIP_DECL_CONSPROP(consPropStp)
949 { /*lint --e{715}*/
950  SCIP_PROBDATA* probdata;
951  GRAPH* graph;
952
953  probdata = SCIPgetProbData(scip);
954  assert(probdata != NULL);
955
956  graph = SCIPprobdataGetGraph(probdata);
957  assert(graph != NULL);
958
959  /* for degree constrained model, check whether problem is infeasible */
960  if( graph->stp_type == STP_DCSTP )
961  {
962  int k;
963  int nnodes;
964  int degsum;
965  int* maxdegs;
966
967  nnodes = graph->knots;
968  maxdegs = graph->maxdeg;
969
970  assert(maxdegs != NULL);
971
972  degsum = 0;
973  for( k = 0; k < nnodes; k++ )
974  {
975  if( Is_term(graph->term[k]) )
976  {
977  assert(maxdegs[k] > 0);
978  degsum += maxdegs[k] - 1;
979  }
980  else
981  {
982  assert(maxdegs[k] >= 0);
983  degsum += MAX(maxdegs[k] - 2, 0);
984  }
985  }
986
987  if( degsum < graph->terms - 2 )
988  *result = SCIP_CUTOFF;
989  else
990  *result = SCIP_DIDNOTFIND;
991  }
992  return SCIP_OKAY;
993 }
994
995 /** variable rounding lock method of constraint handler */
996 static
997 SCIP_DECL_CONSLOCK(consLockStp)
998 { /*lint --e{715}*/
999  SCIP_VAR** vars;
1000  int nvars;
1001  int v;
1002
1003  assert(scip != NULL);
1004  assert(cons != NULL);
1005
1006  vars = SCIPprobdataGetVars(scip);
1007  nvars = SCIPprobdataGetNVars(scip);
1008
1009  for( v = 0; v < nvars; ++v )
1010  {
1011  SCIP_CALL( SCIPaddVarLocksType(scip, vars[v], locktype, nlockspos, nlocksneg) );
1012  }
1013
1014  return SCIP_OKAY;
1015 }
1016
1017 /** constraint copying method of constraint handler */
1018 static
1019 SCIP_DECL_CONSCOPY(consCopyStp)
1020 { /*lint --e{715}*/
1021  const char* consname;
1022  SCIP_PROBDATA* probdata;
1023  GRAPH* graph;
1024
1025  probdata = SCIPgetProbData(scip);
1026  assert(probdata != NULL);
1027
1028  graph = SCIPprobdataGetGraph(probdata);
1029  assert(graph != NULL);
1030
1031  consname = SCIPconsGetName(sourcecons);
1032
1033  /* creates and captures a and constraint */
1034  SCIP_CALL( SCIPcreateConsStp(scip, cons, consname, graph) );
1035
1036  *valid = TRUE;
1037
1038  return SCIP_OKAY;
1039 }
1040
1041
1042 /**@} */
1043
1044 /**@name Interface methods
1045  *
1046  * @{
1047  */
1048
1049 /** creates the handler for stp constraints and includes it in SCIP */
1051  SCIP* scip /**< SCIP data structure */
1052  )
1053 {
1054  SCIP_CONSHDLRDATA* conshdlrdata;
1055  SCIP_CONSHDLR* conshdlr;
1056
1057  /* create stp constraint handler data */
1058  SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
1059
1060  conshdlr = NULL;
1061  /* include constraint handler */
1064  consEnfolpStp, consEnfopsStp, consCheckStp, consLockStp,
1065  conshdlrdata) );
1066  assert(conshdlr != NULL);
1067
1068  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyStp, consCopyStp) );
1069  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteStp) );
1070  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransStp) );
1071  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolStp) );
1072  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolStp) );
1073
1074  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpStp) );
1075  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropStp, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
1077  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpStp, NULL, CONSHDLR_SEPAFREQ,
1079  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeStp) );
1080
1081  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/stp/backcut", "Try Back-Cuts",
1082  &conshdlrdata->backcut, TRUE, DEFAULT_BACKCUT, NULL, NULL) );
1083
1084  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/stp/creepflow", "Use Creep-Flow",
1085  &conshdlrdata->creepflow, TRUE, DEFAULT_CREEPFLOW, NULL, NULL) );
1086
1087  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/stp/disjunctcut", "Only disjunct Cuts",
1088  &conshdlrdata->disjunctcut, TRUE, DEFAULT_DISJUNCTCUT, NULL, NULL) );
1089
1090  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/stp/nestedcut", "Try Nested-Cuts",
1091  &conshdlrdata->nestedcut, TRUE, DEFAULT_NESTEDCUT, NULL, NULL) );
1092
1093  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/stp/flowsep", "Try Flow-Cuts",
1094  &conshdlrdata->flowsep, TRUE, DEFAULT_FLOWSEP, NULL, NULL) );
1095
1096  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/stp/inflowsep", "Try Unit Inflow-Cuts",
1097  &conshdlrdata->inflowsep, TRUE, DEFAULT_INFLOWSEP, NULL, NULL) );
1098
1099  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/stp/intermflowsep", "Try terminal Unit Inflow-Cuts",
1100  &conshdlrdata->intermflowsep, TRUE, DEFAULT_INFLOWTERMSEP, NULL, NULL) );
1101
1102  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/stp/outflowsep", "Try single edge Outflow-Cuts",
1103  &conshdlrdata->outflowsep, TRUE, DEFAULT_OUTFLOWSEP, NULL, NULL) );
1104
1105  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/stp/balanceflowsep", "Try Flow-balance Cuts",
1106  &conshdlrdata->balanceflowsep, TRUE, DEFAULT_BALANCEFLOWSEP, NULL, NULL) );
1107
1109  "maximal number of separation rounds per node (-1: unlimited)",
1110  &conshdlrdata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
1111
1113  "maximal number of separation rounds per node in the root node (-1: unlimited)",
1114  &conshdlrdata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
1115
1117  "maximal number of cuts separated per separation round",
1118  &conshdlrdata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
1119
1121  "maximal number of cuts separated per separation round in the root node",
1122  &conshdlrdata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
1123
1124  conshdlrdata->pacliques = NULL;
1125  conshdlrdata->pcimplications = NULL;
1126  conshdlrdata->vtimplications = NULL;
1127
1128  SCIP_CALL( SCIPcreateRandom(scip, &conshdlrdata->randnumgen, 1, TRUE) );
1129
1130  return SCIP_OKAY;
1131 }
1132
1133 /** creates and captures a stp constraint */
1135  SCIP* scip, /**< SCIP data structure */
1136  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1137  const char* name, /**< name of constraint */
1138  GRAPH* graph /**< graph data structure */
1139  )
1140 {
1141  SCIP_CONSHDLR* conshdlr;
1142  SCIP_CONSDATA* consdata;
1143
1144  /* find the stp constraint handler */
1145  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
1146  if( conshdlr == NULL )
1147  {
1149  return SCIP_PLUGINNOTFOUND;
1150  }
1151
1152  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
1153
1154  consdata->graph = graph;
1155
1156  /* create constraint */
1157  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, FALSE, TRUE, TRUE, TRUE, TRUE,
1158  FALSE, FALSE, FALSE, FALSE, FALSE) );
1159
1160  return SCIP_OKAY;
1161 }
1162
1163 /** add cut corresponding to contraction */
1165  SCIP* scip, /**< SCIP data structure */
1166  SCIP_VAR* edge, /**< edge */
1167  SCIP_VAR* revedge, /**< reversed edge */
1168  SCIP_Bool localcut /**< add local cut? */
1169 )
1170 {
1171  SCIP_ROW* row = NULL;
1172  SCIP_CONSHDLR* conshdlr;
1173  SCIP_Bool infeasible;
1174
1175  if( SCIPvarGetLbLocal(edge) > 0.5 || SCIPvarGetUbLocal(edge) < 0.5 || SCIPvarGetLbLocal(revedge) > 0.5 || SCIPvarGetUbLocal(revedge) < 0.5 )
1176  {
1177  printf("cannot add contraction cut \n");
1178  return SCIP_OKAY;
1179  }
1180
1181  conshdlr = SCIPfindConshdlr(scip, "stp");
1182  assert(conshdlr != NULL);
1183  assert(SCIPconshdlrGetNConss(conshdlr) > 0);
1184
1185  SCIP_CALL(SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "contraction", 1.0, SCIPinfinity(scip), localcut, FALSE, TRUE));
1186  SCIP_CALL(SCIPcacheRowExtensions(scip, row));
1187
1190
1191  SCIP_CALL(SCIPflushRowExtensions(scip, row));
1192
1194
1196  /* add cut to pool */
1197  if( !infeasible )
1199 #endif
1200
1201  SCIP_CALL(SCIPreleaseRow(scip, &row));
1202
1203  return SCIP_OKAY;
1204 }
1205
1206 /** sets graph */
1208  SCIP* scip /**< SCIP data structure */
1209  )
1210 {
1211  SCIP_CONSDATA* consdata;
1212  SCIP_CONSHDLR* conshdlr;
1213
1214  conshdlr = SCIPfindConshdlr(scip, "stp");
1215  assert(conshdlr != NULL);
1216 #ifdef WITH_UG
1217  if( SCIPconshdlrGetNConss(conshdlr) == 0 )
1218  return;
1219 #endif
1220
1221  assert(SCIPconshdlrGetNConss(conshdlr) > 0);
1222  consdata = SCIPconsGetData(SCIPconshdlrGetConss(conshdlr)[0]);
1223  assert(consdata != NULL);
1224  consdata->graph = SCIPprobdataGetGraph2(scip);
1225  assert(consdata->graph != NULL);
1226 }
1227
1228
1229 /** returns implications start array */
1230 const int* SCIPStpGetPcImplStarts(
1231  SCIP* scip /**< SCIP data structure */
1232  )
1233 {
1234  SCIP_CONSHDLR* conshdlr = NULL;
1235  SCIP_CONSHDLRDATA* conshdlrdata;
1236
1237  conshdlr = SCIPfindConshdlr(scip, "stp");
1238  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1239  assert(conshdlrdata);
1240
1241  if( !(conshdlrdata->pcimplications) )
1242  return NULL;
1243
1244  return sepaspecial_pcimplicationsGetStarts(conshdlrdata->pcimplications);
1245 }
1246
1247
1248 /** returns number implications starts */
1250  SCIP* scip /**< SCIP data structure */
1251  )
1252 {
1253  SCIP_CONSHDLR* conshdlr = NULL;
1254  SCIP_CONSHDLRDATA* conshdlrdata;
1255
1256  conshdlr = SCIPfindConshdlr(scip, "stp");
1257  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1258  assert(conshdlrdata);
1259
1260  if( !(conshdlrdata->pcimplications) )
1261  return 0;
1262
1263  return sepaspecial_pcimplicationsGetNstarts(conshdlrdata->pcimplications);
1264 }
1265
1266
1267 /** returns implications vertices array */
1268 const int* SCIPStpGetPcImplVerts(
1269  SCIP* scip /**< SCIP data structure */
1270  )
1271 {
1272  SCIP_CONSHDLR* conshdlr = NULL;
1273  SCIP_CONSHDLRDATA* conshdlrdata;
1274
1275  conshdlr = SCIPfindConshdlr(scip, "stp");
1276  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1277  assert(conshdlrdata);
1278
1279  if( !(conshdlrdata->pcimplications) )
1280  return NULL;
1281
1282  return sepaspecial_pcimplicationsGetVerts(conshdlrdata->pcimplications);
1283 }
1284
1285
1286 /**@} */
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4205
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
#define CONSHDLR_PROPFREQ
Definition: cons_stp.c:76
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:563
static volatile int nterms
Definition: interrupt.c:38
#define DEFAULT_CREEPFLOW
Definition: cons_stp.c:92
static SCIP_DECL_CONSINITSOL(consInitsolStp)
Definition: cons_stp.c:642
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1626
#define DEFAULT_NESTEDCUT
Definition: cons_stp.c:94
Definition: graphdefs.h:224
void sepaspecial_pacliquesFree(SCIP *scip, PACLIQUES **pacliques)
Definition: sepaspecial.c:207
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:82
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8344
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:586
Separator for Steiner tree problem contraints beyond flow-balance-directed-cut constraints.
int source
Definition: graphdefs.h:195
SCIP_RETCODE SCIPStpBranchruleGetVertexChgs(SCIP *scip, int *vertexchgs, SCIP_Bool *conflictFound)
Definition: branch_stp.c:977
const int * sepaspecial_pcimplicationsGetStarts(const PCIMPLICATION *pcimp)
Definition: sepaspecial.c:647
static SCIP_DECL_CONSENFOLP(consEnfolpStp)
Definition: cons_stp.c:873
#define Is_term(a)
Definition: graphdefs.h:102
static SCIP_DECL_CONSSEPALP(consSepalpStp)
Definition: cons_stp.c:739
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1649
Constraint handler for Steiner problems.
#define DEFAULT_BACKCUT
Definition: cons_stp.c:91
int terms
Definition: graphdefs.h:192
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
SCIP_RETCODE sepaspecial_pacliquesSeparate(SCIP *scip, SCIP_CONSHDLR *conshdlr, PACLIQUES *pacliques, int maxcuts, int *ncuts)
Definition: sepaspecial.c:222
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
#define DEFAULT_INFLOWSEP
Definition: cons_stp.c:96
#define DEFAULT_OUTFLOWSEP
Definition: cons_stp.c:98
int *RESTRICT maxdeg
Definition: graphdefs.h:206
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
#define DEFAULT_INFLOWTERMSEP
Definition: cons_stp.c:97
SCIP_RETCODE sepaspecial_vtimplicationsInit(SCIP *scip, const GRAPH *g, VTIMPLICATION **vtimplications)
Definition: sepaspecial.c:669
void graph_pc_2org(SCIP *, GRAPH *)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4547
#define FALSE
Definition: def.h:87
int *RESTRICT inpbeg
Definition: graphdefs.h:202
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:166
void SCIPStpBranchruleInitNodeState(const GRAPH *g, int *nodestate)
Definition: branch_stp.c:954
SCIP_Real SCIPinfinity(SCIP *scip)
Problem data for stp problem.
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8364
#define STP_DCSTP
Definition: graphdefs.h:47
int SCIPprobdataGetNVars(SCIP *scip)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:220
SCIP_RETCODE SCIPStpAddContractionCut(SCIP *scip, SCIP_VAR *edge, SCIP_VAR *revedge, SCIP_Bool localcut)
Definition: cons_stp.c:1165
#define DEFAULT_MAXROUNDS
Definition: cons_stp.c:84
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7442
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
static SCIP_DECL_CONSFREE(consFreeStp)
Definition: cons_stp.c:619
#define DEFAULT_DISJUNCTCUT
Definition: cons_stp.c:93
#define CONSHDLR_CHECKPRIORITY
Definition: cons_stp.c:74
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8354
static SCIP_DECL_CONSLOCK(consLockStp)
Definition: cons_stp.c:998
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:609
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
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
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyStp)
Definition: cons_stp.c:603
static SCIP_RETCODE sep_flow(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSDATA *consdata, const int *termorg, int maxcuts, int *ncuts)
Definition: cons_stp.c:500
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4256
static SCIP_RETCODE sep_flowBalance(SCIP *scip, SCIP_CONSHDLR *conshdlr, const SCIP_Real *nodes_inflow, const GRAPH *g, const SCIP_Real *xval, int vertex, SCIP_VAR **vars, int *cutcount)
Definition: cons_stp.c:368
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:429
static SCIP_DECL_CONSEXITSOL(consExitsolStp)
Definition: cons_stp.c:651
int *RESTRICT oeat
Definition: graphdefs.h:231
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:332
static SCIP_RETCODE sep_flowTermIn(SCIP *scip, SCIP_CONSHDLR *conshdlr, const SCIP_Real *nodes_inflow, const GRAPH *g, const SCIP_Real *xval, const int *termorg, int vertex, SCIP_VAR **vars, int *cutcount)
Definition: cons_stp.c:303
#define CONSHDLR_DESC
Definition: cons_stp.c:71
void graph_pc_2trans(SCIP *, GRAPH *)
int stp_type
Definition: graphdefs.h:264
#define SCIPerrorMessage
Definition: pub_message.h:55
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4175
SCIP_RETCODE sepaspecial_pcimplicationsInit(SCIP *scip, const GRAPH *g, PCIMPLICATION **pcimplications)
Definition: sepaspecial.c:371
#define CONSHDLR_SEPAPRIORITY
Definition: cons_stp.c:72
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_RETCODE SCIPincludeConshdlrStp(SCIP *scip)
Definition: cons_stp.c:1051
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8085
#define DEFAULT_MAXROUNDSROOT
Definition: cons_stp.c:85
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8304
void SCIPStpConshdlrSetGraph(SCIP *scip)
Definition: cons_stp.c:1208
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4195
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Bool SCIPStpBranchruleIsActive(SCIP *scip)
Definition: branch_stp.c:1099
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define CONSHDLR_DELAYPROP
Definition: cons_stp.c:81
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8324
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
const SCIP_Bool * SCIPStpPropGet2BoundedArr(SCIP *scip)
Definition: prop_stp.c:2593
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:56
SCIP_RETCODE SCIPStpValidateSol(SCIP *, const GRAPH *, const double *, SCIP_Bool, SCIP_Bool *)
Definition: validate.c:202
#define CONSHDLR_NAME
Definition: cons_stp.c:70
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4590
static SCIP_DECL_CONSENFOPS(consEnfopsStp)
Definition: cons_stp.c:901
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
propagator for Steiner tree problems, using the LP reduced costs
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define DEFAULT_MAXSEPACUTS
Definition: cons_stp.c:86
static SCIP_DECL_CONSCOPY(consCopyStp)
Definition: cons_stp.c:1020
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT ieat
Definition: graphdefs.h:230
static SCIP_DECL_CONSTRANS(consTransStp)
Definition: cons_stp.c:686
SCIP_RETCODE sepaspecial_vtimplicationsSeparate(SCIP *scip, SCIP_CONSHDLR *conshdlr, VTIMPLICATION *vtimplications, int maxcuts, int *ncuts)
Definition: sepaspecial.c:743
int *RESTRICT tail
Definition: graphdefs.h:223
static SCIP_DECL_CONSDELETE(consDeleteStp)
Definition: cons_stp.c:672
#define BRANCH_STP_VERTEX_TERM
Definition: branch_stp.h:39
#define flipedge(edge)
Definition: graphdefs.h:84
#define MAX(x, y)
Definition: tclique_def.h:83
Definition: scip_cut.c:352
#define STP_TERM
Definition: graphdefs.h:61
const int * sepaspecial_pcimplicationsGetVerts(const PCIMPLICATION *pcimp)
Definition: sepaspecial.c:658
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8284
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8254
int *RESTRICT term
Definition: graphdefs.h:196
#define CONSHDLR_EAGERFREQ
Definition: cons_stp.c:77
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
SCIP_Bool SCIPStpBranchruleProbIsCompatible(const GRAPH *graph)
Definition: branch_stp.c:1119
#define flipedge_Uint(edge)
Definition: graphdefs.h:85
Constraint handler for linear constraints in their most general form, .
const int * SCIPStpGetPcImplVerts(SCIP *scip)
Definition: cons_stp.c:1269
#define DEFAULT_FLOWSEP
Definition: cons_stp.c:95
SCIP_RETCODE SCIPcreateConsStp(SCIP *scip, SCIP_CONS **cons, const char *name, GRAPH *graph)
Definition: cons_stp.c:1135
int sepaspecial_pcimplicationsGetNstarts(const PCIMPLICATION *pcimp)
Definition: sepaspecial.c:636
Portable definitions.
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
Steiner vertex branching rule.
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
#define DEFAULT_MAXSEPACUTSROOT
Definition: cons_stp.c:87
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
static SCIP_DECL_CONSINITLP(consInitlpStp)
Definition: cons_stp.c:717
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8115
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:963
#define CONSHDLR_DELAYSEPA
Definition: cons_stp.c:80
#define CONSHDLR_SEPAFREQ
Definition: cons_stp.c:75
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
const int * SCIPStpGetPcImplStarts(SCIP *scip)
Definition: cons_stp.c:1231
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8334
void sepaspecial_vtimplicationsFree(SCIP *scip, VTIMPLICATION **vtimplications)
Definition: sepaspecial.c:730
#define CONSHDLR_PROP_TIMING
Definition: cons_stp.c:89
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8274
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
int *RESTRICT outbeg
Definition: graphdefs.h:204
#define DEFAULT_BALANCEFLOWSEP
Definition: cons_stp.c:99
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8264
#define STP_BRMWCSP
Definition: graphdefs.h:55
#define CONSHDLR_ENFOPRIORITY
Definition: cons_stp.c:73
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
SCIP_RETCODE sepaspecial_pcimplicationsSeparate(SCIP *scip, SCIP_CONSHDLR *conshdlr, PCIMPLICATION *pcimplications, int maxcuts, int *ncuts)
Definition: sepaspecial.c:498
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:55
static SCIP_RETCODE sep_flowEdgeOut(SCIP *scip, SCIP_CONSHDLR *conshdlr, const SCIP_Real *nodes_inflow, const GRAPH *g, const SCIP_Real *xval, int vertex, SCIP_VAR **vars, int *cutcount)
Definition: cons_stp.c:435
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define nnodes
Definition: gastrans.c:65
static SCIP_RETCODE sep_flowIn(SCIP *scip, SCIP_CONSHDLR *conshdlr, const SCIP_Real *nodes_inflow, const GRAPH *g, const SCIP_Real *xval, int vertex, SCIP_VAR **vars, int *cutcount)
Definition: cons_stp.c:244
#define CONSHDLR_NEEDSCONS
Definition: cons_stp.c:82
static SCIP_DECL_CONSCHECK(consCheckStp)
Definition: cons_stp.c:927
SCIPallocBlockMemory(scip, subsol))
int SCIPStpGetPcImplNstarts(SCIP *scip)
Definition: cons_stp.c:1250
void sepaspecial_pcimplicationsFree(SCIP *scip, PCIMPLICATION **pcimplications)
Definition: sepaspecial.c:485
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:1382
Minimum cut routines for Steiner problems.
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:453
GRAPH * SCIPprobdataGetGraph2(SCIP *scip)
SCIP_RETCODE mincut_separateLp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_RANDNUMGEN *randnumgen, const int *termorg, GRAPH *g, int maxncuts, int *ncuts)
Definition: mincut.c:2360
static SCIP_DECL_CONSPROP(consPropStp)
Definition: cons_stp.c:949
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:266
SCIP_RETCODE sepaspecial_pacliquesInit(SCIP *scip, const GRAPH *g, PACLIQUES **pacliques)
Definition: sepaspecial.c:165