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-2022 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 scipopt.org. */
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 "graph.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  /* get the graph*/
216  graph = SCIPprobdataGetGraph(probdata);
217 
218  /* get dual solutions and save them in mi and pi */
219  for( t = 0; t < pricerdata->realnterms; ++t )
220  {
221  if( farkas )
222  {
223  pricerdata->mi[t] = SCIPgetDualfarkasLinear(scip, pricerdata->pathcons[t]);
224  }
225  else
226  {
227  pricerdata->mi[t] = SCIPgetDualsolLinear(scip, pricerdata->pathcons[t]);
228  assert(!SCIPisNegative(scip, pricerdata->mi[t]));
229  }
230  }
231 
232  for( e = 0; e < pricerdata->nedges; ++e )
233  {
234  if( !pricerdata->bigt )
235  {
236  for( t = 0; t < pricerdata->realnterms; ++t )
237  {
238  if( farkas )
239  {
240  pricerdata->pi[t * pricerdata->nedges + e] = SCIPgetDualfarkasLinear(
241  scip, pricerdata->edgecons[t * pricerdata->nedges + e]);
242  }
243  else
244  {
245  pricerdata->pi[t * pricerdata->nedges + e] = SCIPgetDualsolLinear(
246  scip, pricerdata->edgecons[t * pricerdata->nedges + e]);
247  }
248  }
249  }
250  else
251  {
252  if( farkas )
253  {
254  pricerdata->pi[e] = SCIPgetDualfarkasLinear(
255  scip, pricerdata->edgecons[e]);
256  }
257  else
258  {
259  pricerdata->pi[e] = SCIPgetDualsolLinear(
260  scip, pricerdata->edgecons[e]);
261  }
262  }
263  }
264 
265  SCIP_CALL( SCIPallocMemoryArray(scip, &path, graph->knots) );
266  SCIP_CALL( SCIPallocMemoryArray(scip, &edgecosts, pricerdata->nedges) );
267 
268  if( pricerdata->bigt )
269  {
270  for( e = 0; e < pricerdata->nedges; ++e )
271  {
272  edgecosts[e] = (-pricerdata->pi[e]);
273  }
274  }
275  /* find shortest r-t (r root, t terminal) paths and create corresponding variables iff reduced cost < 0 */
276  for( t = 0; t < pricerdata->realnterms; ++t )
277  {
278  for( e = 0; e < pricerdata->nedges; ++e )
279  {
280  if( !pricerdata->bigt )
281  {
282  edgecosts[e] = (-pricerdata->pi[t * pricerdata->nedges + e]);
283  }
284 
285  assert(!SCIPisNegative(scip, edgecosts[e]));
286  }
287 
288  for( i = 0; i < graph->knots; i++ )
289  graph->mark[i] = 1;
290 
291  graph_path_exec(scip, graph, FSP_MODE, pricerdata->root, edgecosts, path);
292 
293  /* compute reduced cost of shortest path to terminal t */
294  redcost = 0.0;
295  tail = pricerdata->realterms[t];
296  while( tail != pricerdata->root )
297  {
298  redcost += edgecosts[path[tail].edge];
299  tail = graph->tail[path[tail].edge];
300  }
301  redcost -= pricerdata->mi[t];
302 
303  if( !farkas && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
304  {
305  newlowerbound += redcost;
306  }
307  /* check if reduced cost < 0 */
308  if( SCIPisNegative(scip, redcost) )
309  {
310  /* create variable to the shortest path (having reduced cost < 0) */
311  var = NULL;
312  sprintf(varname, "PathVar%d_%d", t, pricerdata->ncreatedvars[t]);
313  ++(pricerdata->ncreatedvars[t]);
314 
315  SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
316  SCIP_CALL( SCIPaddPricedVar(scip, var, -redcost) );
317  tail = pricerdata->realterms[t];
318  while( tail != pricerdata->root )
319  {
320  /* add variable to constraints */
321  if( !pricerdata->bigt )
322  {
323  SCIP_CALL( SCIPaddCoefLinear(scip, pricerdata->edgecons[t * pricerdata->nedges + path[tail].edge], var, 1.0) );
324  }
325  else
326  {
327  SCIP_CALL( SCIPaddCoefLinear(scip, pricerdata->edgecons[path[tail].edge], var, 1.0) );
328  }
329 
330  tail = graph->tail[path[tail].edge];
331  }
332  SCIP_CALL( SCIPaddCoefLinear(scip, pricerdata->pathcons[t], var, 1.0) );
333  }
334  }
335 
336  if( !farkas && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
337  *lowerbound = newlowerbound;
338 
339  SCIPfreeMemoryArray(scip, &edgecosts);
340  SCIPfreeMemoryArray(scip, &path);
341 
342  return SCIP_OKAY;
343 }
344 
345 /** reduced cost pricing method of variable pricer for feasible LPs */
346 static
347 SCIP_DECL_PRICERREDCOST(pricerRedcostStp)
348 { /*lint --e{715}*/
349  SCIP_CALL( pricing(scip, pricer, lowerbound, FALSE) );
350 
351  /* set result pointer */
352  *result = SCIP_SUCCESS;
353  return SCIP_OKAY;
354 }
355 
356 /** Farkas pricing method of variable pricer for infeasible LPs */
357 static
358 SCIP_DECL_PRICERFARKAS(pricerFarkasStp)
359 { /*lint --e{715}*/
360  SCIP_CALL( pricing(scip, pricer, NULL, TRUE) );
361 
362  return SCIP_OKAY;
363 }
364 
365 /*
366  * variable pricer specific interface methods
367  */
368 
369 /** creates the stp variable pricer and includes it in SCIP */
371  SCIP* scip /**< SCIP data structure */
372  )
373 {
374 
375  SCIP_PRICERDATA* pricerdata;
376  SCIP_PRICER* pricer;
377  SCIPdebugPrintf("include Pricer \n");
378 
379  /* create stp variable pricer data */
380  SCIP_CALL( SCIPallocMemory(scip, &pricerdata) );
381  pricerdata->scip = scip;
382 
383  /* include variable pricer */
384  pricer = NULL;
386  pricerRedcostStp, pricerFarkasStp, pricerdata) );
387  assert(pricer != NULL);
388 
389  /* set non fundamental callbacks via setter functions */
390  SCIP_CALL( SCIPsetPricerCopy(scip, pricer, pricerCopyStp) );
391  SCIP_CALL( SCIPsetPricerFree(scip, pricer, pricerFreeStp) );
392  SCIP_CALL( SCIPsetPricerInit(scip, pricer, pricerInitStp) );
393  SCIP_CALL( SCIPsetPricerInitsol(scip, pricer, pricerInitsolStp) );
394  SCIP_CALL( SCIPsetPricerExitsol(scip, pricer, pricerExitsolStp) );
395 
396  return SCIP_OKAY;
397 }
stp variable pricer
void SCIPpricerSetData(SCIP_PRICER *pricer, SCIP_PRICERDATA *pricerdata)
Definition: pricer.c:511
const char * SCIPpricerGetName(SCIP_PRICER *pricer)
Definition: pricer.c:588
#define FSP_MODE
Definition: graphdefs.h:99
SCIP_RETCODE SCIPincludePricerStp(SCIP *scip)
Definition: pricer_stp.c:370
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:71
signed int edge
Definition: graphdefs.h:287
#define SCIP_MAXSTRLEN
Definition: def.h:293
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
void graph_path_exec(SCIP *, const GRAPH *, int, int, const SCIP_Real *, PATH *)
Definition: graph_path.c:541
#define FALSE
Definition: def.h:87
int SCIPprobdataGetNEdges(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:86
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
static SCIP_DECL_PRICEREXITSOL(pricerExitsolStp)
Definition: pricer_stp.c:156
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:185
SCIP_PRICERDATA * SCIPpricerGetData(SCIP_PRICER *pricer)
Definition: pricer.c:501
#define SCIPdebugMessage
Definition: pub_message.h:87
static SCIP_DECL_PRICERFARKAS(pricerFarkasStp)
Definition: pricer_stp.c:358
SCIP_RETCODE SCIPsetPricerExitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICEREXITSOL((*pricerexitsol)))
Definition: scip_pricer.c:286
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
static SCIP_DECL_PRICERCOPY(pricerCopyStp)
Definition: pricer_stp.c:71
int *RESTRICT mark
Definition: graphdefs.h:198
int * SCIPprobdataGetRTerms(SCIP *scip)
SCIP_CONS ** SCIPprobdataGetPathConstraints(SCIP *scip)
#define SCIPdebugPrintf
Definition: pub_message.h:90
SCIP_Real SCIPgetDualsolLinear(SCIP *scip, SCIP_CONS *cons)
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:118
int SCIPprobdataGetRNTerms(SCIP *scip)
SCIP_Bool SCIPprobdataIsBigt(SCIP *scip)
static SCIP_DECL_PRICERINIT(pricerInitStp)
Definition: pricer_stp.c:106
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 NULL
Definition: lpi_spx1.cpp:155
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1482
#define PRICER_NAME
Definition: pricer_stp.c:31
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RETCODE SCIPsetPricerInit(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINIT((*pricerinit)))
Definition: scip_pricer.c:214
SCIP_Real SCIPgetDualfarkasLinear(SCIP *scip, SCIP_CONS *cons)
#define SCIP_Bool
Definition: def.h:84
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
int *RESTRICT tail
Definition: graphdefs.h:223
SCIP_RETCODE SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERFREE((*pricerfree)))
Definition: scip_pricer.c:190
#define PRICER_DESC
Definition: pricer_stp.c:32
Constraint handler for linear constraints in their most general form, .
int SCIPprobdataGetRoot(SCIP *scip)
SCIP_RETCODE SCIPsetPricerInitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINITSOL((*pricerinitsol)))
Definition: scip_pricer.c:262
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
Definition: scip_prob.c:1731
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
#define SCIP_Real
Definition: def.h:177
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
struct SCIP_PricerData SCIP_PRICERDATA
Definition: type_pricer.h:36
SCIP_RETCODE SCIPsetPricerCopy(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERCOPY((*pricercopy)))
Definition: scip_pricer.c:166
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
static SCIP_DECL_PRICERREDCOST(pricerRedcostStp)
Definition: pricer_stp.c:347
static SCIP_DECL_PRICERINITSOL(pricerInitsolStp)
Definition: pricer_stp.c:127
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1766