Scippy

GCG

Branch-and-Price & Column Generation for Everyone

solver_cplex.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_cplex.c
29  * @brief cplex solver for pricing problems
30  * @author Gerald Gamrath
31  * @author Alexander Gross
32  * @author Hanna Franzen
33  * @author Christian Puchert
34  */
35 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 /* #define DEBUG_PRICING_ALL_OUTPUT */
38 
39 #include <string.h>
40 
41 #include "scip/scip.h"
42 #include "gcg.h"
43 #include "solver_cplex.h"
44 #include "pub_solver.h"
45 #include "pub_gcgcol.h"
46 
47 #include "pricer_gcg.h"
48 #include "scip_misc.h"
49 
50 #include "cplex.h"
51 
52 #define CHECK_ZERO(x) { int _restat_; \
53  if( (_restat_ = (x)) != 0 ) \
54  { \
55  SCIPerrorMessage("Error in pricing solver: CPLEX returned %d\n", _restat_); \
56  retval = SCIP_INVALIDRESULT; \
57  goto TERMINATE; \
58  } \
59  }
60 
61 #define CPX_LONG_MAX 9223372036800000000LL
62 
63 
64 #define SOLVER_NAME "cplex"
65 #define SOLVER_DESC "cplex solver for pricing problems"
66 #define SOLVER_PRIORITY 100
67 #define SOLVER_HEURENABLED TRUE /**< indicates whether the heuristic solving method of the solver should be enabled */
68 #define SOLVER_EXACTENABLED TRUE /**< indicates whether the exact solving method of the solver should be enabled */
69 
70 #define DEFAULT_CHECKSOLS TRUE /**< should solutions of the pricing MIPs be checked for duplicity? */
71 #define DEFAULT_THREADS 1 /**< number of threads the CPLEX pricing solver is allowed to use (0: automatic) */
72 #define DEFAULT_STARTNODELIMIT 1000LL /**< start node limit for heuristic pricing */
73 #define DEFAULT_STARTGAPLIMIT 0.2 /**< start gap limit for heuristic pricing */
74 #define DEFAULT_STARTSOLLIMIT 10LL /**< start solution limit for heuristic pricing */
75 #define DEFAULT_NODELIMITFAC 1.25 /**< factor by which to increase node limit for heuristic pricing (1.0: add start limit) */
76 #define DEFAULT_STALLNODELIMITFAC 1.25 /**< factor by which to increase stalling node limit for heuristic pricing */
77 #define DEFAULT_GAPLIMITFAC 0.8 /**< factor by which to decrease gap limit for heuristic pricing (1.0: subtract start limit) */
78 #define DEFAULT_SOLLIMITFAC 1.5 /**< factor by which to increase solution limit for heuristic pricing (1.0: add start limit) */
79 
80 
81 /** pricing solver data */
82 struct GCG_SolverData
83 {
84  SCIP* origprob; /**< original problem SCIP instance */
85  SCIP* masterprob; /**< master problem SCIP instance */
86  SCIP** pricingprobs; /**< array storing the SCIP instances for all pricing problems */
87  int npricingprobs; /**< number of pricing problems */
88  CPXENVptr* cpxenv; /**< array of CPLEX environments for the pricing problems */
89  CPXLPptr* lp; /**< array of CPLEX problems for the pricing problems */
90  int* nupdates; /**< array storing the number of updates for all of the pricing problems */
91  SCIP_Longint* curnodelimit; /**< current node limit per pricing problem */
92  SCIP_Real* curgaplimit; /**< current gap limit per pricing problem */
93  SCIP_Longint* cursollimit; /**< current solution limit per pricing problem */
94  /**
95  * information about the basic pricing problem (without potential branching constraints)
96  */
97  SCIP_VAR*** pricingvars; /**< array storing the variables of the pricing problems */
98  SCIP_CONS*** pricingconss; /**< array storing the constraints of the pricing problems */
99  int* npricingvars; /**< array storing the number of variables of the pricing problems */
100  int* nbasicpricingconss; /**< array storing the basic number of constraints of the pricing problems */
101  /**
102  * parameters
103  */
104  SCIP_Bool checksols; /**< should solutions of the pricing MIPs be checked for duplicity? */
105  int threads; /**< number of threads the CPLEX pricing solver is allowed to use (0: automatic) */
106  SCIP_Longint startnodelimit; /**< start node limit for heuristic pricing */
107  SCIP_Real startgaplimit; /**< start gap limit for heuristic pricing */
108  SCIP_Longint startsollimit; /**< start solution limit for heuristic pricing */
109  SCIP_Real nodelimitfac; /**< factor by which to increase node limit for heuristic pricing (1.0: add start limit) */
110  SCIP_Real gaplimitfac; /**< factor by which to decrease gap limit for heuristic pricing (1.0: subtract start limit) */
111  SCIP_Real sollimitfac; /**< factor by which to increase solution limit for heuristic pricing (1.0: add start limit) */
112 };
113 
114 /*
115  * local methods
116  */
117 
118 /** creates a CPLEX environment and builds the pricing problem */
119 static
120 SCIP_RETCODE buildProblem(
121  SCIP* scip, /**< SCIP data structure */
122  GCG_SOLVERDATA* solverdata, /**< solver data structure */
123  SCIP* pricingprob, /**< pricing problem */
124  int probnr /**< problem number */
125  )
126 {
127  SCIP_CONS** conss;
128  SCIP_VAR** vars;
129  SCIP_VAR** consvars;
130  SCIP_Real* consvals;
131  SCIP_VAR* var;
132  double* varobj;
133  double* varlb;
134  double* varub;
135  char* vartype;
136  char** varnames = NULL;
137  char** consnames = NULL;
138  double* rhss;
139  double* ranges;
140  char* senses;
141  double* coefs = NULL;
142  int* rowidx;
143  int* colidx;
144  SCIP_Real lhs;
145  SCIP_Real rhs;
146  SCIP_VARTYPE type;
147  SCIP_RETCODE retval;
148  int nconss = 0;
149  int nvars = 0;
150  int status;
151  int varidx;
152  int nconsvars;
153  int nnonzeros;
154  int idx;
155  int c;
156  int i;
157  int v;
158 
159  /* open CPLEX environment and create problem */
160  solverdata->cpxenv[probnr] = CPXopenCPLEX(&status);
161  solverdata->lp[probnr] = CPXcreateprob(solverdata->cpxenv[probnr], &status, SCIPgetProbName(pricingprob));
162  solverdata->pricingprobs[probnr] = pricingprob;
163 
164  retval = SCIP_OKAY;
165 
166  /* set parameters */
167  CHECK_ZERO( CPXsetdblparam(solverdata->cpxenv[probnr], CPX_PARAM_EPGAP, 0.0) );
168  CHECK_ZERO( CPXsetdblparam(solverdata->cpxenv[probnr], CPX_PARAM_EPAGAP, 0.0) );
169  CHECK_ZERO( CPXsetdblparam(solverdata->cpxenv[probnr], CPX_PARAM_EPRHS, SCIPfeastol(pricingprob)) );
170  CHECK_ZERO( CPXsetdblparam(solverdata->cpxenv[probnr], CPX_PARAM_EPINT, SCIPfeastol(pricingprob)) );
171  CHECK_ZERO( CPXsetintparam(solverdata->cpxenv[probnr], CPX_PARAM_THREADS, solverdata->threads) );
172 #ifdef DEBUG_PRICING_ALL_OUTPUT
173  CHECK_ZERO( CPXsetintparam(solverdata->cpxenv[probnr], CPX_PARAM_SCRIND, CPX_ON) );
174 #endif
175 
176  /* set objective sense */
177  assert(SCIPgetObjsense(pricingprob) == SCIP_OBJSENSE_MINIMIZE);
178 #if (CPX_VERSION_VERSION == 12 && CPX_VERSION_RELEASE >= 5) || CPX_VERSION_VERSION > 12
179  CHECK_ZERO( CPXchgobjsen(solverdata->cpxenv[probnr], solverdata->lp[probnr], CPX_MIN) );
180 #else
181  CPXchgobjsen(solverdata->cpxenv[probnr], solverdata->lp[probnr], CPX_MIN);
182 #endif
183 
184  conss = SCIPgetOrigConss(pricingprob);
185  nconss = SCIPgetNOrigConss(pricingprob);
186  vars = SCIPgetOrigVars(pricingprob);
187  nvars = SCIPgetNOrigVars(pricingprob);
188 
189  /* arrays for storing the basic constraints and variables */
190  solverdata->npricingvars[probnr] = nvars;
191  solverdata->nbasicpricingconss[probnr] = nconss;
192 
193  SCIP_CALL( SCIPallocMemoryArray(scip, &solverdata->pricingvars[probnr], nvars) ); /*lint !e866*/
194  SCIP_CALL( SCIPallocMemoryArray(scip, &solverdata->pricingconss[probnr], nconss) ); /*lint !e866*/
195 
196  /* temporary memory for storing all data about the variables */
197  SCIP_CALL( SCIPallocBufferArray(scip, &varobj, nvars) );
198  SCIP_CALL( SCIPallocBufferArray(scip, &vartype, nvars) );
199  SCIP_CALL( SCIPallocBufferArray(scip, &varlb, nvars) );
200  SCIP_CALL( SCIPallocBufferArray(scip, &varub, nvars) );
201  SCIP_CALL( SCIPallocBufferArray(scip, &varnames, nvars) );
202 
203  /* temporary memory for storing data about the constraints */
204  SCIP_CALL( SCIPallocBufferArray(scip, &rhss, nconss) );
205  SCIP_CALL( SCIPallocBufferArray(scip, &senses, nconss) );
206  SCIP_CALL( SCIPallocBufferArray(scip, &ranges, nconss) );
207  SCIP_CALL( SCIPallocBufferArray(scip, &consnames, nconss) );
208 
209  BMSclearMemoryArray(consnames, nconss);
210  BMSclearMemoryArray(varnames, nvars);
211 
212  /* collect information about variables: bounds, objective function, name, type */
213  for( i = 0; i < nvars; i++ )
214  {
215  var = vars[i];
216  varidx = SCIPvarGetIndex(var);
217  assert(0 <= varidx);
218  assert(varidx < nvars);
219  solverdata->pricingvars[probnr][varidx] = var;
220  SCIP_CALL( SCIPcaptureVar(pricingprob, var) );
221 
222  varlb[varidx] = SCIPvarGetLbLocal(var);
223  varub[varidx] = SCIPvarGetUbLocal(var);
224  varobj[varidx] = SCIPvarGetObj(var);
225  SCIP_CALL( SCIPduplicateBufferArray(scip, &varnames[varidx], SCIPvarGetName(var),
226  (int)(strlen(SCIPvarGetName(var))+1)) ); /*lint !e866*/
227 
228  type = SCIPvarGetType(var);
229 
230  switch( type )
231  {
232  case SCIP_VARTYPE_BINARY:
233  vartype[varidx] = 'B';
234  break;
235  case SCIP_VARTYPE_CONTINUOUS:
236  vartype[varidx] = 'C';
237  break;
238  case SCIP_VARTYPE_INTEGER:
239  case SCIP_VARTYPE_IMPLINT:
240  vartype[varidx] = 'I';
241  break;
242  default:
243  SCIPerrorMessage("invalid variable type\n");
244  return SCIP_INVALIDDATA;
245  }
246  }
247 
248  /* collect right hand sides and ranges of the constraints, count total number of nonzeros */
249  nnonzeros = 0;
250  for( c = 0; c < nconss; ++c )
251  {
252  solverdata->pricingconss[probnr][c] = conss[c];
253  SCIP_CALL( SCIPcaptureCons(pricingprob, conss[c]) );
254 
255  nnonzeros += GCGconsGetNVars(scip, conss[c]);
256  lhs = GCGconsGetLhs(pricingprob, conss[c]);
257  rhs = GCGconsGetRhs(pricingprob, conss[c]);
258  SCIP_CALL( SCIPduplicateBufferArray(scip, &consnames[c], SCIPconsGetName(conss[c]),
259  (int)(strlen(SCIPconsGetName(conss[c]))+1)) ); /*lint !e866*/
260 
261  if( SCIPisInfinity(scip, -lhs) )
262  {
263  senses[c] = 'L';
264  rhss[c] = (double) rhs;
265  ranges[c] = 0.0;
266  }
267  else if( SCIPisInfinity(scip, rhs) )
268  {
269  senses[c] = 'G';
270  rhss[c] = (double) lhs;
271  ranges[c] = 0.0;
272  }
273  else if( SCIPisEQ(scip, lhs, rhs) )
274  {
275  senses[c] = 'E';
276  rhss[c] = (double) lhs;
277  ranges[c] = 0.0;
278  }
279  else
280  {
281  assert(SCIPisLT(scip, lhs, rhs));
282  senses[c] = 'R';
283  rhss[c] = (double) lhs;
284  ranges[c] = (double) (rhs - lhs);
285  }
286  }
287 
288  /* temporary memory for storing data about coefficients in the constraints */
289  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) );
290  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nvars) );
291 
292  /* temporary memory for storing nonzeros */
293  SCIP_CALL( SCIPallocBufferArray(scip, &rowidx, nnonzeros) );
294  SCIP_CALL( SCIPallocBufferArray(scip, &colidx, nnonzeros) );
295  SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nnonzeros) );
296 
297  /* collect nonzeros */
298  for( c = 0, idx = 0; c < nconss; ++c )
299  {
300  nconsvars = GCGconsGetNVars(scip, conss[c]);
301  SCIP_CALL( GCGconsGetVals(pricingprob, conss[c], consvals, nvars) );
302  SCIP_CALL( GCGconsGetVars(pricingprob, conss[c], consvars, nvars) );
303 
304  /* get coefficients */
305  for( v = 0; v < nconsvars; ++v )
306  {
307  rowidx[idx] = c;
308  colidx[idx] = SCIPvarGetIndex(consvars[v]);
309  coefs[idx] = (double)consvals[v];
310  idx++;
311  }
312  }
313  assert(idx == nnonzeros);
314 
315  /* add variables to CPLEX problem */
316  CHECK_ZERO( CPXnewcols(solverdata->cpxenv[probnr], solverdata->lp[probnr], nvars, varobj, varlb, varub, vartype, varnames) );
317 
318  /* add empty constraints to CPLEX problem */
319  CHECK_ZERO( CPXnewrows(solverdata->cpxenv[probnr], solverdata->lp[probnr], nconss, rhss, senses, ranges, consnames) );
320 
321  /* add variables to constraints in CPLEX problem */
322  CHECK_ZERO( CPXchgcoeflist(solverdata->cpxenv[probnr], solverdata->lp[probnr], nnonzeros, rowidx, colidx, coefs) );
323 
324 #ifdef WRITEPROBLEMS
325  {
326  char filename[SCIP_MAXSTRLEN];
327  (void) SCIPsnprintf(filename, SCIP_MAXSTRLEN, "cplex-%s.lp", SCIPgetProbName(pricingprob));
328  SCIPinfoMessage(pricingprob, NULL, "print pricing problem to %s\n", filename);
329  CHECK_ZERO( CPXwriteprob(solverdata->cpxenv[probnr], solverdata->lp[probnr], filename, "lp") );
330  }
331 #endif
332 
333  TERMINATE:
334  /* free temporary memory */
335  if( coefs != NULL )
336  {
337  SCIPfreeBufferArray(scip, &coefs);
338  SCIPfreeBufferArray(scip, &colidx);
339  SCIPfreeBufferArray(scip, &rowidx);
340 
341  SCIPfreeBufferArray(scip, &consvals);
342  SCIPfreeBufferArray(scip, &consvars);
343 
344  for( v = nvars - 1; v >= 0; --v )
345  {
346  assert(varnames != NULL);
347  SCIPfreeBufferArrayNull(scip, &varnames[v]);
348  }
349 
350  for( c = nconss - 1; c >= 0; --c )
351  {
352  assert(consnames != NULL);
353  SCIPfreeBufferArrayNull(scip, &consnames[c]);
354  }
355 
356  SCIPfreeBufferArray(scip, &consnames);
357  SCIPfreeBufferArray(scip, &ranges);
358  SCIPfreeBufferArray(scip, &senses);
359  SCIPfreeBufferArray(scip, &rhss);
360 
361  SCIPfreeBufferArray(scip, &varnames);
362  SCIPfreeBufferArray(scip, &varub);
363  SCIPfreeBufferArray(scip, &varlb);
364  SCIPfreeBufferArray(scip, &vartype);
365  SCIPfreeBufferArray(scip, &varobj);
366  }
367 
368  return retval;
369 }
370 
371 
372 /** updates bounds and objective coefficients of variables in the given pricing problem */
373 static
374 SCIP_RETCODE updateVars(
375  SCIP* scip, /**< SCIP data structure */
376  GCG_SOLVERDATA* solverdata, /**< solver data structure */
377  SCIP* pricingprob, /**< pricing problem */
378  int probnr, /**< problem number */
379  SCIP_Bool varobjschanged, /**< have the objective coefficients changed? */
380  SCIP_Bool varbndschanged /**< have the lower and upper bounds changed? */
381  )
382 {
383  SCIP_VAR** vars;
384  double* varobj;
385  double* bounds;
386  int* objidx;
387  int* updatevaridx;
388  char* boundtypes;
389  int nvars;
390  int npricingvars;
391 
392  SCIP_RETCODE retval;
393  int i;
394 
395  vars = SCIPgetOrigVars(pricingprob);
396  nvars = SCIPgetNOrigVars(pricingprob);
397  npricingvars = solverdata->npricingvars[probnr];
398 
399  assert(npricingvars == nvars);
400  assert(npricingvars == CPXgetnumcols(solverdata->cpxenv[probnr], solverdata->lp[probnr]));
401 
402  retval = SCIP_OKAY;
403 
404  if( varobjschanged )
405  {
406  SCIP_CALL( SCIPallocBufferArray(scip, &objidx, npricingvars) );
407  SCIP_CALL( SCIPallocBufferArray(scip, &varobj, npricingvars) );
408  }
409 
410  if( varbndschanged)
411  {
412  SCIP_CALL( SCIPallocBufferArray(scip, &updatevaridx, 2 * npricingvars) );
413  SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, 2 * npricingvars) );
414  SCIP_CALL( SCIPallocBufferArray(scip, &bounds, 2 * npricingvars) );
415  }
416 
417  /* get new bounds and objective coefficients of variables */
418  for( i = 0; i < nvars; i++ )
419  {
420  SCIP_VAR* origvar;
421  SCIP_VAR* var;
422  int varidx;
423 
424  origvar = vars[i];
425  varidx = SCIPvarGetIndex(origvar);
426  assert(0 <= varidx);
427  assert(varidx < npricingvars);
428 
429  if( SCIPgetStage(pricingprob) >= SCIP_STAGE_TRANSFORMED )
430  var = SCIPvarGetTransVar(origvar);
431  else
432  var = origvar;
433 
434  updatevaridx[2 * (size_t)varidx] = varidx;
435  updatevaridx[2 * (size_t)varidx + 1] = varidx;
436 
437  if( varbndschanged )
438  {
439  boundtypes[2 * (size_t)varidx] = 'L';
440  boundtypes[2 * (size_t)varidx + 1] = 'U';
441  bounds[2 * (size_t)varidx] = (double) SCIPvarGetLbGlobal(var);
442  bounds[2 * (size_t)varidx + 1] = (double) SCIPvarGetUbGlobal(var);
443  }
444 
445  if( varobjschanged )
446  {
447  objidx[varidx] = varidx;
448  varobj[varidx] = SCIPvarGetObj(origvar);
449  }
450  }
451 
452  /* update bounds and objective coefficient of basic variables */
453  if( varbndschanged )
454  {
455  CHECK_ZERO( CPXchgbds(solverdata->cpxenv[probnr], solverdata->lp[probnr], 2 * nvars, updatevaridx, boundtypes, bounds) );
456  }
457  if( varobjschanged )
458  {
459  CHECK_ZERO( CPXchgobj(solverdata->cpxenv[probnr], solverdata->lp[probnr], nvars, objidx, varobj) );
460  }
461 
462 TERMINATE:
463  if( varbndschanged )
464  {
465  SCIPfreeBufferArray(scip, &bounds);
466  SCIPfreeBufferArray(scip, &boundtypes);
467  SCIPfreeBufferArray(scip, &updatevaridx);
468  }
469  if( varobjschanged)
470  {
471  SCIPfreeBufferArray(scip, &varobj);
472  SCIPfreeBufferArray(scip, &objidx);
473  }
474 
475  return retval;
476 }
477 
478 /** updates branching constraints in the given pricing problem */
479 static
480 SCIP_RETCODE updateBranchingConss(
481  SCIP* scip, /**< SCIP data structure */
482  GCG_SOLVERDATA* solverdata, /**< solver data structure */
483  SCIP* pricingprob, /**< pricing problem */
484  int probnr /**< problem number */
485  )
486 {
487  SCIP_CONS** conss;
488  SCIP_VAR** consvars;
489  SCIP_Real* consvals;
490  char** newconsnames = NULL;
491  char* newsenses;
492  double* newrhss;
493  double* newranges;
494  double* newcoefs;
495  int* newrowidx;
496  int* newcolidx;
497  int nconss;
498  int nbasicpricingconss;
499  int ncpxrows;
500  int nnewconss = 0;
501  int nnonzeros;
502  int nvars;
503 
504  SCIP_RETCODE retval;
505  int idx;
506  int c;
507 
508  conss = SCIPgetOrigConss(pricingprob);
509  nconss = SCIPgetNOrigConss(pricingprob);
510  nbasicpricingconss = solverdata->nbasicpricingconss[probnr];
511 
512  nvars = SCIPgetNOrigVars(pricingprob);
513 
514  retval = SCIP_OKAY;
515 
516  ncpxrows = CPXgetnumrows(solverdata->cpxenv[probnr], solverdata->lp[probnr]);
517 
518  if( nbasicpricingconss < ncpxrows )
519  {
520  CHECK_ZERO( CPXdelrows(solverdata->cpxenv[probnr], solverdata->lp[probnr], nbasicpricingconss, ncpxrows - 1) );
521  }
522 
523  nnewconss = nconss - nbasicpricingconss;
524 
525  if( nnewconss == 0 )
526  return retval;
527 
528  /* temporary arrays for storing data about new constraints */
529  SCIP_CALL( SCIPallocBufferArray(scip, &newsenses, nnewconss) );
530  SCIP_CALL( SCIPallocBufferArray(scip, &newrhss, nnewconss) );
531  SCIP_CALL( SCIPallocBufferArray(scip, &newranges, nnewconss) );
532  SCIP_CALL( SCIPallocClearBufferArray(scip, &newconsnames, nnewconss) );
533 
534  /* get information about new constraints */
535  nnonzeros = 0;
536 
537  for( c = 0; c < nconss; ++c )
538  {
539  SCIP_Real lhs;
540  SCIP_Real rhs;
541  int nconsvars;
542  int considx;
543 
544  /* we assume that nothing changed about the basic constraints */
545  if( c < nbasicpricingconss )
546  {
547  assert(conss[c] == solverdata->pricingconss[probnr][c]);
548  continue;
549  }
550 
551  considx = c - nbasicpricingconss;
552  assert(considx >= 0);
553 
554  nconsvars = GCGconsGetNVars(scip, conss[c]);
555  lhs = GCGconsGetLhs(pricingprob, conss[c]);
556  rhs = GCGconsGetRhs(pricingprob, conss[c]);
557  SCIP_CALL( SCIPduplicateBufferArray(scip, &newconsnames[considx], SCIPconsGetName(conss[c]),
558  (int)(strlen(SCIPconsGetName(conss[c]))+1)) ); /*lint !e866*/
559 
560  if( SCIPisInfinity(scip, -lhs) )
561  {
562  newsenses[considx] = 'L';
563  newrhss[considx] = (double) rhs;
564  newranges[considx] = 0.0;
565  }
566  else if( SCIPisInfinity(scip, rhs) )
567  {
568  newsenses[considx] = 'G';
569  newrhss[considx] = (double) lhs;
570  newranges[considx] = 0.0;
571  }
572  else if( SCIPisEQ(scip, lhs, rhs) )
573  {
574  newsenses[considx] = 'E';
575  newrhss[considx] = (double) lhs;
576  newranges[considx] = 0.0;
577  }
578  else
579  {
580  assert(SCIPisLT(scip, lhs, rhs));
581  newsenses[considx] = 'R';
582  newrhss[considx] = (double) lhs;
583  newranges[considx] = (double) (rhs - lhs);
584  }
585 
586  nnonzeros += nconsvars;
587  }
588 
589  /* temporary arrays for getting variables and coefficients in new constraints */
590  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) );
591  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nvars) );
592 
593  /* temporary arrays for storing data about new constraints */
594  SCIP_CALL( SCIPallocBufferArray(scip, &newrowidx, nnonzeros) );
595  SCIP_CALL( SCIPallocBufferArray(scip, &newcolidx, nnonzeros) );
596  SCIP_CALL( SCIPallocBufferArray(scip, &newcoefs, nnonzeros) );
597 
598  /* collect coefficients in new constriants */
599  for( c = 0, idx = 0; c < nconss; ++c )
600  {
601  int nconsvars;
602 
603  int v;
604 
605  /* we assume that nothing changed about the basic constraints */
606  if( c < nbasicpricingconss )
607  {
608  assert(conss[c] == solverdata->pricingconss[probnr][c]);
609  continue;
610  }
611 
612  nconsvars = GCGconsGetNVars(scip, conss[c]);
613  SCIP_CALL( GCGconsGetVars(pricingprob, conss[c], consvars, nvars) );
614  SCIP_CALL( GCGconsGetVals(pricingprob, conss[c], consvals, nvars) );
615 
616  /* get coefficients */
617  for( v = 0; v < nconsvars; ++v )
618  {
619  newrowidx[idx] = c;
620  newcolidx[idx] = SCIPvarGetIndex(consvars[v]);
621  newcoefs[idx] = (double)consvals[v];
622  idx++;
623  }
624  }
625  assert(idx == nnonzeros);
626 
627  /* add new constraints */
628  CHECK_ZERO( CPXnewrows(solverdata->cpxenv[probnr], solverdata->lp[probnr], nnewconss, newrhss, newsenses, newranges, newconsnames) );
629  CHECK_ZERO( CPXchgcoeflist(solverdata->cpxenv[probnr], solverdata->lp[probnr], nnonzeros, newrowidx, newcolidx, newcoefs) );
630 
631 TERMINATE:
632  if( nnewconss > 0 )
633  {
634  SCIPfreeBufferArray(scip, &newcoefs);
635  SCIPfreeBufferArray(scip, &newcolidx);
636  SCIPfreeBufferArray(scip, &newrowidx);
637 
638  SCIPfreeBufferArray(scip, &consvals);
639  SCIPfreeBufferArray(scip, &consvars);
640 
641  for( c = nnewconss - 1; c >= 0; --c )
642  {
643  assert(newconsnames != NULL);
644  SCIPfreeBufferArrayNull(scip, &newconsnames[c]);
645  }
646 
647  SCIPfreeBufferArray(scip, &newconsnames);
648  SCIPfreeBufferArray(scip, &newranges);
649  SCIPfreeBufferArray(scip, &newrhss);
650  SCIPfreeBufferArray(scip, &newsenses);
651  }
652 
653  return retval;
654 }
655 
656 
657 /** solves the pricing problem with CPLEX */
658 static
659 SCIP_RETCODE solveCplex(
660  SCIP* scip, /**< SCIP data structure (master problem) */
661  GCG_SOLVERDATA* solverdata, /**< solver data structure */
662  SCIP* pricingprob, /**< pricing problem */
663  int probnr, /**< problem number */
664  SCIP_Real dualsolconv, /**< dual solution value of the corresponding convexity constraint */
665  SCIP_Real* lowerbound, /**< pointer to store lower bound */
666  int* ncols, /**< pointer to store number of columns */
667  GCG_PRICINGSTATUS* status /**< pointer to store the pricing status */
668  )
669 { /*lint -e715*/
670  GCG_COL* col;
671  SCIP_RETCODE retval;
672  SCIP_Bool predisabled = FALSE;
673  double* cplexsolvals;
674  double objective;
675  double upperbound;
676  double* primsol = NULL;
677  int curpreind = -1;
678  int curadvind = -1;
679  int nsolscplex;
680  int numcols;
681  int cpxstatus;
682  int s;
683 
684  *ncols = 0;
685  *status = GCG_PRICINGSTATUS_UNKNOWN;
686  upperbound = SCIPinfinity(pricingprob);
687 
688  retval = SCIP_OKAY;
689 
690  numcols = CPXgetnumcols(solverdata->cpxenv[probnr], solverdata->lp[probnr]);
691  assert(numcols == SCIPgetNOrigVars(pricingprob));
692 
693  SCIP_CALL( SCIPallocBufferArray(scip, &cplexsolvals, numcols) );
694  SOLVEAGAIN:
695  /* the optimization call */
696  if( predisabled )
697  {
698  CHECK_ZERO( CPXprimopt(solverdata->cpxenv[probnr], solverdata->lp[probnr]) );
699  }
700  else
701  {
702  CHECK_ZERO( CPXmipopt(solverdata->cpxenv[probnr], solverdata->lp[probnr]) );
703  }
704 
705  /* get number of solutions */
706  nsolscplex = CPXgetsolnpoolnumsolns(solverdata->cpxenv[probnr], solverdata->lp[probnr]);
707 
708  /* get solution status */
709  cpxstatus = CPXgetstat(solverdata->cpxenv[probnr], solverdata->lp[probnr]);
710 
711  /* handle CPLEX solution status */
712  switch( cpxstatus )
713  {
714  /* pricing problem was solved to optimality */
715  case CPXMIP_OPTIMAL: /* 101 */
716  assert(nsolscplex > 0);
717  *status = GCG_PRICINGSTATUS_OPTIMAL;
718  CHECK_ZERO( CPXgetobjval(solverdata->cpxenv[probnr], solverdata->lp[probnr], &upperbound) );
719  break;
720 
721  /* pricing problem was proven to be infeasible */
722  case CPXMIP_INFEASIBLE: /* 103 */
723  assert(nsolscplex == 0);
724  *status = GCG_PRICINGSTATUS_INFEASIBLE;
725  break;
726 
727  /* pricing problem is possibly unbounded */
728  case CPXMIP_UNBOUNDED: /* 118 */
729  case CPXMIP_INForUNBD: /* 119 */
730  {
731  int cpxretval;
732  int dummy;
733 
734  SCIP_CALL( SCIPallocBufferArray(scip, &primsol, numcols) );
735 
736  CHECK_ZERO( CPXsolution(solverdata->cpxenv[probnr], solverdata->lp[probnr], &dummy, NULL, primsol, NULL, NULL, NULL) );
737 
738  assert(dummy == cpxstatus);
739 
740  cpxretval = CPXgetray(solverdata->cpxenv[probnr], solverdata->lp[probnr], cplexsolvals);
741 
742  if( cpxretval == 1254 )
743  {
744  assert(!predisabled);
745 
746  SCIPdebugMessage(" -> disable presolving in CPLEX to get primal ray\n");
747 
748  CHECK_ZERO( CPXgetintparam(solverdata->cpxenv[probnr], CPX_PARAM_PREIND, &curpreind) );
749  CHECK_ZERO( CPXgetintparam(solverdata->cpxenv[probnr], CPX_PARAM_ADVIND, &curadvind) );
750 
751  CHECK_ZERO( CPXchgprobtype(solverdata->cpxenv[probnr], solverdata->lp[probnr], CPXPROB_FIXEDMILP) );
752 
753  CHECK_ZERO( CPXsetintparam(solverdata->cpxenv[probnr], CPX_PARAM_ADVIND, 0) );
754  CHECK_ZERO( CPXsetintparam(solverdata->cpxenv[probnr], CPX_PARAM_PREIND, 0) );
755 
756  predisabled = TRUE;
757 
758  goto SOLVEAGAIN;
759  }
760  else
761  {
762  CHECK_ZERO( cpxretval );
763  }
764 
765  SCIP_CALL( GCGcreateGcgCol(pricingprob, &col, probnr, solverdata->pricingvars[probnr], cplexsolvals, numcols, TRUE, SCIPinfinity(pricingprob)) );
766  SCIP_CALL( GCGpricerAddCol(scip, col) );
767  ++(*ncols);
768 
769  *status = GCG_PRICINGSTATUS_UNBOUNDED;
770 
771  SCIPfreeBufferArray(scip, &primsol);
772 
773  goto TERMINATE;
774  }
775 
776  /* a heuristic pricing limit was reached and may be increased in the next round */
777  /* @todo: CPXMIP_OPTIMAL_TOL = 102 seems to occur even if gaplimit is set to 0 */
778  case CPXMIP_OPTIMAL_TOL: /* 102 */
779  assert(nsolscplex > 0);
780  if( solverdata->gaplimitfac < 1.0 )
781  solverdata->curgaplimit[probnr] *= solverdata->gaplimitfac;
782  else
783  solverdata->curgaplimit[probnr] = MAX(solverdata->curgaplimit[probnr] - solverdata->startgaplimit, 0.0);
784  SCIPdebugMessage(" -> gap limit reached, decreasing to %g\n", solverdata->curgaplimit[probnr]);
785  *status = GCG_PRICINGSTATUS_SOLVERLIMIT;
786  CHECK_ZERO( CPXgetobjval(solverdata->cpxenv[probnr], solverdata->lp[probnr], &upperbound) );
787  break;
788 
789  case CPXMIP_NODE_LIM_FEAS: /* 105 */
790  assert(nsolscplex > 0);
791  if( solverdata->nodelimitfac > 1.0 )
792  solverdata->curnodelimit[probnr] = (SCIP_Longint) (solverdata->curnodelimit[probnr] * solverdata->nodelimitfac);
793  else
794  solverdata->curnodelimit[probnr] += solverdata->startnodelimit;
795  SCIPdebugMessage(" -> node limit reached, increasing to %"SCIP_LONGINT_FORMAT"\n", solverdata->curnodelimit[probnr]);
796  *status = GCG_PRICINGSTATUS_SOLVERLIMIT;
797  CHECK_ZERO( CPXgetobjval(solverdata->cpxenv[probnr], solverdata->lp[probnr], &upperbound) );
798  break;
799 
800  case CPXMIP_SOL_LIM: /* 104 */
801  assert(nsolscplex > 0);
802  if( solverdata->sollimitfac > 1.0 )
803  solverdata->cursollimit[probnr] = (SCIP_Longint) (solverdata->cursollimit[probnr] * solverdata->sollimitfac);
804  else
805  solverdata->cursollimit[probnr] += solverdata->startsollimit;
806  SCIPdebugMessage(" -> solution limit reached, increasing to %"SCIP_LONGINT_FORMAT"\n", solverdata->cursollimit[probnr]);
807  *status = GCG_PRICINGSTATUS_SOLVERLIMIT;
808  CHECK_ZERO( CPXgetobjval(solverdata->cpxenv[probnr], solverdata->lp[probnr], &upperbound) );
809  break;
810 
811  /* no feasible solution was found, not clear whether one exists or the problem is infeasible */
812  case CPXMIP_NODE_LIM_INFEAS: /* 106 */
813  case CPXMIP_TIME_LIM_INFEAS: /* 108 */
814  case CPXMIP_MEM_LIM_INFEAS: /* 111 */
815  case CPXMIP_ABORT_INFEAS: /* 114 */
816  assert(nsolscplex == 0);
817  *status = GCG_PRICINGSTATUS_UNKNOWN;
818  break;
819 
820  /* a feasible solution exists */
821  case CPXMIP_TIME_LIM_FEAS: /* 107 */
822  case CPXMIP_MEM_LIM_FEAS: /* 112 */
823  case CPXMIP_ABORT_FEAS: /* 113 */
824  case CPXMIP_FEASIBLE: /* 127 */
825  assert(nsolscplex > 0);
826  CHECK_ZERO( CPXgetobjval(solverdata->cpxenv[probnr], solverdata->lp[probnr], &upperbound) );
827  *status = GCG_PRICINGSTATUS_UNKNOWN;
828  break;
829 
830  default:
831  *status = GCG_PRICINGSTATUS_UNKNOWN;
832  goto TERMINATE;
833  }
834 
835  CHECK_ZERO( CPXgetbestobjval(solverdata->cpxenv[probnr], solverdata->lp[probnr], lowerbound) );
836 
837  /* In case of optimality, it might happen that the "lower bound" returned by CPLEX exceeds the optimal solution value;
838  * probably, this is not a bug but a feature
839  */
840  *lowerbound = MIN(*lowerbound, upperbound);
841 
842  SCIPdebugMessage(" -> pricing problem %d solved: cpxstatus=%d, nsols=%d, lowerbound=%g, upperbound=%g\n", probnr, cpxstatus, nsolscplex, *lowerbound, upperbound);
843 
844  assert(SCIPisFeasEQ(scip, *lowerbound, upperbound) || cpxstatus != CPXMIP_OPTIMAL);
845 
846 #ifndef NDEBUG
847  /* in debug mode, we check that the first solution in the solution pool is the incumbent */
848  if( nsolscplex > 0 )
849  {
850  double oldobjective;
851 
852  CHECK_ZERO( CPXgetsolnpoolobjval(solverdata->cpxenv[probnr], solverdata->lp[probnr], 0, &oldobjective) );
853 
854  for( s = 1; s < nsolscplex; ++s )
855  {
856  CHECK_ZERO( CPXgetsolnpoolobjval(solverdata->cpxenv[probnr], solverdata->lp[probnr], s, &objective) );
857  assert(SCIPisFeasGE(scip, objective, oldobjective));
858  }
859  }
860 #endif
861 
862  /* iterate over all CPLEX solutions and check for negative reduced costs; the first solution should always be the
863  * incumbent, all other solutions are unsorted
864  */
865  for( s = 0; s < nsolscplex; ++s )
866  {
867  SCIP_SOL* sol;
868  SCIP_Bool feasible;
869 
870  CHECK_ZERO( CPXgetsolnpoolobjval(solverdata->cpxenv[probnr], solverdata->lp[probnr], s, &objective) );
871 
872  CHECK_ZERO( CPXgetsolnpoolx(solverdata->cpxenv[probnr], solverdata->lp[probnr], s, cplexsolvals, 0, numcols - 1) );
873 
874  SCIP_CALL( SCIPcreateOrigSol(pricingprob, &sol, NULL) );
875  SCIP_CALL( SCIPsetSolVals(pricingprob, sol, numcols, solverdata->pricingvars[probnr], cplexsolvals) );
876 
877  feasible = FALSE;
878 
879  /* check whether the solution is feasible */
880  if( !solverdata->checksols )
881  {
882  SCIP_CALL( SCIPcheckSolOrig(pricingprob, sol, &feasible, FALSE, FALSE) );
883 
884  /* if the optimal solution is not feasible, we return GCG_PRICINGSTATUS_UNKNOWN as status */
885  if( !feasible && s == 0 )
886  {
887  *status = GCG_PRICINGSTATUS_UNKNOWN;
888  }
889  }
890  else
891  {
892  feasible = TRUE;
893  }
894 
895  if( feasible )
896  {
897  SCIP_CALL( GCGcreateGcgColFromSol(pricingprob, &col, probnr, sol, FALSE, SCIPinfinity(pricingprob)) );
898  SCIP_CALL( GCGpricerAddCol(scip, col) );
899  ++(*ncols);
900  }
901 
902  SCIP_CALL( SCIPfreeSol(pricingprob, &sol) );
903  }
904 
905  assert(*status != GCG_PRICINGSTATUS_OPTIMAL || *ncols > 0);
906  TERMINATE:
907  if( predisabled )
908  {
909  assert(curpreind >= 0);
910  assert(curadvind >= 0);
911  CHECK_ZERO( CPXsetintparam(solverdata->cpxenv[probnr], CPX_PARAM_PREIND, curpreind) );
912  CHECK_ZERO( CPXsetintparam(solverdata->cpxenv[probnr], CPX_PARAM_ADVIND, curadvind) );
913 
914  CHECK_ZERO( CPXchgprobtype(solverdata->cpxenv[probnr], solverdata->lp[probnr], CPXPROB_MILP) );
915  }
916 
917  if( primsol != NULL )
918  SCIPfreeBufferArray(scip, &primsol);
919 
920  SCIPfreeBufferArray(scip, &cplexsolvals);
921 
922  return retval;
923 }
924 
925 
926 /** destructor of pricing solver to free user data (called when SCIP is exiting) */
927 static
928 GCG_DECL_SOLVERFREE(solverFreeCplex)
929 {
930  GCG_SOLVERDATA* solverdata;
931 
932  assert(scip != NULL);
933  assert(solver != NULL);
934 
935  solverdata = GCGsolverGetData(solver);
936  assert(solverdata != NULL);
937 
938  SCIPfreeMemory(scip, &solverdata);
939  GCGsolverSetData(solver, NULL);
940 
941  return SCIP_OKAY;
942 }
943 
944 /** solving process initialization method of pricing solver (called when branch and bound process is about to begin) */
945 static
946 GCG_DECL_SOLVERINITSOL(solverInitsolCplex)
947 {
948  GCG_SOLVERDATA* solverdata;
949  int npricingprobs;
950 
951  int i;
952 
953  assert(scip != NULL);
954  assert(solver != NULL);
955 
956  solverdata = GCGsolverGetData(solver);
957  assert(solverdata != NULL);
958 
959  solverdata->npricingprobs = GCGgetNPricingprobs(solverdata->origprob);
960  npricingprobs = solverdata->npricingprobs;
961 
962  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(solverdata->cpxenv), npricingprobs) );
963  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(solverdata->lp), npricingprobs) );
964  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(solverdata->nupdates), npricingprobs) );
965  BMSclearMemoryArray(solverdata->nupdates, npricingprobs);
966 
967  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(solverdata->pricingprobs), npricingprobs) );
968  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(solverdata->pricingvars), npricingprobs) );
969  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(solverdata->pricingconss), npricingprobs) );
970  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(solverdata->npricingvars), npricingprobs) );
971  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(solverdata->nbasicpricingconss), npricingprobs) );
972  BMSclearMemoryArray(solverdata->npricingvars, npricingprobs);
973  BMSclearMemoryArray(solverdata->nbasicpricingconss, npricingprobs);
974 
975  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &solverdata->curnodelimit, npricingprobs) );
976  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &solverdata->curgaplimit, npricingprobs) );
977  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &solverdata->cursollimit, npricingprobs) );
978 
979  for( i = 0; i < npricingprobs; ++i )
980  {
981  if( GCGisPricingprobRelevant(solverdata->origprob, i) )
982  {
983  SCIP_CALL( buildProblem(solverdata->masterprob, solverdata, GCGgetPricingprob(solverdata->origprob, i), i) );
984  }
985 
986  solverdata->curnodelimit[i] = solverdata->startnodelimit;
987  solverdata->curgaplimit[i] = solverdata->startgaplimit;
988  solverdata->cursollimit[i] = solverdata->startsollimit;
989  }
990 
991  return SCIP_OKAY;
992 }
993 
994 /** solving process deinitialization method of pricing solver (called before branch and bound process data is freed) */
995 static
996 GCG_DECL_SOLVEREXITSOL(solverExitsolCplex)
997 {
998  GCG_SOLVERDATA* solverdata;
999  SCIP_RETCODE retval;
1000  int npricingprobs;
1001  int i;
1002  int j;
1003 
1004  assert(scip != NULL);
1005  assert(solver != NULL);
1006 
1007  solverdata = GCGsolverGetData(solver);
1008  assert(solverdata != NULL);
1009 
1010  retval = SCIP_OKAY;
1011 
1012  npricingprobs = GCGgetNPricingprobs(solverdata->origprob);
1013 
1014  /* free pricing problems */
1015  for( i = 0; i < npricingprobs; ++i )
1016  {
1017  if( GCGisPricingprobRelevant(solverdata->origprob, i) )
1018  {
1019  /* free LP */
1020  CHECK_ZERO( CPXfreeprob(solverdata->cpxenv[i], &solverdata->lp[i]) );
1021 
1022  /* free environment */
1023  CHECK_ZERO( CPXcloseCPLEX(&solverdata->cpxenv[i]) );
1024 
1025  if( solverdata->nbasicpricingconss[i] > 0 )
1026  {
1027  /* release stored constraints */
1028  for( j = 0; j < solverdata->nbasicpricingconss[i]; ++j )
1029  {
1030  SCIP_CALL( SCIPreleaseCons(solverdata->pricingprobs[i], &solverdata->pricingconss[i][j]) );
1031  }
1032  SCIPfreeMemoryArray(scip, &(solverdata->pricingconss[i]));
1033  }
1034 
1035  if( solverdata->npricingvars[i] > 0 )
1036  {
1037  /* release stored constraints */
1038  for( j = 0; j < solverdata->npricingvars[i]; ++j )
1039  {
1040  SCIP_CALL( SCIPreleaseVar(solverdata->pricingprobs[i], &solverdata->pricingvars[i][j]) );
1041  }
1042  SCIPfreeMemoryArray(scip, &(solverdata->pricingvars[i]));
1043  }
1044  }
1045  }
1046 
1047  TERMINATE:
1048  SCIPfreeBlockMemoryArray(scip, &solverdata->cursollimit, solverdata->npricingprobs);
1049  SCIPfreeBlockMemoryArray(scip, &solverdata->curgaplimit, solverdata->npricingprobs);
1050  SCIPfreeBlockMemoryArray(scip, &solverdata->curnodelimit, solverdata->npricingprobs);
1051 
1052  SCIPfreeBlockMemoryArray(scip, &(solverdata->nbasicpricingconss), solverdata->npricingprobs);
1053  SCIPfreeBlockMemoryArray(scip, &(solverdata->npricingvars), solverdata->npricingprobs);
1054  SCIPfreeBlockMemoryArray(scip, &(solverdata->pricingconss), solverdata->npricingprobs);
1055  SCIPfreeBlockMemoryArray(scip, &(solverdata->pricingvars), solverdata->npricingprobs);
1056  SCIPfreeBlockMemoryArray(scip, &(solverdata->pricingprobs), solverdata->npricingprobs);
1057 
1058  SCIPfreeBlockMemoryArray(scip, &(solverdata->nupdates), solverdata->npricingprobs);
1059  SCIPfreeBlockMemoryArray(scip, &(solverdata->lp), solverdata->npricingprobs);
1060  SCIPfreeBlockMemoryArray(scip, &(solverdata->cpxenv), solverdata->npricingprobs);
1061 
1062  return retval;
1063 }
1064 
1065 #define solverInitCplex NULL
1066 #define solverExitCplex NULL
1067 
1068 /** update method for pricing solver, used to update solver specific pricing problem data */
1069 static
1070 GCG_DECL_SOLVERUPDATE(solverUpdateCplex)
1071 {
1072  GCG_SOLVERDATA* solverdata;
1073 
1074  solverdata = GCGsolverGetData(solver);
1075  assert(solverdata != NULL);
1076 
1077  SCIPdebugMessage("CPLEX solver -- update data for problem %d: varobjschanged = %u, varbndschanged = %u, consschanged = %u\n",
1078  probnr, varobjschanged, varbndschanged, consschanged);
1079 
1080  /* update pricing problem information */
1081  SCIP_CALL( updateVars(solverdata->masterprob, solverdata, pricingprob, probnr, varobjschanged, varbndschanged) );
1082  if( consschanged )
1083  {
1084  SCIP_CALL( updateBranchingConss(solverdata->masterprob, solverdata, pricingprob, probnr) );
1085  }
1086 
1087  /* reset heuristic pricing limits */
1088  solverdata->curnodelimit[probnr] = solverdata->startnodelimit;
1089  solverdata->curgaplimit[probnr] = solverdata->startgaplimit;
1090  solverdata->cursollimit[probnr] = solverdata->startsollimit;
1091 
1092 #ifdef WRITEPROBLEMS
1093  /* Print the pricing problem after updating:
1094  * * after checking variable bounds, because they change in particular when a new generic branching subproblem is considered
1095  * * but not after adding new branching constraints, since objectives will be set afterwards before solving
1096  */
1097  if( varbndschanged && !consschanged )
1098  {
1099  char filename[SCIP_MAXSTRLEN];
1100 
1101  ++(solverdata->nupdates[probnr]);
1102 
1103  (void) SCIPsnprintf(filename, SCIP_MAXSTRLEN, "cplex-%s-%d-%d.lp", SCIPgetProbName(pricingprob), SCIPgetNNodes(scip), solverdata->nupdates[probnr]);
1104  SCIPinfoMessage(pricingprob, NULL, "print pricing problem to %s\n", filename);
1105  CHECK_ZERO( CPXwriteprob(solverdata->cpxenv[probnr], solverdata->lp[probnr], filename, "lp") );
1106  }
1107 #endif
1108 
1109  return SCIP_OKAY;
1110 }
1111 
1112 /** heuristic solving method of CPLEX solver */
1113 static
1114 GCG_DECL_SOLVERSOLVEHEUR(solverSolveHeurCplex)
1115 {
1116  GCG_SOLVERDATA* solverdata;
1117  int ncols;
1118  SCIP_RETCODE retval;
1119 
1120  solverdata = GCGsolverGetData(solver);
1121  assert(solverdata != NULL);
1122 
1123  SCIPdebugMessage("calling heuristic pricing with CPLEX for pricing problem %d\n", probnr);
1124 
1125  retval = SCIP_OKAY;
1126 
1127  /* set heuristic limits */
1128  CHECK_ZERO( CPXsetlongparam(solverdata->cpxenv[probnr], CPX_PARAM_NODELIM, (long long) solverdata->curnodelimit[probnr]) );
1129  CHECK_ZERO( CPXsetdblparam(solverdata->cpxenv[probnr], CPX_PARAM_EPGAP, (double) solverdata->curgaplimit[probnr]) );
1130  CHECK_ZERO( CPXsetlongparam(solverdata->cpxenv[probnr], CPX_PARAM_INTSOLLIM, (long long) solverdata->cursollimit[probnr]) );
1131 
1132  /* solve the pricing problem and evaluate solution */
1133  SCIP_CALL( solveCplex(solverdata->masterprob, solverdata, pricingprob, probnr, dualsolconv, lowerbound, &ncols, status) );
1134  assert(*status != GCG_PRICINGSTATUS_OPTIMAL || ncols > 0);
1135 
1136  TERMINATE:
1137  return retval;
1138 }
1139 
1140 /** solving method for pricing solver which solves the pricing problem to optimality */
1141 static
1142 GCG_DECL_SOLVERSOLVE(solverSolveCplex)
1143 {
1144  GCG_SOLVERDATA* solverdata;
1145  int ncols;
1146  SCIP_RETCODE retval;
1147 
1148  assert(solver != NULL);
1149 
1150  solverdata = GCGsolverGetData(solver);
1151  assert(solverdata != NULL);
1152 
1153  SCIPdebugMessage("calling exact pricing with CPLEX for pricing problem %d\n", probnr);
1154 
1155  retval = SCIP_OKAY;
1156 
1157  /* set limits to (infinite/zero) default values */
1158  CHECK_ZERO( CPXsetlongparam(solverdata->cpxenv[probnr], CPX_PARAM_NODELIM, CPX_LONG_MAX) );
1159  CHECK_ZERO( CPXsetdblparam(solverdata->cpxenv[probnr], CPX_PARAM_EPGAP, 0.0) );
1160  CHECK_ZERO( CPXsetlongparam(solverdata->cpxenv[probnr], CPX_PARAM_INTSOLLIM, CPX_LONG_MAX) );
1161 
1162  /* solve the pricing problem and evaluate solution */
1163  SCIP_CALL( solveCplex(solverdata->masterprob, solverdata, pricingprob, probnr, dualsolconv, lowerbound, &ncols, status) );
1164  assert(*status != GCG_PRICINGSTATUS_OPTIMAL || ncols > 0);
1165 
1166  TERMINATE:
1167  return retval;
1168 }
1169 
1170 /** creates the CPLEX pricing solver and includes it in GCG */
1171 SCIP_RETCODE GCGincludeSolverCplex(
1172  SCIP* scip /**< SCIP data structure */
1173  )
1174 {
1175  GCG_SOLVERDATA* solverdata;
1176 
1177  SCIP_CALL( SCIPallocMemory(scip, &solverdata) );
1178  solverdata->origprob = GCGmasterGetOrigprob(scip);
1179  solverdata->masterprob = scip;
1180 
1181  SCIP_CALL( GCGpricerIncludeSolver(scip, SOLVER_NAME, SOLVER_DESC, SOLVER_PRIORITY,
1182  SOLVER_HEURENABLED, SOLVER_EXACTENABLED,
1183  solverUpdateCplex, solverSolveCplex, solverSolveHeurCplex, solverFreeCplex, solverInitCplex,
1184  solverExitCplex, solverInitsolCplex, solverExitsolCplex, solverdata));
1185 
1186  SCIP_CALL( SCIPaddBoolParam(solverdata->origprob, "pricingsolver/cplex/checksols",
1187  "should solutions of the pricing MIPs be checked for duplicity?",
1188  &solverdata->checksols, TRUE, DEFAULT_CHECKSOLS, NULL, NULL));
1189 
1190  SCIP_CALL( SCIPaddIntParam(solverdata->origprob, "pricingsolver/cplex/threads",
1191  "number of threads the CPLEX pricing solver is allowed to use (0: automatic)",
1192  &solverdata->threads, TRUE, DEFAULT_THREADS, 0, INT_MAX, NULL, NULL));
1193 
1194  SCIP_CALL( SCIPaddLongintParam(solverdata->origprob, "pricingsolver/cplex/startnodelimit",
1195  "start node limit for heuristic pricing",
1196  &solverdata->startnodelimit, TRUE, DEFAULT_STARTNODELIMIT, 0, CPX_LONG_MAX, NULL, NULL) );
1197 
1198  SCIP_CALL( SCIPaddRealParam(solverdata->origprob, "pricingsolver/cplex/startgaplimit",
1199  "start gap limit for heuristic pricing",
1200  &solverdata->startgaplimit, TRUE, DEFAULT_STARTGAPLIMIT, 0.0, 1.0, NULL, NULL) );
1201 
1202  SCIP_CALL( SCIPaddLongintParam(solverdata->origprob, "pricingsolver/cplex/startsollimit",
1203  "start solution limit for heuristic pricing",
1204  &solverdata->startsollimit, TRUE, DEFAULT_STARTSOLLIMIT, 0, CPX_LONG_MAX, NULL, NULL) );
1205 
1206  SCIP_CALL( SCIPaddRealParam(solverdata->origprob, "pricingsolver/cplex/nodelimitfac",
1207  "factor by which to increase node limit for heuristic pricing (1.0: add start limit)",
1208  &solverdata->nodelimitfac, TRUE, DEFAULT_NODELIMITFAC, 1.0, SCIPinfinity(solverdata->origprob), NULL, NULL) );
1209 
1210  SCIP_CALL( SCIPaddRealParam(solverdata->origprob, "pricingsolver/cplex/gaplimitfac",
1211  "factor by which to decrease gap limit for heuristic pricing (1.0: subtract start limit)",
1212  &solverdata->gaplimitfac, TRUE, DEFAULT_GAPLIMITFAC, 0.0, 1.0, NULL, NULL) );
1213 
1214  SCIP_CALL( SCIPaddRealParam(solverdata->origprob, "pricingsolver/cplex/sollimitfac",
1215  "factor by which to increase solution limit for heuristic pricing (1.0: add start limit)",
1216  &solverdata->sollimitfac, TRUE, DEFAULT_SOLLIMITFAC, 1.0, SCIPinfinity(solverdata->origprob), NULL, NULL) );
1217  return SCIP_OKAY;
1218 }
GCG_SolverData::nbasicpricingconss
int * nbasicpricingconss
Definition: solver_cplex.c:100
GCGcreateGcgCol
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
CHECK_ZERO
#define CHECK_ZERO(x)
Definition: solver_cplex.c:52
DEFAULT_SOLLIMITFAC
#define DEFAULT_SOLLIMITFAC
Definition: solver_cplex.c:78
GCG_DECL_SOLVERUPDATE
static GCG_DECL_SOLVERUPDATE(solverUpdateCplex)
Definition: solver_cplex.c:1070
GCGconsGetRhs
SCIP_Real GCGconsGetRhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:108
gcg.h
GCG interface methods.
GCG_SolverData::nupdates
int * nupdates
Definition: solver_cplex.c:90
GCGconsGetLhs
SCIP_Real GCGconsGetLhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:206
GCG_SolverData::pricingconss
SCIP_CONS *** pricingconss
Definition: solver_cplex.c:98
GCG_Col
Definition: struct_gcgcol.h:50
GCGincludeSolverCplex
SCIP_RETCODE GCGincludeSolverCplex(SCIP *scip)
Definition: solver_cplex.c:1171
SOLVER_HEURENABLED
#define SOLVER_HEURENABLED
Definition: solver_cplex.c:67
GCG_SolverData::cpxenv
CPXENVptr * cpxenv
Definition: solver_cplex.c:88
GCGsolverSetData
SCIP_EXPORT void GCGsolverSetData(GCG_SOLVER *solver, GCG_SOLVERDATA *solverdata)
Definition: solver.c:387
DEFAULT_NODELIMITFAC
#define DEFAULT_NODELIMITFAC
Definition: solver_cplex.c:75
GCG_SolverData::masterprob
SCIP * masterprob
Definition: solver_cplex.c:85
GCG_PRICINGSTATUS_UNBOUNDED
@ GCG_PRICINGSTATUS_UNBOUNDED
Definition: type_pricingstatus.h:55
GCGconsGetVars
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:490
DEFAULT_STARTGAPLIMIT
#define DEFAULT_STARTGAPLIMIT
Definition: solver_cplex.c:73
pub_gcgcol.h
public methods for working with gcg columns
GCG_SolverData::curgaplimit
SCIP_Real * curgaplimit
Definition: solver_cplex.c:92
GCGcreateGcgColFromSol
SCIP_RETCODE GCGcreateGcgColFromSol(SCIP *pricingprob, GCG_COL **gcgcol, int prob, SCIP_SOL *sol, SCIP_Bool isray, SCIP_Real redcost)
Definition: gcgcol.c:154
GCGgetPricingprob
SCIP * GCGgetPricingprob(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3939
GCG_DECL_SOLVEREXITSOL
static GCG_DECL_SOLVEREXITSOL(solverExitsolCplex)
Definition: solver_cplex.c:996
GCGgetNPricingprobs
int GCGgetNPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3979
pricer_gcg.h
GCG variable pricer.
GCG_DECL_SOLVERSOLVEHEUR
static GCG_DECL_SOLVERSOLVEHEUR(solverSolveHeurCplex)
Definition: solver_cplex.c:1114
GCG_PRICINGSTATUS
enum GCG_PricingStatus GCG_PRICINGSTATUS
Definition: type_pricingstatus.h:57
scip_misc.h
various SCIP helper methods
SOLVER_EXACTENABLED
#define SOLVER_EXACTENABLED
Definition: solver_cplex.c:68
GCG_SolverData
Definition: solver_cliquer.c:59
GCG_SolverData::threads
int threads
Definition: solver_cplex.c:105
solver_cplex.h
cplex solver for pricing problems
GCG_PRICINGSTATUS_SOLVERLIMIT
@ GCG_PRICINGSTATUS_SOLVERLIMIT
Definition: type_pricingstatus.h:51
DEFAULT_THREADS
#define DEFAULT_THREADS
Definition: solver_cplex.c:71
GCG_PRICINGSTATUS_INFEASIBLE
@ GCG_PRICINGSTATUS_INFEASIBLE
Definition: type_pricingstatus.h:54
GCG_PRICINGSTATUS_OPTIMAL
@ GCG_PRICINGSTATUS_OPTIMAL
Definition: type_pricingstatus.h:52
GCG_SolverData::gaplimitfac
SCIP_Real gaplimitfac
Definition: solver_cplex.c:110
GCG_SolverData::startsollimit
SCIP_Longint startsollimit
Definition: solver_cplex.c:108
GCG_DECL_SOLVERINITSOL
static GCG_DECL_SOLVERINITSOL(solverInitsolCplex)
Definition: solver_cplex.c:946
GCG_SolverData::npricingprobs
int npricingprobs
Definition: solver_cplex.c:87
SOLVER_DESC
#define SOLVER_DESC
Definition: solver_cplex.c:65
solverExitCplex
#define solverExitCplex
Definition: solver_cplex.c:1066
DEFAULT_GAPLIMITFAC
#define DEFAULT_GAPLIMITFAC
Definition: solver_cplex.c:77
GCGsolverGetData
SCIP_EXPORT GCG_SOLVERDATA * GCGsolverGetData(GCG_SOLVER *solver)
Definition: solver.c:377
GCG_SolverData::pricingvars
SCIP_VAR *** pricingvars
Definition: solver_cplex.c:97
GCG_SolverData::pricingprobs
SCIP ** pricingprobs
Definition: solver_cplex.c:86
GCGpricerIncludeSolver
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)
Definition: pricer_gcg.cpp:4370
GCGmasterGetOrigprob
SCIP * GCGmasterGetOrigprob(SCIP *scip)
Definition: pricer_gcg.cpp:4239
GCG_SolverData::lp
CPXLPptr * lp
Definition: solver_cplex.c:89
GCG_SolverData::npricingvars
int * npricingvars
Definition: solver_cplex.c:99
buildProblem
static SCIP_RETCODE buildProblem(SCIP *scip, GCG_SOLVERDATA *solverdata, SCIP *pricingprob, int probnr)
Definition: solver_cplex.c:120
GCG_SolverData::origprob
SCIP * origprob
Definition: solver_cplex.c:84
GCGconsGetVals
SCIP_RETCODE GCGconsGetVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int nvals)
Definition: scip_misc.c:621
CPX_LONG_MAX
#define CPX_LONG_MAX
Definition: solver_cplex.c:61
SOLVER_PRIORITY
#define SOLVER_PRIORITY
Definition: solver_cplex.c:66
GCGconsGetNVars
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:434
solveCplex
static SCIP_RETCODE solveCplex(SCIP *scip, GCG_SOLVERDATA *solverdata, SCIP *pricingprob, int probnr, SCIP_Real dualsolconv, SCIP_Real *lowerbound, int *ncols, GCG_PRICINGSTATUS *status)
Definition: solver_cplex.c:659
GCG_SolverData::startgaplimit
SCIP_Real startgaplimit
Definition: solver_cplex.c:107
GCG_DECL_SOLVERFREE
static GCG_DECL_SOLVERFREE(solverFreeCplex)
Definition: solver_cplex.c:928
GCG_PRICINGSTATUS_UNKNOWN
@ GCG_PRICINGSTATUS_UNKNOWN
Definition: type_pricingstatus.h:46
SOLVER_NAME
#define SOLVER_NAME
Definition: solver_cplex.c:64
GCG_SolverData::sollimitfac
SCIP_Real sollimitfac
Definition: solver_cplex.c:111
GCGpricerAddCol
SCIP_RETCODE GCGpricerAddCol(SCIP *scip, GCG_COL *col)
Definition: pricer_gcg.cpp:4764
GCGisPricingprobRelevant
SCIP_Bool GCGisPricingprobRelevant(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4000
DEFAULT_STARTNODELIMIT
#define DEFAULT_STARTNODELIMIT
Definition: solver_cplex.c:72
GCG_SolverData::checksols
SCIP_Bool checksols
Definition: solver_cplex.c:104
GCG_SolverData::curnodelimit
SCIP_Longint * curnodelimit
Definition: solver_cplex.c:91
GCG_DECL_SOLVERSOLVE
static GCG_DECL_SOLVERSOLVE(solverSolveCplex)
Definition: solver_cplex.c:1142
GCG_SolverData::cursollimit
SCIP_Longint * cursollimit
Definition: solver_cplex.c:93
pub_solver.h
updateVars
static SCIP_RETCODE updateVars(SCIP *scip, GCG_SOLVERDATA *solverdata, SCIP *pricingprob, int probnr, SCIP_Bool varobjschanged, SCIP_Bool varbndschanged)
Definition: solver_cplex.c:374
solverInitCplex
#define solverInitCplex
Definition: solver_cplex.c:1065
updateBranchingConss
static SCIP_RETCODE updateBranchingConss(SCIP *scip, GCG_SOLVERDATA *solverdata, SCIP *pricingprob, int probnr)
Definition: solver_cplex.c:480
GCG_SolverData::nodelimitfac
SCIP_Real nodelimitfac
Definition: solver_cplex.c:109
GCG_SolverData::startnodelimit
SCIP_Longint startnodelimit
Definition: solver_cplex.c:106
DEFAULT_STARTSOLLIMIT
#define DEFAULT_STARTSOLLIMIT
Definition: solver_cplex.c:74
DEFAULT_CHECKSOLS
#define DEFAULT_CHECKSOLS
Definition: solver_cplex.c:70