Scippy

SCIP

Solving Constraint Integer Programs

sepaspecial.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 /* */
6 /* Copyright (C) 2002-2022 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 sepaspecial.c
17  * @brief Separator for Steiner tree problem contraints beyond flow-balance-directed-cut constraints
18  * @author Daniel Rehfeldt
19  *
20  * This file includes some special separator routines beyond the flow-balance directed cut formulation constraints.
21  *
22  *
23  *
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #include <assert.h>
29 #include <string.h>
30 
31 #include "sepaspecial.h"
32 #include "probdata_stp.h"
33 #include "portab.h"
34 #include "stpvector.h"
35 #include "prop_stp.h"
36 #include "scip/cons_linear.h"
37 
38 #define PCIMPLICATIONS_ALLOC_FACTOR 4
39 
40 
41 /** pseudo ancestor cliques */
43 {
44  SCIP_Real* ancestors_lpweights;/**< of size nancestors */
45  int* halfedges_starts; /**< CSR like starts for accessing ancestors */
46  int* halfedges_ancestors;/**< CSR like ancestors per edge */
47  int halfnedges; /**< |A| / 2 */
48  int nancestors; /**< total number of pseudo ancestors */
49  int nfails; /**< number of failures */
50 };
51 
52 
53 /** implications between potential terminals */
55 {
56  int* pcimplstart; /**< start for each proper potential terminal */
57  int* pcimplverts; /**< all vertices */
58  int pcimplnppterms; /**< number of proper potential terminals used */
59 };
60 
61 
62 /** cuts for implications between non-terminals and terminals */
64 {
65  STP_Vectype(int) impverts; /**< implications vertices */
66  STP_Vectype(int) imparcs; /**< implications arcs (from non-terminals to terminals) */
67 };
68 
69 
70 /*
71  * local methods
72  */
73 
74 /** returns incoming flow for given node */
75 static inline
77  const GRAPH* g, /**< graph data structure */
78  const SCIP_Real* xval, /**< edge values */
79  int vert /**< the vertex */
80 )
81 {
82  double insum = 0.0;
83 
84  for( int e = g->inpbeg[vert]; e >= 0; e = g->ieat[e] )
85  insum += xval[e];
86 
87  return insum;
88 }
89 
90 
91 
92 /** initializes pseudo-ancestor CSR like map from edges to ancestors */
93 static
95  SCIP* scip, /**< SCIP data structure */
96  const GRAPH* g, /**< graph data structure */
97  PACLIQUES* pacliques /**< clique data */
98 )
99 {
100  int ancestors_size = 0;
101  int* RESTRICT halfedges_starts;
102  int* RESTRICT halfedges_ancestors;
103  const int nedges = graph_get_nEdges(g);
104 
105  assert(scip && pacliques && g);
106  assert(pacliques->ancestors_lpweights && pacliques->halfedges_starts);
107  assert(pacliques->nancestors > 0);
108 
109  /* count */
110  for( int e = 0; e < nedges; e += 2 )
111  {
112  const int nancestors = graph_edge_nPseudoAncestors(g, e);
113 
114  assert(nancestors >= 0);
115  assert(ancestors_size < INT_MAX - nancestors);
116  assert(graph_edge_nPseudoAncestors(g, e) == graph_edge_nPseudoAncestors(g, e + 1));
117  ancestors_size += nancestors;
118  }
119 
120  /* NOTE: ancestor size might be 0 if all edges with ancestor have been deleted */
121  assert(ancestors_size >= 0);
122  printf("pseudo-ancestor cliques total number of ancestors: %d \n", ancestors_size);
123 
124  if( ancestors_size > 0 )
125  {
126  SCIP_CALL( SCIPallocMemoryArray(scip, &(pacliques->halfedges_ancestors), ancestors_size) );
127  }
128  else
129  {
130  pacliques->halfedges_ancestors = NULL;
131  }
132 
133  halfedges_starts = pacliques->halfedges_starts;
134  halfedges_ancestors = pacliques->halfedges_ancestors;
135  halfedges_starts[0] = 0;
136 
137  /* insert */
138  for( int e = 0; e < nedges; e += 2 )
139  {
140  const int e_half = e / 2;
141  const int nancestors = graph_edge_nPseudoAncestors(g, e);
142 
143  halfedges_starts[e_half + 1] = halfedges_starts[e_half] + nancestors;
144 
145  if( nancestors > 0 )
146  {
147  const int* const ancestors = graph_edge_getPseudoAncestors(g, e);
148  assert(halfedges_ancestors);
149 
150  BMScopyMemoryArray(halfedges_ancestors + halfedges_starts[e_half], ancestors, nancestors);
151  }
152  }
153  assert(halfedges_starts[pacliques->halfnedges] == ancestors_size);
154 
155  return SCIP_OKAY;
156 }
157 
158 
159 /*
160  * Interface methods
161  */
162 
163 
164 /** initializes pseudo-ancestor cliques */
166  SCIP* scip, /**< SCIP data structure */
167  const GRAPH* g, /**< graph data structure */
168  PACLIQUES** pacliques /**< clique data */
169 )
170 {
171  PACLIQUES* pac;
172  const int nedges = graph_get_nEdges(g);
173 
174  assert(scip && g);
175 
176  SCIP_CALL( SCIPallocMemory(scip, pacliques) );
177  pac = *pacliques;
178 
179  pac->halfnedges = nedges / 2;
180  assert(pac->halfnedges > 0);
182  assert(pac->nancestors >= 0);
183 
184  pac->nfails = 0;
185 
186  pac->halfedges_starts = NULL;
187 
188  if( pac->nancestors > 0 )
189  {
191  SCIP_CALL( SCIPallocMemoryArray(scip, &(pac->halfedges_starts), pac->halfnedges + 1) );
192 
193  SCIP_CALL( pacliquesBuildMap(scip, g, pac) );
194  }
195  else
196  {
197  pac->ancestors_lpweights = NULL;
198  pac->halfedges_starts = NULL;
199  pac->halfedges_ancestors = NULL;
200  }
201 
202  return SCIP_OKAY;
203 }
204 
205 
206 /** frees */
208  SCIP* scip, /**< SCIP data structure */
209  PACLIQUES** pacliques /**< clique data */
210 )
211 {
212  SCIPfreeMemoryArrayNull(scip, &((*pacliques)->halfedges_ancestors));
213  SCIPfreeMemoryArrayNull(scip, &((*pacliques)->halfedges_starts));
214  SCIPfreeMemoryArrayNull(scip, &((*pacliques)->ancestors_lpweights));
215 
216  SCIPfreeMemoryArray(scip, pacliques);
217 }
218 
219 
220 
221 /** separates */
223  SCIP* scip, /**< SCIP data structure */
224  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
225  PACLIQUES* pacliques, /**< clique data */
226  int maxcuts, /**< maximal number of cuts */
227  int* ncuts /**< pointer to store number of cuts */
228  )
229 {
230  SCIP_ROW** rows;
231  GRAPH* g = SCIPprobdataGetGraph2(scip);
232  SCIP_VAR** vars;
233  const int* halfedges_starts;
234  const int* halfedges_ancestors;
235  SCIP_Real* RESTRICT ancestorweights;
236  const SCIP_Real* xval;
237  const int nedges = graph_get_nEdges(g);
238  int cutscount;
239  const int nancestors = pacliques->nancestors;
240  SCIP_Bool hasViolations = FALSE;
241 
242  assert(pacliques && conshdlr && ncuts);
243  assert(maxcuts > 0);
244 
245  /* nothing to separate? */
246  if( nancestors == 0 )
247  return SCIP_OKAY;
248 
249  if( pacliques->nfails > 1 )
250  return SCIP_OKAY;
251 
252  cutscount = 0;
253 
254  halfedges_starts = pacliques->halfedges_starts;
255  halfedges_ancestors = pacliques->halfedges_ancestors;
256  ancestorweights = pacliques->ancestors_lpweights;
257  vars = SCIPprobdataGetVars(scip);
258  xval = SCIPprobdataGetXval(scip, NULL);
259 
260  assert(halfedges_starts && ancestorweights);
261  assert(vars && xval);
262 
263  for( int i = 0; i < nancestors; i++ )
264  {
265  ancestorweights[i] = 0.0;
266  }
267 
268  /* add LP ancestor weights up */
269  for( int e = 0; e < nedges; e += 2 )
270  {
271  const SCIP_Real edgeweight = xval[e] + xval[e + 1];
272 
273  if( GT(edgeweight, 0.0) )
274  {
275  const int e_half = e / 2;
276  for( int i = halfedges_starts[e_half]; i != halfedges_starts[e_half + 1]; i++ )
277  {
278  const int ancestor = halfedges_ancestors[i];
279  assert(0 <= ancestor && ancestor < nancestors);
280 
281  ancestorweights[ancestor] += edgeweight;
282 
283  if( !hasViolations && GT(ancestorweights[ancestor], 1.0) )
284  hasViolations = TRUE;
285  }
286  }
287  }
288 
289  if( !hasViolations )
290  {
291  printf("no violations found... \n");
292  pacliques->nfails++;
293  return SCIP_OKAY;
294  }
295 
296  SCIP_CALL( SCIPallocBufferArray(scip, &rows, nancestors) );
297 
298  for( int i = 0; i < nancestors; i++ )
299  {
300  if( SCIPisFeasGT(scip, ancestorweights[i], 1.0) )
301  {
302  printf("violation for ancestor %d (%f > 1) \n", i, ancestorweights[i]);
303 
304  SCIP_CALL(SCIPcreateEmptyRowConshdlr(scip, &(rows[i]), conshdlr, "pa-clique", -SCIPinfinity(scip), 1.0, FALSE, FALSE, TRUE));
305  SCIP_CALL(SCIPcacheRowExtensions(scip, rows[i]));
306  }
307  else
308  {
309  rows[i] = NULL;
310  }
311  }
312 
313  /* separation loop */
314  for( int e = 0; e < nedges; e += 2 )
315  {
316  const int e_half = e / 2;
317 
318  for( int i = halfedges_starts[e_half]; i != halfedges_starts[e_half + 1]; i++ )
319  {
320  const int ancestor = halfedges_ancestors[i];
321  assert(0 <= ancestor && ancestor < nancestors);
322 
323  if( rows[ancestor] )
324  {
325  SCIP_CALL(SCIPaddVarToRow(scip, rows[ancestor], vars[e], 1.0));
326  SCIP_CALL(SCIPaddVarToRow(scip, rows[ancestor], vars[e + 1], 1.0));
327  }
328  }
329  }
330 
331  for( int i = 0; i < nancestors; i++ )
332  {
333  if( rows[i] )
334  {
335  SCIP_CALL(SCIPflushRowExtensions(scip, rows[i]));
336 
337  if( SCIPisCutEfficacious(scip, NULL, rows[i]) )
338  {
339  SCIP_Bool infeasible;
340 
341  SCIP_CALL(SCIPaddRow(scip, rows[i], FALSE, &infeasible));
342  assert(!infeasible);
343 
344  printf("added conflict-cut for ancestor %d \n", i);
345 #if ADDCUTSTOPOOL
346  /* add cut to pool */
347  if( !infeasible )
348  SCIP_CALL( SCIPaddPoolCut(scip, row) );
349 #endif
350  if( *ncuts + cutscount++ >= maxcuts )
351  {
352  SCIP_CALL(SCIPreleaseRow(scip, &(rows[i])));
353  break;
354  }
355  }
356 
357  SCIP_CALL(SCIPreleaseRow(scip, &(rows[i])));
358  }
359  }
360 
361  SCIPfreeBufferArray(scip, &rows);
362 
363  if( cutscount == 0 )
364  pacliques->nfails++;
365 
366  return SCIP_OKAY;
367 }
368 
369 
370 /** initializes (R)PC implications */
372  SCIP* scip, /**< SCIP data structure */
373  const GRAPH* g, /**< graph data structure */
374  PCIMPLICATION** pcimplications /**< implication data */
375 )
376 {
377  PCIMPLICATION* pcimps;
378  int* start;
379  int* verts;
380  int* termmark;
381  int* visitlist;
382  SCIP_Real* dist;
383  STP_Bool* visited;
384  int nspares;
385  int termscount;
386  int nimplications;
387  const int nnodes = graph_get_nNodes(g);
388  const int nppterms = graph_pc_nProperPotentialTerms(g);
389  const int maxnimplications = PCIMPLICATIONS_ALLOC_FACTOR * g->edges;
390  const int slotsize = ((nppterms == 0) ? 0 : maxnimplications / nppterms);
391 
392  assert(scip && g);
393  assert(graph_pc_isPcMw(g) && !g->extended);
394 
395  SCIP_CALL( SCIPallocMemory(scip, pcimplications) );
396  pcimps = *pcimplications;
397  pcimps->pcimplnppterms = 0;
398 
399  if( nppterms == 0 )
400  {
401  pcimps->pcimplstart = NULL;
402  pcimps->pcimplverts = NULL;
403  return SCIP_OKAY;
404  }
405 
406  assert(slotsize >= 1 && slotsize * nppterms <= maxnimplications);
407 
408  SCIP_CALL(SCIPallocBufferArray(scip, &dist, nnodes));
409  SCIP_CALL(SCIPallocBufferArray(scip, &visited, nnodes));
410  SCIP_CALL(SCIPallocBufferArray(scip, &visitlist, nnodes));
411  SCIP_CALL(SCIPallocBufferArray(scip, &termmark, nnodes));
412  SCIP_CALL(SCIPallocMemoryArray(scip, &(pcimps->pcimplstart), nppterms + 1));
413  SCIP_CALL(SCIPallocMemoryArray(scip, &(pcimps->pcimplverts), maxnimplications));
414 
415  start = pcimps->pcimplstart;
416  verts = pcimps->pcimplverts;
417  pcimps->pcimplnppterms = nppterms;
418 
419  for( int i = 0; i < nnodes; i++ )
420  {
421  visited[i] = FALSE;
422  g->path_state[i] = UNKNOWN;
423  dist[i] = FARAWAY;
424  }
425 
426  graph_pc_termMarkProper(g, termmark);
427 
428  start[0] = 0;
429  nspares = 0;
430  termscount = 0;
431  nimplications = 0;
432 
433  /* main loop: initialize implication lists */
434  for( int i = 0; i < nnodes; i++ )
435  {
436  int nvisits;
437  int nadded;
438 
439  if( !Is_term(g->term[i]) || graph_pc_knotIsFixedTerm(g, i) || graph_pc_termIsNonLeafTerm(g, i) )
440  continue;
441 
442  assert(i != g->source);
443  assert(g->path_heap && g->path_state);
444 
445  (void) graph_sdWalksConnected(scip, g, termmark, g->cost, NULL, i, 1000, dist, visitlist, &nvisits, visited, TRUE);
446 
447  assert(nvisits >= 1 && visitlist[0] == i);
448  assert(nspares >= 0);
449 
450  for( int j = 1; j < MIN(nvisits, slotsize + nspares + 1); j++ )
451  {
452  const int vert = visitlist[j];
453  assert(nimplications < maxnimplications);
454 
455  verts[nimplications++] = vert;
456  }
457 
458  nadded = nimplications - start[termscount];
459  assert(nadded >= 0);
460 
461  if( nadded > slotsize )
462  nspares -= nadded - slotsize;
463  else
464  nspares += slotsize - nadded;
465 
466  assert(termscount < nppterms);
467  start[++termscount] = nimplications;
468  }
469  assert(termscount == nppterms);
470 
471 #ifndef WITH_UG
472  printf("number of implications %d \n", nimplications);
473 #endif
474 
475  SCIPfreeBufferArray(scip, &termmark);
476  SCIPfreeBufferArray(scip, &visitlist);
477  SCIPfreeBufferArray(scip, &visited);
478  SCIPfreeBufferArray(scip, &dist);
479 
480  return SCIP_OKAY;
481 }
482 
483 
484 /** frees (R)PC implications */
486  SCIP* scip, /**< SCIP data structure */
487  PCIMPLICATION** pcimplications /**< implication data */
488 )
489 {
490  SCIPfreeMemoryArrayNull(scip, &((*pcimplications)->pcimplstart));
491  SCIPfreeMemoryArrayNull(scip, &((*pcimplications)->pcimplverts));
492 
493  SCIPfreeMemoryArray(scip, pcimplications);
494 }
495 
496 
497 /** separates PCSPG/MWCS implications */
499  SCIP* scip, /**< SCIP data structure */
500  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
501  PCIMPLICATION* pcimplications, /**< implications */
502  int maxcuts, /**< maximal number of cuts */
503  int* ncuts /**< pointer to store number of cuts */
504  )
505 {
506  GRAPH* g = SCIPprobdataGetGraph2(scip);
507  SCIP_Real* nodeinflow;
508  SCIP_VAR** vars = SCIPprobdataGetVars(scip);
509  SCIP_ROW* row = NULL;
510  const SCIP_Real* xval = SCIPprobdataGetXval(scip, NULL);
511  const int* verts;
512  const int* start;
513  const int nnodes = g->knots;
514  int cutscount;
515  int ptermcount;
516 
517  assert(scip != NULL);
518  assert(conshdlr != NULL);
519  assert(pcimplications != NULL);
520  assert(g != NULL);
521  assert(xval != NULL);
522 
523  /* nothing to separate? */
524  if( pcimplications->pcimplnppterms == 0 )
525  {
526  assert(graph_pc_nNonFixedTerms(g) == 0);
527  return SCIP_OKAY;
528  }
529 
530  assert(graph_pc_nNonFixedTerms(g) > 0);
531 
532  assert(pcimplications );
533  verts = pcimplications->pcimplverts;
534  start = pcimplications->pcimplstart;
535  assert(verts && start);
536 
537  SCIP_CALL( SCIPallocBufferArray(scip, &nodeinflow, nnodes) );
538 
539  /* initialize node sums */
540  for( int i = 0; i < nnodes; i++ )
541  nodeinflow[i] = get_inflow(g, xval, i);
542 
543  cutscount = 0;
544  ptermcount = 0;
545 
546  assert(g->extended);
547 
548  /* main separation loop */
549  for( int i = 0; i < nnodes; i++ )
550  {
551  int maxnode;
553  const SCIP_Real inflow = nodeinflow[i];
554 
555  if( !Is_pseudoTerm(g->term[i]) )
556  continue;
557 
558  ptermcount++;
559 
560  if( SCIPisFeasGE(scip, inflow, 1.0) )
561  continue;
562 
563  maxnode = -1;
564  maxflow = 0.0;
565  for( int j = start[ptermcount - 1]; j < start[ptermcount]; j++ )
566  {
567  const int vert = verts[j];
568  if( SCIPisFeasGT(scip, nodeinflow[vert], inflow) && nodeinflow[vert] > maxflow )
569  {
570  maxnode = vert;
571  maxflow = nodeinflow[vert];
572  }
573  }
574 
575  /* separate? */
576  if( maxnode >= 0 )
577  {
578 #ifdef XXX_XXX
579  SCIP_CALL(SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "pcimplicate", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE));
580  SCIP_CALL(SCIPcacheRowExtensions(scip, row));
581 
582  for( int e = g->inpbeg[maxnode]; e != EAT_LAST; e = g->ieat[e] )
583  SCIP_CALL(SCIPaddVarToRow(scip, row, vars[e], 1.0));
584 
585  for( int e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
586  SCIP_CALL(SCIPaddVarToRow(scip, row, vars[e], -1.0));
587 #else
588  {
589  const int twinterm = graph_pc_getTwinTerm(g, i);
590  const int rootedge = graph_pc_getRoot2PtermEdge(g, twinterm);
591  assert(rootedge >= 0);
592 
593  SCIP_CALL(SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "pcimplicate", -SCIPinfinity(scip), 1.0, FALSE, FALSE, TRUE));
594  SCIP_CALL(SCIPcacheRowExtensions(scip, row));
595 
596  for( int e = g->inpbeg[maxnode]; e != EAT_LAST; e = g->ieat[e] )
597  SCIP_CALL(SCIPaddVarToRow(scip, row, vars[e], 1.0));
598 
599  SCIP_CALL(SCIPaddVarToRow(scip, row, vars[rootedge], 1.0));
600  }
601 #endif
602 
603  SCIP_CALL(SCIPflushRowExtensions(scip, row));
604 
605  if( SCIPisCutEfficacious(scip, NULL, row) )
606  {
607  SCIP_Bool infeasible;
608  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
609 #if ADDCUTSTOPOOL
610  /* add cut to pool */
611  if( !infeasible )
612  SCIP_CALL( SCIPaddPoolCut(scip, row) );
613 #endif
614 
615  if( *ncuts + cutscount++ >= maxcuts )
616  {
617  SCIP_CALL( SCIPreleaseRow(scip, &row) );
618  break;
619  }
620  }
621 
622  SCIP_CALL( SCIPreleaseRow(scip, &row) );
623  }
624  }
625  assert((*ncuts + cutscount > maxcuts) || ptermcount == graph_pc_nProperPotentialTerms(g));
626 
627  *ncuts += cutscount;
628  SCIPdebugMessage("PcImplication Separator: %d Inequalities added\n", cutscount);
629 
630  SCIPfreeBufferArray(scip, &nodeinflow);
631 
632  return SCIP_OKAY;
633 }
634 
635 /** return number of proper potential terminals */
637  const PCIMPLICATION* pcimp /**< implications */
638  )
639 {
640  assert(pcimp);
641 
642  return pcimp->pcimplnppterms;
643 }
644 
645 
646 /** return CSR like starts */
648  const PCIMPLICATION* pcimp /**< implications */
649  )
650 {
651  assert(pcimp);
652 
653  return pcimp->pcimplstart;
654 }
655 
656 
657 /** return CSR like vertices */
659  const PCIMPLICATION* pcimp /**< implications */
660  )
661 {
662  assert(pcimp);
663 
664  return pcimp->pcimplverts;
665 }
666 
667 
668 /** initializes implications */
670  SCIP* scip, /**< SCIP data structure */
671  const GRAPH* g, /**< graph data structure */
672  VTIMPLICATION** vtimplications /**< implication data */
673 )
674 {
675  VTIMPLICATION* vtimps;
676  const int nnodes = graph_get_nNodes(g);
677 
678  assert(scip);
679 
680  SCIP_CALL( SCIPallocMemory(scip, vtimplications) );
681  vtimps = *vtimplications;
682  vtimps->impverts = NULL;
683  vtimps->imparcs = NULL;
684 
685  // todo reactivate if it works well
686  if( !graph_typeIsSpgLike(g) )
687  {
688  return SCIP_OKAY;
689  }
690 
691  for( int i = 0; i < nnodes; i++ )
692  {
693  if( Is_term(g->term[i]) )
694  {
695  SCIP_Real min = FARAWAY;
696  int minedge = -1;
697 
698  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
699  {
700  if( GE(g->cost[e], BLOCKED) )
701  {
702  minedge = -2;
703  break;
704  }
705 
706  if( LT(g->cost[e], min) )
707  {
708  min = g->cost[e];
709  minedge = e;
710  }
711  }
712 
713  assert(minedge != -1);
714 
715  if( minedge == -2 )
716  continue;
717 
718  assert(!Is_term(g->term[g->head[minedge]]));
719 
720  StpVecPushBack(scip, vtimps->impverts, g->head[minedge]);
721  StpVecPushBack(scip, vtimps->imparcs, flipedge(minedge));
722  }
723  }
724 
725  return SCIP_OKAY;
726 }
727 
728 
729 /** frees implications */
731  SCIP* scip, /**< SCIP data structure */
732  VTIMPLICATION** vtimplications /**< implication data */
733 )
734 {
735  StpVecFree(scip, (*vtimplications)->imparcs);
736  StpVecFree(scip, (*vtimplications)->impverts);
737 
738  SCIPfreeMemoryArray(scip, vtimplications);
739 }
740 
741 
742 /** separates implications */
744  SCIP* scip, /**< SCIP data structure */
745  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
746  VTIMPLICATION* vtimplications, /**< implication data */
747  int maxcuts, /**< maximal number of cuts */
748  int* ncuts /**< pointer to store number of cuts */
749  )
750 {
751  GRAPH* g = SCIPprobdataGetGraph2(scip);
752  SCIP_VAR** vars = SCIPprobdataGetVars(scip);
753  const SCIP_Real* xval = SCIPprobdataGetXval(scip, NULL);
754  int cutscount = 0;
755  int nimplications;
756 
757  assert(scip && conshdlr && vtimplications && ncuts);
758  assert(maxcuts > 0);
759  assert(StpVecGetSize(vtimplications->imparcs) == StpVecGetSize(vtimplications->impverts));
760 
761  nimplications = StpVecGetSize(vtimplications->imparcs);
762 
763  /* nothing to separate? */
764  if( nimplications == 0)
765  {
766  return SCIP_OKAY;
767  }
768 
769  for( int i = 0; i < nimplications; i++ )
770  {
771  const int impvert = vtimplications->impverts[i];
772  const int imparc = vtimplications->imparcs[i];
773  const int imparc_rev = flipedge(imparc);
774  const SCIP_Real inflow = get_inflow(g, xval, impvert);
775 
776  assert(graph_edge_isInRange(g, imparc));
777  assert(g->tail[imparc] == impvert);
778 
779  if( SCIPisFeasLT(scip, xval[imparc] + xval[imparc_rev], inflow) )
780  {
781  SCIP_ROW* row = NULL;
782 
783  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "vtimplicate", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
784  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
785 
786  printf("found implication cut: %f < %f \n", xval[imparc] + xval[imparc_rev], inflow);
787 
788  for( int e = g->inpbeg[impvert]; e != EAT_LAST; e = g->ieat[e] )
789  {
790  if( e != imparc_rev )
791  {
792  SCIP_CALL(SCIPaddVarToRow(scip, row, vars[e], 1.0));
793  }
794  assert(e != imparc);
795  }
796 
797  SCIP_CALL(SCIPaddVarToRow(scip, row, vars[imparc], -1.0));
798  SCIP_CALL(SCIPflushRowExtensions(scip, row));
799 
800  if( SCIPisCutEfficacious(scip, NULL, row) )
801  {
802  SCIP_Bool infeasible;
803  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
804  printf("...added implication cut! \n");
805 
806 #if ADDCUTSTOPOOL
807  /* add cut to pool */
808  if( !infeasible )
809  SCIP_CALL( SCIPaddPoolCut(scip, row) );
810 #endif
811 
812  if( *ncuts + cutscount++ >= maxcuts )
813  {
814  SCIP_CALL( SCIPreleaseRow(scip, &row) );
815  break;
816  }
817  }
818 
819  SCIP_CALL( SCIPreleaseRow(scip, &row) );
820  }
821  }
822 
823  *ncuts += cutscount;
824  SCIPdebugMessage("Vertex-Terminal Implication Separator: %d Inequalities added\n", cutscount);
825 
826  return SCIP_OKAY;
827 }
#define STP_Vectype(type)
Definition: stpvector.h:44
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
int graph_edge_nPseudoAncestors(const GRAPH *, int)
#define StpVecGetSize(vec)
Definition: stpvector.h:139
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1626
int *RESTRICT head
Definition: graphdefs.h:224
void sepaspecial_pacliquesFree(SCIP *scip, PACLIQUES **pacliques)
Definition: sepaspecial.c:207
SCIP_Bool graph_sdWalksConnected(SCIP *, const GRAPH *, const int *, const SCIP_Real *, const STP_Bool *, int, int, SCIP_Real *, int *, int *, STP_Bool *, SCIP_Bool)
Separator for Steiner tree problem contraints beyond flow-balance-directed-cut constraints.
int source
Definition: graphdefs.h:195
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
const int * sepaspecial_pcimplicationsGetStarts(const PCIMPLICATION *pcimp)
Definition: sepaspecial.c:647
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1649
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
void graph_pc_termMarkProper(const GRAPH *, int *)
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
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_Real * ancestors_lpweights
Definition: sepaspecial.c:44
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE sepaspecial_vtimplicationsInit(SCIP *scip, const GRAPH *g, VTIMPLICATION **vtimplications)
Definition: sepaspecial.c:669
#define FALSE
Definition: def.h:87
int *RESTRICT inpbeg
Definition: graphdefs.h:202
int *RESTRICT path_state
Definition: graphdefs.h:256
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
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
static SCIP_Real get_inflow(const GRAPH *g, const SCIP_Real *xval, int vert)
Definition: sepaspecial.c:76
#define FARAWAY
Definition: graphdefs.h:89
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
header only, simple implementation of an STL like vector
SCIP_Bool graph_pc_termIsNonLeafTerm(const GRAPH *, int)
static SCIP_RETCODE pacliquesBuildMap(SCIP *scip, const GRAPH *g, PACLIQUES *pacliques)
Definition: sepaspecial.c:94
int *RESTRICT oeat
Definition: graphdefs.h:231
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:108
int graph_pc_getRoot2PtermEdge(const GRAPH *, int)
#define GE(a, b)
Definition: portab.h:85
SCIP_Bool extended
Definition: graphdefs.h:267
SCIP_RETCODE sepaspecial_pcimplicationsInit(SCIP *scip, const GRAPH *g, PCIMPLICATION **pcimplications)
Definition: sepaspecial.c:371
#define NULL
Definition: lpi_spx1.cpp:155
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 LT(a, b)
Definition: portab.h:81
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
static double maxflow(GRAPH *gr, GRAPHNODE *s_ptr, GRAPHNODE *t_ptr)
unsigned char STP_Bool
Definition: portab.h:34
propagator for Steiner tree problems, using the LP reduced costs
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT ieat
Definition: graphdefs.h:230
int *RESTRICT path_heap
Definition: graphdefs.h:255
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
#define flipedge(edge)
Definition: graphdefs.h:84
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:352
const int * sepaspecial_pcimplicationsGetVerts(const PCIMPLICATION *pcimp)
Definition: sepaspecial.c:658
int graph_pc_nProperPotentialTerms(const GRAPH *)
const int * graph_edge_getPseudoAncestors(const GRAPH *, int)
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
#define PCIMPLICATIONS_ALLOC_FACTOR
Definition: sepaspecial.c:38
Constraint handler for linear constraints in their most general form, .
int sepaspecial_pcimplicationsGetNstarts(const PCIMPLICATION *pcimp)
Definition: sepaspecial.c:636
Portable definitions.
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
#define SCIP_Real
Definition: def.h:177
void sepaspecial_vtimplicationsFree(SCIP *scip, VTIMPLICATION **vtimplications)
Definition: sepaspecial.c:730
#define BLOCKED
Definition: graphdefs.h:90
#define StpVecFree(scip, vec)
Definition: stpvector.h:149
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
int *RESTRICT outbeg
Definition: graphdefs.h:204
int edges
Definition: graphdefs.h:219
int graph_getNpseudoAncestors(const GRAPH *)
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
int graph_pc_nNonFixedTerms(const GRAPH *)
#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
#define UNKNOWN
Definition: sepa_mcf.c:4095
#define nnodes
Definition: gastrans.c:65
#define StpVecPushBack(scip, vec, value)
Definition: stpvector.h:163
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
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
GRAPH * SCIPprobdataGetGraph2(SCIP *scip)
int graph_pc_getTwinTerm(const GRAPH *, int)
SCIP_RETCODE sepaspecial_pacliquesInit(SCIP *scip, const GRAPH *g, PACLIQUES **pacliques)
Definition: sepaspecial.c:165