1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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
tryToInsert(SCIP * scip,SCIP_Bool ** facets,SCIP_Real * lambda,int i,int j,int f_max,int nsubspacevars,SCIP_Real lam,int * nfacets)81 void tryToInsert(
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
getSolFromFacet(SCIP * scip,SCIP_Bool * facet,SCIP_SOL * sol,SCIP_Bool * sign,SCIP_VAR ** subspacevars,int nsubspacevars)126 SCIP_RETCODE getSolFromFacet(
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
generateObjectiveRay(SCIP * scip,SCIP_Real * raydirection,SCIP_VAR ** subspacevars,int nsubspacevars)163 SCIP_RETCODE generateObjectiveRay(
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
generateDifferenceRay(SCIP * scip,SCIP_Real * raydirection,SCIP_VAR ** subspacevars,int nsubspacevars)183 SCIP_RETCODE generateDifferenceRay(
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
generateAverageRay(SCIP * scip,SCIP_Real * raydirection,SCIP_VAR ** subspacevars,int nsubspacevars,SCIP_Bool weighted)205 SCIP_RETCODE generateAverageRay(
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
generateAverageNBRay(SCIP * scip,SCIP_Real * raydirection,int * fracspace,SCIP_VAR ** subspacevars,int nsubspacevars)410 SCIP_RETCODE generateAverageNBRay(
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
generateStartingPoint(SCIP * scip,SCIP_Real * rayorigin,SCIP_VAR ** subspacevars,int nsubspacevars)508 void generateStartingPoint(
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
flipCoords(SCIP_Real * rayorigin,SCIP_Real * raydirection,SCIP_Bool * sign,int nsubspacevars)529 void flipCoords(
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
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)560 void generateNeighborFacets(
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
isZero(SCIP * scip,SCIP_Real * raydirection,int nsubspacevars)653 SCIP_Bool isZero(
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
SCIP_DECL_HEURCOPY(heurCopyOctane)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 */
691 SCIP_CALL( SCIPincludeHeurOctane(scip) );
692
693 return SCIP_OKAY;
694 }
695
696 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
697 static
SCIP_DECL_HEURFREE(heurFreeOctane)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
SCIP_DECL_HEURINIT(heurInitOctane)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
SCIP_DECL_HEUREXIT(heurExitOctane)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
SCIP_DECL_HEUREXEC(heurExecOctane)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 */
816 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
817 return SCIP_OKAY;
818
819 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
820 if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
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 */
SCIPincludeHeurOctane(SCIP * scip)1187 SCIP_RETCODE SCIPincludeHeurOctane(
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,
1199 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
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
1221 SCIP_CALL( SCIPaddBoolParam(scip,
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
1226 SCIP_CALL( SCIPaddBoolParam(scip,
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
1231 SCIP_CALL( SCIPaddBoolParam(scip,
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
1236 SCIP_CALL( SCIPaddBoolParam(scip,
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
1241 SCIP_CALL( SCIPaddBoolParam(scip,
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
1246 SCIP_CALL( SCIPaddBoolParam(scip,
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 }
1253