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-2020 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  return SCIP_OKAY;
894 
895  assert(0 < nsubspacevars && nsubspacevars <= nvars);
896 
897  for( i = 0; i < nsubspacevars; i++)
898  assert(fracspace[SCIPvarGetProbindex(subspacevars[i])] == i);
899 
900  /* at most 2^(n-1) facets can be hit */
901  if( nsubspacevars < 30 )
902  {
903  /*lint --e{701}*/
904  assert(f_max > 0);
905  f_max = MIN(f_max, 1 << (nsubspacevars - 1) );
906  }
907 
908  f_first = MIN(f_first, f_max);
909 
910  /* memory allocation */
911  SCIP_CALL( SCIPallocBufferArray(scip, &rayorigin, nsubspacevars) );
912  SCIP_CALL( SCIPallocBufferArray(scip, &raydirection, nsubspacevars) );
913  SCIP_CALL( SCIPallocBufferArray(scip, &negquotient, nsubspacevars) );
914  SCIP_CALL( SCIPallocBufferArray(scip, &sign, nsubspacevars) );
915  SCIP_CALL( SCIPallocBufferArray(scip, &perm, nsubspacevars) );
916  SCIP_CALL( SCIPallocBufferArray(scip, &lambda, f_max + 1) );
917  SCIP_CALL( SCIPallocBufferArray(scip, &facets, f_max + 1) );
918 
919  for( i = f_max; i >= 0; --i )
920  {
921  /*lint --e{866}*/
922  SCIP_CALL( SCIPallocBufferArray(scip, &facets[i], nsubspacevars) );
923  }
924  SCIP_CALL( SCIPallocBufferArray(scip, &first_sols, f_first) );
925 
926  *result = SCIP_DIDNOTFIND;
927 
928  /* starting OCTANE */
929  SCIPdebugMsg(scip, "run Octane heuristic on %s variables, which are %d vars, generate at most %d facets, using rule number %d\n",
930  usefracspace ? "fractional" : "all", nsubspacevars, f_max, (heurdata->lastrule+1)%5);
931 
932  /* generate starting point in original coordinates */
933  generateStartingPoint(scip, rayorigin, subspacevars, nsubspacevars);
934  for( i = nsubspacevars - 1; i >= 0; --i )
935  rayorigin[i] -= 0.5;
936 
937  firstrule = heurdata->lastrule;
938  ++firstrule;
939  for( r = firstrule; r <= firstrule + 5 && !SCIPisStopped(scip); r++ )
940  {
941  SCIP_ROW** rows;
942  int nrows;
943 
944  /* generate shooting ray in original coordinates by certain rules */
945  switch(r % 5)
946  {
947  case 1:
948  if( !heurdata->useavgnbray )
949  continue;
950 
951  SCIP_CALL( generateAverageNBRay(scip, raydirection, fracspace, subspacevars, nsubspacevars) );
952  break;
953  case 2:
954  if( !heurdata->useobjray )
955  continue;
956 
957  SCIP_CALL( generateObjectiveRay(scip, raydirection, subspacevars, nsubspacevars) );
958  break;
959  case 3:
960  if( !heurdata->usediffray )
961  continue;
962 
963  SCIP_CALL( generateDifferenceRay(scip, raydirection, subspacevars, nsubspacevars) );
964  break;
965  case 4:
966  if( !heurdata->useavgwgtray || !SCIPisLPSolBasic(scip) )
967  continue;
968 
969  SCIP_CALL( generateAverageRay(scip, raydirection, subspacevars, nsubspacevars, TRUE) );
970  break;
971  case 0:
972  if( !heurdata->useavgray || !SCIPisLPSolBasic(scip) )
973  continue;
974 
975  SCIP_CALL( generateAverageRay(scip, raydirection, subspacevars, nsubspacevars, FALSE) );
976  break;
977  default:
978  SCIPerrorMessage("invalid ray rule identifier\n");
979  SCIPABORT();
980  }
981 
982  /* there must be a feasible direction for the shooting ray */
983  if( isZero(scip, raydirection, nsubspacevars) )
984  continue;
985 
986  /* transform coordinates such that raydirection >= 0 */
987  flipCoords(rayorigin, raydirection, sign, nsubspacevars);
988 
989  for( i = f_max - 1; i >= 0; --i)
990  lambda[i] = SCIPinfinity(scip);
991 
992  /* calculate negquotient, initialize perm, facets[0], p, and q */
993  p = 0.5 * nsubspacevars;
994  q = 0.0;
995  for( i = nsubspacevars - 1; i >= 0; --i )
996  {
997  /* calculate negquotient, the ratio of rayorigin and raydirection, paying special attention to the case raydirection[i] == 0 */
998  if( SCIPisFeasZero(scip, raydirection[i]) )
999  {
1000  if( rayorigin[i] < 0 )
1001  negquotient[i] = SCIPinfinity(scip);
1002  else
1003  negquotient[i] = -SCIPinfinity(scip);
1004  }
1005  else
1006  negquotient[i] = - (rayorigin[i] / raydirection[i]);
1007 
1008  perm[i] = i;
1009 
1010  /* initialization of facets[0] to the all-one facet with p and q its characteristic values */
1011  facets[0][i] = TRUE;
1012  p -= rayorigin[i];
1013  q += raydirection[i];
1014  }
1015 
1016  assert(SCIPisPositive(scip, q));
1017 
1018  /* resort the coordinates in nonincreasing order of negquotient */
1019  SCIPsortDownRealRealRealBoolPtr(negquotient, raydirection, rayorigin, sign, (void**) subspacevars, nsubspacevars);
1020 
1021 #ifndef NDEBUG
1022  for( i = 0; i < nsubspacevars; i++ )
1023  {
1024  assert( raydirection[i] >= 0 );
1025  assert(!SCIPisInfinity(scip, REALABS(raydirection[i])));
1026  }
1027  for( i = 1; i < nsubspacevars; i++ )
1028  assert( negquotient[i - 1] >= negquotient[i] );
1029 #endif
1030  /* finished initialization */
1031 
1032  /* find the first facet of the octahedron hit by a ray shot from rayorigin into direction raydirection */
1033  for( i = 0; i < nsubspacevars && negquotient[i] * q > p; ++i )
1034  {
1035  facets[0][i] = FALSE;
1036  p += 2 * rayorigin[i];
1037  q -= 2 * raydirection[i];
1038  assert(SCIPisPositive(scip, p));
1039  assert(SCIPisPositive(scip, q));
1040  }
1041 
1042  /* avoid dividing by values close to 0.0 */
1043  if( !SCIPisFeasPositive(scip, q) )
1044  continue;
1045 
1046  /* assert necessary for flexelint */
1047  assert(q != 0.0);
1048  lambda[0] = p / q;
1049 
1050  nfacets = 1;
1051 
1052  /* find the first facets hit by the ray */
1053  for( i = 0; i < nfacets && i < f_first; ++i)
1054  generateNeighborFacets(scip, facets, lambda, rayorigin, raydirection, negquotient, nsubspacevars, f_max, i, &nfacets);
1055 
1056  /* construct the first ffirst possible solutions */
1057  for( i = 0; i < nfacets && i < f_first; ++i )
1058  {
1059  SCIP_CALL( SCIPcreateSol(scip, &first_sols[i], heur) );
1060  SCIP_CALL( getSolFromFacet(scip, facets[i], first_sols[i], sign, subspacevars, nsubspacevars) );
1061  assert( first_sols[i] != NULL );
1062  }
1063 
1064  /* try, whether there is a row violated by all of the first ffirst solutions */
1065  cons_viol = FALSE;
1066  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
1067  for( i = nrows - 1; i >= 0; --i )
1068  {
1069  if( !SCIProwIsLocal(rows[i]) )
1070  {
1071  SCIP_COL** cols;
1072  SCIP_Real constant;
1073  SCIP_Real lhs;
1074  SCIP_Real rhs;
1075  SCIP_Real rowval;
1076  SCIP_Real* coeffs;
1077  int nnonzerovars;
1078  int k;
1079 
1080  /* get the row's data */
1081  constant = SCIProwGetConstant(rows[i]);
1082  lhs = SCIProwGetLhs(rows[i]);
1083  rhs = SCIProwGetRhs(rows[i]);
1084  coeffs = SCIProwGetVals(rows[i]);
1085  nnonzerovars = SCIProwGetNNonz(rows[i]);
1086  cols = SCIProwGetCols(rows[i]);
1087  rowval = constant;
1088 
1089  for( j = nnonzerovars - 1; j >= 0; --j )
1090  rowval += coeffs[j] * SCIPgetSolVal(scip, first_sols[0], SCIPcolGetVar(cols[j]));
1091 
1092  /* if the row's lhs is violated by the first sol, test, whether it is violated by the next ones, too */
1093  if( lhs > rowval )
1094  {
1095  cons_viol = TRUE;
1096  for( k = MIN(f_first, nfacets) - 1; k > 0; --k )
1097  {
1098  rowval = constant;
1099  for( j = nnonzerovars - 1; j >= 0; --j )
1100  rowval += coeffs[j] * SCIPgetSolVal(scip, first_sols[k], SCIPcolGetVar(cols[j]));
1101  if( lhs <= rowval )
1102  {
1103  cons_viol = FALSE;
1104  break;
1105  }
1106  }
1107  }
1108  /* dito for the right hand side */
1109  else if( rhs < rowval )
1110  {
1111  cons_viol = TRUE;
1112  for( k = MIN(f_first, nfacets) - 1; k > 0; --k )
1113  {
1114  rowval = constant;
1115  for( j = nnonzerovars - 1; j >= 0; --j )
1116  rowval += coeffs[j] * SCIPgetSolVal(scip, first_sols[k], SCIPcolGetVar(cols[j]));
1117  if( rhs >= rowval )
1118  {
1119  cons_viol = FALSE;
1120  break;
1121  }
1122  }
1123  }
1124  /* break as soon as one row is violated by all of the ffirst solutions */
1125  if( cons_viol )
1126  break;
1127  }
1128  }
1129 
1130  if( !cons_viol )
1131  {
1132  /* if there was no row violated by all solutions, try whether one or more of them are feasible */
1133  for( i = MIN(f_first, nfacets) - 1; i >= 0; --i )
1134  {
1135  assert(first_sols[i] != NULL);
1136  SCIP_CALL( SCIPtrySol(scip, first_sols[i], FALSE, FALSE, TRUE, FALSE, TRUE, &success) );
1137  if( success )
1138  *result = SCIP_FOUNDSOL;
1139  }
1140  /* search for further facets and construct and try solutions out of facets fixed as closest ones */
1141  for( i = f_first; i < f_max; ++i)
1142  {
1143  if( i >= nfacets )
1144  break;
1145  generateNeighborFacets(scip, facets, lambda, rayorigin, raydirection, negquotient, nsubspacevars, f_max, i, &nfacets);
1146  SCIP_CALL( getSolFromFacet(scip, facets[i], sol, sign, subspacevars, nsubspacevars) );
1147  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, TRUE, &success) );
1148  if( success )
1149  *result = SCIP_FOUNDSOL;
1150  }
1151  }
1152 
1153  /* finished OCTANE */
1154  for( i = MIN(f_first, nfacets) - 1; i >= 0; --i )
1155  {
1156  SCIP_CALL( SCIPfreeSol(scip, &first_sols[i]) );
1157  }
1158  }
1159  heurdata->lastrule = r;
1160 
1161  if( *result == SCIP_FOUNDSOL )
1162  ++(heurdata->nsuccess);
1163 
1164  /* free temporary memory */
1165  SCIPfreeBufferArray(scip, &first_sols);
1166  for( i = 0; i <= f_max; ++i )
1167  SCIPfreeBufferArray(scip, &facets[i]);
1168  SCIPfreeBufferArray(scip, &facets);
1169  SCIPfreeBufferArray(scip, &lambda);
1170  SCIPfreeBufferArray(scip, &perm);
1171  SCIPfreeBufferArray(scip, &sign);
1172  SCIPfreeBufferArray(scip, &negquotient);
1173  SCIPfreeBufferArray(scip, &raydirection);
1174  SCIPfreeBufferArray(scip, &rayorigin);
1175  SCIPfreeBufferArray(scip, &subspacevars);
1176  SCIPfreeBufferArray(scip, &fracspace);
1177 
1178  return SCIP_OKAY;
1179 }
1180 
1181 
1182 /*
1183  * primal heuristic specific interface methods
1184  */
1185 
1186 /** creates the octane primal heuristic and includes it in SCIP */
1188  SCIP* scip /**< SCIP data structure */
1189  )
1190 {
1191  SCIP_HEURDATA* heurdata;
1192  SCIP_HEUR* heur;
1193 
1194  /* create Octane primal heuristic data */
1195  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1196 
1197  /* include primal heuristic */
1198  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1200  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecOctane, heurdata) );
1201 
1202  assert(heur != NULL);
1203 
1204  /* set non-NULL pointers to callback methods */
1205  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyOctane) );
1206  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeOctane) );
1207  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitOctane) );
1208  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitOctane) );
1209 
1210  /* add octane primal heuristic parameters */
1211  SCIP_CALL( SCIPaddIntParam(scip,
1212  "heuristics/octane/fmax",
1213  "number of 0-1-points to be tested as possible solutions by OCTANE",
1214  &heurdata->f_max, TRUE, DEFAULT_FMAX, 1, INT_MAX, NULL, NULL) );
1215 
1216  SCIP_CALL( SCIPaddIntParam(scip,
1217  "heuristics/octane/ffirst",
1218  "number of 0-1-points to be tested at first whether they violate a common row",
1219  &heurdata->f_first, TRUE, DEFAULT_FFIRST, 1, INT_MAX, NULL, NULL) );
1220 
1222  "heuristics/octane/usefracspace",
1223  "execute OCTANE only in the space of fractional variables (TRUE) or in the full space?",
1224  &heurdata->usefracspace, TRUE, DEFAULT_USEFRACSPACE, NULL, NULL) );
1225 
1227  "heuristics/octane/useobjray",
1228  "should the inner normal of the objective be used as one ray direction?",
1229  &heurdata->useobjray, TRUE, TRUE, NULL, NULL) );
1230 
1232  "heuristics/octane/useavgray",
1233  "should the average of the basic cone be used as one ray direction?",
1234  &heurdata->useavgray, TRUE, TRUE, NULL, NULL) );
1235 
1237  "heuristics/octane/usediffray",
1238  "should the difference between the root solution and the current LP solution be used as one ray direction?",
1239  &heurdata->usediffray, TRUE, FALSE, NULL, NULL) );
1240 
1242  "heuristics/octane/useavgwgtray",
1243  "should the weighted average of the basic cone be used as one ray direction?",
1244  &heurdata->useavgwgtray, TRUE, TRUE, NULL, NULL) );
1245 
1247  "heuristics/octane/useavgnbray",
1248  "should the weighted average of the nonbasic cone be used as one ray direction?",
1249  &heurdata->useavgnbray, TRUE, TRUE, NULL, NULL) );
1250 
1251  return SCIP_OKAY;
1252 }
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip_lp.c:462
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1555
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:977
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17263
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:687
#define DEFAULT_USEFRACSPACE
Definition: heur_octane.c:56
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:17174
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
public methods for SCIP parameter handling
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for memory management
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
#define DEFAULT_FMAX
Definition: heur_octane.c:54
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:17075
SCIP_EXPORT SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18041
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
static SCIP_Bool isZero(SCIP *scip, SCIP_Real *raydirection, int nsubspacevars)
Definition: heur_octane.c:653
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17120
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17515
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1018
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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
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 SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
static void flipCoords(SCIP_Real *rayorigin, SCIP_Real *raydirection, SCIP_Bool *sign, int nsubspacevars)
Definition: heur_octane.c:529
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
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:3126
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1575
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
public methods for querying solving statistics
SCIP_EXPORT SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:13119
#define HEUR_PRIORITY
Definition: heur_octane.c:47
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
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define HEUR_DISPCHAR
Definition: heur_octane.c:46
static SCIP_DECL_HEURCOPY(heurCopyOctane)
Definition: heur_octane.c:684
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17100
#define DEFAULT_FFIRST
Definition: heur_octane.c:55
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:540
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE generateAverageRay(SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars, SCIP_Bool weighted)
Definition: heur_octane.c:205
static SCIP_DECL_HEUREXIT(heurExitOctane)
Definition: heur_octane.c:743
#define HEUR_USESSUBSCIP
Definition: heur_octane.c:52
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17110
SCIPInterval sign(const SCIPInterval &x)
#define HEUR_MAXDEPTH
Definition: heur_octane.c:50
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
#define NULL
Definition: lpi_spx1.cpp:155
#define REALABS(x)
Definition: def.h:187
static SCIP_DECL_HEUREXEC(heurExecOctane)
Definition: heur_octane.c:763
#define SCIP_CALL(x)
Definition: def.h:364
static SCIP_DECL_HEURINIT(heurInitOctane)
Definition: heur_octane.c:718
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:637
static SCIP_RETCODE generateObjectiveRay(SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:163
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
public methods for primal heuristic plugins and divesets
#define HEUR_NAME
Definition: heur_octane.c:44
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_EXPORT SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17381
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Real SCIPinfinity(SCIP *scip)
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
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
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17154
public methods for LP management
#define HEUR_FREQ
Definition: heur_octane.c:48
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:126
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16904
SCIP_RETCODE SCIPincludeHeurOctane(SCIP *scip)
Definition: heur_octane.c:1187
public methods for the LP relaxation, rows and columns
SCIP_Real * r
Definition: circlepacking.c:50
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
methods for sorting joint arrays of various types
#define HEUR_DESC
Definition: heur_octane.c:45
public methods for branching rule plugins and branching
general public methods
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for solutions
SCIP_RETCODE SCIPgetLPBInvACol(SCIP *scip, int c, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip_lp.c:789
static SCIP_DECL_HEURFREE(heurFreeOctane)
Definition: heur_octane.c:698
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
public methods for message output
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1860
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
#define SCIP_Real
Definition: def.h:163
public methods for message handling
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
#define HEUR_TIMING
Definition: heur_octane.c:51
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
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_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17360
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17164
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:122
public methods for primal heuristics
SCIP_EXPORT void SCIPsortDownRealRealRealBoolPtr(SCIP_Real *realarray1, SCIP_Real *realarray2, SCIP_Real *realarray3, SCIP_Bool *boolarray, void **ptrarray, int len)
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
#define SCIPABORT()
Definition: def.h:336
public methods for global and local (sub)problems
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:16955
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
#define HEUR_FREQOFS
Definition: heur_octane.c:49
memory allocation routines