Scippy

GCG

Branch-and-Price & Column Generation for Everyone

solver_mip.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-2021 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 
28 /**@file solver_mip.c
29  * @brief pricing solver solving the pricing problem as a sub-MIP, using SCIP
30  * @author Gerald Gamrath
31  * @author Martin Bergner
32  * @author Christian Puchert
33  *
34  */
35 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 /* #define DEBUG_PRICING_ALL_OUTPUT */
38 
39 #include <assert.h>
40 #include <string.h>
41 
42 #include "solver_mip.h"
43 #include "scip/cons_linear.h"
44 #include "scip/cons_knapsack.h"
45 #include "gcg.h"
46 #include "pricer_gcg.h"
47 #include "pub_solver.h"
48 #include "scip/scipdefplugins.h"
49 #include "pub_gcgcol.h"
50 
51 #define SOLVER_NAME "mip"
52 #define SOLVER_DESC "pricing solver solving the pricing problem as a sub-MIP, using SCIP"
53 #define SOLVER_PRIORITY 0
54 #define SOLVER_HEURENABLED TRUE /**< indicates whether the heuristic solving method of the solver should be enabled */
55 #define SOLVER_EXACTENABLED TRUE /**< indicates whether the exact solving method of the solver should be enabled */
56 
57 #define DEFAULT_CHECKSOLS TRUE /**< should solutions be checked extensively */
58 #define DEFAULT_STARTNODELIMIT 1000LL /**< start node limit for heuristic pricing */
59 #define DEFAULT_STARTSTALLNODELIMIT 100LL /**< start stalling node limit for heuristic pricing */
60 #define DEFAULT_STARTGAPLIMIT 0.2 /**< start gap limit for heuristic pricing */
61 #define DEFAULT_STARTSOLLIMIT 10 /**< start solution limit for heuristic pricing */
62 #define DEFAULT_NODELIMITFAC 1.0 /**< factor by which to increase node limit for heuristic pricing (1.0: add start limit) */
63 #define DEFAULT_STALLNODELIMITFAC 1.0 /**< factor by which to increase stalling node limit for heuristic pricing (1.0: add start limit) */
64 #define DEFAULT_GAPLIMITFAC 0.8 /**< factor by which to decrease gap limit for heuristic pricing (1.0: subtract start limit) */
65 #define DEFAULT_SOLLIMITFAC 1.0 /**< factor by which to increase solution limit for heuristic pricing (1.0: add start limit) */
66 #define DEFAULT_SETTINGSFILE "-" /**< settings file to be applied in pricing problems */
67 
68 
69 
70 /** pricing solver data */
71 struct GCG_SolverData
72 {
73  /* parameters */
74  SCIP_Bool checksols; /**< should solutions be checked extensively */
75  SCIP_Longint startnodelimit; /**< start node limit for heuristic pricing */
76  SCIP_Longint startstallnodelimit; /**< start stalling node limit for heuristic pricing */
77  SCIP_Real startgaplimit; /**< start gap limit for heuristic pricing */
78  int startsollimit; /**< start solution limit for heuristic pricing */
79  SCIP_Real nodelimitfac; /**< factor by which to increase node limit for heuristic pricing (1.0: add start limit) */
80  SCIP_Real stallnodelimitfac; /**< factor by which to increase stalling node limit for heuristic pricing (1.0: add start limit) */
81  SCIP_Real gaplimitfac; /**< factor by which to decrease gap limit for heuristic pricing (1.0: subtract start limit) */
82  SCIP_Real sollimitfac; /**< factor by which to increase solution limit for heuristic pricing (1.0: add start limit) */
83  char* settingsfile; /**< settings file to be applied in pricing problems */
84 
85  /* solver data */
86  SCIP_Longint* curnodelimit; /**< current node limit per pricing problem */
87  SCIP_Longint* curstallnodelimit; /**< current stalling node limit per pricing problem */
88  SCIP_Real* curgaplimit; /**< current gap limit per pricing problem */
89  int* cursollimit; /**< current solution limit per pricing problem */
90 };
91 
92 
93 /*
94  * Local methods
95  */
96 
97 /** extracts ray from pricing problem */
98 static
99 SCIP_RETCODE createColumnFromRay(
100  SCIP* pricingprob, /**< pricing problem SCIP data structure */
101  int probnr, /**< problem number */
102  GCG_COL** newcol /**< column pointer to store new column */
103 )
104 {
105  SCIP_VAR** probvars;
106  SCIP_VAR** solvars;
107  SCIP_Real* solvals;
108  int nprobvars;
109  int nsolvars;
110  int i;
111 
112  assert(pricingprob != NULL);
113  assert(newcol != NULL);
114  assert(SCIPhasPrimalRay(pricingprob));
115 
116  probvars = SCIPgetOrigVars(pricingprob);
117  nprobvars = SCIPgetNOrigVars(pricingprob);
118  nsolvars = 0;
119  SCIP_CALL( SCIPallocBufferArray(pricingprob, &solvars, nprobvars) );
120  SCIP_CALL( SCIPallocBufferArray(pricingprob, &solvals, nprobvars) );
121 
122  /* store the primal ray values */
123  for ( i = 0; i < nprobvars; i++ )
124  {
125  if ( SCIPisZero(pricingprob, SCIPgetPrimalRayVal(pricingprob, probvars[i])) )
126  continue;
127 
128  assert(!SCIPisInfinity(pricingprob, SCIPgetPrimalRayVal(pricingprob, probvars[i])));
129  assert(!SCIPisInfinity(pricingprob, -SCIPgetPrimalRayVal(pricingprob, probvars[i])));
130 
131  solvars[nsolvars] = probvars[i];
132  solvals[nsolvars] = SCIPgetPrimalRayVal(pricingprob, probvars[i]);
133  assert(!SCIPisInfinity(pricingprob, solvals[nsolvars]));
134  /* todo: check if/ensure that this value is integral! */
135  nsolvars++;
136 
137  SCIPdebugMessage("%s: %g (obj = %g)\n", SCIPvarGetName(probvars[i]), SCIPgetPrimalRayVal(pricingprob, probvars[i]), SCIPvarGetObj(probvars[i]));
138  }
139 
140  SCIP_CALL( SCIPfreeSolve(pricingprob, TRUE) );
141  SCIP_CALL( SCIPtransformProb(pricingprob) );
142 
143  /* todo: is it okay to write pricingprob into column structure? */
144  SCIP_CALL( GCGcreateGcgCol(pricingprob, newcol, probnr, solvars, solvals, nsolvars, TRUE, SCIPinfinity(pricingprob)) );
145 
146  SCIPfreeBufferArray(pricingprob, &solvals);
147  SCIPfreeBufferArray(pricingprob, &solvars);
148 
149  SCIPdebugMessage("pricingproblem has an unbounded ray!\n");
150 
151  return SCIP_OKAY;
152 }
153 
154 /** solves the pricing problem again without presolving */
155 static
157  SCIP* pricingprob /**< pricing problem to solve again */
158  )
159 {
160  assert(pricingprob != NULL);
161  SCIP_CALL( SCIPfreeTransform(pricingprob) );
162 
163  SCIP_CALL( SCIPsetIntParam(pricingprob, "presolving/maxrounds", 0) );
164  SCIP_CALL( SCIPtransformProb(pricingprob) );
165  SCIP_CALL( SCIPsolve(pricingprob) );
166  SCIP_CALL( SCIPsetIntParam(pricingprob, "presolving/maxrounds", -1) );
167 
168  return SCIP_OKAY;
169 }
170 
171 /** checks whether the given solution is equal to one of the former solutions in the sols array */
172 static
173 SCIP_RETCODE checkSolNew(
174  SCIP* pricingprob, /**< pricing problem SCIP data structure */
175  SCIP_SOL** sols, /**< array of solutions */
176  int idx, /**< index of the solution */
177  SCIP_Bool* isnew /**< pointer to store whether the solution is new */
178  )
179 {
180  SCIP_VAR** probvars;
181  int nprobvars;
182  SCIP_Real* newvals;
183 
184  int s;
185  int i;
186 
187  assert(pricingprob != NULL);
188  assert(sols != NULL);
189  assert(sols[idx] != NULL);
190  assert(isnew != NULL);
191 
192  probvars = SCIPgetVars(pricingprob);
193  nprobvars = SCIPgetNVars(pricingprob);
194 
195  *isnew = TRUE;
196 
197  SCIP_CALL( SCIPallocBufferArray(pricingprob, &newvals, nprobvars) );
198 
199  SCIP_CALL( SCIPgetSolVals(pricingprob, sols[idx], nprobvars, probvars, newvals) );
200 
201  for( s = 0; s < idx && *isnew == TRUE; s++ )
202  {
203  assert(sols[s] != NULL);
204  /** @todo ensure that the solutions are sorted */
205  if( (!SCIPisInfinity(pricingprob, -SCIPgetSolOrigObj(pricingprob, sols[s])) && !SCIPisInfinity(pricingprob, -SCIPgetSolOrigObj(pricingprob, sols[idx])) )
206  && !SCIPisEQ(pricingprob, SCIPgetSolOrigObj(pricingprob, sols[s]), SCIPgetSolOrigObj(pricingprob, sols[idx])) )
207  continue;
208 
209  if( (SCIPisInfinity(pricingprob, -SCIPgetSolOrigObj(pricingprob, sols[s])) && !SCIPisInfinity(pricingprob, -SCIPgetSolOrigObj(pricingprob, sols[idx])) )
210  ||(!SCIPisInfinity(pricingprob, -SCIPgetSolOrigObj(pricingprob, sols[s])) && SCIPisInfinity(pricingprob, -SCIPgetSolOrigObj(pricingprob, sols[idx]))) )
211  continue;
212 
213 
214  if( SCIPsolGetOrigin(sols[s]) != SCIP_SOLORIGIN_ORIGINAL && SCIPsolGetOrigin(sols[idx]) != SCIP_SOLORIGIN_ORIGINAL )
215  continue;
216 
217  for( i = 0; i < nprobvars; i++ )
218  if( !SCIPisEQ(pricingprob, SCIPgetSolVal(pricingprob, sols[s], probvars[i]), newvals[i]) )
219  break;
220 
221  if( i == nprobvars )
222  *isnew = FALSE;
223  }
224 
225  SCIPfreeBufferArray(pricingprob, &newvals);
226 
227  return SCIP_OKAY;
228 }
229 
230 /** get the status of the pricing problem */
231 static
233  SCIP* pricingprob /**< pricing problem SCIP data structure */
234  )
235 {
236  /* all SCIP statuses handled so far; these are currently:
237  * SCIP_STATUS_USERINTERRUPT
238  * SCIP_STATUS_NODELIMIT
239  * SCIP_STATUS_TOTALNODELIMIT
240  * SCIP_STATUS_STALLNODELIMIT
241  * SCIP_STATUS_TIMELIMIT
242  * SCIP_STATUS_MEMLIMIT
243  * SCIP_STATUS_GAPLIMIT
244  * SCIP_STATUS_SOLLIMIT
245  * SCIP_STATUS_BESTSOLLIMIT
246  * SCIP_STATUS_OPTIMAL
247  * SCIP_STATUS_INFEASIBLE
248  * SCIP_STATUS_UNBOUNDED
249  * SCIP_STATUS_INFORUNBD
250  */
251  /* @todo: can SCIP_STATUS_UNKNOWN happen, too? */
252  assert((SCIPgetStatus(pricingprob) >= SCIP_STATUS_USERINTERRUPT && SCIPgetStatus(pricingprob) <= SCIP_STATUS_BESTSOLLIMIT)
253  || SCIPgetStatus(pricingprob) == SCIP_STATUS_OPTIMAL
254  || SCIPgetStatus(pricingprob) == SCIP_STATUS_INFEASIBLE
255  || SCIPgetStatus(pricingprob) == SCIP_STATUS_UNBOUNDED
256  || SCIPgetStatus(pricingprob) == SCIP_STATUS_INFORUNBD);
257 
258  /* translate SCIP solution status to GCG pricing status */
259  switch( SCIPgetStatus(pricingprob) )
260  {
261  case SCIP_STATUS_USERINTERRUPT:
262  SCIPdebugMessage(" -> interrupted, %d solutions found\n", SCIPgetNSols(pricingprob)); /*lint -fallthrough*/
263  case SCIP_STATUS_UNKNOWN:
264  case SCIP_STATUS_TOTALNODELIMIT:
265  case SCIP_STATUS_TIMELIMIT:
266  case SCIP_STATUS_MEMLIMIT:
267  case SCIP_STATUS_BESTSOLLIMIT:
269 
270  case SCIP_STATUS_NODELIMIT:
271  case SCIP_STATUS_STALLNODELIMIT:
272  case SCIP_STATUS_GAPLIMIT:
273  case SCIP_STATUS_SOLLIMIT:
275 
276  case SCIP_STATUS_OPTIMAL:
278 
279  case SCIP_STATUS_INFEASIBLE:
281 
282  case SCIP_STATUS_UNBOUNDED:
283  case SCIP_STATUS_INFORUNBD:
285 
286  default:
287  SCIPerrorMessage("invalid SCIP status of pricing problem: %d\n", SCIPgetStatus(pricingprob));
289  }
290 }
291 
292 /** check whether a column contains an infinite solution value */
293 static
295  SCIP* pricingprob, /**< pricing problem SCIP data structure */
296  SCIP_SOL* sol /**< solution to be checked */
297  )
298 {
299  SCIP_VAR** vars;
300  int nvars;
301 
302  int i;
303 
304  vars = SCIPgetOrigVars(pricingprob);
305  nvars = SCIPgetNOrigVars(pricingprob);
306 
307  for( i = 0; i < nvars; ++i )
308  if( SCIPisInfinity(pricingprob, SCIPgetSolVal(pricingprob, sol, vars[i])) )
309  return TRUE;
310 
311  return FALSE;
312 }
313 
314 /** transforms feasible solutions of the pricing problem into columns */
315 static
317  SCIP* scip, /**< master problem SCIP data structure */
318  SCIP* pricingprob, /**< pricing problem SCIP data structure */
319  int probnr, /**< problem number */
320  SCIP_Bool checksols /**< should solutions be checked extensively */
321 )
322 {
323  SCIP_SOL** probsols;
324  int nprobsols;
325 
326  int s;
327 
328  probsols = SCIPgetSols(pricingprob);
329  nprobsols = SCIPgetNSols(pricingprob);
330 
331  for( s = 0; s < nprobsols; s++ )
332  {
333  GCG_COL* col;
334  SCIP_Bool feasible;
335  assert(probsols[s] != NULL);
336  SCIP_CALL( SCIPcheckSolOrig(pricingprob, probsols[s], &feasible, FALSE, FALSE) );
337 
338  if( !feasible )
339  {
340  SCIPwarningMessage(pricingprob, "solution of pricing problem %d not feasible:\n", probnr);
341  SCIP_CALL( SCIPcheckSolOrig(pricingprob, probsols[s], &feasible, TRUE, TRUE) );
342  }
343 
344  /* check whether the solution is equal to one of the previous solutions */
345  if( checksols )
346  {
347  SCIP_Bool isnew;
348 
349  SCIP_CALL( checkSolNew(pricingprob, probsols, s, &isnew) );
350 
351  if( !isnew )
352  continue;
353  }
354 
355  /* Check whether the pricing problem solution has infinite values; if not, transform it to a column */
356  if( !solutionHasInfiniteValue(pricingprob, probsols[s]) )
357  {
358  SCIP_CALL( GCGcreateGcgColFromSol(pricingprob, &col, probnr, probsols[s], FALSE, SCIPinfinity(pricingprob)) );
359  SCIP_CALL( GCGpricerAddCol(scip, col) );
360  }
361  /* If the best solution has infinite values, try to repair it */
362  else if( s == 0 )
363  {
364  SCIP_SOL* newsol;
365  SCIP_Bool success;
366 
367  newsol = NULL;
368  success = FALSE;
369 
370  SCIPdebugMessage("solution has infinite values, create a copy with finite values\n");
371 
372  SCIP_CALL( SCIPcreateFiniteSolCopy(pricingprob, &newsol, probsols[0], &success) );
373  assert(success);
374  assert(newsol != NULL);
375 
376  SCIP_CALL( GCGcreateGcgColFromSol(pricingprob, &col, probnr, newsol, FALSE, SCIPinfinity(pricingprob)) );
377  SCIP_CALL( GCGpricerAddCol(scip, col) );
378  }
379  }
380 
381  return SCIP_OKAY;
382 }
383 
384 /** solves the given pricing problem as a sub-SCIP */
385 static
386 SCIP_RETCODE solveProblem(
387  SCIP* scip, /**< master problem SCIP data structure */
388  SCIP* pricingprob, /**< pricing problem SCIP data structure */
389  int probnr, /**< problem number */
390  GCG_SOLVERDATA* solverdata, /**< solver data structure */
391  SCIP_Real* lowerbound, /**< pointer to store lower bound */
392  GCG_PRICINGSTATUS* status /**< pointer to store pricing problem status */
393  )
394 {
395  GCG_COL* col;
396  SCIP_RETCODE retcode;
397 #ifdef SCIP_STATISTIC
398  SCIP_Longint oldnnodes;
399 #endif
400 
401  assert(scip != NULL);
402  assert(pricingprob != NULL);
403  assert(probnr >= 0);
404  assert(solverdata != NULL);
405  assert(lowerbound != NULL);
406  assert(status != NULL);
407 
408 #ifdef SCIP_STATISTIC
409  oldnnodes = SCIPgetNNodes(pricingprob);
410 #endif
411  /* solve the pricing SCIP */
412  retcode = SCIPsolve(pricingprob);
413  if( retcode != SCIP_OKAY )
414  {
415  SCIPwarningMessage(pricingprob, "Pricing problem %d terminated with retcode = %d, ignoring\n", probnr, retcode);
416  return SCIP_OKAY;
417  }
418 
419  SCIPdebugMessage(" -> status = %d\n", SCIPgetStatus(pricingprob));
420  SCIPdebugMessage(" -> nsols = %d\n", SCIPgetNSols(pricingprob));
421 
422 #ifdef SCIP_STATISTIC
423  SCIPstatisticMessage("P p %d: %"SCIP_LONGINT_FORMAT" no\n", probnr, SCIPgetNNodes(pricingprob) - oldnnodes);
424 #endif
425 
426  *status = getPricingstatus(pricingprob);
427 
428  assert(*status != GCG_PRICINGSTATUS_NOTAPPLICABLE);
429 
430  switch( *status )
431  {
433  SCIPdebugMessage(" -> infeasible.\n");
434  break;
435 
436  /* The pricing problem was declared to be unbounded and we should have a primal ray at hand,
437  * so copy the primal ray into the solution structure and mark it to be a primal ray
438  */
440  if( !SCIPhasPrimalRay(pricingprob) )
441  {
442  SCIP_CALL( resolvePricingWithoutPresolving(pricingprob) );
443  }
444 
445  SCIPdebugMessage(" -> unbounded, creating column from ray\n");
446  SCIP_CALL( createColumnFromRay(pricingprob, probnr, &col) );
447  SCIP_CALL( GCGpricerAddCol(scip, col) );
448 
449  break;
450 
451  /* If the pricing problem is neither infeasible nor unbounded, try to extract feasible columns */
455  assert(SCIPgetNSols(pricingprob) > 0
456  || (SCIPgetStatus(pricingprob) != SCIP_STATUS_OPTIMAL
457  && SCIPgetStatus(pricingprob) != SCIP_STATUS_GAPLIMIT
458  && SCIPgetStatus(pricingprob) != SCIP_STATUS_SOLLIMIT));
459 
460  /* Transform at most maxcols many solutions from the pricing problem into columns */
461  SCIP_CALL( getColumnsFromPricingprob(scip, pricingprob, probnr, solverdata->checksols) );
462 
463  *lowerbound = SCIPgetDualbound(pricingprob);
464 
465  SCIPdebugMessage(" -> lowerbound = %.4g\n", *lowerbound);
466  break;
467 
468  default:
469  SCIPerrorMessage("Pricing problem %d has invalid status: %d\n", probnr, SCIPgetStatus(pricingprob));
470  break; /*lint !e788 */
471  }
472 
473  return SCIP_OKAY;
474 }
475 
476 
477 /*
478  * Callback methods for pricing problem solver
479  */
480 
481 /** destructor of pricing solver to free user data (called when SCIP is exiting) */
482 static
483 GCG_DECL_SOLVERFREE(solverFreeMip)
484 {
485  GCG_SOLVERDATA* solverdata;
486 
487  assert(scip != NULL);
488  assert(solver != NULL);
489 
490  solverdata = GCGsolverGetData(solver);
491  assert(solverdata != NULL);
492 
493  SCIPfreeMemory(scip, &solverdata);
494 
495  GCGsolverSetData(solver, NULL);
496 
497  return SCIP_OKAY;
498 }
499 
500 /** initialization method of pricing solver (called after problem was transformed and solver is active) */
501 #define solverInitMip NULL
502 
503 /** deinitialization method of pricing solver (called before transformed problem is freed and solver is active) */
504 #define solverExitMip NULL
505 
506 /** solving process initialization method of pricing solver (called when branch and bound process is about to begin) */
507 static
508 GCG_DECL_SOLVERINITSOL(solverInitsolMip)
509 {
510  GCG_SOLVERDATA* solverdata;
511  int npricingprobs;
512  int i;
513 
514  assert(scip != NULL);
515  assert(solver != NULL);
516 
517  solverdata = GCGsolverGetData(solver);
518  assert(solverdata != NULL);
519 
520  npricingprobs = GCGgetNPricingprobs(GCGmasterGetOrigprob(scip));
521 
522  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &solverdata->curnodelimit, npricingprobs) );
523  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &solverdata->curstallnodelimit, npricingprobs) );
524  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &solverdata->curgaplimit, npricingprobs) );
525  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &solverdata->cursollimit, npricingprobs) );
526 
527  for( i = 0; i < npricingprobs; ++i )
528  {
529  solverdata->curnodelimit[i] = solverdata->startnodelimit;
530  solverdata->curstallnodelimit[i] = solverdata->startstallnodelimit;
531  solverdata->curgaplimit[i] = solverdata->startgaplimit;
532  solverdata->cursollimit[i] = solverdata->startsollimit;
533  }
534 
535  return SCIP_OKAY;
536 }
537 
538 /** solving process deinitialization method of pricing solver (called before branch and bound process data is freed) */
539 static
540 GCG_DECL_SOLVEREXITSOL(solverExitsolMip)
541 {
542  GCG_SOLVERDATA* solverdata;
543  int npricingprobs;
544 
545  assert(scip != NULL);
546  assert(solver != NULL);
547 
548  solverdata = GCGsolverGetData(solver);
549  assert(solverdata != NULL);
550 
551  npricingprobs = GCGgetNPricingprobs(GCGmasterGetOrigprob(scip));
552 
553  SCIPfreeBlockMemoryArray(scip, &solverdata->cursollimit, npricingprobs);
554  SCIPfreeBlockMemoryArray(scip, &solverdata->curgaplimit, npricingprobs);
555  SCIPfreeBlockMemoryArray(scip, &solverdata->curstallnodelimit, npricingprobs);
556  SCIPfreeBlockMemoryArray(scip, &solverdata->curnodelimit, npricingprobs);
557 
558  return SCIP_OKAY;
559 }
560 
561 #define solverUpdateMip NULL
562 
563 /** solving method for pricing solver which solves the pricing problem to optimality */
564 static
565 GCG_DECL_SOLVERSOLVE(solverSolveMip)
566 { /*lint --e{715}*/
567  GCG_SOLVERDATA* solverdata;
568 
569  solverdata = GCGsolverGetData(solver);
570  assert(solverdata != NULL);
571 
572  if( strcmp(solverdata->settingsfile, "-") != 0 )
573  {
574  SCIP_CALL( SCIPreadParams(pricingprob, solverdata->settingsfile) );
575  }
576 
577  SCIP_CALL( SCIPsetLongintParam(pricingprob, "limits/stallnodes", -1LL) );
578  SCIP_CALL( SCIPsetLongintParam(pricingprob, "limits/nodes", -1LL) );
579  SCIP_CALL( SCIPsetRealParam(pricingprob, "limits/gap", 0.0) );
580  SCIP_CALL( SCIPsetIntParam(pricingprob, "limits/solutions", -1) );
581 
582 #ifdef DEBUG_PRICING_ALL_OUTPUT
583  SCIP_CALL( SCIPsetIntParam(pricingprob, "display/verblevel", SCIP_VERBLEVEL_HIGH) );
584  SCIP_CALL( SCIPwriteParams(pricingprob, "pricing.set", TRUE, TRUE) );
585 #endif
586 
587  *lowerbound = -SCIPinfinity(pricingprob);
588 
589  SCIPdebugMessage("Solving pricing %d (pointer: %p)\n", probnr, (void*)pricingprob);
590  SCIP_CALL( solveProblem(scip, pricingprob, probnr, solverdata, lowerbound, status) );
591 
592 #ifdef DEBUG_PRICING_ALL_OUTPUT
593  SCIP_CALL( SCIPsetIntParam(pricingprob, "display/verblevel", 0) );
594  SCIP_CALL( SCIPprintStatistics(pricingprob, NULL) );
595 #endif
596 
597  return SCIP_OKAY;
598 }
599 
600 /** heuristic solving method of mip solver */
601 static
602 GCG_DECL_SOLVERSOLVEHEUR(solverSolveHeurMip)
603 { /*lint --e{715}*/
604  GCG_SOLVERDATA* solverdata;
605 
606 #ifdef DEBUG_PRICING_ALL_OUTPUT
607  SCIP_CALL( SCIPsetIntParam(pricingprob, "display/verblevel", SCIP_VERBLEVEL_HIGH) );
608 #endif
609 
610  solverdata = GCGsolverGetData(solver);
611  assert(solverdata != NULL);
612 
613  *lowerbound = -SCIPinfinity(pricingprob);
614 
615  /* setup heuristic solver parameters */
616  if( SCIPgetStage(pricingprob) == SCIP_STAGE_PROBLEM )
617  {
618  solverdata->curnodelimit[probnr] = solverdata->startnodelimit;
619  solverdata->curstallnodelimit[probnr] = solverdata->startstallnodelimit;
620  solverdata->curgaplimit[probnr] = solverdata->startgaplimit;
621  solverdata->cursollimit[probnr] = solverdata->startsollimit;
622  }
623  else
624  {
625  if( SCIPgetStatus(pricingprob) == SCIP_STATUS_NODELIMIT )
626  {
627  if( solverdata->nodelimitfac > 1.0 )
628  solverdata->curnodelimit[probnr] = (SCIP_Longint) (solverdata->curnodelimit[probnr] * solverdata->nodelimitfac);
629  else
630  solverdata->curnodelimit[probnr] += solverdata->startnodelimit;
631  }
632  else if( SCIPgetStatus(pricingprob) == SCIP_STATUS_STALLNODELIMIT )
633  {
634  if( solverdata->stallnodelimitfac > 1.0 )
635  solverdata->curstallnodelimit[probnr] = (SCIP_Longint) (solverdata->curstallnodelimit[probnr] * solverdata->stallnodelimitfac);
636  else
637  solverdata->curstallnodelimit[probnr] += solverdata->startstallnodelimit;
638  }
639  else if( SCIPgetStatus(pricingprob) == SCIP_STATUS_GAPLIMIT )
640  {
641  if( solverdata->gaplimitfac < 1.0 )
642  solverdata->curgaplimit[probnr] *= solverdata->gaplimitfac;
643  else
644  solverdata->curgaplimit[probnr] = MAX(solverdata->curgaplimit[probnr] - solverdata->startgaplimit, 0.0);
645  }
646  else if( SCIPgetStatus(pricingprob) == SCIP_STATUS_SOLLIMIT )
647  {
648  if( solverdata->sollimitfac > 1.0 )
649  solverdata->cursollimit[probnr] = (int) (solverdata->cursollimit[probnr] * solverdata->sollimitfac);
650  else
651  solverdata->cursollimit[probnr] += solverdata->startsollimit;
652  }
653  else
654  {
655  *status = GCG_PRICINGSTATUS_UNKNOWN;
656  return SCIP_OKAY;
657  }
658  }
659  SCIP_CALL( SCIPsetLongintParam(pricingprob, "limits/nodes", solverdata->curnodelimit[probnr]) );
660  SCIP_CALL( SCIPsetLongintParam(pricingprob, "limits/stallnodes", solverdata->curstallnodelimit[probnr]) );
661  SCIP_CALL( SCIPsetRealParam(pricingprob, "limits/gap", solverdata->curgaplimit[probnr]) );
662  SCIP_CALL( SCIPsetIntParam(pricingprob, "limits/solutions", solverdata->cursollimit[probnr]) );
663 
664  /* solve the pricing problem */
665  SCIPdebugMessage("Solving pricing %d heuristically (pointer: %p)\n", probnr, (void*)pricingprob);
666  SCIP_CALL( solveProblem(scip, pricingprob, probnr, solverdata, lowerbound, status) );
667 
668 #ifdef DEBUG_PRICING_ALL_OUTPUT
669  SCIP_CALL( SCIPsetIntParam(pricingprob, "display/verblevel", 0) );
670  SCIP_CALL( SCIPprintStatistics(pricingprob, NULL) );
671 #endif
672 
673  return SCIP_OKAY;
674 }
675 
676 /** creates the mip solver for pricing problems and includes it in GCG */
677 SCIP_RETCODE GCGincludeSolverMip(
678  SCIP* scip /**< SCIP data structure */
679  )
680 {
681  SCIP* origprob;
682  GCG_SOLVERDATA* solverdata;
683 
684  origprob = GCGmasterGetOrigprob(scip);
685 
686  SCIP_CALL( SCIPallocMemory(scip, &solverdata) );
687  solverdata->settingsfile = NULL;
688 
691  solverUpdateMip, solverSolveMip, solverSolveHeurMip, solverFreeMip, solverInitMip, solverExitMip,
692  solverInitsolMip, solverExitsolMip, solverdata) );
693 
694  SCIP_CALL( SCIPaddBoolParam(origprob, "pricingsolver/mip/checksols",
695  "should solutions of the pricing MIPs be checked for duplicity?",
696  &solverdata->checksols, TRUE, DEFAULT_CHECKSOLS, NULL, NULL) );
697 
698  SCIP_CALL( SCIPaddLongintParam(origprob, "pricingsolver/mip/startnodelimit",
699  "start node limit for heuristic pricing",
700  &solverdata->startnodelimit, TRUE, DEFAULT_STARTNODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
701 
702  SCIP_CALL( SCIPaddLongintParam(origprob, "pricingsolver/mip/startstallnodelimit",
703  "start stalling node limit for heuristic pricing",
704  &solverdata->startstallnodelimit, TRUE, DEFAULT_STARTSTALLNODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
705 
706  SCIP_CALL( SCIPaddRealParam(origprob, "pricingsolver/mip/startgaplimit",
707  "start gap limit for heuristic pricing",
708  &solverdata->startgaplimit, TRUE, DEFAULT_STARTGAPLIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
709 
710  SCIP_CALL( SCIPaddIntParam(origprob, "pricingsolver/mip/startsollimit",
711  "start solution limit for heuristic pricing",
712  &solverdata->startsollimit, TRUE, DEFAULT_STARTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
713 
714  SCIP_CALL( SCIPaddRealParam(origprob, "pricingsolver/mip/nodelimitfac",
715  "factor by which to increase node limit for heuristic pricing (1.0: add start limit)",
716  &solverdata->nodelimitfac, TRUE, DEFAULT_NODELIMITFAC, 1.0, SCIPinfinity(origprob), NULL, NULL) );
717 
718  SCIP_CALL( SCIPaddRealParam(origprob, "pricingsolver/mip/stallnodelimitfac",
719  "factor by which to increase stalling node limit for heuristic pricing (1.0: add start limit)",
720  &solverdata->stallnodelimitfac, TRUE, DEFAULT_STALLNODELIMITFAC, 1.0, SCIPinfinity(origprob), NULL, NULL) );
721 
722  SCIP_CALL( SCIPaddRealParam(origprob, "pricingsolver/mip/gaplimitfac",
723  "factor by which to decrease gap limit for heuristic pricing (1.0: subtract start limit)",
724  &solverdata->gaplimitfac, TRUE, DEFAULT_GAPLIMITFAC, 0.0, 1.0, NULL, NULL) );
725 
726  SCIP_CALL( SCIPaddRealParam(origprob, "pricingsolver/mip/sollimitfac",
727  "factor by which to increase solution limit for heuristic pricing (1.0: add start limit)",
728  &solverdata->sollimitfac, TRUE, DEFAULT_SOLLIMITFAC, 1.0, SCIPinfinity(origprob), NULL, NULL) );
729 
730  SCIP_CALL( SCIPaddStringParam(origprob, "pricingsolver/mip/settingsfile",
731  "settings file for pricing problems",
732  &solverdata->settingsfile, TRUE, DEFAULT_SETTINGSFILE, NULL, NULL) );
733 
734 
735  return SCIP_OKAY;
736 }
SCIP_Real stallnodelimitfac
Definition: solver_mip.c:80
int * cursollimit
Definition: solver_mip.c:89
SCIP_RETCODE GCGcreateGcgCol(SCIP *pricingprob, GCG_COL **gcgcol, int probnr, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Bool isray, SCIP_Real redcost)
Definition: gcgcol.c:52
GCG interface methods.
#define DEFAULT_GAPLIMITFAC
Definition: solver_mip.c:64
#define SOLVER_DESC
Definition: solver_mip.c:52
SCIP_EXPORT void GCGsolverSetData(GCG_SOLVER *solver, GCG_SOLVERDATA *solverdata)
Definition: solver.c:387
#define DEFAULT_CHECKSOLS
Definition: solver_mip.c:57
static SCIP_RETCODE resolvePricingWithoutPresolving(SCIP *pricingprob)
Definition: solver_mip.c:156
#define DEFAULT_SETTINGSFILE
Definition: solver_mip.c:66
@ GCG_PRICINGSTATUS_UNBOUNDED
public methods for working with gcg columns
SCIP_Real * curgaplimit
Definition: solver_cplex.c:92
SCIP_RETCODE GCGcreateGcgColFromSol(SCIP *pricingprob, GCG_COL **gcgcol, int prob, SCIP_SOL *sol, SCIP_Bool isray, SCIP_Real redcost)
Definition: gcgcol.c:154
static GCG_DECL_SOLVERSOLVEHEUR(solverSolveHeurMip)
Definition: solver_mip.c:602
char * settingsfile
Definition: solver_mip.c:83
#define DEFAULT_STARTNODELIMIT
Definition: solver_mip.c:58
#define solverUpdateMip
Definition: solver_mip.c:561
int GCGgetNPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3979
SCIP_Longint startstallnodelimit
Definition: solver_mip.c:76
GCG variable pricer.
enum GCG_PricingStatus GCG_PRICINGSTATUS
#define DEFAULT_STARTSTALLNODELIMIT
Definition: solver_mip.c:59
#define DEFAULT_STARTSOLLIMIT
Definition: solver_mip.c:61
static SCIP_RETCODE createColumnFromRay(SCIP *pricingprob, int probnr, GCG_COL **newcol)
Definition: solver_mip.c:99
#define solverExitMip
Definition: solver_mip.c:504
static SCIP_RETCODE solveProblem(SCIP *scip, SCIP *pricingprob, int probnr, GCG_SOLVERDATA *solverdata, SCIP_Real *lowerbound, GCG_PRICINGSTATUS *status)
Definition: solver_mip.c:386
@ GCG_PRICINGSTATUS_SOLVERLIMIT
@ GCG_PRICINGSTATUS_NOTAPPLICABLE
@ GCG_PRICINGSTATUS_INFEASIBLE
@ GCG_PRICINGSTATUS_OPTIMAL
SCIP_Real gaplimitfac
Definition: solver_cplex.c:110
static GCG_DECL_SOLVERFREE(solverFreeMip)
Definition: solver_mip.c:483
SCIP_Longint startsollimit
Definition: solver_cplex.c:108
static GCG_PRICINGSTATUS getPricingstatus(SCIP *pricingprob)
Definition: solver_mip.c:232
#define DEFAULT_STARTGAPLIMIT
Definition: solver_mip.c:60
SCIP_RETCODE GCGincludeSolverMip(SCIP *scip)
Definition: solver_mip.c:677
SCIP_EXPORT GCG_SOLVERDATA * GCGsolverGetData(GCG_SOLVER *solver)
Definition: solver.c:377
#define SOLVER_NAME
Definition: solver_mip.c:51
static GCG_DECL_SOLVERINITSOL(solverInitsolMip)
Definition: solver_mip.c:508
#define DEFAULT_SOLLIMITFAC
Definition: solver_mip.c:65
SCIP_RETCODE GCGpricerIncludeSolver(SCIP *scip, const char *name, const char *desc, int priority, SCIP_Bool heurenabled, SCIP_Bool exactenabled, GCG_DECL_SOLVERUPDATE((*solverupdate)), GCG_DECL_SOLVERSOLVE((*solversolve)), GCG_DECL_SOLVERSOLVEHEUR((*solversolveheur)), GCG_DECL_SOLVERFREE((*solverfree)), GCG_DECL_SOLVERINIT((*solverinit)), GCG_DECL_SOLVEREXIT((*solverexit)), GCG_DECL_SOLVERINITSOL((*solverinitsol)), GCG_DECL_SOLVEREXITSOL((*solverexitsol)), GCG_SOLVERDATA *solverdata)
SCIP * GCGmasterGetOrigprob(SCIP *scip)
static SCIP_RETCODE getColumnsFromPricingprob(SCIP *scip, SCIP *pricingprob, int probnr, SCIP_Bool checksols)
Definition: solver_mip.c:316
#define DEFAULT_STALLNODELIMITFAC
Definition: solver_mip.c:63
SCIP_Real startgaplimit
Definition: solver_cplex.c:107
static SCIP_RETCODE checkSolNew(SCIP *pricingprob, SCIP_SOL **sols, int idx, SCIP_Bool *isnew)
Definition: solver_mip.c:173
#define solverInitMip
Definition: solver_mip.c:501
#define SOLVER_HEURENABLED
Definition: solver_mip.c:54
@ GCG_PRICINGSTATUS_UNKNOWN
SCIP_Real sollimitfac
Definition: solver_cplex.c:111
SCIP_RETCODE GCGpricerAddCol(SCIP *scip, GCG_COL *col)
#define SOLVER_PRIORITY
Definition: solver_mip.c:53
SCIP_Longint * curstallnodelimit
Definition: solver_mip.c:87
SCIP_Bool checksols
Definition: solver_cplex.c:104
static SCIP_Bool solutionHasInfiniteValue(SCIP *pricingprob, SCIP_SOL *sol)
Definition: solver_mip.c:294
SCIP_Longint * curnodelimit
Definition: solver_cplex.c:91
SCIP_Longint * cursollimit
Definition: solver_cplex.c:93
static GCG_DECL_SOLVERSOLVE(solverSolveMip)
Definition: solver_mip.c:565
static GCG_DECL_SOLVEREXITSOL(solverExitsolMip)
Definition: solver_mip.c:540
SCIP_Real nodelimitfac
Definition: solver_cplex.c:109
SCIP_Longint startnodelimit
Definition: solver_cplex.c:106
#define SOLVER_EXACTENABLED
Definition: solver_mip.c:55
mip solver for pricing problems
#define DEFAULT_NODELIMITFAC
Definition: solver_mip.c:62