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-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_octane.c
17  * @brief octane primal heuristic based on Balas, Ceria, Dawande, Margot, and Pataki
18  * @author Timo Berthold
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "blockmemshell/memory.h"
24 #include "scip/heur_octane.h"
25 #include "scip/pub_heur.h"
26 #include "scip/pub_lp.h"
27 #include "scip/pub_message.h"
28 #include "scip/pub_misc_sort.h"
29 #include "scip/pub_var.h"
30 #include "scip/scip_branch.h"
31 #include "scip/scip_general.h"
32 #include "scip/scip_heur.h"
33 #include "scip/scip_lp.h"
34 #include "scip/scip_mem.h"
35 #include "scip/scip_message.h"
36 #include "scip/scip_numerics.h"
37 #include "scip/scip_param.h"
38 #include "scip/scip_prob.h"
39 #include "scip/scip_sol.h"
40 #include "scip/scip_solvingstats.h"
41 #include <string.h>
42 
43 #define HEUR_NAME "octane"
44 #define HEUR_DESC "octane primal heuristic for pure {0;1}-problems based on Balas et al."
45 #define HEUR_DISPCHAR 'O'
46 #define HEUR_PRIORITY -1008000
47 #define HEUR_FREQ -1
48 #define HEUR_FREQOFS 0
49 #define HEUR_MAXDEPTH -1
50 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
51 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
52 
53 #define DEFAULT_FMAX 100 /**< {0,1}-points to be checked */
54 #define DEFAULT_FFIRST 10 /**< {0,1}-points to be generated at first */
55 #define DEFAULT_USEFRACSPACE TRUE /**< use heuristic for the space of fractional variables or for whole space? */
56 
57 /** primal heuristic data */
58 struct SCIP_HeurData
59 {
60  SCIP_SOL* sol; /**< working solution */
61  int f_max; /**< {0,1}-points to be checked */
62  int f_first; /**< {0,1}-points to be generated at first in order to check whether restart is necessary */
63  int lastrule; /**< last ray selection rule that was performed */
64  SCIP_Bool usefracspace; /**< use heuristic for the space of fractional variables or for the whole space? */
65  SCIP_Bool useobjray; /**< should the inner normal of the objective be used as one ray direction? */
66  SCIP_Bool useavgray; /**< should the average ray of the basic cone be used as one ray direction? */
67  SCIP_Bool usediffray; /**< should difference between root sol and current LP sol be used as one ray direction? */
68  SCIP_Bool useavgwgtray; /**< should the weighted average ray of the basic cone be used as one ray direction? */
69  SCIP_Bool useavgnbray; /**< should the average ray of the nonbasic cone be used as one ray direction? */
70  int nsuccess; /**< number of runs that produced at least one feasible solution */
71 };
72 
73 /*
74  * Local methods
75  */
76 
77 
78 /** tries to insert the facet obtained from facet i flipped in component j into the list of the fmax nearest facets */
79 static
81  SCIP* scip, /**< SCIP data structure */
82  SCIP_Bool** facets, /**< facets got so far */
83  SCIP_Real* lambda, /**< distances of the facets */
84  int i, /**< current facet */
85  int j, /**< component to flip */
86  int f_max, /**< maximal number of facets to create */
87  int nsubspacevars, /**< dimension of the fractional space */
88  SCIP_Real lam, /**< distance of the current facet */
89  int* nfacets /**< number of facets */
90  )
91 {
92  SCIP_Bool* lastfacet;
93  int k;
94 
95  assert(scip != NULL);
96  assert(facets != NULL);
97  assert(lambda != NULL);
98  assert(nfacets != NULL);
99 
100  if( SCIPisFeasLE(scip, lam, 0.0) || SCIPisFeasGE(scip, lam, lambda[f_max-1]) )
101  return;
102 
103  lastfacet = facets[f_max];
104 
105  /* shifting lam through lambda, lambda keeps increasingly sorted */
106  for( k = f_max; k > 0 && SCIPisFeasGT(scip, lambda[k-1], lam); --k )
107  {
108  lambda[k] = lambda[k-1];
109  facets[k] = facets[k-1];
110  }
111  assert(i < k && k < f_max );
112 
113  /* inserting new facet into list, new facet is facet at position i flipped in coordinate j, new distance lam */
114  facets[k] = lastfacet;
115  lambda[k] = lam;
116 
117  /*lint --e{866}*/
118  BMScopyMemoryArray(facets[k], facets[i], nsubspacevars);
119  facets[k][j] = !facets[k][j];
120  (*nfacets)++;
121 }
122 
123 /** constructs a solution from a given facet paying attention to the transformations made at the beginning of OCTANE */
124 static
126  SCIP* scip, /**< SCIP data structure */
127  SCIP_Bool* facet, /**< current facet */
128  SCIP_SOL* sol, /**< solution to create */
129  SCIP_Bool* sign, /**< marker for retransformation */
130  SCIP_VAR** subspacevars, /**< pointer to fractional space variables */
131  int nsubspacevars /**< dimension of fractional space */
132  )
133 {
134  int v;
135 
136  assert(scip != NULL);
137  assert(facet != NULL);
138  assert(sol != NULL);
139  assert(sign != NULL);
140  assert(subspacevars != NULL);
141 
142  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
143  for( v = nsubspacevars - 1; v >= 0; --v )
144  {
145  /* after permutation, a variable should be set to 1, iff there was no reflection in this coordinate and the hit
146  * facet has coordinate + or there was a reflection and the facet has coordinate - */
147  if( facet[v] == sign[v] )
148  {
149  SCIP_CALL( SCIPsetSolVal(scip, sol, subspacevars[v], 1.0) );
150  }
151  else
152  {
153  SCIP_CALL( SCIPsetSolVal(scip, sol, subspacevars[v], 0.0) );
154  }
155  }
156 
157  return SCIP_OKAY;
158 }
159 
160 /** generates the direction of the shooting ray as the inner normal of the objective function */
161 static
163  SCIP* scip, /**< SCIP data structure */
164  SCIP_Real* raydirection, /**< shooting ray */
165  SCIP_VAR** subspacevars, /**< pointer to fractional space variables */
166  int nsubspacevars /**< dimension of fractional space */
167  )
168 {
169  int v;
170 
171  assert(scip != NULL);
172  assert(raydirection != NULL);
173  assert(subspacevars != NULL);
174 
175  for( v = nsubspacevars - 1; v >= 0; --v )
176  raydirection[v] = SCIPvarGetObj(subspacevars[v]);
177  return SCIP_OKAY;
178 }
179 
180 /** generates the direction of the shooting ray as the difference between the root and the current LP solution */
181 static
183  SCIP* scip, /**< SCIP data structure */
184  SCIP_Real* raydirection, /**< shooting ray */
185  SCIP_VAR** subspacevars, /**< pointer to fractional space variables */
186  int nsubspacevars /**< dimension of fractional space */
187  )
188 {
189  int v;
190 
191  assert(scip != NULL);
192  assert(raydirection != NULL);
193  assert(subspacevars != NULL);
194 
195  for( v = nsubspacevars - 1; v >= 0; --v )
196  raydirection[v] = SCIPvarGetLPSol(subspacevars[v]) - SCIPvarGetRootSol(subspacevars[v]);
197 
198  return SCIP_OKAY;
199 }
200 
201 
202 /** generates the direction of the shooting ray as the average of the extreme rays of the basic cone */
203 static
205  SCIP* scip, /**< SCIP data structure */
206  SCIP_Real* raydirection, /**< shooting ray */
207  SCIP_VAR** subspacevars, /**< pointer to fractional space variables */
208  int nsubspacevars, /**< dimension of fractional space */
209  SCIP_Bool weighted /**< should the rays be weighted? */
210  )
211 {
212  SCIP_ROW** rows;
213  SCIP_Real** tableaurows;
214  SCIP_Real* rownorm;
215  SCIP_Real rowweight;
216  int** tableaurowinds; /* indices of non-zero entries */
217  int* ntableaurowinds; /* number of non-zero entries */
218  SCIP_Bool* usedrowids = NULL; /* visited row indices */
219  int* rowids; /* row indices */
220  int nrowids = 0; /* number of row indices */
221  int tableaurowind;
222  int nrows;
223  int i;
224  int j;
225  int sparse = -1; /* used to check that either all information is sparse or not sparse */
226 
227  assert(scip != NULL);
228  assert(raydirection != NULL);
229  assert(subspacevars != NULL);
230  assert(nsubspacevars > 0);
231 
232  /* get data */
233  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
234  assert(nrows > 0);
235  assert(rows != NULL);
236 
237  /* allocate memory */
238  SCIP_CALL( SCIPallocBufferArray(scip, &tableaurows, nsubspacevars) );
239  SCIP_CALL( SCIPallocBufferArray(scip, &tableaurowinds, nsubspacevars) );
240  SCIP_CALL( SCIPallocBufferArray(scip, &ntableaurowinds, nsubspacevars) );
241  for( j = nsubspacevars - 1; j >= 0; --j )
242  {
243  /*lint --e{866}*/
244  SCIP_CALL( SCIPallocBufferArray(scip, &tableaurows[j], nrows) );
245  SCIP_CALL( SCIPallocBufferArray(scip, &tableaurowinds[j], nrows) );
246  }
247 
248  SCIP_CALL( SCIPallocBufferArray(scip, &rownorm, nrows) );
249  BMSclearMemoryArray(rownorm, nrows);
250 
251  /* clear ray */
252  BMSclearMemoryArray(raydirection, nsubspacevars);
253 
254  /* get the relevant columns of the simplex tableau */
255  for( j = nsubspacevars - 1; j >= 0; --j )
256  {
257  assert(SCIPcolGetLPPos(SCIPvarGetCol(subspacevars[j])) >= 0);
258  SCIP_CALL( SCIPgetLPBInvACol(scip, SCIPcolGetLPPos(SCIPvarGetCol(subspacevars[j])), tableaurows[j], tableaurowinds[j], &ntableaurowinds[j]) );
259 
260  if( ntableaurowinds[j] == -1 )
261  {
262  assert(sparse == 0 || sparse == -1);
263  sparse = 0;
264 
265  for( i = nrows - 1; i >= 0; --i )
266  rownorm[i] += tableaurows[j][i] * tableaurows[j][i];
267  }
268  else
269  {
270  assert(sparse == 1 || sparse == -1);
271  sparse = 1;
272 
273  /* allocate temporary memory */
274  if( usedrowids == NULL )
275  {
276  SCIP_CALL( SCIPallocBufferArray(scip, &rowids, nrows) );
277  SCIP_CALL( SCIPallocBufferArray(scip, &usedrowids, nrows) );
278  BMSclearMemoryArray(usedrowids, nrows);
279  }
280 
281  for( i = ntableaurowinds[j] - 1; i >= 0; --i )
282  {
283  tableaurowind = tableaurowinds[j][i];
284  rownorm[tableaurowind] += tableaurows[j][tableaurowind] * tableaurows[j][tableaurowind];
285  if( !usedrowids[tableaurowind] )
286  {
287  usedrowids[tableaurowind] = TRUE;
288  rowids[nrowids] = tableaurowind; /*lint !e644*/
289  ++nrowids;
290  assert(nrowids <= nrows);
291  }
292  }
293  }
294  }
295 
296  /* compute ray direction (dense) */
297  if( sparse == 0 )
298  {
299  /* take average over all rows of the tableau */
300  for( i = nrows - 1; i >= 0; --i )
301  {
302  if( SCIPisFeasZero(scip, rownorm[i]) )
303  continue;
304  else
305  rownorm[i] = SQRT(rownorm[i]);
306 
307  if( weighted )
308  {
309  rowweight = SCIProwGetDualsol(rows[i]);
310  if( SCIPisFeasZero(scip, rowweight) )
311  continue;
312  }
313  else
314  rowweight = 1.0;
315 
316  for( j = nsubspacevars - 1; j >= 0; --j )
317  {
318  raydirection[j] += tableaurows[j][i] / (rownorm[i] * rowweight);
319  assert( ! SCIPisInfinity(scip, REALABS(raydirection[j])) );
320  }
321  }
322  }
323  /* compute ray direction (sparse) */
324  else
325  {
326  SCIP_Real* rowweights;
327  int r;
328  int k;
329 
330  assert(usedrowids != NULL);
331  assert(rowids != NULL);
332  assert(sparse == 1);
333  assert(0 <= nrowids && nrowids <= nrows);
334 
335  SCIP_CALL( SCIPallocBufferArray(scip, &rowweights, nrows) );
336 
337  /* compute norms of important rows and rowweights */
338  for( i = nrowids - 1; i >= 0; --i )
339  {
340  r = rowids[i];
341  assert(0 <= r && r < nrows);
342  assert(usedrowids[r]);
343 
344  if( SCIPisFeasZero(scip, rownorm[r]) )
345  {
346  usedrowids[r] = FALSE;
347  --nrowids;
348  continue;
349  }
350  else
351  rownorm[r] = SQRT(rownorm[r]);
352 
353  if( weighted )
354  {
355  rowweights[r] = SCIProwGetDualsol(rows[r]);
356  if( SCIPisFeasZero(scip, rowweights[r]) )
357  {
358  usedrowids[r] = FALSE;
359  --nrowids;
360  continue;
361  }
362  }
363  else
364  rowweights[r] = 1.0;
365  }
366 
367  if( nrowids > 0 )
368  {
369  /* take average over all rows of the tableau */
370  for( j = nsubspacevars - 1; j >= 0; --j )
371  {
372  for( k = ntableaurowinds[j] - 1; k >= 0; --k )
373  {
374  tableaurowind = tableaurowinds[j][k];
375 
376  if( usedrowids[tableaurowind] )
377  {
378  raydirection[j] += tableaurows[j][tableaurowind] / (rownorm[tableaurowind] * rowweights[tableaurowind]);
379  assert( ! SCIPisInfinity(scip, REALABS(raydirection[j])) );
380  }
381  }
382  }
383  }
384 
385  SCIPfreeBufferArray(scip, &rowweights);
386  SCIPfreeBufferArray(scip, &usedrowids);
387  SCIPfreeBufferArray(scip, &rowids);
388  }
389  assert(usedrowids == NULL);
390 
391  /* free memory */
392  SCIPfreeBufferArray(scip, &rownorm);
393  for( j = 0; j < nsubspacevars; ++j )
394  {
395  SCIPfreeBufferArray(scip, &tableaurowinds[j]);
396  SCIPfreeBufferArray(scip, &tableaurows[j]);
397  }
398  SCIPfreeBufferArray(scip, &ntableaurowinds);
399  SCIPfreeBufferArray(scip, &tableaurowinds);
400  SCIPfreeBufferArray(scip, &tableaurows);
401 
402  return SCIP_OKAY;
403 }
404 
405 
406 /** generates the direction of the shooting ray as the average of the normalized non-basic vars and rows */
407 static
409  SCIP* scip, /**< SCIP data structure */
410  SCIP_Real* raydirection, /**< shooting ray */
411  int* fracspace, /**< index set of fractional variables */
412  SCIP_VAR** subspacevars, /**< pointer to fractional space variables */
413  int nsubspacevars /**< dimension of fractional space */
414  )
415 {
416  SCIP_ROW** rows;
417  SCIP_COL** cols;
418  int nrows;
419  int ncols;
420  int i;
421 
422  assert(scip != NULL);
423  assert(raydirection != NULL);
424  assert(fracspace != NULL);
425  assert(subspacevars != NULL);
426 
427  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
428  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
429 
430  /* add up non-basic variables */
431  for( i = nsubspacevars - 1; i >= 0; --i )
432  {
433  SCIP_Real solval;
434 
435  solval = SCIPvarGetLPSol(subspacevars[i]);
436 
437  if( SCIPisFeasEQ(scip, solval, SCIPvarGetLbLocal(subspacevars[i])) )
438  raydirection[i] = +1.0;
439  else if( SCIPisFeasEQ(scip, solval, SCIPvarGetUbLocal(subspacevars[i])) )
440  raydirection[i] = -1.0;
441  else
442  raydirection[i] = 0.0;
443  }
444 
445  /* add up non-basic rows */
446  for( i = nrows - 1; i >= 0; --i )
447  {
448  SCIP_Real dualsol;
449  SCIP_Real factor;
450  SCIP_Real* coeffs;
451  SCIP_Real rownorm;
452  int j;
453  int nnonz;
454 
455  dualsol = SCIProwGetDualsol(rows[i]);
456  if( SCIPisFeasPositive(scip, dualsol) )
457  factor = 1.0;
458  else if( SCIPisFeasNegative(scip, dualsol) )
459  factor = -1.0;
460  else
461  continue;
462 
463  /* get the row's data */
464  coeffs = SCIProwGetVals(rows[i]);
465  cols = SCIProwGetCols(rows[i]);
466 
467  nnonz = SCIProwGetNNonz(rows[i]);
468 
469  rownorm = 0.0;
470  for( j = nnonz - 1; j >= 0; --j )
471  {
472  SCIP_VAR* var;
473  var = SCIPcolGetVar(cols[j]);
474  if( fracspace[SCIPvarGetProbindex(var)] >= 0 )
475  rownorm += coeffs[j] * coeffs[j];
476  }
477 
478  if( SCIPisFeasZero(scip,rownorm) )
479  continue;
480  else
481  {
482  assert(rownorm > 0);
483  rownorm = SQRT(rownorm);
484  }
485 
486  for( j = nnonz - 1; j >= 0; --j )
487  {
488  SCIP_VAR* var;
489  int f;
490 
491  var = SCIPcolGetVar(cols[j]);
492  f = fracspace[SCIPvarGetProbindex(var)];
493 
494  if( f >= 0 )
495  {
496  raydirection[f] += factor * coeffs[j] / rownorm;
497  assert( ! SCIPisInfinity(scip, REALABS(raydirection[f])) );
498  }
499  }
500  }
501  return SCIP_OKAY;
502 }
503 
504 /** generates the starting point for the shooting ray in original coordinates */
505 static
507  SCIP* scip, /**< SCIP data structure */
508  SCIP_Real* rayorigin, /**< origin of the shooting ray */
509  SCIP_VAR** subspacevars, /**< pointer to fractional space variables */
510  int nsubspacevars /**< dimension of fractional space */
511  )
512 {
513  int v;
514 
515  assert(scip != NULL);
516  assert(rayorigin != NULL);
517  assert(subspacevars != NULL);
518 
519  for( v = nsubspacevars - 1; v >= 0; --v )
520  rayorigin[v] = SCIPvarGetLPSol(subspacevars[v]);
521 
522  return SCIP_OKAY;
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  SCIP_CALL( 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:427
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1380
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17075
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
#define NULL
Definition: def.h:253
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:686
#define DEFAULT_USEFRACSPACE
Definition: heur_octane.c:55
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:16986
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
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:1165
#define DEFAULT_FMAX
Definition: heur_octane.c:53
static SCIP_RETCODE generateStartingPoint(SCIP *scip, SCIP_Real *rayorigin, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:506
static SCIP_RETCODE generateDifferenceRay(SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:182
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16887
SCIP_EXPORT SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17726
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
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:16932
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17200
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1017
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
public methods for problem variables
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:47
#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:184
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:3124
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:158
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1400
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:73
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:319
public methods for querying solving statistics
SCIP_EXPORT SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:12842
#define HEUR_PRIORITY
Definition: heur_octane.c:46
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:107
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define HEUR_DISPCHAR
Definition: heur_octane.c:45
static SCIP_DECL_HEURCOPY(heurCopyOctane)
Definition: heur_octane.c:684
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16912
#define DEFAULT_FFIRST
Definition: heur_octane.c:54
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:505
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:204
static SCIP_DECL_HEUREXIT(heurExitOctane)
Definition: heur_octane.c:743
#define HEUR_USESSUBSCIP
Definition: heur_octane.c:51
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16922
SCIPInterval sign(const SCIPInterval &x)
#define HEUR_MAXDEPTH
Definition: heur_octane.c:49
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
#define REALABS(x)
Definition: def.h:188
static SCIP_DECL_HEUREXEC(heurExecOctane)
Definition: heur_octane.c:763
#define SCIP_CALL(x)
Definition: def.h:365
static SCIP_DECL_HEURINIT(heurInitOctane)
Definition: heur_octane.c:718
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:602
static SCIP_RETCODE generateObjectiveRay(SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:162
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:237
public methods for primal heuristic plugins and divesets
#define HEUR_NAME
Definition: heur_octane.c:43
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_EXPORT SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17066
#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:200
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:125
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16966
#define MIN(x, y)
Definition: def.h:223
public methods for LP management
#define HEUR_FREQ
Definition: heur_octane.c:47
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:124
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17408
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16736
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:17418
methods for sorting joint arrays of various types
#define HEUR_DESC
Definition: heur_octane.c:44
#define SQRT(x)
Definition: def.h:206
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:754
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:152
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:1861
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:73
#define SCIP_Real
Definition: def.h:164
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:384
#define HEUR_TIMING
Definition: heur_octane.c:50
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:168
static SCIP_RETCODE generateAverageNBRay(SCIP *scip, SCIP_Real *raydirection, int *fracspace, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:408
octane primal heuristic based on Balas, Ceria, Dawande, Margot, and Pataki
SCIP_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17045
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16976
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:120
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:80
#define SCIPABORT()
Definition: def.h:337
public methods for global and local (sub)problems
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:16777
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
#define HEUR_FREQOFS
Definition: heur_octane.c:48
memory allocation routines