Scippy

SCIP

Solving Constraint Integer Programs

heur_octane.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-2017 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_octane.c
17  * @brief octane primal heuristic based on Balas, Ceria, Dawande, Margot, and Pataki
18  * @author Timo Berthold
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 #include <math.h>
26 #include "scip/heur_octane.h"
27 
28 #define HEUR_NAME "octane"
29 #define HEUR_DESC "octane primal heuristic for pure {0;1}-problems based on Balas et al."
30 #define HEUR_DISPCHAR 'O'
31 #define HEUR_PRIORITY -1008000
32 #define HEUR_FREQ -1
33 #define HEUR_FREQOFS 0
34 #define HEUR_MAXDEPTH -1
35 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
36 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
37 
38 #define DEFAULT_FMAX 100 /**< {0,1}-points to be checked */
39 #define DEFAULT_FFIRST 10 /**< {0,1}-points to be generated at first */
40 #define DEFAULT_USEFRACSPACE TRUE /**< use heuristic for the space of fractional variables or for whole space? */
41 
42 /** primal heuristic data */
43 struct SCIP_HeurData
44 {
45  SCIP_SOL* sol; /**< working solution */
46  int f_max; /**< {0,1}-points to be checked */
47  int f_first; /**< {0,1}-points to be generated at first in order to check whether restart is necessary */
48  int lastrule; /**< last ray selection rule that was performed */
49  SCIP_Bool usefracspace; /**< use heuristic for the space of fractional variables or for the whole space? */
50  SCIP_Bool useobjray; /**< should the inner normal of the objective be used as one ray direction? */
51  SCIP_Bool useavgray; /**< should the average ray of the basic cone be used as one ray direction? */
52  SCIP_Bool usediffray; /**< should difference between root sol and current LP sol be used as one ray direction? */
53  SCIP_Bool useavgwgtray; /**< should the weighted average ray of the basic cone be used as one ray direction? */
54  SCIP_Bool useavgnbray; /**< should the average ray of the nonbasic cone be used as one ray direction? */
55  int nsuccess; /**< number of runs that produced at least one feasible solution */
56 };
57 
58 /*
59  * Local methods
60  */
61 
62 
63 /** tries to insert the facet obtained from facet i flipped in component j into the list of the fmax nearest facets */
64 static
66  SCIP* scip, /**< SCIP data structure */
67  SCIP_Bool** facets, /**< facets got so far */
68  SCIP_Real* lambda, /**< distances of the facets */
69  int i, /**< current facet */
70  int j, /**< component to flip */
71  int f_max, /**< maximal number of facets to create */
72  int nsubspacevars, /**< dimension of the fractional space */
73  SCIP_Real lam, /**< distance of the current facet */
74  int* nfacets /**< number of facets */
75  )
76 {
77  SCIP_Bool* lastfacet;
78  int k;
79 
80  assert(scip != NULL);
81  assert(facets != NULL);
82  assert(lambda != NULL);
83  assert(nfacets != NULL);
84 
85  if( SCIPisFeasLE(scip, lam, 0.0) || SCIPisFeasGE(scip, lam, lambda[f_max-1]) )
86  return;
87 
88  lastfacet = facets[f_max];
89 
90  /* shifting lam through lambda, lambda keeps increasingly sorted */
91  for( k = f_max; k > 0 && SCIPisFeasGT(scip, lambda[k-1], lam); --k )
92  {
93  lambda[k] = lambda[k-1];
94  facets[k] = facets[k-1];
95  }
96  assert(i < k && k < f_max );
97 
98  /* inserting new facet into list, new facet is facet at position i flipped in coordinate j, new distance lam */
99  facets[k] = lastfacet;
100  lambda[k] = lam;
101 
102  /*lint --e{866}*/
103  BMScopyMemoryArray(facets[k], facets[i], nsubspacevars);
104  facets[k][j] = !facets[k][j];
105  (*nfacets)++;
106 }
107 
108 /** constructs a solution from a given facet paying attention to the transformations made at the beginning of OCTANE */
109 static
111  SCIP* scip, /**< SCIP data structure */
112  SCIP_Bool* facet, /**< current facet */
113  SCIP_SOL* sol, /**< solution to create */
114  SCIP_Bool* sign, /**< marker for retransformation */
115  SCIP_VAR** subspacevars, /**< pointer to fractional space variables */
116  int nsubspacevars /**< dimension of fractional space */
117  )
118 {
119  int v;
120 
121  assert(scip != NULL);
122  assert(facet != NULL);
123  assert(sol != NULL);
124  assert(sign != NULL);
125  assert(subspacevars != NULL);
126 
127  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
128  for( v = nsubspacevars - 1; v >= 0; --v )
129  {
130  /* after permutation, a variable should be set to 1, iff there was no reflection in this coordinate and the hit
131  * facet has coordinate + or there was a reflection and the facet has coordinate - */
132  if( facet[v] == sign[v] )
133  {
134  SCIP_CALL( SCIPsetSolVal(scip, sol, subspacevars[v], 1.0) );
135  }
136  else
137  {
138  SCIP_CALL( SCIPsetSolVal(scip, sol, subspacevars[v], 0.0) );
139  }
140  }
141 
142  return SCIP_OKAY;
143 }
144 
145 /** generates the direction of the shooting ray as the inner normal of the objective function */
146 static
148  SCIP* scip, /**< SCIP data structure */
149  SCIP_Real* raydirection, /**< shooting ray */
150  SCIP_VAR** subspacevars, /**< pointer to fractional space variables */
151  int nsubspacevars /**< dimension of fractional space */
152  )
153 {
154  int v;
155 
156  assert(scip != NULL);
157  assert(raydirection != NULL);
158  assert(subspacevars != NULL);
159 
160  for( v = nsubspacevars - 1; v >= 0; --v )
161  raydirection[v] = SCIPvarGetObj(subspacevars[v]);
162  return SCIP_OKAY;
163 }
164 
165 /** generates the direction of the shooting ray as the difference between the root and the current LP solution */
166 static
168  SCIP* scip, /**< SCIP data structure */
169  SCIP_Real* raydirection, /**< shooting ray */
170  SCIP_VAR** subspacevars, /**< pointer to fractional space variables */
171  int nsubspacevars /**< dimension of fractional space */
172  )
173 {
174  int v;
175 
176  assert(scip != NULL);
177  assert(raydirection != NULL);
178  assert(subspacevars != NULL);
179 
180  for( v = nsubspacevars - 1; v >= 0; --v )
181  raydirection[v] = SCIPvarGetLPSol(subspacevars[v]) - SCIPvarGetRootSol(subspacevars[v]);
182 
183  return SCIP_OKAY;
184 }
185 
186 
187 /** generates the direction of the shooting ray as the average of the extreme rays of the basic cone */
188 static
190  SCIP* scip, /**< SCIP data structure */
191  SCIP_Real* raydirection, /**< shooting ray */
192  SCIP_VAR** subspacevars, /**< pointer to fractional space variables */
193  int nsubspacevars, /**< dimension of fractional space */
194  SCIP_Bool weighted /**< should the rays be weighted? */
195  )
196 {
197  SCIP_ROW** rows;
198  SCIP_Real** tableaurows;
199  SCIP_Real* rownorm;
200  SCIP_Real rowweight;
201  int** tableaurowinds; /* indices of non-zero entries */
202  int* ntableaurowinds; /* number of non-zero entries */
203  SCIP_Bool* usedrowids = NULL; /* visited row indices */
204  int* rowids; /* row indices */
205  int nrowids = 0; /* number of row indices */
206  int tableaurowind;
207  int nrows;
208  int i;
209  int j;
210  int sparse = -1; /* used to check that either all information is sparse or not sparse */
211 
212  assert(scip != NULL);
213  assert(raydirection != NULL);
214  assert(subspacevars != NULL);
215  assert(nsubspacevars > 0);
216 
217  /* get data */
218  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
219  assert(nrows > 0);
220  assert(rows != NULL);
221 
222  /* allocate memory */
223  SCIP_CALL( SCIPallocBufferArray(scip, &tableaurows, nsubspacevars) );
224  SCIP_CALL( SCIPallocBufferArray(scip, &tableaurowinds, nsubspacevars) );
225  SCIP_CALL( SCIPallocBufferArray(scip, &ntableaurowinds, nsubspacevars) );
226  for( j = nsubspacevars - 1; j >= 0; --j )
227  {
228  /*lint --e{866}*/
229  SCIP_CALL( SCIPallocBufferArray(scip, &tableaurows[j], nrows) );
230  SCIP_CALL( SCIPallocBufferArray(scip, &tableaurowinds[j], nrows) );
231  }
232 
233  SCIP_CALL( SCIPallocBufferArray(scip, &rownorm, nrows) );
234  BMSclearMemoryArray(rownorm, nrows);
235 
236  /* clear ray */
237  BMSclearMemoryArray(raydirection, nsubspacevars);
238 
239  /* get the relevant columns of the simplex tableau */
240  for( j = nsubspacevars - 1; j >= 0; --j )
241  {
242  assert(SCIPcolGetLPPos(SCIPvarGetCol(subspacevars[j])) >= 0);
243  SCIP_CALL( SCIPgetLPBInvACol(scip, SCIPcolGetLPPos(SCIPvarGetCol(subspacevars[j])), tableaurows[j], tableaurowinds[j], &ntableaurowinds[j]) );
244 
245  if( ntableaurowinds[j] == -1 )
246  {
247  assert(sparse == 0 || sparse == -1);
248  sparse = 0;
249 
250  for( i = nrows - 1; i >= 0; --i )
251  rownorm[i] += tableaurows[j][i] * tableaurows[j][i];
252  }
253  else
254  {
255  assert(sparse == 1 || sparse == -1);
256  sparse = 1;
257 
258  /* allocate temporary memory */
259  if( usedrowids == NULL )
260  {
261  SCIP_CALL( SCIPallocBufferArray(scip, &rowids, nrows) );
262  SCIP_CALL( SCIPallocBufferArray(scip, &usedrowids, nrows) );
263  BMSclearMemoryArray(usedrowids, nrows);
264  }
265 
266  for( i = ntableaurowinds[j] - 1; i >= 0; --i )
267  {
268  tableaurowind = tableaurowinds[j][i];
269  rownorm[tableaurowind] += tableaurows[j][tableaurowind] * tableaurows[j][tableaurowind];
270  if( !usedrowids[tableaurowind] )
271  {
272  usedrowids[tableaurowind] = TRUE;
273  rowids[nrowids] = tableaurowind; /*lint !e644*/
274  ++nrowids;
275  assert(nrowids <= nrows);
276  }
277  }
278  }
279  }
280 
281  /* compute ray direction (dense) */
282  if( sparse == 0 )
283  {
284  /* take average over all rows of the tableau */
285  for( i = nrows - 1; i >= 0; --i )
286  {
287  if( SCIPisFeasZero(scip, rownorm[i]) )
288  continue;
289  else
290  rownorm[i] = SQRT(rownorm[i]);
291 
292  if( weighted )
293  {
294  rowweight = SCIProwGetDualsol(rows[i]);
295  if( SCIPisFeasZero(scip, rowweight) )
296  continue;
297  }
298  else
299  rowweight = 1.0;
300 
301  for( j = nsubspacevars - 1; j >= 0; --j )
302  {
303  raydirection[j] += tableaurows[j][i] / (rownorm[i] * rowweight);
304  assert( ! SCIPisInfinity(scip, REALABS(raydirection[j])) );
305  }
306  }
307  }
308  /* compute ray direction (sparse) */
309  else
310  {
311  SCIP_Real* rowweights;
312  int r;
313  int k;
314 
315  assert(usedrowids != NULL);
316  assert(rowids != NULL);
317  assert(sparse == 1);
318  assert(0 <= nrowids && nrowids <= nrows);
319 
320  SCIP_CALL( SCIPallocBufferArray(scip, &rowweights, nrows) );
321 
322  /* compute norms of important rows and rowweights */
323  for( i = nrowids - 1; i >= 0; --i )
324  {
325  r = rowids[i];
326  assert(0 <= r && r < nrows);
327  assert(usedrowids[r]);
328 
329  if( SCIPisFeasZero(scip, rownorm[r]) )
330  {
331  usedrowids[r] = FALSE;
332  --nrowids;
333  continue;
334  }
335  else
336  rownorm[r] = SQRT(rownorm[r]);
337 
338  if( weighted )
339  {
340  rowweights[r] = SCIProwGetDualsol(rows[r]);
341  if( SCIPisFeasZero(scip, rowweights[r]) )
342  {
343  usedrowids[r] = FALSE;
344  --nrowids;
345  continue;
346  }
347  }
348  else
349  rowweights[r] = 1.0;
350  }
351 
352  if( nrowids > 0 )
353  {
354  /* take average over all rows of the tableau */
355  for( j = nsubspacevars - 1; j >= 0; --j )
356  {
357  for( k = ntableaurowinds[j] - 1; k >= 0; --k )
358  {
359  tableaurowind = tableaurowinds[j][k];
360 
361  if( usedrowids[tableaurowind] )
362  {
363  raydirection[j] += tableaurows[j][tableaurowind] / (rownorm[tableaurowind] * rowweights[tableaurowind]);
364  assert( ! SCIPisInfinity(scip, REALABS(raydirection[j])) );
365  }
366  }
367  }
368  }
369 
370  SCIPfreeBufferArray(scip, &rowweights);
371  SCIPfreeBufferArray(scip, &usedrowids);
372  SCIPfreeBufferArray(scip, &rowids);
373  }
374  assert(usedrowids == NULL);
375 
376  /* free memory */
377  SCIPfreeBufferArray(scip, &rownorm);
378  for( j = 0; j < nsubspacevars; ++j )
379  {
380  SCIPfreeBufferArray(scip, &tableaurowinds[j]);
381  SCIPfreeBufferArray(scip, &tableaurows[j]);
382  }
383  SCIPfreeBufferArray(scip, &ntableaurowinds);
384  SCIPfreeBufferArray(scip, &tableaurowinds);
385  SCIPfreeBufferArray(scip, &tableaurows);
386 
387  return SCIP_OKAY;
388 }
389 
390 
391 /** generates the direction of the shooting ray as the average of the normalized non-basic vars and rows */
392 static
394  SCIP* scip, /**< SCIP data structure */
395  SCIP_Real* raydirection, /**< shooting ray */
396  int* fracspace, /**< index set of fractional variables */
397  SCIP_VAR** subspacevars, /**< pointer to fractional space variables */
398  int nsubspacevars /**< dimension of fractional space */
399  )
400 {
401  SCIP_ROW** rows;
402  SCIP_COL** cols;
403  int nrows;
404  int ncols;
405  int i;
406 
407  assert(scip != NULL);
408  assert(raydirection != NULL);
409  assert(fracspace != NULL);
410  assert(subspacevars != NULL);
411 
412  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
413  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
414 
415  /* add up non-basic variables */
416  for( i = nsubspacevars - 1; i >= 0; --i )
417  {
418  SCIP_Real solval;
419 
420  solval = SCIPvarGetLPSol(subspacevars[i]);
421 
422  if( SCIPisFeasEQ(scip, solval, SCIPvarGetLbLocal(subspacevars[i])) )
423  raydirection[i] = +1.0;
424  else if( SCIPisFeasEQ(scip, solval, SCIPvarGetUbLocal(subspacevars[i])) )
425  raydirection[i] = -1.0;
426  else
427  raydirection[i] = 0.0;
428  }
429 
430  /* add up non-basic rows */
431  for( i = nrows - 1; i >= 0; --i )
432  {
433  SCIP_Real dualsol;
434  SCIP_Real factor;
435  SCIP_Real* coeffs;
436  SCIP_Real rownorm;
437  int j;
438  int nnonz;
439 
440  dualsol = SCIProwGetDualsol(rows[i]);
441  if( SCIPisFeasPositive(scip, dualsol) )
442  factor = 1.0;
443  else if( SCIPisFeasNegative(scip, dualsol) )
444  factor = -1.0;
445  else
446  continue;
447 
448  /* get the row's data */
449  coeffs = SCIProwGetVals(rows[i]);
450  cols = SCIProwGetCols(rows[i]);
451 
452  nnonz = SCIProwGetNNonz(rows[i]);
453 
454  rownorm = 0.0;
455  for( j = nnonz - 1; j >= 0; --j )
456  {
457  SCIP_VAR* var;
458  var = SCIPcolGetVar(cols[j]);
459  if( fracspace[SCIPvarGetProbindex(var)] >= 0 )
460  rownorm += coeffs[j] * coeffs[j];
461  }
462 
463  if( SCIPisFeasZero(scip,rownorm) )
464  continue;
465  else
466  {
467  assert(rownorm > 0);
468  rownorm = SQRT(rownorm);
469  }
470 
471  for( j = nnonz - 1; j >= 0; --j )
472  {
473  SCIP_VAR* var;
474  int f;
475 
476  var = SCIPcolGetVar(cols[j]);
477  f = fracspace[SCIPvarGetProbindex(var)];
478 
479  if( f >= 0 )
480  {
481  raydirection[f] += factor * coeffs[j] / rownorm;
482  assert( ! SCIPisInfinity(scip, REALABS(raydirection[f])) );
483  }
484  }
485  }
486  return SCIP_OKAY;
487 }
488 
489 /** generates the starting point for the shooting ray in original coordinates */
490 static
492  SCIP* scip, /**< SCIP data structure */
493  SCIP_Real* rayorigin, /**< origin of the shooting ray */
494  SCIP_VAR** subspacevars, /**< pointer to fractional space variables */
495  int nsubspacevars /**< dimension of fractional space */
496  )
497 {
498  int v;
499 
500  assert(scip != NULL);
501  assert(rayorigin != NULL);
502  assert(subspacevars != NULL);
503 
504  for( v = nsubspacevars - 1; v >= 0; --v )
505  rayorigin[v] = SCIPvarGetLPSol(subspacevars[v]);
506 
507  return SCIP_OKAY;
508 }
509 
510 /** translates the inner point of the LP to an inner point rayorigin of the unit hyper octahedron and
511  * transforms raydirection and rayorigin by reflections stored in sign
512  */
513 static
515  SCIP_Real* rayorigin, /**< origin of the shooting ray */
516  SCIP_Real* raydirection, /**< direction of the shooting ray */
517  SCIP_Bool* sign, /**< marker for flipped coordinates */
518  int nsubspacevars /**< dimension of fractional space */
519  )
520 {
521  int v;
522 
523  assert(rayorigin != NULL);
524  assert(raydirection != NULL);
525  assert(sign != NULL);
526 
527  for( v = nsubspacevars - 1; v >= 0; --v )
528  {
529  /* if raydirection[v] is negative, flip its sign */
530  if( raydirection[v] < 0 )
531  {
532  sign[v] = FALSE;
533  raydirection[v] *= -1.0;
534  rayorigin[v] *= -1.0; /* flip starting point in the same way like raydirection */
535  }
536  else
537  sign[v] = TRUE;
538  }
539 }
540 
541 /** generates all facets, from which facet i could be obtained by a decreasing + to - flip
542  * or a nonincreasing - to + flip and tests whether they are among the fmax nearest ones
543  */
544 static
546  SCIP* scip, /**< SCIP data structure */
547  SCIP_Bool** facets, /**< facets got so far */
548  SCIP_Real* lambda, /**< distances of the facets */
549  SCIP_Real* rayorigin, /**< origin of the shooting ray */
550  SCIP_Real* raydirection, /**< direction of the shooting ray */
551  SCIP_Real* negquotient, /**< array by which coordinates are sorted */
552  int nsubspacevars, /**< dimension of fractional space */
553  int f_max, /**< maximal number of facets to create */
554  int i, /**< current facet */
555  int* nfacets /**< number of facets */
556  )
557 {
558  SCIP_Real p;
559  SCIP_Real q;
560  SCIP_Real lam;
561  int minplus;
562  int j;
563 
564  assert(scip != NULL);
565  assert(facets != NULL);
566  assert(facets[i] != NULL);
567  assert(lambda != NULL);
568  assert(rayorigin != NULL);
569  assert(raydirection != NULL);
570  assert(negquotient != NULL);
571  assert(nfacets != NULL);
572  assert(0 <= i && i < f_max);
573 
574  /* determine the p and q values of the next facet to fix as a closest one */
575  p = 0.5 * nsubspacevars;
576  q = 0.0;
577  for( j = nsubspacevars - 1; j >= 0; --j )
578  {
579  if( facets[i][j] )
580  {
581  p -= rayorigin[j];
582  q += raydirection[j];
583  }
584  else
585  {
586  p += rayorigin[j];
587  q -= raydirection[j];
588  }
589  }
590 
591  /* get the first + entry of the facet */
592  minplus = -1;
593  for( j = 0; j < nsubspacevars; ++j )
594  {
595  if( facets[i][j] )
596  {
597  minplus = j;
598  break;
599  }
600  }
601 
602  /* facet (- - ... -) cannot be hit, because raydirection >= 0 */
603  assert(minplus >= 0);
604  assert(q != 0.0);
605  assert(SCIPisFeasEQ(scip, lambda[i], p/q));
606  assert(lambda[i] >= 0.0);
607 
608  /* reverse search for facets from which the actual facet can be got by a single, decreasing + to - flip */
609  /* a facet will be inserted into the queue, iff it is one of the fmax closest ones already found */
610  for( j = 0; j < nsubspacevars && !facets[i][j] && SCIPisFeasGT(scip, negquotient[j], lambda[i]); ++j )
611  {
612  if( SCIPisFeasPositive(scip, q + 2*raydirection[j]) )
613  {
614  lam = (p - 2*rayorigin[j]) / (q + 2*raydirection[j]);
615  tryToInsert(scip, facets, lambda, i, j, f_max, nsubspacevars, lam, nfacets);
616  }
617  }
618 
619  /* reverse search for facets from which the actual facet can be got by a single, nonincreasing - to + flip */
620  /* a facet will be inserted into the queue, iff it is one of the fmax closest ones already found */
621  for( j = nsubspacevars - 1; j >= 0 && facets[i][j] && SCIPisFeasLE(scip, negquotient[j], lambda[i]); --j )
622  {
623  if( SCIPisFeasPositive(scip, q - 2*raydirection[j]) )
624  {
625  lam = (p + 2*rayorigin[j]) / (q - 2*raydirection[j]);
626  if( negquotient[minplus] <= lam )
627  tryToInsert(scip, facets, lambda, i, j, f_max, nsubspacevars, lam, nfacets);
628  }
629  }
630 #ifndef NDEBUG
631  for( j = 1; j < f_max; j++)
632  assert(SCIPisFeasGE(scip, lambda[j], lambda[j-1]));
633 #endif
634 }
635 
636 /** tests, whether an array is completely zero */
637 static
639  SCIP* scip, /**< SCIP data structure */
640  SCIP_Real* raydirection, /**< array to be checked */
641  int nsubspacevars /**< size of array */
642  )
643 {
644  int v;
645  SCIP_Bool iszero;
646 
647  assert(scip != NULL);
648  assert(raydirection != NULL);
649  iszero = TRUE;
650  for( v = nsubspacevars - 1; v >= 0; --v )
651  {
652  assert(!SCIPisInfinity(scip, raydirection[v]));
653 
654  if( !SCIPisFeasZero(scip, raydirection[v]/100) )
655  iszero = FALSE;
656  else
657  raydirection[v] = 0.0;
658  }
659  return iszero;
660 }
661 
662 
663 /*
664  * Callback methods of primal heuristic
665  */
666 
667 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
668 static
669 SCIP_DECL_HEURCOPY(heurCopyOctane)
670 { /*lint --e{715}*/
671  assert(scip != NULL);
672  assert(heur != NULL);
673  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
674 
675  /* call inclusion method of primal heuristic */
677 
678  return SCIP_OKAY;
679 }
680 
681 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
682 static
683 SCIP_DECL_HEURFREE(heurFreeOctane)
684 { /*lint --e{715}*/
685  SCIP_HEURDATA* heurdata;
686 
687  assert(heur != NULL);
688  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
689  assert(scip != NULL);
690 
691  /* free heuristic data */
692  heurdata = SCIPheurGetData(heur);
693  assert(heurdata != NULL);
694  SCIPfreeBlockMemory(scip, &heurdata);
695  SCIPheurSetData(heur, NULL);
696 
697  return SCIP_OKAY;
698 }
699 
700 
701 /** initialization method of primal heuristic (called after problem was transformed) */
702 static
703 SCIP_DECL_HEURINIT(heurInitOctane)
704 { /*lint --e{715}*/
705  SCIP_HEURDATA* heurdata;
706 
707  assert(heur != NULL);
708  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
709 
710  /* get heuristic data */
711  heurdata = SCIPheurGetData(heur);
712  assert(heurdata != NULL);
713 
714  /* create working solution */
715  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
716 
717  /* initialize data */
718  heurdata->lastrule = 0;
719  heurdata->nsuccess = 0;
720 
721  return SCIP_OKAY;
722 }
723 
724 
725 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
726 
727 static
728 SCIP_DECL_HEUREXIT(heurExitOctane)
729 { /*lint --e{715}*/
730  SCIP_HEURDATA* heurdata;
731 
732  assert(heur != NULL);
733  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
734 
735  /* get heuristic data */
736  heurdata = SCIPheurGetData(heur);
737  assert(heurdata != NULL);
738 
739  /* free working solution */
740  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
741 
742  return SCIP_OKAY;
743 }
744 
745 
746 /** execution method of primal heuristic */
747 static
748 SCIP_DECL_HEUREXEC(heurExecOctane)
749 { /*lint --e{715}*/
750  SCIP_HEURDATA* heurdata;
751  SCIP_SOL* sol;
752  SCIP_SOL** first_sols; /* stores the first ffirst sols in order to check for common violation of a row */
753 
754  SCIP_VAR** vars; /* the variables of the problem */
755  SCIP_VAR** fracvars; /* variables, that are fractional in current LP solution */
756  SCIP_VAR** subspacevars; /* the variables on which the search is performed. Either coinciding with vars or with the
757  * space of all fractional variables of the current LP solution */
758 
759  SCIP_Real p; /* n/2 - <delta,x> ( for some facet delta ) */
760  SCIP_Real q; /* <delta,a> */
761 
762  SCIP_Real* rayorigin; /* origin of the ray, vector x in paper */
763  SCIP_Real* raydirection; /* direction of the ray, vector a in paper */
764  SCIP_Real* negquotient; /* negated quotient of rayorigin and raydirection, vector v in paper */
765  SCIP_Real* lambda; /* stores the distance of the facets (s.b.) to the origin of the ray */
766 
767  SCIP_Bool usefracspace; /* determines whether the search concentrates on fractional variables and fixes integer ones */
768  SCIP_Bool cons_viol; /* used for checking whether a linear constraint is violated by one of the possible solutions */
769  SCIP_Bool success;
770  SCIP_Bool* sign; /* signature of the direction of the ray */
771  SCIP_Bool** facets; /* list of extended facets */
772 
773  int nvars; /* number of variables */
774  int nbinvars; /* number of 0-1-variables */
775  int nfracvars; /* number of fractional variables in current LP solution */
776  int nsubspacevars; /* dimension of the subspace on which the search is performed */
777  int nfacets; /* number of facets hidden by the ray that where already found */
778  int i; /* counter */
779  int j; /* counter */
780  int f_max; /* {0,1}-points to be checked */
781  int f_first; /* {0,1}-points to be generated at first in order to check whether a restart is necessary */
782  int r; /* counter */
783  int firstrule;
784 
785  int* perm; /* stores the way in which the coordinates were permuted */
786  int* fracspace; /* maps the variables of the subspace to the original variables */
787 
788  assert(heur != NULL);
789  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
790  assert(scip != NULL);
791  assert(result != NULL);
792  assert(SCIPhasCurrentNodeLP(scip));
793 
794  *result = SCIP_DELAYED;
795 
796  /* do not call heuristic of node was already detected to be infeasible */
797  if( nodeinfeasible )
798  return SCIP_OKAY;
799 
800  /* only call heuristic, if an optimal LP solution is at hand */
802  return SCIP_OKAY;
803 
804  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
806  return SCIP_OKAY;
807 
808  *result = SCIP_DIDNOTRUN;
809 
810  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
811 
812  /* OCTANE is for use in 0-1 programs only */
813  if( nvars != nbinvars )
814  return SCIP_OKAY;
815 
816  /* get heuristic's data */
817  heurdata = SCIPheurGetData(heur);
818  assert( heurdata != NULL );
819 
820  /* don't call heuristic, if it was not successful enough in the past */
821  /*lint --e{647}*/
822  if( SCIPgetNNodes(scip) % (SCIPheurGetNCalls(heur) / (100 * SCIPheurGetNBestSolsFound(heur) + 10*heurdata->nsuccess + 1) + 1) != 0 )
823  return SCIP_OKAY;
824 
825  SCIP_CALL( SCIPgetLPBranchCands(scip, &fracvars, NULL, NULL, &nfracvars, NULL, NULL) );
826 
827  /* don't use integral starting points */
828  if( nfracvars == 0 )
829  return SCIP_OKAY;
830 
831  /* get working pointers from heurdata */
832  sol = heurdata->sol;
833  assert( sol != NULL );
834  f_max = heurdata->f_max;
835  f_first = heurdata->f_first;
836  usefracspace = heurdata->usefracspace;
837 
838  SCIP_CALL( SCIPallocBufferArray(scip, &fracspace, nvars) );
839 
840  /* determine the space one which OCTANE should work either as the whole space or as the space of fractional variables */
841  if( usefracspace )
842  {
843  nsubspacevars = nfracvars;
844  SCIP_CALL( SCIPallocBufferArray(scip, &subspacevars, nsubspacevars) );
845  BMScopyMemoryArray(subspacevars, fracvars, nsubspacevars);
846  for( i = nvars - 1; i >= 0; --i )
847  fracspace[i] = -1;
848  for( i = nsubspacevars - 1; i >= 0; --i )
849  fracspace[SCIPvarGetProbindex(subspacevars[i])] = i;
850  }
851  else
852  {
853  int currentindex;
854 
855  nsubspacevars = nvars;
856  SCIP_CALL( SCIPallocBufferArray(scip, &subspacevars, nsubspacevars) );
857 
858  /* only copy the variables which are in the current LP */
859  currentindex = 0;
860  for( i = 0; i < nvars; ++i )
861  {
862  if( SCIPcolGetLPPos(SCIPvarGetCol(vars[i])) >= 0 )
863  {
864  subspacevars[currentindex] = vars[i];
865  fracspace[i] = currentindex;
866  ++currentindex;
867 
868  }
869  else
870  {
871  fracspace[i] = -1;
872  --nsubspacevars;
873  }
874  }
875  }
876 
877  /* nothing to do for empty search space */
878  if( nsubspacevars == 0 )
879  return SCIP_OKAY;
880 
881  assert(0 < nsubspacevars && nsubspacevars <= nvars);
882 
883  for( i = 0; i < nsubspacevars; i++)
884  assert(fracspace[SCIPvarGetProbindex(subspacevars[i])] == i);
885 
886  /* at most 2^(n-1) facets can be hit */
887  if( nsubspacevars < 30 )
888  {
889  /*lint --e{701}*/
890  assert(f_max > 0);
891  f_max = MIN(f_max, 1 << (nsubspacevars - 1) );
892  }
893 
894  f_first = MIN(f_first, f_max);
895 
896  /* memory allocation */
897  SCIP_CALL( SCIPallocBufferArray(scip, &rayorigin, nsubspacevars) );
898  SCIP_CALL( SCIPallocBufferArray(scip, &raydirection, nsubspacevars) );
899  SCIP_CALL( SCIPallocBufferArray(scip, &negquotient, nsubspacevars) );
900  SCIP_CALL( SCIPallocBufferArray(scip, &sign, nsubspacevars) );
901  SCIP_CALL( SCIPallocBufferArray(scip, &perm, nsubspacevars) );
902  SCIP_CALL( SCIPallocBufferArray(scip, &lambda, f_max + 1) );
903  SCIP_CALL( SCIPallocBufferArray(scip, &facets, f_max + 1) );
904 
905 
906  for( i = f_max; i >= 0; --i )
907  {
908  /*lint --e{866}*/
909  SCIP_CALL( SCIPallocBufferArray(scip, &facets[i], nsubspacevars) );
910  }
911  SCIP_CALL( SCIPallocBufferArray(scip, &first_sols, f_first) );
912 
913  *result = SCIP_DIDNOTFIND;
914 
915  /* starting OCTANE */
916  SCIPdebugMsg(scip, "run Octane heuristic on %s variables, which are %d vars, generate at most %d facets, using rule number %d\n",
917  usefracspace ? "fractional" : "all", nsubspacevars, f_max, (heurdata->lastrule+1)%5);
918 
919  /* generate starting point in original coordinates */
920  SCIP_CALL( generateStartingPoint(scip, rayorigin, subspacevars, nsubspacevars) );
921  for( i = nsubspacevars - 1; i >= 0; --i )
922  rayorigin[i] -= 0.5;
923 
924  firstrule = heurdata->lastrule;
925  ++firstrule;
926  for( r = firstrule; r <= firstrule + 5 && !SCIPisStopped(scip); r++ )
927  {
928  SCIP_ROW** rows;
929  int nrows;
930 
931  /* generate shooting ray in original coordinates by certain rules */
932  switch(r % 5)
933  {
934  case 1:
935  if( !heurdata->useavgnbray )
936  continue;
937 
938  SCIP_CALL( generateAverageNBRay(scip, raydirection, fracspace, subspacevars, nsubspacevars) );
939  break;
940  case 2:
941  if( !heurdata->useobjray )
942  continue;
943 
944  SCIP_CALL( generateObjectiveRay(scip, raydirection, subspacevars, nsubspacevars) );
945  break;
946  case 3:
947  if( !heurdata->usediffray )
948  continue;
949 
950  SCIP_CALL( generateDifferenceRay(scip, raydirection, subspacevars, nsubspacevars) );
951  break;
952  case 4:
953  if( !heurdata->useavgwgtray || !SCIPisLPSolBasic(scip) )
954  continue;
955 
956  SCIP_CALL( generateAverageRay(scip, raydirection, subspacevars, nsubspacevars, TRUE) );
957  break;
958  case 0:
959  if( !heurdata->useavgray || !SCIPisLPSolBasic(scip) )
960  continue;
961 
962  SCIP_CALL( generateAverageRay(scip, raydirection, subspacevars, nsubspacevars, FALSE) );
963  break;
964  default:
965  SCIPerrorMessage("invalid ray rule identifier\n");
966  SCIPABORT();
967  }
968 
969  /* there must be a feasible direction for the shooting ray */
970  if( isZero(scip, raydirection, nsubspacevars) )
971  continue;
972 
973  /* transform coordinates such that raydirection >= 0 */
974  flipCoords(rayorigin, raydirection, sign, nsubspacevars);
975 
976  for( i = f_max - 1; i >= 0; --i)
977  lambda[i] = SCIPinfinity(scip);
978 
979  /* calculate negquotient, initialize perm, facets[0], p, and q */
980  p = 0.5 * nsubspacevars;
981  q = 0.0;
982  for( i = nsubspacevars - 1; i >= 0; --i )
983  {
984  /* calculate negquotient, the ratio of rayorigin and raydirection, paying special attention to the case raydirection[i] == 0 */
985  if( SCIPisFeasZero(scip, raydirection[i]) )
986  {
987  if( rayorigin[i] < 0 )
988  negquotient[i] = SCIPinfinity(scip);
989  else
990  negquotient[i] = -SCIPinfinity(scip);
991  }
992  else
993  negquotient[i] = - (rayorigin[i] / raydirection[i]);
994 
995  perm[i] = i;
996 
997  /* initialization of facets[0] to the all-one facet with p and q its characteristic values */
998  facets[0][i] = TRUE;
999  p -= rayorigin[i];
1000  q += raydirection[i];
1001  }
1002 
1003  assert(SCIPisPositive(scip, q));
1004 
1005  /* resort the coordinates in nonincreasing order of negquotient */
1006  SCIPsortDownRealRealRealBoolPtr(negquotient, raydirection, rayorigin, sign, (void**) subspacevars, nsubspacevars);
1007 
1008 #ifndef NDEBUG
1009  for( i = 0; i < nsubspacevars; i++ )
1010  {
1011  assert( raydirection[i] >= 0 );
1012  assert(!SCIPisInfinity(scip, REALABS(raydirection[i])));
1013  }
1014  for( i = 1; i < nsubspacevars; i++ )
1015  assert( negquotient[i - 1] >= negquotient[i] );
1016 #endif
1017  /* finished initialization */
1018 
1019  /* find the first facet of the octahedron hit by a ray shot from rayorigin into direction raydirection */
1020  for( i = 0; i < nsubspacevars && negquotient[i] * q > p; ++i )
1021  {
1022  facets[0][i] = FALSE;
1023  p += 2 * rayorigin[i];
1024  q -= 2 * raydirection[i];
1025  assert(SCIPisPositive(scip, p));
1026  assert(SCIPisPositive(scip, q));
1027  }
1028 
1029  /* avoid dividing by values close to 0.0 */
1030  if( !SCIPisFeasPositive(scip, q) )
1031  continue;
1032 
1033  /* assert necessary for flexelint */
1034  assert(q != 0.0);
1035  lambda[0] = p / q;
1036 
1037  nfacets = 1;
1038 
1039  /* find the first facets hit by the ray */
1040  for( i = 0; i < nfacets && i < f_first; ++i)
1041  generateNeighborFacets(scip, facets, lambda, rayorigin, raydirection, negquotient, nsubspacevars, f_max, i, &nfacets);
1042 
1043  /* construct the first ffirst possible solutions */
1044  for( i = 0; i < nfacets && i < f_first; ++i )
1045  {
1046  SCIP_CALL( SCIPcreateSol(scip, &first_sols[i], heur) );
1047  SCIP_CALL( getSolFromFacet(scip, facets[i], first_sols[i], sign, subspacevars, nsubspacevars) );
1048  assert( first_sols[i] != NULL );
1049  }
1050 
1051  /* try, whether there is a row violated by all of the first ffirst solutions */
1052  cons_viol = FALSE;
1053  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
1054  for( i = nrows - 1; i >= 0; --i )
1055  {
1056  if( !SCIProwIsLocal(rows[i]) )
1057  {
1058  SCIP_COL** cols;
1059  SCIP_Real constant;
1060  SCIP_Real lhs;
1061  SCIP_Real rhs;
1062  SCIP_Real rowval;
1063  SCIP_Real* coeffs;
1064  int nnonzerovars;
1065  int k;
1066 
1067  /* get the row's data */
1068  constant = SCIProwGetConstant(rows[i]);
1069  lhs = SCIProwGetLhs(rows[i]);
1070  rhs = SCIProwGetRhs(rows[i]);
1071  coeffs = SCIProwGetVals(rows[i]);
1072  nnonzerovars = SCIProwGetNNonz(rows[i]);
1073  cols = SCIProwGetCols(rows[i]);
1074  rowval = constant;
1075 
1076  for( j = nnonzerovars - 1; j >= 0; --j )
1077  rowval += coeffs[j] * SCIPgetSolVal(scip, first_sols[0], SCIPcolGetVar(cols[j]));
1078 
1079  /* if the row's lhs is violated by the first sol, test, whether it is violated by the next ones, too */
1080  if( lhs > rowval )
1081  {
1082  cons_viol = TRUE;
1083  for( k = MIN(f_first, nfacets) - 1; k > 0; --k )
1084  {
1085  rowval = constant;
1086  for( j = nnonzerovars - 1; j >= 0; --j )
1087  rowval += coeffs[j] * SCIPgetSolVal(scip, first_sols[k], SCIPcolGetVar(cols[j]));
1088  if( lhs <= rowval )
1089  {
1090  cons_viol = FALSE;
1091  break;
1092  }
1093  }
1094  }
1095  /* dito for the right hand side */
1096  else if( rhs < rowval )
1097  {
1098  cons_viol = TRUE;
1099  for( k = MIN(f_first, nfacets) - 1; k > 0; --k )
1100  {
1101  rowval = constant;
1102  for( j = nnonzerovars - 1; j >= 0; --j )
1103  rowval += coeffs[j] * SCIPgetSolVal(scip, first_sols[k], SCIPcolGetVar(cols[j]));
1104  if( rhs >= rowval )
1105  {
1106  cons_viol = FALSE;
1107  break;
1108  }
1109  }
1110  }
1111  /* break as soon as one row is violated by all of the ffirst solutions */
1112  if( cons_viol )
1113  break;
1114  }
1115  }
1116 
1117 
1118  if( !cons_viol )
1119  {
1120  /* if there was no row violated by all solutions, try whether one or more of them are feasible */
1121  for( i = MIN(f_first, nfacets) - 1; i >= 0; --i )
1122  {
1123  assert(first_sols[i] != NULL);
1124  SCIP_CALL( SCIPtrySol(scip, first_sols[i], FALSE, FALSE, TRUE, FALSE, TRUE, &success) );
1125  if( success )
1126  *result = SCIP_FOUNDSOL;
1127  }
1128  /* search for further facets and construct and try solutions out of facets fixed as closest ones */
1129  for( i = f_first; i < f_max; ++i)
1130  {
1131  if( i >= nfacets )
1132  break;
1133  generateNeighborFacets(scip, facets, lambda, rayorigin, raydirection, negquotient, nsubspacevars, f_max, i, &nfacets);
1134  SCIP_CALL( getSolFromFacet(scip, facets[i], sol, sign, subspacevars, nsubspacevars) );
1135  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, TRUE, &success) );
1136  if( success )
1137  *result = SCIP_FOUNDSOL;
1138  }
1139  }
1140 
1141  /* finished OCTANE */
1142  for( i = MIN(f_first, nfacets) - 1; i >= 0; --i )
1143  {
1144  SCIP_CALL( SCIPfreeSol(scip, &first_sols[i]) );
1145  }
1146  }
1147  heurdata->lastrule = r;
1148 
1149  if( *result == SCIP_FOUNDSOL )
1150  ++(heurdata->nsuccess);
1151 
1152  /* free temporary memory */
1153  SCIPfreeBufferArray(scip, &first_sols);
1154  for( i = 0; i <= f_max; ++i )
1155  SCIPfreeBufferArray(scip, &facets[i]);
1156  SCIPfreeBufferArray(scip, &facets);
1157  SCIPfreeBufferArray(scip, &lambda);
1158  SCIPfreeBufferArray(scip, &perm);
1159  SCIPfreeBufferArray(scip, &sign);
1160  SCIPfreeBufferArray(scip, &negquotient);
1161  SCIPfreeBufferArray(scip, &raydirection);
1162  SCIPfreeBufferArray(scip, &rayorigin);
1163  SCIPfreeBufferArray(scip, &subspacevars);
1164  SCIPfreeBufferArray(scip, &fracspace);
1165 
1166  return SCIP_OKAY;
1167 }
1168 
1169 
1170 /*
1171  * primal heuristic specific interface methods
1172  */
1173 
1174 /** creates the octane primal heuristic and includes it in SCIP */
1176  SCIP* scip /**< SCIP data structure */
1177  )
1178 {
1179  SCIP_HEURDATA* heurdata;
1180  SCIP_HEUR* heur;
1181 
1182  /* create Octane primal heuristic data */
1183  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1184 
1185  /* include primal heuristic */
1186  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1188  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecOctane, heurdata) );
1189 
1190  assert(heur != NULL);
1191 
1192  /* set non-NULL pointers to callback methods */
1193  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyOctane) );
1194  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeOctane) );
1195  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitOctane) );
1196  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitOctane) );
1197 
1198  /* add octane primal heuristic parameters */
1199  SCIP_CALL( SCIPaddIntParam(scip,
1200  "heuristics/octane/fmax",
1201  "number of 0-1-points to be tested as possible solutions by OCTANE",
1202  &heurdata->f_max, TRUE, DEFAULT_FMAX, 1, INT_MAX, NULL, NULL) );
1203 
1204  SCIP_CALL( SCIPaddIntParam(scip,
1205  "heuristics/octane/ffirst",
1206  "number of 0-1-points to be tested at first whether they violate a common row",
1207  &heurdata->f_first, TRUE, DEFAULT_FFIRST, 1, INT_MAX, NULL, NULL) );
1208 
1210  "heuristics/octane/usefracspace",
1211  "execute OCTANE only in the space of fractional variables (TRUE) or in the full space?",
1212  &heurdata->usefracspace, TRUE, DEFAULT_USEFRACSPACE, NULL, NULL) );
1213 
1215  "heuristics/octane/useobjray",
1216  "should the inner normal of the objective be used as one ray direction?",
1217  &heurdata->useobjray, TRUE, TRUE, NULL, NULL) );
1218 
1220  "heuristics/octane/useavgray",
1221  "should the average of the basic cone be used as one ray direction?",
1222  &heurdata->useavgray, TRUE, TRUE, NULL, NULL) );
1223 
1225  "heuristics/octane/usediffray",
1226  "should the difference between the root solution and the current LP solution be used as one ray direction?",
1227  &heurdata->usediffray, TRUE, FALSE, NULL, NULL) );
1228 
1230  "heuristics/octane/useavgwgtray",
1231  "should the weighted average of the basic cone be used as one ray direction?",
1232  &heurdata->useavgwgtray, TRUE, TRUE, NULL, NULL) );
1233 
1235  "heuristics/octane/useavgnbray",
1236  "should the weighted average of the nonbasic cone be used as one ray direction?",
1237  &heurdata->useavgnbray, TRUE, TRUE, NULL, NULL) );
1238 
1239  return SCIP_OKAY;
1240 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36995
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47357
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38570
#define DEFAULT_USEFRACSPACE
Definition: heur_octane.c:40
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47292
void SCIPsortDownRealRealRealBoolPtr(SCIP_Real *realarray1, SCIP_Real *realarray2, SCIP_Real *realarray3, SCIP_Bool *boolarray, void **ptrarray, int len)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:43447
#define DEFAULT_FMAX
Definition: heur_octane.c:38
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1344
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8177
static SCIP_RETCODE generateStartingPoint(SCIP *scip, SCIP_Real *rayorigin, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:491
static SCIP_RETCODE generateDifferenceRay(SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:167
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16402
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:47082
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47009
static SCIP_Bool isZero(SCIP *scip, SCIP_Real *raydirection, int nsubspacevars)
Definition: heur_octane.c:638
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47381
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:12758
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47344
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11680
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16481
#define FALSE
Definition: def.h:64
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16969
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
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.c:8084
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1119
static void flipCoords(SCIP_Real *rayorigin, SCIP_Real *raydirection, SCIP_Bool *sign, int nsubspacevars)
Definition: heur_octane.c:514
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip.c:29556
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:16501
#define SCIPdebugMsg
Definition: scip.h:455
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.c:4265
#define HEUR_PRIORITY
Definition: heur_octane.c:31
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29731
#define HEUR_DISPCHAR
Definition: heur_octane.c:30
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1198
static SCIP_DECL_HEURCOPY(heurCopyOctane)
Definition: heur_octane.c:669
#define DEFAULT_FFIRST
Definition: heur_octane.c:39
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8145
static SCIP_RETCODE generateAverageRay(SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars, SCIP_Bool weighted)
Definition: heur_octane.c:189
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:16590
static SCIP_DECL_HEUREXIT(heurExitOctane)
Definition: heur_octane.c:728
#define HEUR_USESSUBSCIP
Definition: heur_octane.c:36
SCIPInterval sign(const SCIPInterval &x)
SCIP_RETCODE SCIPincludeHeurOctane(SCIP *scip)
Definition: heur_octane.c:1175
#define HEUR_MAXDEPTH
Definition: heur_octane.c:34
#define REALABS(x)
Definition: def.h:173
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17650
static SCIP_DECL_HEUREXEC(heurExecOctane)
Definition: heur_octane.c:748
#define SCIP_CALL(x)
Definition: def.h:350
static SCIP_DECL_HEURINIT(heurInitOctane)
Definition: heur_octane.c:703
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47331
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47318
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16491
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1324
static SCIP_RETCODE generateObjectiveRay(SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:147
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16427
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:29202
SCIP_RETCODE SCIPgetLPBInvACol(SCIP *scip, int c, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip.c:29883
#define HEUR_NAME
Definition: heur_octane.c:28
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:38765
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16437
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
static void generateNeighborFacets(SCIP *scip, SCIP_Bool **facets, SCIP_Real *lambda, SCIP_Real *rayorigin, SCIP_Real *raydirection, SCIP_Real *negquotient, int nsubspacevars, int f_max, int i, int *nfacets)
Definition: heur_octane.c:545
static SCIP_RETCODE getSolFromFacet(SCIP *scip, SCIP_Bool *facet, SCIP_SOL *sol, SCIP_Bool *sign, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:110
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:38529
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17124
#define HEUR_FREQ
Definition: heur_octane.c:32
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:116
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16990
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
SCIP_RETCODE SCIPtrySol(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.c:40694
#define HEUR_DESC
Definition: heur_octane.c:29
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:16447
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29366
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16251
static SCIP_DECL_HEURFREE(heurFreeOctane)
Definition: heur_octane.c:683
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8161
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:47369
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
#define HEUR_TIMING
Definition: heur_octane.c:35
static SCIP_RETCODE generateAverageNBRay(SCIP *scip, SCIP_Real *raydirection, int *fracspace, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:393
octane primal heuristic based on Balas, Ceria, Dawande, Margot, and Pataki
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8129
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29634
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1109
static void tryToInsert(SCIP *scip, SCIP_Bool **facets, SCIP_Real *lambda, int i, int j, int f_max, int nsubspacevars, SCIP_Real lam, int *nfacets)
Definition: heur_octane.c:65
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:42127
#define SCIPABORT()
Definition: def.h:322
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:16292
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38905
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4239
#define HEUR_FREQOFS
Definition: heur_octane.c:33
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37872