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