Scippy

SCIP

Solving Constraint Integer Programs

heur_mpec.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_mpec.c
17  * @brief mpec primal heuristic
18  * @author Felipe Serrano
19  * @author Benjamin Mueller
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "blockmemshell/memory.h"
25 #include "nlpi/nlpi.h"
26 #include "nlpi/pub_expr.h"
27 #include "scip/heur_mpec.h"
28 #include "scip/heur_subnlp.h"
29 #include "scip/pub_cons.h"
30 #include "scip/pub_heur.h"
31 #include "scip/pub_message.h"
32 #include "scip/pub_misc.h"
33 #include "scip/pub_nlp.h"
34 #include "scip/pub_var.h"
35 #include "scip/scip_cons.h"
36 #include "scip/scip_general.h"
37 #include "scip/scip_heur.h"
38 #include "scip/scip_mem.h"
39 #include "scip/scip_message.h"
40 #include "scip/scip_nlp.h"
41 #include "scip/scip_nonlinear.h"
42 #include "scip/scip_numerics.h"
43 #include "scip/scip_param.h"
44 #include "scip/scip_prob.h"
45 #include "scip/scip_sol.h"
46 #include "scip/scip_solvingstats.h"
47 #include "scip/scip_timing.h"
48 #include <string.h>
49 
50 
51 #define HEUR_NAME "mpec"
52 #define HEUR_DESC "regularization heuristic for convex and nonconvex MINLPs"
53 #define HEUR_DISPCHAR 'W'
54 #define HEUR_PRIORITY -2050000
55 #define HEUR_FREQ 50
56 #define HEUR_FREQOFS 0
57 #define HEUR_MAXDEPTH -1
58 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
59 #define HEUR_USESSUBSCIP TRUE /**< disable the heuristic in sub-SCIPs, even though it does not use any */
60 
61 #define DEFAULT_INITTHETA 0.125 /**< default initial regularization right-hand side value (< 0.25) */
62 #define DEFAULT_SIGMA 0.5 /**< default regularization update factor (< 1) */
63 #define DEFAULT_MAXITER 100 /**< default maximum number of iterations of the MPEC loop */
64 #define DEFAULT_MAXNLPITER 500 /**< default maximum number of NLP iterations per solve */
65 #define DEFAULT_MINGAPLEFT 0.05 /**< default minimum amount of gap left in order to call the heuristic */
66 #define DEFAULT_SUBNLPTRIGGER 1e-3 /**< default maximum integrality violation before triggering a sub-NLP call */
67 #define DEFAULT_MAXNLPCOST 1e+8 /**< default maximum cost available for solving NLPs per call of the heuristic */
68 #define DEFAULT_MINIMPROVE 0.01 /**< default factor by which heuristic should at least improve the incumbent */
69 #define DEFAULT_MAXNUNSUCC 10 /**< default maximum number of consecutive calls for which the heuristic did not find an improving solution */
70 
71 /*
72  * Data structures
73  */
74 
75 /** primal heuristic data */
76 struct SCIP_HeurData
77 {
78  SCIP_NLPI* nlpi; /**< nlpi used to create the nlpi problem */
79  SCIP_NLPIPROBLEM* nlpiprob; /**< nlpi problem representing the NLP relaxation */
80  SCIP_HASHMAP* var2idx; /**< mapping between variables and nlpi indices */
81  SCIP_HEUR* subnlp; /**< sub-NLP heuristic */
82 
83  SCIP_Real inittheta; /**< initial regularization right-hand side value */
84  SCIP_Real sigma; /**< regularization update factor */
85  SCIP_Real subnlptrigger; /**< maximum number of NLP iterations per solve */
86  SCIP_Real maxnlpcost; /**< maximum cost available for solving NLPs per call of the heuristic */
87  SCIP_Real minimprove; /**< factor by which heuristic should at least improve the incumbent */
88  SCIP_Real mingapleft; /**< minimum amount of gap left in order to call the heuristic */
89  int maxiter; /**< maximum number of iterations of the MPEC loop */
90  int maxnlpiter; /**< maximum number of NLP iterations per solve */
91  int nunsucc; /**< number of consecutive calls for which the heuristic did not find an
92  * improving solution */
93  int maxnunsucc; /**< maximum number of consecutive calls for which the heuristic did not
94  * find an improving solution */
95 };
96 
97 
98 /*
99  * Local methods
100  */
101 
102 /** creates the data structure for generating the current NLP relaxation */
103 static
105  SCIP* scip, /**< SCIP data structure */
106  SCIP_HEURDATA* heurdata /**< heuristic data */
107  )
108 {
109  SCIP_Real cutoff = SCIPinfinity(scip);
110 
111  assert(heurdata != NULL);
112  assert(heurdata->nlpi != NULL);
113 
114  /* NLP has been already created */
115  if( heurdata->nlpiprob != NULL )
116  return SCIP_OKAY;
117 
118  /* compute cutoff value to ensure minimum improvement */
119  if( SCIPgetNSols(scip) > 0 )
120  {
121  SCIP_Real upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
122 
123  assert( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) );
124 
125  if( !SCIPisInfinity(scip, -SCIPgetLowerbound(scip)) )
126  {
127  cutoff = (1.0 - heurdata->minimprove) * SCIPgetUpperbound(scip)
128  + heurdata->minimprove * SCIPgetLowerbound(scip);
129  }
130  else
131  {
132  if( SCIPgetUpperbound(scip) >= 0.0 )
133  cutoff = ( 1.0 - heurdata->minimprove ) * SCIPgetUpperbound(scip);
134  else
135  cutoff = ( 1.0 + heurdata->minimprove ) * SCIPgetUpperbound(scip);
136  }
137  cutoff = MIN(upperbound, cutoff);
138  SCIPdebugMsg(scip, "set objective limit %g in [%g,%g]\n", cutoff, SCIPgetLowerbound(scip),
139  SCIPgetUpperbound(scip));
140  }
141 
142  SCIP_CALL( SCIPnlpiCreateProblem(heurdata->nlpi, &heurdata->nlpiprob, "MPEC-nlp") );
143  SCIP_CALL( SCIPhashmapCreate(&heurdata->var2idx, SCIPblkmem(scip), SCIPgetNVars(scip)) );
144  SCIP_CALL( SCIPcreateNlpiProb(scip, heurdata->nlpi, SCIPgetNLPNlRows(scip), SCIPgetNNLPNlRows(scip),
145  heurdata->nlpiprob, heurdata->var2idx, NULL, cutoff, TRUE, FALSE) );
146 
147  return SCIP_OKAY;
148 }
149 
150 /** frees the data structures for the NLP relaxation */
151 static
153  SCIP* scip, /**< SCIP data structure */
154  SCIP_HEURDATA* heurdata /**< heuristic data */
155  )
156 {
157  assert(heurdata != NULL);
158 
159  /* NLP has not been created yet */
160  if( heurdata->nlpiprob == NULL )
161  return SCIP_OKAY;
162 
163  assert(heurdata->nlpi != NULL);
164  assert(heurdata->var2idx != NULL);
165 
166  SCIPhashmapFree(&heurdata->var2idx);
167  SCIP_CALL( SCIPnlpiFreeProblem(heurdata->nlpi, &heurdata->nlpiprob) );
168 
169  return SCIP_OKAY;
170 }
171 
172 /** add or updates the regularization constraints to the NLP; for a given parameter theta we add for each non-fixed
173  * binary variable z the constraint z*(1-z) <= theta; if these constraint are already present we update the theta on
174  * the right-hand side
175  */
176 static
178  SCIP* scip, /**< SCIP data structure */
179  SCIP_HEURDATA* heurdata, /**< heuristic data */
180  SCIP_VAR** binvars, /**< array containing all non-fixed binary variables */
181  int nbinvars, /**< total number of non-fixed binary variables */
182  SCIP_Real theta, /**< regularization parameter */
183  SCIP_Bool update /**< should the regularization constraints be added or updated? */
184  )
185 {
186  int i;
187 
188  assert(binvars != NULL);
189  assert(nbinvars > 0);
190 
191  /* add or update regularization for each non-fixed binary variables */
192  if( !update )
193  {
194  SCIP_QUADELEM* quadelems;
195  SCIP_Real* linvals;
196  int* lininds;
197 
198  SCIP_CALL( SCIPallocBufferArray(scip, &quadelems, 1) );
199  SCIP_CALL( SCIPallocBufferArray(scip, &lininds, 1) );
200  SCIP_CALL( SCIPallocBufferArray(scip, &linvals, 1) );
201 
202  for( i = 0; i < nbinvars; ++i )
203  {
204  SCIP_VAR* var = binvars[i];
205  SCIP_Real lhs = -SCIPinfinity(scip);
206  SCIP_Real rhs = theta;
207  int nlininds = 1;
208  int nquadelems = 1;
209  int idx;
210 
211  assert(var != NULL);
212  assert(heurdata->var2idx != NULL);
213  assert(SCIPhashmapExists(heurdata->var2idx, (void*)var));
214  idx = (int)(size_t)SCIPhashmapGetImage(heurdata->var2idx, (void*)var);
215 
216  lininds[0] = idx;
217  linvals[0] = 1.0;
218  quadelems->idx1 = lininds[0];
219  quadelems->idx2 = lininds[0];
220  quadelems->coef = -1.0;
221 
222  SCIP_CALL( SCIPnlpiAddConstraints(heurdata->nlpi, heurdata->nlpiprob, 1, &lhs, &rhs, &nlininds,
223  &lininds, &linvals, &nquadelems, &quadelems, NULL, NULL, NULL) );
224  }
225 
226  SCIPfreeBufferArray(scip, &linvals);
227  SCIPfreeBufferArray(scip, &lininds);
228  SCIPfreeBufferArray(scip, &quadelems);
229  }
230  else
231  {
232  int startidx = SCIPgetNNLPNlRows(scip) + 1; /* the cutoff is a separate constraint */
233  SCIP_Real* lhss;
234  SCIP_Real* rhss;
235  int* indices;
236 
237  SCIP_CALL( SCIPallocBufferArray(scip, &lhss, nbinvars) );
238  SCIP_CALL( SCIPallocBufferArray(scip, &rhss, nbinvars) );
239  SCIP_CALL( SCIPallocBufferArray(scip, &indices, nbinvars) );
240 
241  for( i = 0; i < nbinvars; ++i )
242  {
243  lhss[i] = -SCIPinfinity(scip);
244  rhss[i] = theta;
245  indices[i] = startidx + i;
246  }
247 
248  SCIP_CALL( SCIPnlpiChgConsSides(heurdata->nlpi, heurdata->nlpiprob, nbinvars, indices, lhss, rhss) );
249 
250  SCIPfreeBufferArray(scip, &indices);
251  SCIPfreeBufferArray(scip, &rhss);
252  SCIPfreeBufferArray(scip, &lhss);
253  }
254 
255  return SCIP_OKAY;
256 }
257 
258 /** recursive helper function to count the number of nodes in a sub-tree */
259 static
261  SCIP_EXPR* expr /**< expression */
262  )
263 {
264  int sum;
265  int i;
266 
267  assert(expr != NULL);
268 
269  sum = 0;
270  for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
271  {
272  SCIP_EXPR* child = SCIPexprGetChildren(expr)[i];
273  sum += getExprSize(child);
274  }
275  return 1 + sum;
276 }
277 
278 /** returns the number of nodes in an expression tree */
279 static
281  SCIP_EXPRTREE* tree /**< expression tree */
282  )
283 {
284  if( tree == NULL )
285  return 0;
286  return getExprSize(SCIPexprtreeGetRoot(tree));
287 }
288 
289 /** returns the available time limit that is left */
290 static
292  SCIP* scip, /**< SCIP data structure */
293  SCIP_Real* timeleft /**< pointer to store the remaining time limit */
294  )
295 {
296  SCIP_Real timelim;
297 
298  assert(timeleft != NULL);
299 
300  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelim) );
301 
302  if( SCIPisInfinity(scip, timelim) )
303  *timeleft = timelim - SCIPgetSolvingTime(scip);
304  else
305  *timeleft = SCIPinfinity(scip);
306 
307  return SCIP_OKAY;
308 }
309 
310 /** main execution function of the MPEC heuristic */
311 static
313  SCIP* scip, /**< SCIP data structure */
314  SCIP_HEUR* heur, /**< MPEC heuristic */
315  SCIP_HEURDATA* heurdata, /**< heuristic data */
316  SCIP_RESULT* result /**< pointer to store the result */
317  )
318 {
319  SCIP_NLPSTATISTICS* nlpstatistics = NULL;
320  SCIP_VAR** binvars = NULL;
321  SCIP_Real* initguess = NULL;
322  SCIP_Real* ubs = NULL;
323  SCIP_Real* lbs = NULL;
324  int* indices = NULL;
325  SCIP_Real theta = heurdata->inittheta;
326  SCIP_Real nlpcostperiter = 0.0;
327  SCIP_Real nlpcostleft = heurdata->maxnlpcost;
328  SCIP_Bool reinit = TRUE;
329  SCIP_Bool fixed = FALSE;
330  SCIP_Bool subnlpcalled = FALSE;
331  int nbinvars = 0;
332  int i;
333 
334  assert(heurdata->nlpiprob != NULL);
335  assert(heurdata->var2idx != NULL);
336  assert(heurdata->nlpi != NULL);
337  assert(result != NULL);
338 
339  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, SCIPgetNBinVars(scip)) );
340  SCIP_CALL( SCIPnlpStatisticsCreate(SCIPblkmem(scip), &nlpstatistics) );
341 
342  /* collect all non-fixed binary variables */
343  for( i = 0; i < SCIPgetNBinVars(scip); ++i )
344  {
345  SCIP_VAR* var = SCIPgetVars(scip)[i];
346  assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY);
347 
348  if( !SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
349  binvars[nbinvars++] = var;
350  }
351 
352  /* all binary variables are fixed */
353  SCIPdebugMsg(scip, "nbinvars %d\n", nbinvars);
354  if( nbinvars == 0 )
355  goto TERMINATE;
356 
357  SCIP_CALL( SCIPallocBufferArray(scip, &initguess, SCIPgetNVars(scip)) );
358  SCIP_CALL( SCIPallocBufferArray(scip, &lbs, nbinvars) );
359  SCIP_CALL( SCIPallocBufferArray(scip, &ubs, nbinvars) );
360  SCIP_CALL( SCIPallocBufferArray(scip, &indices, nbinvars) );
361 
362  /* compute estimate cost for each NLP iteration */
363  for( i = 0; i < SCIPgetNNLPNlRows(scip); ++i )
364  {
365  SCIP_NLROW* nlrow = SCIPgetNLPNlRows(scip)[i];
366  assert(nlrow != NULL);
367 
368  nlpcostperiter += 1.0 * SCIPnlrowGetNLinearVars(nlrow)
369  + 2.0 * SCIPnlrowGetNQuadElems(nlrow)
370  + 3.0 * getExprtreeSize(SCIPnlrowGetExprtree(nlrow));
371  }
372 
373  /* set initial guess */
374  for( i = 0; i < SCIPgetNVars(scip); ++i )
375  {
376  SCIP_VAR* var = SCIPgetVars(scip)[i];
377  initguess[i] = SCIPgetSolVal(scip, NULL, var);
378  /* SCIPdebugMsg(scip, "set initial value for %s to %g\n", SCIPvarGetName(var), initguess[i]); */
379  }
380  SCIP_CALL( SCIPnlpiSetInitialGuess(heurdata->nlpi, heurdata->nlpiprob, initguess, NULL, NULL, NULL) );
381 
382  /* set parameters of NLP solver */
383  SCIP_CALL( SCIPnlpiSetRealPar(heurdata->nlpi, heurdata->nlpiprob, SCIP_NLPPAR_FEASTOL,
384  SCIPfeastol(scip) / 10.0) );
385  SCIP_CALL( SCIPnlpiSetRealPar(heurdata->nlpi, heurdata->nlpiprob, SCIP_NLPPAR_RELOBJTOL,
386  SCIPdualfeastol(scip) / 10.0) );
387  SCIP_CALL( SCIPnlpiSetIntPar(heurdata->nlpi, heurdata->nlpiprob, SCIP_NLPPAR_VERBLEVEL, 0) );
388 
389  /* main loop */
390  for( i = 0; i < heurdata->maxiter && *result != SCIP_FOUNDSOL && nlpcostleft > 0.0 && !SCIPisStopped(scip); ++i )
391  {
392  SCIP_Real* primal = NULL;
393  SCIP_Real timeleft = SCIPinfinity(scip);
394  SCIP_Bool binaryfeasible;
395  SCIP_Bool regularfeasible;
396  SCIP_NLPSOLSTAT solstat;
397  SCIP_Real maxviolbin = 0.0;
398  SCIP_Real maxviolreg = 0.0;
399  int j;
400 
401  /* add or update regularization */
402  SCIP_CALL( addRegularScholtes(scip, heurdata, binvars, nbinvars, theta, i > 0) );
403 
404  /* set working limits */
405  SCIP_CALL( getTimeLeft(scip, &timeleft) );
406  if( timeleft <= 0.0 )
407  {
408  SCIPdebugMsg(scip, "skip NLP solve; no time left\n");
409  break;
410  }
411 
412  SCIP_CALL( SCIPnlpiSetRealPar(heurdata->nlpi, heurdata->nlpiprob, SCIP_NLPPAR_TILIM, timeleft) );
413  SCIP_CALL( SCIPnlpiSetIntPar(heurdata->nlpi, heurdata->nlpiprob, SCIP_NLPPAR_ITLIM, heurdata->maxnlpiter) );
414 
415  /* solve NLP */
416  SCIP_CALL( SCIPnlpiSolve(heurdata->nlpi, heurdata->nlpiprob) );
417  solstat = SCIPnlpiGetSolstat(heurdata->nlpi, heurdata->nlpiprob);
418 
419  /* give up if an error occurred or no primal values are accessible */
420  if( solstat > SCIP_NLPSOLSTAT_LOCINFEASIBLE )
421  {
422  SCIPdebugMsg(scip, "error occured during NLP solve -> stop!\n");
423  break;
424  }
425 
426  /* update nlpcostleft */
427  SCIP_CALL( SCIPnlpiGetStatistics(heurdata->nlpi, heurdata->nlpiprob, nlpstatistics) );
428  nlpcostleft -= SCIPnlpStatisticsGetNIterations(nlpstatistics) * nlpcostperiter * nbinvars;
429  SCIPdebugMsg(scip, "nlpcostleft = %e\n", nlpcostleft);
430 
431  SCIP_CALL( SCIPnlpiGetSolution(heurdata->nlpi, heurdata->nlpiprob, &primal, NULL, NULL, NULL, NULL) );
432  assert(primal != NULL);
433 
434  /* check for binary feasibility */
435  binaryfeasible = TRUE;
436  regularfeasible = TRUE;
437  for( j = 0; j < nbinvars; ++j )
438  {
439  int idx = (int)(size_t)SCIPhashmapGetImage(heurdata->var2idx, (void*)binvars[j]);
440  binaryfeasible = binaryfeasible && SCIPisFeasIntegral(scip, primal[idx]);
441  regularfeasible = regularfeasible && SCIPisLE(scip, primal[idx] - SQR(primal[idx]), theta);
442 
443  maxviolreg = MAX(maxviolreg, primal[idx] - SQR(primal[idx]) - theta);
444  maxviolbin = MAX(maxviolbin, MIN(primal[idx], 1.0-primal[idx]));
445  }
446  SCIPdebugMsg(scip, "maxviol-regularization %g maxviol-integrality %g\n", maxviolreg, maxviolbin);
447 
448  /* call sub-NLP heuristic when the maximum binary infeasibility is small enough (or this is the last iteration
449  * because we reached the nlpcost limit)
450  */
451  if( !subnlpcalled && heurdata->subnlp != NULL
452  && (SCIPisLE(scip, maxviolbin, heurdata->subnlptrigger) || nlpcostleft <= 0.0)
453  && !SCIPisStopped(scip) )
454  {
455  SCIP_SOL* refpoint;
456  SCIP_RESULT subnlpresult;
457 
458  SCIPdebugMsg(scip, "call sub-NLP heuristic because binary infeasibility is small enough\n");
459  SCIP_CALL( SCIPcreateSol(scip, &refpoint, heur) );
460 
461  for( j = 0; j < SCIPgetNVars(scip); ++j )
462  {
463  SCIP_VAR* var = SCIPgetVars(scip)[j];
464  SCIP_Real val = SCIPvarIsBinary(var) ? SCIPfeasRound(scip, primal[j]) : primal[j];
465  SCIP_CALL( SCIPsetSolVal(scip, refpoint, var, val) );
466  }
467 
468  SCIP_CALL( getTimeLeft(scip, &timeleft) );
469  SCIP_CALL( SCIPapplyHeurSubNlp(scip, heurdata->subnlp, &subnlpresult, refpoint, -1LL, timeleft,
470  heurdata->minimprove, NULL,
471  NULL) );
472  SCIP_CALL( SCIPfreeSol(scip, &refpoint) );
473  SCIPdebugMsg(scip, "result of sub-NLP call: %d\n", subnlpresult);
474 
475  /* stop MPEC heuristic when the sub-NLP heuristic has found a feasible solution */
476  if( subnlpresult == SCIP_FOUNDSOL )
477  {
478  SCIPdebugMsg(scip, "sub-NLP found a feasible solution -> stop!\n");
479  break;
480  }
481 
482  subnlpcalled = TRUE;
483  }
484 
485  /* NLP feasible + binary feasible -> add solution and stop */
486  if( solstat <= SCIP_NLPSOLSTAT_FEASIBLE && binaryfeasible )
487  {
488  SCIP_SOL* sol;
489  SCIP_Bool stored;
490 
491  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
492 
493  for( j = 0; j < SCIPgetNVars(scip); ++j )
494  {
495  SCIP_VAR* var = SCIPgetVars(scip)[j];
496  assert(j == (int)(size_t)SCIPhashmapGetImage(heurdata->var2idx, (void*)var));
497  SCIP_CALL( SCIPsetSolVal(scip, sol, var, primal[j]) );
498  }
499 
500 #ifdef SCIP_DEBUG
501  SCIP_CALL( SCIPtrySolFree(scip, &sol, TRUE, TRUE, TRUE, TRUE, FALSE, &stored) );
502 #else
503  SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, TRUE, TRUE, FALSE, &stored) );
504 #endif
505  SCIPdebugMsg(scip, "found a solution (stored = %u)\n", stored);
506 
507  if( stored )
508  *result = SCIP_FOUNDSOL;
509  break;
510  }
511 
512  /* NLP feasible + binary infeasible -> reduce theta */
513  else if( solstat <= SCIP_NLPSOLSTAT_FEASIBLE && !binaryfeasible )
514  {
515  BMScopyMemoryArray(initguess, primal, SCIPgetNVars(scip));
516  SCIP_CALL( SCIPnlpiSetInitialGuess(heurdata->nlpi, heurdata->nlpiprob, primal, NULL, NULL, NULL) );
517  SCIPdebugMsg(scip, "update theta from %g -> %g\n", theta, theta*heurdata->sigma);
518 
519  if( !reinit )
520  {
521  SCIPdebugMsg(scip, "reinit fixed the infeasibility\n");
522  reinit = TRUE;
523  }
524 
525  theta *= heurdata->sigma;
526 
527  /* unfix binary variables */
528  if( fixed )
529  {
530  SCIPdebugMsg(scip, "unfixing binary variables\n");
531  for( j = 0; j < nbinvars; ++j )
532  {
533  lbs[j] = 0.0;
534  ubs[j] = 1.0;
535  indices[j] = (int)(size_t)SCIPhashmapGetImage(heurdata->var2idx, (void*)binvars[j]);
536  }
537  SCIP_CALL( SCIPnlpiChgVarBounds(heurdata->nlpi, heurdata->nlpiprob, nbinvars, indices, lbs, ubs) );
538  fixed = FALSE;
539  }
540  }
541 
542  /* NLP infeasible + regularization feasible -> stop (give up) */
543  else if( solstat > SCIP_NLPSOLSTAT_FEASIBLE && regularfeasible )
544  {
545  SCIPdebugMsg(scip, "NLP is infeasible but regularization constraints are satisfied -> stop!\n");
546  break;
547  }
548 
549  /* NLP infeasible + binary infeasible -> set initial point / fix binary variables */
550  else
551  {
552  assert(solstat > SCIP_NLPSOLSTAT_FEASIBLE && !regularfeasible);
553 
554  SCIPdebugMsg(scip, "NLP solution is not feasible for the NLP and the binary variables\n");
555 
556  /* stop if fixing did not resolve the infeasibility */
557  if( fixed )
558  {
559  SCIPdebugMsg(scip, "fixing variables did not resolve infeasibility -> stop!\n");
560  break;
561  }
562 
563  /* fix variables if reinit is FALSE; otherwise set another initial point */
564  if( !reinit )
565  {
566  int nfixedvars = 0;
567 
568  /* fix binary variables */
569  for( j = 0; j < nbinvars; ++j )
570  {
571  int idx = (int)(size_t)SCIPhashmapGetImage(heurdata->var2idx, (void*)binvars[j]);
572  indices[j] = idx;
573 
574  if( SCIPisFeasLE(scip, primal[idx] - SQR(primal[idx]), theta) )
575  {
576  lbs[j] = 0.0;
577  ubs[j] = 1.0;
578  }
579  else
580  {
581  lbs[j] = primal[idx] >= 0.5 ? 0.0 : 1.0;
582  ubs[j] = primal[idx] >= 0.5 ? 0.0 : 1.0;
583  ++nfixedvars;
584  /* SCIPdebugMsg(scip, "fix binary variable %s = %g\n", SCIPvarGetName(binvars[j]), ubs[j]); */
585  }
586  }
587  SCIPdebugMsg(scip, "fixed %d binary variables\n", nfixedvars);
588  SCIP_CALL( SCIPnlpiChgVarBounds(heurdata->nlpi, heurdata->nlpiprob, nbinvars, indices, lbs, ubs) );
589  fixed = TRUE;
590  }
591  else
592  {
593  SCIPdebugMsg(scip, "update initial guess\n");
594 
595  /* set initial point */
596  for( j = 0; j < nbinvars; ++j )
597  {
598  int idx = (int)(size_t)SCIPhashmapGetImage(heurdata->var2idx, (void*)binvars[j]);
599  initguess[idx] = primal[idx] >= 0.5 ? 0.0 : 1.0;
600  /* SCIPdebugMsg(scip, "update init guess for %s to %g\n", SCIPvarGetName(binvars[j]), initguess[idx]); */
601  }
602  SCIP_CALL( SCIPnlpiSetInitialGuess(heurdata->nlpi, heurdata->nlpiprob, initguess, NULL, NULL, NULL) );
603  reinit = FALSE;
604  }
605  }
606  }
607 
608 TERMINATE:
609  SCIPfreeBufferArrayNull(scip, &indices);
610  SCIPfreeBufferArrayNull(scip, &ubs);
611  SCIPfreeBufferArrayNull(scip, &lbs);
612  SCIPfreeBufferArrayNull(scip, &initguess);
613  SCIPnlpStatisticsFree(SCIPblkmem(scip), &nlpstatistics);
614  SCIPfreeBufferArray(scip, &binvars);
615 
616  return SCIP_OKAY;
617 }
618 
619 
620 /*
621  * Callback methods of primal heuristic
622  */
623 
624 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
625 static
626 SCIP_DECL_HEURCOPY(heurCopyMpec)
627 { /*lint --e{715}*/
628  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
629 
630  /* call inclusion method of primal heuristic */
632 
633  return SCIP_OKAY;
634 }
635 
636 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
637 static
638 SCIP_DECL_HEURFREE(heurFreeMpec)
639 { /*lint --e{715}*/
640  SCIP_HEURDATA* heurdata = SCIPheurGetData(heur);
641  assert(heurdata != NULL);
642 
643  SCIPfreeBlockMemory(scip, &heurdata);
644  SCIPheurSetData(heur, NULL);
645 
646  return SCIP_OKAY;
647 }
648 
649 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
650 static
651 SCIP_DECL_HEURINITSOL(heurInitsolMpec)
652 { /*lint --e{715}*/
653  SCIP_HEURDATA* heurdata = SCIPheurGetData(heur);
654 
655  assert(heurdata != NULL);
656  assert(heurdata->nlpi == NULL);
657 
658  if( SCIPgetNNlpis(scip) > 0 )
659  {
660  heurdata->nlpi = SCIPgetNlpis(scip)[0];
661  heurdata->subnlp = SCIPfindHeur(scip, "subnlp");
662  }
663 
664  return SCIP_OKAY;
665 }
666 
667 
668 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
669 static
670 SCIP_DECL_HEUREXITSOL(heurExitsolMpec)
671 { /*lint --e{715}*/
672  SCIP_HEURDATA* heurdata = SCIPheurGetData(heur);
673 
674  assert(heurdata != NULL);
675  heurdata->nlpi = NULL;
676 
677  return SCIP_OKAY;
678 }
679 
680 /** execution method of primal heuristic */
681 static
682 SCIP_DECL_HEUREXEC(heurExecMpec)
683 { /*lint --e{715}*/
684  SCIP_HEURDATA* heurdata = SCIPheurGetData(heur);
685  SCIP_CONSHDLR* andhdlr = SCIPfindConshdlr(scip, "and");
686  SCIP_CONSHDLR* sosonehdlr = SCIPfindConshdlr(scip, "SOS1");
687  SCIP_CONSHDLR* sostwohdlr = SCIPfindConshdlr(scip, "SOS2");
688 
689  assert(heurdata != NULL);
690 
691  *result = SCIP_DIDNOTRUN;
692 
693  if( SCIPgetNIntVars(scip) > 0 || SCIPgetNBinVars(scip) == 0
694  || heurdata->nlpi == NULL || !SCIPisNLPConstructed(scip)
695  || heurdata->mingapleft > SCIPgetGap(scip)
696  || heurdata->nunsucc > heurdata->maxnunsucc )
697  return SCIP_OKAY;
698 
699  /* skip heuristic if constraints without a nonlinear representation are present */
700  if( (andhdlr != NULL && SCIPconshdlrGetNConss(andhdlr) > 0) ||
701  (sosonehdlr != NULL && SCIPconshdlrGetNConss(sosonehdlr) > 0) ||
702  (sostwohdlr != NULL && SCIPconshdlrGetNConss(sostwohdlr) > 0) )
703  {
704  return SCIP_OKAY;
705  }
706 
707  *result = SCIP_DIDNOTFIND;
708 
709  /* call MPEC method */
710  SCIP_CALL( createNLP(scip, heurdata) );
711  SCIP_CALL( heurExec(scip, heur, heurdata, result) );
712  SCIP_CALL( freeNLP(scip, heurdata) );
713 
714  /* update number of unsuccessful calls */
715  heurdata->nunsucc = (*result == SCIP_FOUNDSOL) ? 0 : heurdata->nunsucc + 1;
716 
717  return SCIP_OKAY;
718 }
719 
720 
721 /*
722  * primal heuristic specific interface methods
723  */
724 
725 /** creates the mpec primal heuristic and includes it in SCIP */
727  SCIP* scip /**< SCIP data structure */
728  )
729 {
730  SCIP_HEURDATA* heurdata = NULL;
731  SCIP_HEUR* heur = NULL;
732 
733  /* create mpec primal heuristic data */
734  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
735  BMSclearMemory(heurdata);
736 
737  /* include primal heuristic */
738  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
740  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecMpec, heurdata) );
741 
742  assert(heur != NULL);
743 
744  /* set non fundamental callbacks via setter functions */
745  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyMpec) );
746  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeMpec) );
747  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolMpec) );
748  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolMpec) );
749 
750  /* add mpec primal heuristic parameters */
751  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/inittheta",
752  "initial regularization right-hand side value",
753  &heurdata->inittheta, FALSE, DEFAULT_INITTHETA, 0.0, 0.25, NULL, NULL) );
754 
755  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/sigma",
756  "regularization update factor",
757  &heurdata->sigma, FALSE, DEFAULT_SIGMA, 0.0, 1.0, NULL, NULL) );
758 
759  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/subnlptrigger",
760  "maximum number of NLP iterations per solve",
761  &heurdata->subnlptrigger, FALSE, DEFAULT_SUBNLPTRIGGER, 0.0, 1.0, NULL, NULL) );
762 
763  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxnlpcost",
764  "maximum cost available for solving NLPs per call of the heuristic",
765  &heurdata->maxnlpcost, FALSE, DEFAULT_MAXNLPCOST, 0.0, SCIPinfinity(scip), NULL, NULL) );
766 
767  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
768  "factor by which heuristic should at least improve the incumbent",
769  &heurdata->minimprove, FALSE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
770 
771  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mingapleft",
772  "minimum amount of gap left in order to call the heuristic",
773  &heurdata->mingapleft, FALSE, DEFAULT_MINGAPLEFT, 0.0, SCIPinfinity(scip), NULL, NULL) );
774 
775  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxiter",
776  "maximum number of iterations of the MPEC loop",
777  &heurdata->maxiter, FALSE, DEFAULT_MAXITER, 0, INT_MAX, NULL, NULL) );
778 
779  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnlpiter",
780  "maximum number of NLP iterations per solve",
781  &heurdata->maxnlpiter, FALSE, DEFAULT_MAXNLPITER, 0, INT_MAX, NULL, NULL) );
782 
783  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnunsucc",
784  "maximum number of consecutive calls for which the heuristic did not find an improving solution",
785  &heurdata->maxnunsucc, FALSE, DEFAULT_MAXNUNSUCC, 0, INT_MAX, NULL, NULL) );
786 
787  return SCIP_OKAY;
788 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:312
SCIP_RETCODE SCIPincludeHeurMpec(SCIP *scip)
Definition: heur_mpec.c:726
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2134
static SCIP_RETCODE heurExec(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result)
Definition: heur_mpec.c:312
#define HEUR_FREQ
Definition: heur_mpec.c:55
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:513
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:436
mpec primal heuristic
#define NULL
Definition: def.h:239
SCIP_RETCODE SCIPnlpiGetStatistics(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPSTATISTICS *statistics)
Definition: nlpi.c:556
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:284
static SCIP_DECL_HEURFREE(heurFreeMpec)
Definition: heur_mpec.c:638
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
public methods for memory management
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:954
SCIP_RETCODE SCIPcreateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLROW **nlrows, int nnlrows, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:379
#define SQR(x)
Definition: def.h:191
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17399
internal methods for NLPI solver interfaces
SCIP_RETCODE SCIPnlpiCreateProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem, const char *name)
Definition: nlpi.c:211
public methods for timing
SCIP_Real SCIPfeasRound(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16909
SCIP_RETCODE SCIPnlpiGetSolution(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_Real **primalvalues, SCIP_Real **consdualvalues, SCIP_Real **varlbdualvalues, SCIP_Real **varubdualvalues, SCIP_Real *objval)
Definition: nlpi.c:537
SCIP_Real SCIPdualfeastol(SCIP *scip)
#define DEFAULT_SUBNLPTRIGGER
Definition: heur_mpec.c:66
#define FALSE
Definition: def.h:65
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
SCIP_RETCODE SCIPnlpiAddConstraints(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nconss, const SCIP_Real *lhss, const SCIP_Real *rhss, const int *nlininds, int *const *lininds, SCIP_Real *const *linvals, const int *nquadelems, SCIP_QUADELEM *const *quadelems, int *const *exprvaridxs, SCIP_EXPRTREE *const *exprtrees, const char **names)
Definition: nlpi.c:268
static SCIP_RETCODE createNLP(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_mpec.c:104
#define DEFAULT_MAXNLPITER
Definition: heur_mpec.c:64
SCIP_Real SCIPinfinity(SCIP *scip)
#define HEUR_USESSUBSCIP
Definition: heur_mpec.c:59
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define DEFAULT_MAXNLPCOST
Definition: heur_mpec.c:67
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3246
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:187
SCIP_RETCODE SCIPnlpiChgVarBounds(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nvars, const int *indices, const SCIP_Real *lbs, const SCIP_Real *ubs)
Definition: nlpi.c:325
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
void SCIPnlpStatisticsFree(BMS_BLKMEM *blkmem, SCIP_NLPSTATISTICS **statistics)
Definition: nlpi.c:801
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
#define DEFAULT_MAXNUNSUCC
Definition: heur_mpec.c:69
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:155
#define DEFAULT_MINGAPLEFT
Definition: heur_mpec.c:65
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:491
#define HEUR_DESC
Definition: heur_mpec.c:52
#define DEFAULT_MAXITER
Definition: heur_mpec.c:63
public methods for numerical tolerances
int SCIPnlrowGetNQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3323
public methods for expressions, expression trees, expression graphs, and related stuff ...
static SCIP_DECL_HEUREXITSOL(heurExitsolMpec)
Definition: heur_mpec.c:670
public methods for querying solving statistics
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3025
SCIP_RETCODE SCIPnlpiSolve(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:497
SCIP_Real coef
Definition: type_expr.h:104
public methods for managing constraints
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:296
static SCIP_RETCODE getTimeLeft(SCIP *scip, SCIP_Real *timeleft)
Definition: heur_mpec.c:291
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:328
static int getExprtreeSize(SCIP_EXPRTREE *tree)
Definition: heur_mpec.c:280
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:248
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition: type_nlpi.h:69
public methods for nonlinear functions
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:143
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:128
static SCIP_DECL_HEURCOPY(heurCopyMpec)
Definition: heur_mpec.c:626
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
int SCIPgetNNlpis(SCIP *scip)
Definition: scip_nlp.c:206
SCIP_RETCODE SCIPnlpiChgConsSides(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nconss, const int *indices, const SCIP_Real *lhss, const SCIP_Real *rhss)
Definition: nlpi.c:343
#define SCIP_CALL(x)
Definition: def.h:351
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_RETCODE SCIPnlpiSetInitialGuess(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_Real *primalvalues, SCIP_Real *consdualvalues, SCIP_Real *varlbdualvalues, SCIP_Real *varubdualvalues)
Definition: nlpi.c:479
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_HEUREXEC(heurExecMpec)
Definition: heur_mpec.c:682
#define HEUR_TIMING
Definition: heur_mpec.c:58
#define HEUR_PRIORITY
Definition: heur_mpec.c:54
SCIP_EXPR * SCIPexprtreeGetRoot(SCIP_EXPRTREE *tree)
Definition: expr.c:8602
SCIP_NLPSOLSTAT SCIPnlpiGetSolstat(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:511
public methods for primal heuristic plugins and divesets
static SCIP_RETCODE freeNLP(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_mpec.c:152
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4593
public methods for constraint handler plugins and constraints
public methods for NLP management
#define HEUR_MAXDEPTH
Definition: heur_mpec.c:57
#define HEUR_NAME
Definition: heur_mpec.c:51
SCIP_RETCODE SCIPnlpiFreeProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem)
Definition: nlpi.c:224
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1270
public data structures and miscellaneous methods
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:5713
#define SCIP_Bool
Definition: def.h:62
#define DEFAULT_INITTHETA
Definition: heur_mpec.c:61
SCIP_RETCODE SCIPnlpiSetIntPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, int ival)
Definition: nlpi.c:636
SCIP_Real SCIPgetGap(SCIP *scip)
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3291
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:5703
#define MIN(x, y)
Definition: def.h:209
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:1034
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2280
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:116
SCIP_RETCODE SCIPapplyHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint, SCIP_Longint itercontingent, SCIP_Real timelimit, SCIP_Real minimprove, SCIP_Longint *iterused, SCIP_SOL *resultsol)
Definition: heur_subnlp.c:1700
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define BMSclearMemory(ptr)
Definition: memory.h:111
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2089
static int getExprSize(SCIP_EXPR *expr)
Definition: heur_mpec.c:260
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2044
public methods for nonlinear relaxations
SCIP_EXPRTREE * SCIPnlrowGetExprtree(SCIP_NLROW *nlrow)
Definition: nlp.c:3364
#define HEUR_DISPCHAR
Definition: heur_mpec.c:53
general public methods
#define MAX(x, y)
Definition: def.h:208
public methods for solutions
static SCIP_DECL_HEURINITSOL(heurInitsolMpec)
Definition: heur_mpec.c:651
#define DEFAULT_SIGMA
Definition: heur_mpec.c:62
public methods for message output
NLP local search primal heuristic using sub-SCIPs.
SCIP_RETCODE SCIPnlpStatisticsCreate(BMS_BLKMEM *blkmem, SCIP_NLPSTATISTICS **statistics)
Definition: nlpi.c:784
#define HEUR_FREQOFS
Definition: heur_mpec.c:56
static SCIP_RETCODE addRegularScholtes(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **binvars, int nbinvars, SCIP_Real theta, SCIP_Bool update)
Definition: heur_mpec.c:177
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
#define SCIP_Real
Definition: def.h:150
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:739
public methods for message handling
int SCIPnlpStatisticsGetNIterations(SCIP_NLPSTATISTICS *statistics)
Definition: nlpi.c:816
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16894
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:232
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17409
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
Definition: scip_nlp.c:193
SCIP_Real SCIPgetUpperbound(SCIP *scip)
public methods for primal heuristics
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:211
#define DEFAULT_MINIMPROVE
Definition: heur_mpec.c:68
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:377
SCIP_RETCODE SCIPnlpiSetRealPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, SCIP_Real dval)
Definition: nlpi.c:671
memory allocation routines