solver.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 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include "pub_solver.h"
37 #include "solver.h"
38 #include "struct_solver.h"
39 
40 #include "gcg.h"
41 #include "pricer_gcg.h"
42 
43 #include <string.h>
44 
45 
47 SCIP_DECL_SORTPTRCOMP(GCGsolverComp)
48 { /*lint --e{715}*/
49  GCG_SOLVER* solver1 = (GCG_SOLVER*) elem1;
50  GCG_SOLVER* solver2 = (GCG_SOLVER*) elem2;
51 
52  assert(solver1 != NULL);
53  assert(solver2 != NULL);
54 
55  return solver2->priority - solver1->priority; /* prefer higher priorities */
56 }
57 
59 SCIP_RETCODE GCGsolverCreate(
60  SCIP* scip,
61  GCG_SOLVER** solver,
62  const char* name,
63  const char* desc,
64  int priority,
65  SCIP_Bool enabled,
66  GCG_DECL_SOLVERUPDATE((*solverupdate)),
67  GCG_DECL_SOLVERSOLVE ((*solversolve)),
68  GCG_DECL_SOLVERSOLVEHEUR((*solveheur)),
69  GCG_DECL_SOLVERFREE ((*solverfree)),
70  GCG_DECL_SOLVERINIT ((*solverinit)),
71  GCG_DECL_SOLVEREXIT ((*solverexit)),
72  GCG_DECL_SOLVERINITSOL((*solverinitsol)),
73  GCG_DECL_SOLVEREXITSOL((*solverexitsol)),
74  GCG_SOLVERDATA* solverdata
75  )
76 {
77  char paramname[SCIP_MAXSTRLEN];
78  char paramdesc[SCIP_MAXSTRLEN];
79 
80  assert(scip != NULL);
81  assert(solver != NULL);
82 
83  SCIP_CALL( SCIPallocMemory(scip, solver) ); /*lint !e866*/
84 
85  SCIP_ALLOC( BMSduplicateMemoryArray(&(*solver)->name, name, strlen(name)+1) );
86  SCIP_ALLOC( BMSduplicateMemoryArray(&(*solver)->desc, desc, strlen(desc)+1) );
87 
88  (*solver)->priority = priority;
89  (*solver)->enabled = enabled;
90  (*solver)->solverupdate = solverupdate;
91  (*solver)->solversolve = solversolve;
92  (*solver)->solversolveheur = solveheur;
93  (*solver)->solverfree = solverfree;
94  (*solver)->solverinit = solverinit;
95  (*solver)->solverexit = solverexit;
96  (*solver)->solverinitsol = solverinitsol;
97  (*solver)->solverexitsol = solverexitsol;
98  (*solver)->solverdata = solverdata;
99 
100  SCIP_CALL( SCIPcreateCPUClock(scip, &((*solver)->optfarkasclock)) );
101  SCIP_CALL( SCIPcreateCPUClock(scip, &((*solver)->optredcostclock)) );
102  SCIP_CALL( SCIPcreateCPUClock(scip, &((*solver)->heurfarkasclock)) );
103  SCIP_CALL( SCIPcreateCPUClock(scip, &((*solver)->heurredcostclock)) );
104 
105  (*solver)->optfarkascalls = 0;
106  (*solver)->optredcostcalls = 0;
107  (*solver)->heurfarkascalls = 0;
108  (*solver)->heurredcostcalls = 0;
109 
110  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "pricingsolver/%s/enabled", name);
111  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "flag to indicate whether solver <%s> is enabled", name);
112  SCIP_CALL( SCIPaddBoolParam(GCGmasterGetOrigprob(scip), paramname, paramdesc,
113  &((*solver)->enabled), FALSE, enabled, NULL, NULL));
114 
115  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "pricingsolver/%s/priority", name);
116  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of solver <%s>", name);
117  SCIP_CALL( SCIPaddIntParam(GCGmasterGetOrigprob(scip), paramname, paramdesc,
118  &((*solver)->priority), FALSE, priority, INT_MIN/4, INT_MAX/4, NULL, NULL));
119 
120  return SCIP_OKAY;
121 }
122 
124 SCIP_RETCODE GCGsolverFree(
125  SCIP* scip,
126  GCG_SOLVER** solver
127  )
128 {
129  assert(scip != NULL);
130  assert(solver != NULL);
131  assert(*solver != NULL);
132 
133  if( (*solver)->solverfree != NULL )
134  {
135  SCIP_CALL( (*solver)->solverfree(scip, *solver) );
136  }
137 
138  BMSfreeMemoryArray(&(*solver)->name);
139  BMSfreeMemoryArray(&(*solver)->desc);
140 
141  SCIP_CALL( SCIPfreeClock(scip, &((*solver)->optfarkasclock)) );
142  SCIP_CALL( SCIPfreeClock(scip, &((*solver)->optredcostclock)) );
143  SCIP_CALL( SCIPfreeClock(scip, &((*solver)->heurfarkasclock)) );
144  SCIP_CALL( SCIPfreeClock(scip, &((*solver)->heurredcostclock)) );
145 
146  SCIPfreeMemory(scip, solver);
147 
148  return SCIP_OKAY;
149 }
150 
152 SCIP_RETCODE GCGsolverInit(
153  SCIP* scip,
154  GCG_SOLVER* solver
155  )
156 {
157  SCIP_Bool resetstat;
158 
159  assert(scip != NULL);
160  assert(solver != NULL);
161 
162  SCIP_CALL( SCIPgetBoolParam(scip, "misc/resetstat", &resetstat) );
163 
164  if( resetstat )
165  {
166  SCIP_CALL( SCIPresetClock(scip, solver->optfarkasclock) );
167  SCIP_CALL( SCIPresetClock(scip, solver->optredcostclock) );
168  SCIP_CALL( SCIPresetClock(scip, solver->heurfarkasclock) );
169  SCIP_CALL( SCIPresetClock(scip, solver->heurredcostclock) );
170 
171  solver->optfarkascalls = 0;
172  solver->optredcostcalls = 0;
173  solver->heurfarkascalls = 0;
174  solver->heurredcostcalls = 0;
175  }
176 
177  if( solver->solverinit != NULL )
178  {
179  SCIP_CALL( solver->solverinit(scip, solver) );
180  }
181 
182  return SCIP_OKAY;
183 }
184 
186 SCIP_RETCODE GCGsolverExit(
187  SCIP* scip,
188  GCG_SOLVER* solver
189  )
190 {
191  assert(scip != NULL);
192  assert(solver != NULL);
193 
194  if( solver->solverexit != NULL )
195  {
196  SCIP_CALL( solver->solverexit(scip, solver) );
197  }
198 
199  return SCIP_OKAY;
200 }
201 
203 SCIP_RETCODE GCGsolverInitsol(
204  SCIP* scip,
205  GCG_SOLVER* solver
206  )
207 {
208  assert(scip != NULL);
209  assert(solver != NULL);
210 
211  if( solver->solverinitsol != NULL )
212  {
213  SCIP_CALL( solver->solverinitsol(scip, solver) );
214  }
215 
216  return SCIP_OKAY;
217 }
218 
220 SCIP_RETCODE GCGsolverExitsol(
221  SCIP* scip,
222  GCG_SOLVER* solver
223  )
224 {
225  assert(scip != NULL);
226  assert(solver != NULL);
227 
228  if( solver->solverexitsol != NULL )
229  {
230  SCIP_CALL( solver->solverexitsol(scip, solver) );
231  }
232 
233  return SCIP_OKAY;
234 }
235 
237 SCIP_RETCODE GCGsolverUpdate(
238  SCIP* pricingprob,
239  GCG_SOLVER* solver,
240  int probnr,
241  SCIP_Bool varobjschanged,
242  SCIP_Bool varbndschanged,
243  SCIP_Bool consschanged
244  )
245 {
246  assert(pricingprob != NULL);
247  assert(solver != NULL);
248 
249  if( solver->solverupdate != NULL )
250  {
251  SCIP_CALL( solver->solverupdate(pricingprob, solver, probnr, varobjschanged, varbndschanged, consschanged) );
252  }
253 
254  return SCIP_OKAY;
255 }
256 
260 SCIP_RETCODE GCGsolverSolve(
261  SCIP* scip,
262  SCIP* pricingprob,
263  GCG_SOLVER* solver,
264  SCIP_Bool redcost,
265  SCIP_Bool heuristic,
266  int probnr,
267  SCIP_Real dualsolconv,
268  SCIP_Real* lowerbound,
269  GCG_PRICINGSTATUS* status,
270  SCIP_Bool* solved
271  )
272 {
273  SCIP_CLOCK* clock;
274 
275  assert(scip != NULL);
276  assert(pricingprob != NULL);
277  assert(solver != NULL);
278  assert(lowerbound != NULL);
279  assert(status != NULL);
280 
281  *solved = FALSE;
282 
283  if( heuristic )
284  {
285  if( solver->solversolveheur != NULL )
286  {
287  if( redcost )
288  clock = solver->heurredcostclock;
289  else
290  clock = solver->heurfarkasclock;
291 
292  #pragma omp critical (clock)
293  {
294  SCIP_CALL_ABORT( SCIPstartClock(scip, clock) );
295  }
296 
297  SCIP_CALL( solver->solversolveheur(scip, pricingprob, solver, probnr, dualsolconv, lowerbound, status) );
298  *solved = TRUE;
299 
300  #pragma omp critical (clock)
301  {
302  SCIP_CALL_ABORT( SCIPstopClock(scip, clock) );
303  }
304  }
305  }
306  else
307  {
308  if( solver->solversolve != NULL )
309  {
310  if( redcost )
311  clock = solver->optredcostclock;
312  else
313  clock = solver->optfarkasclock;
314 
315  #pragma omp critical (clock)
316  {
317  SCIP_CALL_ABORT( SCIPstartClock(scip, clock) );
318  }
319 
320  SCIP_CALL( solver->solversolve(scip, pricingprob, solver, probnr, dualsolconv, lowerbound, status) );
321  *solved = TRUE;
322 
323  #pragma omp critical (clock)
324  {
325  SCIP_CALL_ABORT( SCIPstopClock(scip, clock) );
326  }
327 
328  }
329  }
330 
331  if( *status != GCG_PRICINGSTATUS_NOTAPPLICABLE )
332  {
333  if( redcost )
334  if( heuristic )
335  #pragma omp atomic
336  ++solver->heurredcostcalls;
337  else
338  #pragma omp atomic
339  ++solver->optredcostcalls;
340  else
341  if( heuristic )
342  #pragma omp atomic
343  ++solver->heurfarkascalls;
344  else
345  #pragma omp atomic
346  ++solver->optfarkascalls;
347  }
348 
349  return SCIP_OKAY;
350 }
351 
354  GCG_SOLVER* solver
355  )
356 {
357  assert(solver != NULL);
358 
359  return solver->solverdata;
360 }
361 
364  GCG_SOLVER* solver,
365  GCG_SOLVERDATA* solverdata
366  )
367 {
368  assert(solver != NULL);
369 
370  solver->solverdata = solverdata;
371 }
372 
374 const char* GCGsolverGetName(
375  GCG_SOLVER* solver
376  )
377 {
378  assert(solver != NULL);
379 
380  return solver->name;
381 }
382 
384 const char* GCGsolverGetDesc(
385  GCG_SOLVER* solver
386  )
387 {
388  assert(solver != NULL);
389 
390  return solver->desc;
391 }
392 
395  GCG_SOLVER* solver
396  )
397 {
398  assert(solver != NULL);
399 
400  return solver->priority;
401 }
402 
405  GCG_SOLVER* solver
406  )
407 {
408  assert(solver != NULL);
409 
410  return solver->enabled;
411 }
412 
415  GCG_SOLVER* solver
416  )
417 {
418  assert(solver != NULL);
419 
420  return solver->optfarkascalls;
421 }
422 
425  GCG_SOLVER* solver
426  )
427 {
428  assert(solver != NULL);
429 
430  return solver->optredcostcalls;
431 }
432 
435  GCG_SOLVER* solver
436  )
437 {
438  assert(solver != NULL);
439 
440  return solver->heurfarkascalls;
441 }
442 
445  GCG_SOLVER* solver
446  )
447 {
448  assert(solver != NULL);
449 
450  return solver->heurredcostcalls;
451 }
452 
455  SCIP* scip,
456  GCG_SOLVER* solver
457  )
458 {
459  assert(scip != NULL);
460  assert(solver != NULL);
461 
462  return SCIPgetClockTime(scip, solver->optfarkasclock);
463 }
464 
467  SCIP* scip,
468  GCG_SOLVER* solver
469  )
470 {
471  assert(scip != NULL);
472  assert(solver != NULL);
473 
474  return SCIPgetClockTime(scip, solver->optredcostclock);
475 }
476 
479  SCIP* scip,
480  GCG_SOLVER* solver
481  )
482 {
483  assert(scip != NULL);
484  assert(solver != NULL);
485 
486  return SCIPgetClockTime(scip, solver->heurfarkasclock);
487 }
488 
491  SCIP* scip,
492  GCG_SOLVER* solver
493  )
494 {
495  assert(scip != NULL);
496  assert(solver != NULL);
497 
498  return SCIPgetClockTime(scip, solver->heurredcostclock);
499 }
SCIP_RETCODE GCGsolverInitsol(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:203
struct GCG_Solver GCG_SOLVER
Definition: type_solver.h:50
int GCGsolverGetOptRedcostCalls(GCG_SOLVER *solver)
Definition: solver.c:424
SCIP_RETCODE GCGsolverExitsol(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:220
int GCGsolverGetHeurFarkasCalls(GCG_SOLVER *solver)
Definition: solver.c:434
int GCGsolverGetPriority(GCG_SOLVER *solver)
Definition: solver.c:394
GCG interface methods.
#define GCG_DECL_SOLVEREXIT(x)
Definition: type_solver.h:75
enum GCG_PricingStatus GCG_PRICINGSTATUS
SCIP_Bool GCGsolverIsEnabled(GCG_SOLVER *solver)
Definition: solver.c:404
SCIP_RETCODE GCGsolverInit(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:152
#define GCG_DECL_SOLVERFREE(x)
Definition: type_solver.h:59
SCIP_DECL_SORTPTRCOMP(GCGsolverComp)
Definition: solver.c:47
SCIP_RETCODE GCGsolverExit(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:186
SCIP_RETCODE GCGsolverCreate(SCIP *scip, GCG_SOLVER **solver, const char *name, const char *desc, int priority, SCIP_Bool enabled, GCG_DECL_SOLVERUPDATE((*solverupdate)), GCG_DECL_SOLVERSOLVE((*solversolve)), GCG_DECL_SOLVERSOLVEHEUR((*solveheur)), GCG_DECL_SOLVERFREE((*solverfree)), GCG_DECL_SOLVERINIT((*solverinit)), GCG_DECL_SOLVEREXIT((*solverexit)), GCG_DECL_SOLVERINITSOL((*solverinitsol)), GCG_DECL_SOLVEREXITSOL((*solverexitsol)), GCG_SOLVERDATA *solverdata)
Definition: solver.c:59
SCIP_RETCODE GCGsolverUpdate(SCIP *pricingprob, GCG_SOLVER *solver, int probnr, SCIP_Bool varobjschanged, SCIP_Bool varbndschanged, SCIP_Bool consschanged)
Definition: solver.c:237
SCIP_Real GCGsolverGetHeurRedcostTime(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:490
SCIP_Real GCGsolverGetHeurFarkasTime(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:478
#define GCG_DECL_SOLVERINITSOL(x)
Definition: type_solver.h:86
GCG variable pricer.
SCIP_Real GCGsolverGetOptRedcostTime(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:466
#define GCG_DECL_SOLVEREXITSOL(x)
Definition: type_solver.h:97
public methods for GCG pricing solvers
SCIP * GCGmasterGetOrigprob(SCIP *scip)
GCG_SOLVERDATA * GCGsolverGetData(GCG_SOLVER *solver)
Definition: solver.c:353
SCIP_RETCODE GCGsolverFree(SCIP *scip, GCG_SOLVER **solver)
Definition: solver.c:124
#define GCG_DECL_SOLVERUPDATE(x)
Definition: type_solver.h:105
int GCGsolverGetHeurRedcostCalls(GCG_SOLVER *solver)
Definition: solver.c:444
SCIP_Real GCGsolverGetOptFarkasTime(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:454
#define GCG_DECL_SOLVERSOLVE(x)
Definition: type_solver.h:119
#define GCG_DECL_SOLVERINIT(x)
Definition: type_solver.h:67
void GCGsolverSetData(GCG_SOLVER *solver, GCG_SOLVERDATA *solverdata)
Definition: solver.c:363
SCIP_RETCODE GCGsolverSolve(SCIP *scip, SCIP *pricingprob, GCG_SOLVER *solver, SCIP_Bool redcost, SCIP_Bool heuristic, int probnr, SCIP_Real dualsolconv, SCIP_Real *lowerbound, GCG_PRICINGSTATUS *status, SCIP_Bool *solved)
Definition: solver.c:260
const char * GCGsolverGetName(GCG_SOLVER *solver)
Definition: solver.c:374
const char * GCGsolverGetDesc(GCG_SOLVER *solver)
Definition: solver.c:384
int GCGsolverGetOptFarkasCalls(GCG_SOLVER *solver)
Definition: solver.c:414
#define GCG_DECL_SOLVERSOLVEHEUR(x)
Definition: type_solver.h:133