Scippy

SCIP

Solving Constraint Integer Programs

pricer_stp.c
Go to the documentation of this file.
1 
2 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
3 /* */
4 /* This file is part of the program and library */
5 /* SCIP --- Solving Constraint Integer Programs */
6 /* */
7 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
8 /* fuer Informationstechnik Berlin */
9 /* */
10 /* SCIP is distributed under the terms of the ZIB Academic License. */
11 /* */
12 /* You should have received a copy of the ZIB Academic License */
13 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
14 /* */
15 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
16 
17 /**@file pricer_stp.c
18  * @brief stp variable pricer
19  * @author Daniel Rehfeldt
20  */
21 
22 #include <assert.h>
23 #include <string.h>
24 #include "scip/cons_linear.h"
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include "pricer_stp.h"
28 #include "grph.h"
29 
30 
31 #define PRICER_NAME "stp"
32 #define PRICER_DESC "pricer for stp"
33 #define PRICER_PRIORITY 1
34 #define PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */
35 
36 /*
37  * Data structures
38  */
39 
40 
41 /** variable pricer data */
42 struct SCIP_PricerData
43 {
44  SCIP* scip; /**< SCIP data structure */
45  SCIP_CONS** edgecons; /**< array containing all edge constraints */
46  SCIP_CONS** pathcons; /**< array containing all path constraints */
47  SCIP_Real* pi; /**< array of the dual solutions to the edge constraints*/
48  SCIP_Real* mi; /**< array of the dual solutions to the path constraint*/
49  SCIP_Real lowerbound; /**< lower bound computed by the pricer */
50  int* realterms; /**< array of all terminals except the root */
51  int* ncreatedvars; /**< array (1,...,realnterms); in ncreatedvars[t] the number of
52  created variables (during pricing) pertaining to terminal t is stored */
53  int root; /**< root node */
54  int nedges; /**< number of edges */
55  int realnterms; /**< number of terminals except the root */
56  SCIP_Bool bigt; /**< stores whether the 'T' model is being used */
57 };
58 
59 
60 /*
61  * Local methods
62  */
63 
64 
65 /*
66  * Callback methods of variable pricer
67  */
68 
69 /** copy method for pricer plugins (called when SCIP copies plugins) */
70 static
71 SCIP_DECL_PRICERCOPY(pricerCopyStp)
72 { /*lint --e{715}*/
73  SCIPdebugPrintf("pricerCopy \n");
74  assert(pricer != NULL);
75  assert(strcmp(SCIPpricerGetName(pricer), PRICER_NAME) == 0);
76 
77  return SCIP_OKAY;
78 }
79 
80 /** destructor of variable pricer to free user data (called when SCIP is exiting) */
81 /**! [SnippetPricerFreeSTP] */
82 static
83 SCIP_DECL_PRICERFREE(pricerFreeStp)
84 {
85  SCIP_PRICERDATA* pricerdata;
86  SCIPdebugPrintf("pricerfree \n");
87  assert(scip != NULL);
88 
89  /* get pricerdata */
90  pricerdata = SCIPpricerGetData(pricer);
91 
92  /* free memory for pricerdata*/
93  if ( pricerdata != NULL )
94  {
95  SCIPfreeMemory(scip, &pricerdata);
96  }
97 
98  SCIPpricerSetData(pricer, NULL);
99 
100  return SCIP_OKAY;
101 }
102 /**! [SnippetPricerFreeSTP] */
103 
104 /** initialization method of variable pricer (called after problem was transformed) */
105 static
106 SCIP_DECL_PRICERINIT(pricerInitStp)
107 {
108  SCIP_PRICERDATA* pricerdata;
109  SCIPdebugPrintf("pricer Init \n");
110  assert(scip != NULL);
111  assert(pricer != NULL);
112 
113  pricerdata = SCIPpricerGetData(pricer);
114  pricerdata->edgecons = SCIPprobdataGetEdgeConstraints(scip);
115  pricerdata->pathcons = SCIPprobdataGetPathConstraints(scip);
116  pricerdata->root = SCIPprobdataGetRoot(scip);
117  pricerdata->nedges = SCIPprobdataGetNEdges(scip);
118  pricerdata->realnterms = SCIPprobdataGetRNTerms(scip);
119  pricerdata->realterms = SCIPprobdataGetRTerms(scip);
120  pricerdata->bigt = SCIPprobdataIsBigt(scip);
121  pricerdata->lowerbound = 0;
122  return SCIP_OKAY;
123 }
124 
125 /** solving process initialization method of variable pricer (called when branch and bound process is about to begin) */
126 static
127 SCIP_DECL_PRICERINITSOL(pricerInitsolStp)
128 {
129  SCIP_PRICERDATA* pricerdata;
130  SCIPdebugPrintf("pricerinitsol \n");
131  assert(scip != NULL);
132  assert(pricer != NULL);
133 
134  pricerdata = SCIPpricerGetData(pricer);
135  assert(pricerdata != NULL);
136 
137  /* allocate memory */
138  if( !pricerdata->bigt )
139  {
141  }
142  else
143  {
145  }
146 
148  SCIP_CALL( SCIPallocMemoryArray(scip, &pricerdata->ncreatedvars, SCIPprobdataGetRNTerms(scip)) );
149  BMSclearMemoryArray(pricerdata->ncreatedvars, SCIPprobdataGetRNTerms(scip));
150 
151  return SCIP_OKAY;
152 }
153 
154 /** solving process deinitialization method of variable pricer (called before branch and bound process data is freed) */
155 static
156 SCIP_DECL_PRICEREXITSOL(pricerExitsolStp)
157 {
158  SCIP_PRICERDATA* pricerdata;
159 
160  assert(scip != NULL);
161  assert(pricer != NULL);
162 
163  pricerdata = SCIPpricerGetData(pricer);
164  assert(pricerdata != NULL);
165 
166  /* free memory */
167  SCIPfreeMemoryArray(scip, &(pricerdata->mi));
168  SCIPfreeMemoryArray(scip, &(pricerdata->pi));
169  SCIPfreeMemoryArray(scip, &pricerdata->ncreatedvars);
170 
171  return SCIP_OKAY;
172 }
173 
174 /** method for either Farkas or Redcost pricing */
175 static
177  SCIP* scip, /**< SCIP data structure */
178  SCIP_PRICER* pricer, /**< pricer */
179  SCIP_Real* lowerbound, /**< lowerbound pointer */
180  SCIP_Bool farkas /**< TRUE: Farkas pricing; FALSE: Redcost pricing */
181  )
182 {
183  SCIP_PRICERDATA* pricerdata; /* the data of the pricer */
184  SCIP_PROBDATA* probdata;
185  GRAPH* graph;
186  SCIP_VAR* var;
187  PATH* path;
188  SCIP_Real* edgecosts; /* edgecosts of the current subproblem */
189  char varname[SCIP_MAXSTRLEN];
190  SCIP_Real newlowerbound = -SCIPinfinity(scip);
191  SCIP_Real redcost; /* reduced cost */
192  int tail;
193  int e;
194  int t;
195  int i;
196 
197  assert(scip != NULL);
198  assert(pricer != NULL);
199 
200  /* get pricer data */
201  pricerdata = SCIPpricerGetData(pricer);
202  assert(pricerdata != NULL);
203 
204  /* get problem data */
205  probdata = SCIPgetProbData(scip);
206  assert(probdata != NULL);
207 
208  SCIPdebugMessage("solstat=%d\n", SCIPgetLPSolstat(scip));
209 
210  if( !farkas && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
211  newlowerbound = SCIPgetSolTransObj(scip, NULL);
212 
214 
215 # if 0
216  if ( pricerdata->lowerbound <= 4 )
217  {
218  char label[SCIP_MAXSTRLEN];
219  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "X%g.gml", pricerdata->lowerbound);
220  SCIP_CALL( SCIPprobdataPrintGraph(scip, label , NULL, TRUE) );
221  pricerdata->lowerbound++;
222  }
223 #endif
224  /* get the graph*/
225  graph = SCIPprobdataGetGraph(probdata);
226 
227  /* get dual solutions and save them in mi and pi */
228  for( t = 0; t < pricerdata->realnterms; ++t )
229  {
230  if( farkas )
231  {
232  pricerdata->mi[t] = SCIPgetDualfarkasLinear(scip, pricerdata->pathcons[t]);
233  }
234  else
235  {
236  pricerdata->mi[t] = SCIPgetDualsolLinear(scip, pricerdata->pathcons[t]);
237  assert(!SCIPisNegative(scip, pricerdata->mi[t]));
238  }
239  }
240 
241  for( e = 0; e < pricerdata->nedges; ++e )
242  {
243  if( !pricerdata->bigt )
244  {
245  for( t = 0; t < pricerdata->realnterms; ++t )
246  {
247  if( farkas )
248  {
249  pricerdata->pi[t * pricerdata->nedges + e] = SCIPgetDualfarkasLinear(
250  scip, pricerdata->edgecons[t * pricerdata->nedges + e]);
251  }
252  else
253  {
254  pricerdata->pi[t * pricerdata->nedges + e] = SCIPgetDualsolLinear(
255  scip, pricerdata->edgecons[t * pricerdata->nedges + e]);
256  }
257  }
258  }
259  else
260  {
261  if( farkas )
262  {
263  pricerdata->pi[e] = SCIPgetDualfarkasLinear(
264  scip, pricerdata->edgecons[e]);
265  }
266  else
267  {
268  pricerdata->pi[e] = SCIPgetDualsolLinear(
269  scip, pricerdata->edgecons[e]);
270  }
271  }
272  }
273 
274  SCIP_CALL( SCIPallocMemoryArray(scip, &path, graph->knots) );
275  SCIP_CALL( SCIPallocMemoryArray(scip, &edgecosts, pricerdata->nedges) );
276 
277  if( pricerdata->bigt )
278  {
279  for( e = 0; e < pricerdata->nedges; ++e )
280  {
281  edgecosts[e] = (-pricerdata->pi[e]);
282  }
283  }
284  /* find shortest r-t (r root, t terminal) paths and create corresponding variables iff reduced cost < 0 */
285  for( t = 0; t < pricerdata->realnterms; ++t )
286  {
287  for( e = 0; e < pricerdata->nedges; ++e )
288  {
289  if( !pricerdata->bigt )
290  {
291  edgecosts[e] = (-pricerdata->pi[t * pricerdata->nedges + e]);
292  }
293 
294  assert(!SCIPisNegative(scip, edgecosts[e]));
295  }
296 
297  for( i = 0; i < graph->knots; i++ )
298  graph->mark[i] = 1;
299 
300  graph_path_exec(scip, graph, FSP_MODE, pricerdata->root, edgecosts, path);
301 
302  /* compute reduced cost of shortest path to terminal t */
303  redcost = 0.0;
304  tail = pricerdata->realterms[t];
305  while( tail != pricerdata->root )
306  {
307  redcost += edgecosts[path[tail].edge];
308  tail = graph->tail[path[tail].edge];
309  }
310  redcost -= pricerdata->mi[t];
311 
312  if( !farkas && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
313  {
314  newlowerbound += redcost;
315  }
316  /* check if reduced cost < 0 */
317  if( SCIPisNegative(scip, redcost) )
318  {
319  /* create variable to the shortest path (having reduced cost < 0) */
320  var = NULL;
321  sprintf(varname, "PathVar%d_%d", t, pricerdata->ncreatedvars[t]);
322  ++(pricerdata->ncreatedvars[t]);
323 
324  SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
325  SCIP_CALL( SCIPaddPricedVar(scip, var, -redcost) );
326  tail = pricerdata->realterms[t];
327  while( tail != pricerdata->root )
328  {
329  /* add variable to constraints */
330  if( !pricerdata->bigt )
331  {
332  SCIP_CALL( SCIPaddCoefLinear(scip, pricerdata->edgecons[t * pricerdata->nedges + path[tail].edge], var, 1.0) );
333  }
334  else
335  {
336  SCIP_CALL( SCIPaddCoefLinear(scip, pricerdata->edgecons[path[tail].edge], var, 1.0) );
337  }
338 
339  tail = graph->tail[path[tail].edge];
340  }
341  SCIP_CALL( SCIPaddCoefLinear(scip, pricerdata->pathcons[t], var, 1.0) );
342  }
343  }
344 
345  if( !farkas && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
346  *lowerbound = newlowerbound;
347 
348  SCIPfreeMemoryArray(scip, &edgecosts);
349  SCIPfreeMemoryArray(scip, &path);
350 
351  return SCIP_OKAY;
352 }
353 
354 /** reduced cost pricing method of variable pricer for feasible LPs */
355 static
356 SCIP_DECL_PRICERREDCOST(pricerRedcostStp)
357 { /*lint --e{715}*/
358  SCIP_CALL( pricing(scip, pricer, lowerbound, FALSE) );
359 
360  /* set result pointer */
361  *result = SCIP_SUCCESS;
362  return SCIP_OKAY;
363 }
364 
365 /** Farkas pricing method of variable pricer for infeasible LPs */
366 static
367 SCIP_DECL_PRICERFARKAS(pricerFarkasStp)
368 { /*lint --e{715}*/
369  SCIP_CALL( pricing(scip, pricer, NULL, TRUE) );
370 
371  return SCIP_OKAY;
372 }
373 
374 /*
375  * variable pricer specific interface methods
376  */
377 
378 /** creates the stp variable pricer and includes it in SCIP */
380  SCIP* scip /**< SCIP data structure */
381  )
382 {
383 
384  SCIP_PRICERDATA* pricerdata;
385  SCIP_PRICER* pricer;
386  SCIPdebugPrintf("include Pricer \n");
387 
388  /* create stp variable pricer data */
389  SCIP_CALL( SCIPallocMemory(scip, &pricerdata) );
390  pricerdata->scip = scip;
391 
392  /* include variable pricer */
393  pricer = NULL;
395  pricerRedcostStp, pricerFarkasStp, pricerdata) );
396  assert(pricer != NULL);
397 
398  /* set non fundamental callbacks via setter functions */
399  SCIP_CALL( SCIPsetPricerCopy(scip, pricer, pricerCopyStp) );
400  SCIP_CALL( SCIPsetPricerFree(scip, pricer, pricerFreeStp) );
401  SCIP_CALL( SCIPsetPricerInit(scip, pricer, pricerInitStp) );
402  SCIP_CALL( SCIPsetPricerInitsol(scip, pricer, pricerInitsolStp) );
403  SCIP_CALL( SCIPsetPricerExitsol(scip, pricer, pricerExitsolStp) );
404 
405  return SCIP_OKAY;
406 }
stp variable pricer
SCIP_RETCODE SCIPsetPricerInit(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINIT((*pricerinit)))
Definition: scip_pricer.c:213
#define NULL
Definition: def.h:253
Definition: grph.h:57
SCIP_RETCODE SCIPincludePricerStp(SCIP *scip)
Definition: pricer_stp.c:379
SCIP_CONS ** SCIPprobdataGetEdgeConstraints(SCIP *scip)
#define PRICER_PRIORITY
Definition: pricer_stp.c:33
#define PRICER_DELAY
Definition: pricer_stp.c:34
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:69
signed int edge
Definition: grph.h:146
#define SCIP_MAXSTRLEN
Definition: def.h:274
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:53
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:184
SCIP_RETCODE SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERFREE((*pricerfree)))
Definition: scip_pricer.c:189
#define FALSE
Definition: def.h:73
int SCIPprobdataGetNEdges(SCIP *scip)
#define TRUE
Definition: def.h:72
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static SCIP_DECL_PRICEREXITSOL(pricerExitsolStp)
Definition: pricer_stp.c:156
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:963
#define SCIPdebugMessage
Definition: pub_message.h:77
static SCIP_DECL_PRICERFARKAS(pricerFarkasStp)
Definition: pricer_stp.c:367
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:158
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
Definition: scip_prob.c:1732
static SCIP_DECL_PRICERCOPY(pricerCopyStp)
Definition: pricer_stp.c:71
int *RESTRICT mark
Definition: grph.h:70
SCIP_RETCODE SCIPsetPricerCopy(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERCOPY((*pricercopy)))
Definition: scip_pricer.c:165
int * SCIPprobdataGetRTerms(SCIP *scip)
SCIP_CONS ** SCIPprobdataGetPathConstraints(SCIP *scip)
#define SCIPdebugPrintf
Definition: pub_message.h:80
int SCIPprobdataGetRNTerms(SCIP *scip)
SCIP_Bool SCIPprobdataIsBigt(SCIP *scip)
static SCIP_DECL_PRICERINIT(pricerInitStp)
Definition: pricer_stp.c:106
SCIP_Real SCIPgetDualfarkasLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPprobdataPrintGraph(SCIP *scip, const char *filename, SCIP_SOL *sol, SCIP_Bool printsol)
static SCIP_RETCODE pricing(SCIP *scip, SCIP_PRICER *pricer, SCIP_Real *lowerbound, SCIP_Bool farkas)
Definition: pricer_stp.c:176
static SCIP_DECL_PRICERFREE(pricerFreeStp)
Definition: pricer_stp.c:83
#define FSP_MODE
Definition: grph.h:163
#define PRICER_NAME
Definition: pricer_stp.c:31
SCIP_RETCODE SCIPsetPricerExitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICEREXITSOL((*pricerexitsol)))
Definition: scip_pricer.c:285
void graph_path_exec(SCIP *, const GRAPH *, const int, int, const SCIP_Real *, PATH *)
Definition: grphpath.c:491
int knots
Definition: grph.h:62
SCIP_RETCODE SCIPsetPricerInitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINITSOL((*pricerinitsol)))
Definition: scip_pricer.c:261
#define SCIP_CALL(x)
Definition: def.h:365
SCIP_Real SCIPinfinity(SCIP *scip)
#define SCIP_Bool
Definition: def.h:70
int *RESTRICT tail
Definition: grph.h:95
void SCIPpricerSetData(SCIP_PRICER *pricer, SCIP_PRICERDATA *pricerdata)
Definition: pricer.c:511
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
const char * SCIPpricerGetName(SCIP_PRICER *pricer)
Definition: pricer.c:588
SCIP_RETCODE SCIPincludePricerBasic(SCIP *scip, SCIP_PRICER **pricerptr, const char *name, const char *desc, int priority, SCIP_Bool delay, SCIP_DECL_PRICERREDCOST((*pricerredcost)), SCIP_DECL_PRICERFARKAS((*pricerfarkas)), SCIP_PRICERDATA *pricerdata)
Definition: scip_pricer.c:117
#define PRICER_DESC
Definition: pricer_stp.c:32
Constraint handler for linear constraints in their most general form, .
int SCIPprobdataGetRoot(SCIP *scip)
includes various files containing graph methods used for Steiner tree problems
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:67
SCIP_PRICERDATA * SCIPpricerGetData(SCIP_PRICER *pricer)
Definition: pricer.c:501
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1482
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10263
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1766
#define SCIP_Real
Definition: def.h:164
SCIP_Real SCIPgetDualsolLinear(SCIP *scip, SCIP_CONS *cons)
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
struct SCIP_PricerData SCIP_PRICERDATA
Definition: type_pricer.h:36
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:120
static SCIP_DECL_PRICERREDCOST(pricerRedcostStp)
Definition: pricer_stp.c:356
static SCIP_DECL_PRICERINITSOL(pricerInitsolStp)
Definition: pricer_stp.c:127