Scippy

SCIP

Solving Constraint Integer Programs

solpool.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 solpool.c
17  * @brief includes solution pool for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file contains several basic methods for a Steiner tree solution pool.
21  *
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 /*lint -esym(766,stdlib.h) -esym(766,malloc.h) */
27 /*lint -esym(766,string.h) */
28 //#define SCIP_DEBUG
29 
30 #include "solpool.h"
31 #include "probdata_stp.h"
32 
33 
34 /** is given solution in pool? */
36  const int* soledges, /**< edge array of solution to be checked */
37  const STPSOLPOOL* pool /**< the pool */
38 )
39 {
40  STPSOL** poolsols = pool->sols;
41  const int poolsize = pool->size;
42  const int nedges = pool->nedges;
43 
44  for( int i = 0; i < poolsize; i++ )
45  {
46  int j;
47  const int* pooledges = poolsols[i]->soledges;
48  assert(pooledges != NULL);
49 
50  for( j = 0; j < nedges; j++ )
51  if( pooledges[j] != soledges[j] )
52  break;
53 
54  /* pooledges == soledges? */
55  if( j == nedges )
56  {
57  SCIPdebugMessage("Pool: solution is already contained \n");
58  return TRUE;
59  }
60  }
61  return FALSE;
62 }
63 
64 
65 /** get solution from index */
67  STPSOLPOOL* pool, /**< the pool */
68  const int soindex /**< the index */
69 )
70 {
71  int i;
72  int size;
73 
74  assert(pool != NULL);
75  assert(soindex >= 0 && soindex <= pool->maxindex);
76 
77  size = pool->size;
78 
79  for( i = 0; i < size; i++ )
80  if( pool->sols[i]->index == soindex )
81  break;
82 
83  if( i == size )
84  return NULL;
85  else
86  return pool->sols[i];
87 }
88 
89 
90 /** initializes STPSOL pool */
92  SCIP* scip, /**< SCIP data structure */
93  STPSOLPOOL** pool, /**< the pool */
94  const int nedges, /**< number of edges of solutions to be stored in the pool */
95  const int maxsize /**< capacity of pool */
96 )
97 {
98  STPSOLPOOL* dpool;
99 
100  assert(pool != NULL);
101  assert(nedges > 0);
102  assert(maxsize > 0);
103 
104  SCIP_CALL( SCIPallocBlockMemory(scip, pool) );
105 
106  dpool = *pool;
107  SCIP_CALL( SCIPallocMemoryArray(scip, &(dpool->sols), maxsize) );
108 
109  for( int i = 0; i < maxsize; i++ )
110  dpool->sols[i] = NULL;
111 
112  dpool->size = 0;
113  dpool->nedges = nedges;
114  dpool->maxsize = maxsize;
115  dpool->maxindex = -1;
116 
117  return SCIP_OKAY;
118 }
119 
120 
121 /** frees STPSOL pool */
123  SCIP* scip, /**< SCIP data structure */
124  STPSOLPOOL** pool /**< the pool */
125  )
126 {
127  STPSOLPOOL* dpool = *pool;
128  const int poolsize = dpool->size;
129 
130  assert(pool != NULL);
131  assert(dpool != NULL);
132  assert(poolsize == dpool->maxsize || dpool->sols[poolsize] == NULL);
133 
134  for( int i = poolsize - 1; i >= 0; i-- )
135  {
136  STPSOL* sol = dpool->sols[i];
137 
138  assert(sol != NULL);
139 
140  SCIPfreeMemoryArray(scip, &(sol->soledges));
141  SCIPfreeBlockMemory(scip, &sol);
142  }
143 
144  SCIPfreeMemoryArray(scip, &(dpool->sols));
145  SCIPfreeBlockMemory(scip, pool);
146 }
147 
148 
149 /** tries to add sol to SCIP */
151  SCIP* scip, /**< SCIP data structure */
152  SCIP_HEUR* heur, /**< heuristic data structure or NULL */
153  const GRAPH* g, /**< graph data structure */
154  const int* result, /**< edge array of solution to be added */
155  SCIP_Bool* success /**< has solution been added? */
156  )
157 {
158  const int nedges = graph_get_nEdges(g);
159  const int nvars = SCIPprobdataGetNVars(scip);
160  SCIP_Real* nval;
161  SCIP_CALL( SCIPallocBufferArray(scip, &nval, nvars) );
162 
163  assert(result && success);
164 
165  for( int e = 0; e < nedges; e++ )
166  {
167  if( result[e] == CONNECT )
168  nval[e] = 1.0;
169  else
170  nval[e] = 0.0;
171  }
172 
173  SCIP_CALL( SCIPprobdataAddNewSol(scip, nval, heur, success) );
174  SCIPdebugMessage("Ascend-and-prune added solution \n");
175 
176  SCIPfreeBufferArray(scip, &nval);
177 
178  return SCIP_OKAY;
179 }
180 
181 
182 /** tries to add STPSOL to pool */
184  SCIP* scip, /**< SCIP data structure */
185  const SCIP_Real obj, /**< objective of solution to be added */
186  const int* soledges, /**< edge array of solution to be added */
187  STPSOLPOOL* pool, /**< the pool */
188  SCIP_Bool* success /**< has solution been added? */
189  )
190 {
191  STPSOL** poolsols = pool->sols;
192  STPSOL* sol;
193  int i;
194  int poolsize = pool->size;
195  const int nedges = pool->nedges;
196  const int poolmaxsize = pool->maxsize;
197 
198  assert(scip != NULL);
199  assert(pool != NULL);
200  assert(poolsols != NULL);
201  assert(poolsize >= 0);
202  assert(poolmaxsize >= 0);
203  assert(poolsize <= poolmaxsize);
204 
205  *success = FALSE;
206 
207  /* is solution in pool? */
208  if( solpool_isContained(soledges, pool) )
209  return SCIP_OKAY;
210 
211  SCIPdebugMessage("Pool: add to pool (current size: %d, max: %d) \n", poolsize, poolmaxsize);
212 
213  /* enlarge pool if possible */
214  if( poolsize < poolmaxsize )
215  {
216  SCIPdebugMessage("Pool: alloc memory at position %d \n", poolsize);
217 
218  SCIP_CALL( SCIPallocBlockMemory(scip, &(poolsols[poolsize])) );
219  SCIP_CALL( SCIPallocMemoryArray(scip, &(poolsols[poolsize]->soledges), nedges) );
220 
221  poolsize++;
222  pool->size++;
223  }
224  /* pool is full; new solution worse than worst solution in pool? */
225  else if( SCIPisGT(scip, obj, poolsols[poolsize - 1]->obj) )
226  {
227  return SCIP_OKAY;
228  }
229 
230  /* overwrite last element of pool (either empty or inferior to current solution) */
231  sol = poolsols[poolsize - 1];
232  assert(sol != NULL);
233  sol->obj = obj;
234  sol->index = ++(pool->maxindex);
235  BMScopyMemoryArray(sol->soledges, soledges, nedges);
236 
237  /* shift solution up */
238  for( i = poolsize - 1; i >= 1; i-- )
239  {
240  if( SCIPisGT(scip, obj, poolsols[i - 1]->obj) )
241  break;
242 
243  poolsols[i] = poolsols[i - 1];
244  }
245 
246  poolsols[i] = sol;
247  SCIPdebugMessage("Pool: put new solution to position %d \n", i);
248  *success = TRUE;
249 
250  return SCIP_OKAY;
251 }
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
STPSOL * solpool_solFromIndex(STPSOLPOOL *pool, const int soindex)
Definition: solpool.c:66
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
#define FALSE
Definition: def.h:87
Problem data for stp problem.
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
int index
Definition: solpool.h:42
int SCIPprobdataGetNVars(SCIP *scip)
SCIP_RETCODE solpool_init(SCIP *scip, STPSOLPOOL **pool, const int nedges, const int maxsize)
Definition: solpool.c:91
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define SCIPdebugMessage
Definition: pub_message.h:87
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void solpool_free(SCIP *scip, STPSOLPOOL **pool)
Definition: solpool.c:122
STPSOL ** sols
Definition: solpool.h:48
SCIP_RETCODE solpool_addSol(SCIP *scip, const SCIP_Real obj, const int *soledges, STPSOLPOOL *pool, SCIP_Bool *success)
Definition: solpool.c:183
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_HEUR *heur, SCIP_Bool *success)
SCIP_Bool solpool_isContained(const int *soledges, const STPSOLPOOL *pool)
Definition: solpool.c:35
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
includes solution pool for Steiner tree problems
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define SCIP_Bool
Definition: def.h:84
SCIP_Real obj
Definition: solpool.h:40
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
#define CONNECT
Definition: graphdefs.h:87
int * soledges
Definition: solpool.h:41
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_Real
Definition: def.h:177
SCIPallocBlockMemory(scip, subsol))
SCIP_RETCODE solpool_addSolToScip(SCIP *scip, SCIP_HEUR *heur, const GRAPH *g, const int *result, SCIP_Bool *success)
Definition: solpool.c:150