Scippy

SCIP

Solving Constraint Integer Programs

validate.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-2019 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 validate.c
17  * @brief Method to validate Steiner problem solutions
18  * @author Thorsten Koch
19  * @author Gerald Gamrath
20  * @author Daniel Rehfeldt
21  *
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include <math.h>
30 #include <assert.h>
31 #include "grph.h"
32 #include "portab.h"
33 
34 #if 0
35 static void show(
36  GRAPH* g,
37  int vars,
38  STP_Bool* state,
39  double* xval)
40 {
41  int i;
42  for(i = 0; i < vars; i++)
43  {
44  if (xval[i] > 1e-6)
45  {
46  fprintf(stderr, "%d-%d, xval[%d]=%g (%d)\n",
47  g->tail[i % g->edges] + 1,
48  g->head[i % g->edges] + 1,
49  i,
50  xval[i],
51  state[i]);
52  }
53  }
54 }
55 #endif
56 
57 static int nail(
58  const GRAPH* g,
59  const double* xval)
60 {
61  double sum;
62  int i;
63  int l;
64  int ind;
65 
66  assert(g != NULL);
67  assert(xval != NULL);
68 
69  if (g->layers == 1)
70  return(TRUE);
71 
72  for(i = 0; i < g->edges; i += 2)
73  {
74  sum = 0.0;
75 
76  for(l = 0; l < g->layers; l++)
77  {
78  ind = l * g->edges + i;
79  sum += xval[ind] + xval[ind + 1];
80  }
81  assert(sum >= -EPSILON);
82 
83 #ifdef WITH_CAPACITIES
84  assert(g->capa[i] > 0);
85 
86  if (sum - EPSILON > (double)g->capa[i])
87  return(FALSE);
88 #else
89  if (sum - EPSILON > 1.0)
90  return(FALSE);
91 #endif
92  }
93  return(TRUE);
94 }
95 #if 1
96 /*---------------------------------------------------------------------------*/
97 /*--- Name : Trail ---*/
98 /*--- Function : Durchlaeuft einen Graphen entsprechend einer Loesung und ---*/
99 /*--- stellt fest ob er bei allen Knoten vorbeikommt ---*/
100 /*--- Parameter: Startknoten, Loesung, Herkunft, Schongewesenliste ---*/
101 /*--- Returns : Nichts ---*/
102 /*---------------------------------------------------------------------------*/
103 static void trail(
104  const GRAPH* g,
105  int i,
106  const double* xval,
107  int tail,
108  int* connected,
109  int hop,
110  int max_hops)
111 {
112  int k;
113 
114  if( connected[i] < 2 )
115  {
116  ++(connected[i]);
117 
118  if ((connected[i] < 2) && (hop < max_hops))
119  {
120  for(k = g->outbeg[i]; k != EAT_LAST; k = g->oeat[k])
121  if ((g->head[k] != tail) && (xval[k] + EPSILON > 1.0))
122  trail(g, g->head[k], xval, i, connected, hop + 1, max_hops);
123  }
124  }
125 }
126 #endif
127 
128 /*---------------------------------------------------------------------------*/
129 /*--- Name : Validate Solution ---*/
130 /*--- Function : Stellt fuer eine (Teil-)Loesung fest, ob sie zulaessig ---*/
131 /*--- unzulaessig oder schon eine vollstaendige Loesung ist ---*/
132 /*--- Parameter: Graph, Loesung. ---*/
133 /*--- Returns : TRUE / FALSE ---*/
134 /*---------------------------------------------------------------------------*/
135 /** validates whether a (LP) solution is feasible */
137  SCIP* scip,
138  const GRAPH* g,
139  const double* xval,
140  SCIP_Bool* feasible
141  )
142 {
143  int* connected;
144  int ret = TRUE;
145  int i;
146  int layer;
147  int deg;
148  int e;
149  assert(g != NULL);
150 
151  if( g->knots == 1 )
152  {
153  *feasible = TRUE;
154  return SCIP_OKAY;
155  }
156 
157  assert(xval != NULL);
158 
159  SCIP_CALL( SCIPallocClearBufferArray(scip, &connected, g->knots) );
160 
161  *feasible = FALSE;
162  for(layer = 0; ret && (layer < g->layers); layer++)
163  {
164  trail(g, g->source, xval + layer * g->edges, -1,
165  connected,
166  0, 1000000000);
167 
168  for(i = 0; i < g->knots; i++)
169  {
170  if( g->stp_type == STP_DCSTP )
171  {
172  deg = 0;
173  for( e = g->outbeg[i]; e != EAT_LAST ; e = g->oeat[e] )
174  if( EQ(xval[e], 1.0) || EQ(xval[flipedge(e)], 1.0) )
175  deg++;
176 
177  if( deg > g->maxdeg[i] )
178  {
179  ret = FALSE;
180  SCIPdebugMessage("deg condition violated \n");
181  break;
182  }
183 
184  }
185  /* circle? */
186  if( connected[i] >= 2)
187  {
188  ret = FALSE;
189  break;
190  }
191 
192  /* vertex not reached? */
193  if ((g->grad[i] > 0) && (g->term[i] == layer) && !connected[i])
194  {
195  ret = FALSE;
196  break;
197  }
198  }
199  }
200  SCIPfreeBufferArray(scip, &connected);
201 
202  if( ret )
203  ret = nail(g, xval);
204 
205  /* SCIP-Heuristiken können (z.B. durch Runden) Lösungen konstruieren, die einen Kreis aus Steiner-Knoten enthalten, der
206  * nicht zum Baum gehört
207  */
208 #if 0
209 #ifndef NDEBUG
210  /* Test ob alle Kanten nur in eine Richtung benutzt werden.
211  */
212  if (ret)
213  {
214  int e;
215 
216  for(e = 0; e < g->edges; e += 2)
217  if ((xval[e] > EPSILON) && (xval[e + 1] > EPSILON))
218  /* CONSTCOND */
219  assert(FALSE);
220  }
221 #endif
222 #endif
223  *feasible = (SCIP_Bool) ret;
224  return SCIP_OKAY;
225 }
#define NULL
Definition: def.h:246
int *RESTRICT head
Definition: grph.h:96
Definition: grph.h:57
int source
Definition: grph.h:67
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:132
int *RESTRICT maxdeg
Definition: grph.h:78
#define EAT_LAST
Definition: grph.h:31
#define FALSE
Definition: def.h:72
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPdebugMessage
Definition: pub_message.h:77
static int nail(const GRAPH *g, const double *xval)
Definition: validate.c:57
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
int *RESTRICT oeat
Definition: grph.h:103
int stp_type
Definition: grph.h:127
SCIP_RETCODE SCIPStpValidateSol(SCIP *scip, const GRAPH *g, const double *xval, SCIP_Bool *feasible)
Definition: validate.c:136
unsigned char STP_Bool
Definition: grph.h:52
#define STP_DCSTP
Definition: grph.h:43
static void trail(const GRAPH *g, int i, const double *xval, int tail, int *connected, int hop, int max_hops)
Definition: validate.c:103
int *RESTRICT grad
Definition: grph.h:73
#define EPSILON
Definition: portab.h:31
#define EQ(a, b)
Definition: portab.h:62
int knots
Definition: grph.h:62
#define SCIP_CALL(x)
Definition: def.h:358
#define SCIP_Bool
Definition: def.h:69
int *RESTRICT tail
Definition: grph.h:95
int *RESTRICT term
Definition: grph.h:68
includes various files containing graph methods used for Steiner tree problems
Portable defintions.
int layers
Definition: grph.h:65
int *RESTRICT outbeg
Definition: grph.h:76
int edges
Definition: grph.h:92
#define flipedge(edge)
Definition: grph.h:150