pricingprob.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2018 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 
38 #include "pricingprob.h"
39 #include "pub_pricingprob.h"
40 
41 #include "gcg.h"
42 #include "pricestore_gcg.h"
43 #include "pub_colpool.h"
44 #include "pub_gcgcol.h"
45 #include "pub_pricingjob.h"
46 
47 #include "scip/scip.h"
48 
49 
51 SCIP_RETCODE GCGpricingprobCreate(
52  SCIP* scip,
53  GCG_PRICINGPROB** pricingprob,
54  SCIP* pricingscip,
55  int probnr,
56  int nroundscol
57 )
58 {
59  SCIP_CALL( SCIPallocMemory(scip, pricingprob) );
60 
61  (*pricingprob)->pricingscip = pricingscip;
62  (*pricingprob)->probnr = probnr;
63  (*pricingprob)->branchconss = NULL;
64  (*pricingprob)->branchduals = NULL;
65  (*pricingprob)->nbranchconss = 0;
66  (*pricingprob)->branchconsssize = 0;
67  (*pricingprob)->branchconsidx = 0;
68  (*pricingprob)->consisadded = TRUE;
69  (*pricingprob)->status = GCG_PRICINGSTATUS_UNKNOWN;
70  (*pricingprob)->lowerbound = -SCIPinfinity(scip);
71  (*pricingprob)->nimpcols = 0;
72  (*pricingprob)->nsolves = 0;
73 
74  SCIP_CALL( SCIPallocClearMemoryArray(scip, &(*pricingprob)->ncolsround, nroundscol) );
75 
76 
77  return SCIP_OKAY;
78 }
79 
82  SCIP* scip,
83  GCG_PRICINGPROB** pricingprob
84 )
85 {
86  SCIPfreeMemoryArrayNull(scip, &(*pricingprob)->branchduals);
87  SCIPfreeMemoryArrayNull(scip, &(*pricingprob)->branchconss);
88  SCIPfreeMemoryArray(scip, &(*pricingprob)->ncolsround);
89  SCIPfreeMemory(scip, pricingprob);
90  *pricingprob = NULL;
91 }
92 
95  GCG_PRICINGPROB* pricingprob
96  )
97 {
98  assert(pricingprob->nimpcols == 0);
99 
100  pricingprob->nbranchconss = 0;
101  pricingprob->branchconsidx = 0;
102  pricingprob->consisadded = TRUE;
103 }
104 
107  GCG_PRICINGPROB* pricingprob,
108  int nroundscol
109  )
110 {
111  int i;
112 
113  for( i = nroundscol-1; i > 0; --i )
114  pricingprob->ncolsround[i] = pricingprob->ncolsround[i-1];
115  pricingprob->ncolsround[0] = pricingprob->nimpcols;
116 
117  pricingprob->nimpcols = 0;
118 }
119 
122  SCIP* scip,
123  GCG_PRICINGPROB* pricingprob,
124  SCIP_CONS* branchcons,
125  SCIP_Real branchdual
126  )
127 {
128  /* allocate memory, if necessary */
129  if( pricingprob->branchconsssize == pricingprob->nbranchconss )
130  {
131  assert((pricingprob->branchconsssize == 0) == (pricingprob->branchconss == NULL));
132  assert((pricingprob->branchconsssize == 0) == (pricingprob->branchduals == NULL));
133 
134  pricingprob->branchconsssize = SCIPcalcMemGrowSize(scip, pricingprob->branchconsssize+1);
135 
136  if( pricingprob->branchconss == NULL )
137  {
138  SCIP_CALL( SCIPallocMemoryArray(scip, &pricingprob->branchconss, pricingprob->branchconsssize) );
139  SCIP_CALL( SCIPallocMemoryArray(scip, &pricingprob->branchduals, pricingprob->branchconsssize) );
140  }
141  else
142  {
143  SCIP_CALL( SCIPreallocMemoryArray(scip, &pricingprob->branchconss, pricingprob->branchconsssize) );
144  SCIP_CALL( SCIPreallocMemoryArray(scip, &pricingprob->branchduals, pricingprob->branchconsssize) );
145  }
146 
147  }
148 
149  /* add constraint and dual solution value */
150  pricingprob->branchconss[pricingprob->nbranchconss] = branchcons;
151  pricingprob->branchduals[pricingprob->nbranchconss] = branchdual;
152  ++pricingprob->nbranchconss;
153  ++pricingprob->branchconsidx;
154 
155  return SCIP_OKAY;
156 }
157 
160  SCIP* scip,
161  GCG_PRICINGPROB* pricingprob
162  )
163 {
164  assert(pricingprob->nimpcols == 0);
165 
166  pricingprob->branchconsidx = pricingprob->nbranchconss;
167  pricingprob->status = GCG_PRICINGSTATUS_UNKNOWN;
168  pricingprob->lowerbound = -SCIPinfinity(scip);
169  pricingprob->nsolves = 0;
170 }
171 
174  SCIP* scip,
175  GCG_PRICINGPROB* pricingprob,
176  GCG_PRICINGSTATUS status,
177  SCIP_Real lowerbound,
178  int nimpcols
179  )
180 {
181  /* if the solver was not applicable to the problem, there is nothing to be done */
182  if( status == GCG_PRICINGSTATUS_NOTAPPLICABLE )
183  return;
184 
185  /* update status, lower bound and number of improving columns */
186  pricingprob->status = status;
187  if( SCIPisDualfeasGT(scip, lowerbound, pricingprob->lowerbound) )
188  pricingprob->lowerbound = lowerbound;
189  pricingprob->nimpcols += nimpcols;
190 
191  ++pricingprob->nsolves;
192 }
193 
196  GCG_PRICINGPROB* pricingprob
197  )
198 {
199  return pricingprob->pricingscip;
200 }
201 
204  GCG_PRICINGPROB* pricingprob
205  )
206 {
207  return pricingprob->probnr;
208 }
209 
212  GCG_PRICINGPROB* pricingprob,
213  SCIP_CONS*** branchconss,
214  SCIP_Real** branchduals,
215  int* nbranchconss
216  )
217 {
218  if( branchconss != NULL )
219  *branchconss = pricingprob->branchconss;
220  if( branchduals != NULL )
221  *branchduals = pricingprob->branchduals;
222  if( nbranchconss != NULL )
223  *nbranchconss = pricingprob->nbranchconss;
224 }
225 
228  GCG_PRICINGPROB* pricingprob
229  )
230 {
231  return pricingprob->nbranchconss;
232 }
233 
236  GCG_PRICINGPROB* pricingprob
237  )
238 {
239  return pricingprob->branchconsidx;
240 }
241 
244  GCG_PRICINGPROB* pricingprob
245  )
246 {
247  return pricingprob->consisadded;
248 }
249 
252  GCG_PRICINGPROB* pricingprob
253  )
254 {
255  pricingprob->consisadded = TRUE;
256 }
257 
260  GCG_PRICINGPROB* pricingprob
261  )
262 {
263  assert(pricingprob->branchconsidx >= 1);
264  --pricingprob->branchconsidx;
265  pricingprob->consisadded = FALSE;
266  pricingprob->status = GCG_PRICINGSTATUS_UNKNOWN;
267 }
268 
271  GCG_PRICINGPROB* pricingprob
272  )
273 {
274  return pricingprob->status;
275 }
276 
279  GCG_PRICINGPROB* pricingprob
280  )
281 {
282  return pricingprob->lowerbound;
283 }
284 
287  GCG_PRICINGPROB* pricingprob
288  )
289 {
290  return pricingprob->nimpcols;
291 }
292 
295  GCG_PRICINGPROB* pricingprob
296  )
297 {
298  return pricingprob->nsolves;
299 }
300 
303  GCG_PRICINGPROB* pricingprob,
304  int nroundscol
305  )
306 {
307  int ncols;
308  int i;
309 
310  ncols = 0;
311  for( i = 0; i < nroundscol; ++i )
312  ncols += pricingprob->ncolsround[i];
313 
314  return ncols;
315 }
void GCGpricingprobMarkBranchconsAdded(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:251
SCIP_RETCODE GCGpricingprobCreate(SCIP *scip, GCG_PRICINGPROB **pricingprob, SCIP *pricingscip, int probnr, int nroundscol)
Definition: pricingprob.c:51
int GCGpricingprobGetProbnr(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:203
SCIP_RETCODE GCGpricingprobAddGenericBranchData(SCIP *scip, GCG_PRICINGPROB *pricingprob, SCIP_CONS *branchcons, SCIP_Real branchdual)
Definition: pricingprob.c:121
GCG interface methods.
int GCGpricingprobGetBranchconsIdx(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:235
int GCGpricingprobGetNSolves(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:294
int GCGpricingprobGetNGenericBranchconss(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:227
SCIP_Real GCGpricingprobGetLowerbound(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:278
void GCGpricingprobFree(SCIP *scip, GCG_PRICINGPROB **pricingprob)
Definition: pricingprob.c:81
void GCGpricingprobReset(SCIP *scip, GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:159
enum GCG_PricingStatus GCG_PRICINGSTATUS
void GCGpricingprobInitPricing(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:94
int GCGpricingprobGetNColsLastRounds(GCG_PRICINGPROB *pricingprob, int nroundscol)
Definition: pricingprob.c:302
private methods for working with pricing problems, to be used by the pricing controller only ...
void GCGpricingprobExitPricing(GCG_PRICINGPROB *pricingprob, int nroundscol)
Definition: pricingprob.c:106
public methods for working with gcg columns
SCIP_Bool GCGpricingprobBranchconsIsAdded(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:243
SCIP * GCGpricingprobGetPricingscip(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:195
void GCGpricingprobUpdate(SCIP *scip, GCG_PRICINGPROB *pricingprob, GCG_PRICINGSTATUS status, SCIP_Real lowerbound, int nimpcols)
Definition: pricingprob.c:173
void GCGpricingprobGetGenericBranchData(GCG_PRICINGPROB *pricingprob, SCIP_CONS ***branchconss, SCIP_Real **branchduals, int *nbranchconss)
Definition: pricingprob.c:211
GCG_PRICINGSTATUS GCGpricingprobGetStatus(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:270
int GCGpricingprobGetNImpCols(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:286
public methods for storing cols in a col pool
public methods for working with pricing jobs
public methods for working with pricing problems
struct GCG_PricingProb GCG_PRICINGPROB
void GCGpricingprobNextBranchcons(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:259