Scippy

SCIP

Solving Constraint Integer Programs

heur_twoopt.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-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file heur_twoopt.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief primal heuristic to improve incumbent solution by flipping pairs of variables
28 * @author Timo Berthold
29 * @author Gregor Hendel
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
35#include "scip/heur_twoopt.h"
36#include "scip/pub_heur.h"
37#include "scip/pub_lp.h"
38#include "scip/pub_message.h"
39#include "scip/pub_misc.h"
40#include "scip/pub_misc_sort.h"
41#include "scip/pub_sol.h"
42#include "scip/pub_var.h"
43#include "scip/scip_heur.h"
44#include "scip/scip_lp.h"
45#include "scip/scip_mem.h"
46#include "scip/scip_message.h"
47#include "scip/scip_numerics.h"
48#include "scip/scip_param.h"
49#include "scip/scip_prob.h"
51#include "scip/scip_sol.h"
53#include <string.h>
54
55#define HEUR_NAME "twoopt"
56#define HEUR_DESC "primal heuristic to improve incumbent solution by flipping pairs of variables"
57#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ITERATIVE
58#define HEUR_PRIORITY -20100
59#define HEUR_FREQ -1
60#define HEUR_FREQOFS 0
61#define HEUR_MAXDEPTH -1
62
63#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
64#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
65
66/* default parameter values */
67#define DEFAULT_INTOPT FALSE /**< optional integer optimization is applied by default */
68#define DEFAULT_WAITINGNODES 0 /**< default number of nodes to wait after current best solution before calling heuristic */
69#define DEFAULT_MATCHINGRATE 0.5 /**< default percentage by which two variables have to match in their LP-row set to be
70 * associated as pair by heuristic */
71#define DEFAULT_MAXNSLAVES 199 /**< default number of slave candidates for a master variable */
72#define DEFAULT_ARRAYSIZE 10 /**< the default array size for temporary arrays */
73#define DEFAULT_RANDSEED 37 /**< initial random seed */
74
75/*
76 * Data structures
77 */
78
79/** primal heuristic data */
80struct SCIP_HeurData
81{
82 int lastsolindex; /**< index of last solution for which heuristic was performed */
83 SCIP_Real matchingrate; /**< percentage by which two variables have have to match in their LP-row
84 * set to be associated as pair by heuristic */
85 SCIP_VAR** binvars; /**< Array of binary variables which are sorted with respect to their occurrence
86 * in the LP-rows */
87 int nbinvars; /**< number of binary variables stored in heuristic array */
88 int waitingnodes; /**< user parameter to determine number of nodes to wait after last best solution
89 * before calling heuristic */
90 SCIP_Bool presolved; /**< flag to indicate whether presolving has already been executed */
91 int* binblockstart; /**< array to store the start indices of each binary block */
92 int* binblockend; /**< array to store the end indices of each binary block */
93 int nbinblocks; /**< number of blocks */
94
95 /* integer variable twoopt data */
96 SCIP_Bool intopt; /**< parameter to determine if integer 2-opt should be applied */
97 SCIP_VAR** intvars; /**< array to store the integer variables in non-decreasing order
98 * with respect to their objective coefficient */
99 int nintvars; /**< the number of integer variables stored in array intvars */
100 int* intblockstart; /**< array to store the start indices of each binary block */
101 int* intblockend; /**< array to store the end indices of each binary block */
102 int nintblocks; /**< number of blocks */
103
104 SCIP_Bool execute; /**< has presolveTwoOpt detected necessary structure for execution of heuristic? */
105 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
106 int maxnslaves; /**< delimits the maximum number of slave candidates for a master variable */
107
108#ifdef SCIP_STATISTIC
109 /* statistics */
110 int ntotalbinvars; /**< total number of binary variables over all runs */
111 int ntotalintvars; /**< total number of Integer variables over all runs */
112 int nruns; /**< counts the number of runs, i.e. the number of initialized
113 * branch and bound processes */
114 int maxbinblocksize; /**< maximum size of a binary block */
115 int maxintblocksize; /**< maximum size of an integer block */
116 int binnblockvars; /**< number of binary variables that appear in blocks */
117 int binnblocks; /**< number of blocks with at least two variables */
118 int intnblockvars; /**< number of Integer variables that appear in blocks */
119 int intnblocks; /**< number of blocks with at least two variables */
120 int binnexchanges; /**< number of executed changes of binary solution values leading to
121 * improvement in objective function */
122 int intnexchanges; /**< number of executed changes of Integer solution values leading to improvement in
123 * objective function */
124#endif
125};
126
127/** indicator for optimizing for binaries or integer variables */
129{
133typedef enum Opttype OPTTYPE;
134
135/** indicator for direction of shifting variables */
137{
142typedef enum Direction DIRECTION;
143
144/*
145 * Local methods
146 */
147
148/** Tries to switch the values of two binary or integer variables and checks feasibility with respect to the LP.
149 *
150 * @todo Adapt method not to copy entire activities array, but only the relevant region.
151 */
152static
154 SCIP* scip, /**< scip instance */
155 SCIP_VAR* master, /**< first variable of variable pair */
156 SCIP_VAR* slave, /**< second variable of pair */
157 SCIP_Real mastersolval, /**< current value of variable1 in solution */
158 DIRECTION masterdir, /**< the direction into which the master variable has to be shifted */
159 SCIP_Real slavesolval, /**< current value of variable2 in solution */
160 DIRECTION slavedir, /**< the direction into which the slave variable has to be shifted */
161 SCIP_Real shiftval, /**< the value that variables should be shifted by */
162 SCIP_Real* activities, /**< the LP-row activities */
163 int nrows, /**< size of activities array */
164 SCIP_Bool* feasible /**< set to true if method has successfully switched the variable values */
165 )
166{ /*lint --e{715}*/
167 SCIP_COL* col;
168 SCIP_ROW** masterrows;
169 SCIP_ROW** slaverows;
170 SCIP_Real* mastercolvals;
171 SCIP_Real* slavecolvals;
172 int ncolmasterrows;
173 int ncolslaverows;
174
175 assert(scip != NULL);
176 assert(master != NULL);
177 assert(slave != NULL);
178 assert(activities != NULL);
179 assert(SCIPisFeasGT(scip, shiftval, 0.0));
180
181 assert(SCIPisFeasGE(scip, mastersolval + (int)masterdir * shiftval, SCIPvarGetLbGlobal(master)));
182 assert(SCIPisFeasLE(scip, mastersolval + (int)masterdir * shiftval, SCIPvarGetUbGlobal(master)));
183
184 assert(SCIPisFeasGE(scip, slavesolval + (int)slavedir * shiftval, SCIPvarGetLbGlobal(slave)));
185 assert(SCIPisFeasLE(scip, slavesolval + (int)slavedir * shiftval, SCIPvarGetUbGlobal(slave)));
186
187 /* get variable specific rows and coefficients for both master and slave. */
188 col = SCIPvarGetCol(master);
189 masterrows = SCIPcolGetRows(col);
190 mastercolvals = SCIPcolGetVals(col);
191 ncolmasterrows = SCIPcolGetNNonz(col);
192 assert(ncolmasterrows == 0 || masterrows != NULL);
193
194 col = SCIPvarGetCol(slave);
195 slaverows = SCIPcolGetRows(col);
196 slavecolvals = SCIPcolGetVals(col);
197 ncolslaverows = SCIPcolGetNNonz(col);
198 assert(ncolslaverows == 0 || slaverows != NULL);
199
200 /* update the activities of the LP rows of the master variable */
201 for( int i = 0; i < ncolmasterrows && SCIProwGetLPPos(masterrows[i]) >= 0; ++i )
202 {
203 int rowpos;
204
205 rowpos = SCIProwGetLPPos(masterrows[i]);
206 assert(rowpos < nrows);
207
208 /* skip local rows */
209 if( rowpos >= 0 && ! SCIProwIsLocal(masterrows[i]) )
210 activities[rowpos] += mastercolvals[i] * (int)masterdir * shiftval;
211 }
212
213 /* update the activities of the LP rows of the slave variable */
214 for( int j = 0; j < ncolslaverows && SCIProwGetLPPos(slaverows[j]) >= 0; ++j )
215 {
216 int rowpos;
217
218 rowpos = SCIProwGetLPPos(slaverows[j]);
219 assert(rowpos < nrows);
220
221 /* skip local rows */
222 if( rowpos >= 0 && ! SCIProwIsLocal(slaverows[j]) )
223 {
224 activities[rowpos] += slavecolvals[j] * (int)slavedir * shiftval;
225 assert(SCIPisFeasGE(scip, activities[rowpos], SCIProwGetLhs(slaverows[j])));
226 assert(SCIPisFeasLE(scip, activities[rowpos], SCIProwGetRhs(slaverows[j])));
227 }
228 }
229
230 /* in debug mode, the master rows are checked for feasibility which should be granted by the
231 * decision for a shift value */
232#ifndef NDEBUG
233 for( int i = 0; i < ncolmasterrows && SCIProwGetLPPos(masterrows[i]) >= 0; ++i )
234 {
235 /* local rows can be skipped */
236 if( SCIProwIsLocal(masterrows[i]) )
237 continue;
238
239 assert(SCIPisFeasGE(scip, activities[SCIProwGetLPPos(masterrows[i])], SCIProwGetLhs(masterrows[i])));
240 assert(SCIPisFeasLE(scip, activities[SCIProwGetLPPos(masterrows[i])], SCIProwGetRhs(masterrows[i])));
241 }
242#endif
243
244 *feasible = TRUE;
245
246 return SCIP_OKAY;
247}
248
249/** Compare two variables with respect to their columns.
250 *
251 * Columns are treated as {0,1} vector, where every nonzero entry is treated as '1', and compared to each other
252 * lexicographically. I.e. var1 is < var2 if the corresponding column of var2 has the smaller single nonzero index of
253 * the two columns. This comparison costs O(constraints) in the worst case
254 */
255static
257 SCIP_VAR* var1, /**< left argument of comparison */
258 SCIP_VAR* var2 /**< right argument of comparison */
259 )
260{
261 SCIP_COL* col1;
262 SCIP_COL* col2;
263 SCIP_ROW** rows1;
264 SCIP_ROW** rows2;
265 int nnonzeros1;
266 int nnonzeros2;
267
268 assert(var1 != NULL);
269 assert(var2 != NULL);
270
271 /* get the necessary row and column data */
272 col1 = SCIPvarGetCol(var1);
273 col2 = SCIPvarGetCol(var2);
274 rows1 = SCIPcolGetRows(col1);
275 rows2 = SCIPcolGetRows(col2);
276 nnonzeros1 = SCIPcolGetNNonz(col1);
277 nnonzeros2 = SCIPcolGetNNonz(col2);
278
279 assert(nnonzeros1 == 0 || rows1 != NULL);
280 assert(nnonzeros2 == 0 || rows2 != NULL);
281
282 /* loop over the rows, stopped as soon as they differ in one index,
283 * or if counter reaches the end of a variables row set */
284 for( int i = 0; i < nnonzeros1 && i < nnonzeros2; ++i )
285 {
286 if( SCIProwGetIndex(rows1[i]) != SCIProwGetIndex(rows2[i]) )
287 return SCIProwGetIndex(rows1[i]) - SCIProwGetIndex(rows2[i]);
288 }
289
290 /* loop is finished, without differing in one of common row indices, due to loop invariant
291 * variable i reached either nnonzeros1 or nnonzeros2 or both.
292 * one can easily check that the difference of these two numbers always has the desired sign for comparison. */
293 return nnonzeros2 - nnonzeros1 ;
294}
295
296/** implements a comparator to compare two variables with respect to their column entries */
297static
299{
300 return varColCompare((SCIP_VAR*) elem1, (SCIP_VAR*) elem2);
301}
302
303/** checks if two given variables are contained in common LP rows,
304 * returns true if variables share the necessary percentage (matchingrate) of rows.
305 */
306static
308 SCIP* scip, /**< current SCIP instance */
309 SCIP_VAR* var1, /**< first variable */
310 SCIP_VAR* var2, /**< second variable */
311 SCIP_Real matchingrate /**< determines the ratio of shared LP rows compared to the total number of
312 * LP-rows each variable appears in */
313 )
314{
315 SCIP_COL* col1;
316 SCIP_COL* col2;
317 SCIP_ROW** rows1;
318 SCIP_ROW** rows2;
319 int nnonzeros1;
320 int nnonzeros2;
321 int i;
322 int j;
323 int nrows1not2; /* the number of LP-rows of variable 1 which variable 2 doesn't appear in */
324 int nrows2not1; /* vice versa */
325 int nrowmaximum;
326 int nrowabs;
327
328 assert(var1 != NULL);
329 assert(var2 != NULL);
330
331 /* get the necessary row and column data */
332 col1 = SCIPvarGetCol(var1);
333 col2 = SCIPvarGetCol(var2);
334 rows1 = SCIPcolGetRows(col1);
335 rows2 = SCIPcolGetRows(col2);
336 nnonzeros1 = SCIPcolGetNNonz(col1);
337 nnonzeros2 = SCIPcolGetNNonz(col2);
338
339 assert(nnonzeros1 == 0 || rows1 != NULL);
340 assert(nnonzeros2 == 0 || rows2 != NULL);
341
342 if( nnonzeros1 == 0 && nnonzeros2 == 0 )
343 return TRUE;
344
345 /* if matching rate is 0.0, we don't need to check anything */
346 if( matchingrate == 0.0 )
347 return TRUE;
348
349 /* initialize the counters for the number of rows not shared. */
350 nrowmaximum = MAX(nnonzeros1, nnonzeros2);
351
352 nrowabs = ABS(nnonzeros1 - nnonzeros2);
353 nrows1not2 = nrowmaximum - nnonzeros2;
354 nrows2not1 = nrowmaximum - nnonzeros1;
355
356 /* if the numbers of nonzero rows differs too much, w.r.t.matching ratio, the more expensive check over the rows
357 * doesn't have to be applied anymore because the counters for not shared rows can only increase.
358 */
359 assert(nrowmaximum > 0);
360
361 if( (nrowmaximum - nrowabs) / (SCIP_Real) nrowmaximum < matchingrate )
362 return FALSE;
363
364 i = 0;
365 j = 0;
366
367 /* loop over all rows and determine number of non-shared rows */
368 while( i < nnonzeros1 && j < nnonzeros2 )
369 {
370 /* variables share a common row */
371 if( SCIProwGetIndex(rows1[i]) == SCIProwGetIndex(rows2[j]) )
372 {
373 ++i;
374 ++j;
375 }
376 /* variable 1 appears in rows1[i], variable 2 doesn't */
377 else if( SCIProwGetIndex(rows1[i]) < SCIProwGetIndex(rows2[j]) )
378 {
379 ++i;
380 ++nrows1not2;
381 }
382 /* variable 2 appears in rows2[j], variable 1 doesn't */
383 else
384 {
385 ++j;
386 ++nrows2not1;
387 }
388 }
389
390 /* now apply the ratio based comparison, that is if the ratio of shared rows is greater or equal the matching rate
391 * for each variable */
392 /* nnonzeros1 = 0 or nnonzeros2 = 0 iff matching rate is 0, but in this case, we return TRUE at the beginning */
393 /* coverity[divide_by_zero] */
394 return ( SCIPisFeasLE(scip, matchingrate, (nnonzeros1 - nrows1not2) / (SCIP_Real)(nnonzeros1)) ||
395 SCIPisFeasLE(scip, matchingrate, (nnonzeros2 - nrows2not1) / (SCIP_Real)(nnonzeros2)) ); /*lint !e795 */
396}
397
398/** Determines a bound by which the absolute solution value of two integer variables can be shifted at most.
399 *
400 * The criterion is the maintenance of feasibility of any global LP row.
401 * The first implementation only considers shifting proportion 1:1, i.e. if master value is shifted by a certain
402 * integer value k downwards, the value of slave is simultaneously shifted by k upwards.
403 */
404static
406 SCIP* scip, /**< current scip instance */
407 SCIP_SOL* sol, /**< current incumbent */
408 SCIP_VAR* master, /**< current master variable */
409 DIRECTION masterdirection, /**< the shifting direction of the master variable */
410 SCIP_VAR* slave, /**< slave variable with same LP_row set as master variable */
411 DIRECTION slavedirection, /**< the shifting direction of the slave variable */
412 SCIP_Real* activities, /**< array of LP row activities */
413 int nrows /**< the number of rows in LP and the size of the activities array */
414 )
415{ /*lint --e{715}*/
416 SCIP_Real masterbound;
417 SCIP_Real slavebound;
419 SCIP_Real mastersolval;
420 SCIP_Real slavesolval;
421
422 SCIP_COL* col;
423 SCIP_ROW** slaverows;
424 SCIP_ROW** masterrows;
425 SCIP_Real* mastercolvals;
426 SCIP_Real* slavecolvals;
427 int nslaverows;
428 int nmasterrows;
429 int i;
430 int j;
431
432 assert(scip != NULL);
433 assert(sol != NULL);
434 assert(master != NULL);
435 assert(slave != NULL);
436 assert(SCIPvarIsIntegral(master) && SCIPvarIsIntegral(slave));
437 assert(masterdirection == DIRECTION_UP || masterdirection == DIRECTION_DOWN);
438 assert(slavedirection == DIRECTION_UP || slavedirection == DIRECTION_DOWN);
439
440 mastersolval = SCIPgetSolVal(scip, sol, master);
441 slavesolval = SCIPgetSolVal(scip, sol, slave);
442
443 /* determine the trivial variable bounds for shift */
444 if( masterdirection == DIRECTION_UP )
445 {
446 bound = SCIPvarGetUbGlobal(master);
447 masterbound = bound - mastersolval;
448 masterbound = SCIPisFeasLE(scip, mastersolval + ceil(masterbound), bound) ? ceil(masterbound) : floor(masterbound);
449 }
450 else
451 {
452 bound = SCIPvarGetLbGlobal(master);
453 masterbound = mastersolval - bound;
454 masterbound = SCIPisFeasGE(scip, mastersolval - ceil(masterbound), bound) ? ceil(masterbound) : floor(masterbound);
455 }
456
457 if( slavedirection == DIRECTION_UP )
458 {
459 bound = SCIPvarGetUbGlobal(slave);
460 slavebound = bound - slavesolval;
461 slavebound = SCIPisFeasLE(scip, slavesolval + ceil(slavebound), bound) ? ceil(slavebound) : floor(slavebound);
462 }
463 else
464 {
465 bound = SCIPvarGetLbGlobal(slave);
466 slavebound = slavesolval - bound;
467 slavebound = SCIPisFeasGE(scip, slavesolval - ceil(slavebound), bound) ? ceil(slavebound) : floor(slavebound);
468 }
469
470 bound = MIN(masterbound, slavebound);
471
472 /* due to numerical reasons, bound can be negative -> Return value zero */
473 if( bound <= 0.0 )
474 return 0.0;
475
476 /* get the necessary row and and column data for each variable */
477 col = SCIPvarGetCol(slave);
478 slaverows = SCIPcolGetRows(col);
479 slavecolvals = SCIPcolGetVals(col);
480 nslaverows = SCIPcolGetNNonz(col);
481
482 col = SCIPvarGetCol(master);
483 mastercolvals = SCIPcolGetVals(col);
484 masterrows = SCIPcolGetRows(col);
485 nmasterrows = SCIPcolGetNNonz(col);
486
487 assert(nslaverows == 0 || slavecolvals != NULL);
488 assert(nmasterrows == 0 || mastercolvals != NULL);
489
490 SCIPdebugMsg(scip, " Master: %s with direction %d and %d rows, Slave: %s with direction %d and %d rows \n", SCIPvarGetName(master),
491 (int)masterdirection, nmasterrows, SCIPvarGetName(slave), (int)slavedirection, nslaverows);
492
493 /* loop over all LP rows and determine the maximum integer bound by which both variables
494 * can be shifted without loss of feasibility
495 */
496 i = 0;
497 j = 0;
498 while( i < nslaverows || j < nmasterrows )
499 {
500 SCIP_ROW* row;
501 int rowpos;
502 int masterindex;
503 int slaveindex;
504 SCIP_Bool slaveincrement;
505 SCIP_Bool masterincrement;
506
507 /* check if one pointer already reached the end of the respective array */
508 if( i < nslaverows && SCIProwGetLPPos(slaverows[i]) == -1 )
509 {
510 SCIPdebugMsg(scip, " Slaverow %s is not in LP (i=%d, j=%d)\n", SCIProwGetName(slaverows[i]), i, j);
511 i = nslaverows;
512 continue;
513 }
514 if( j < nmasterrows && SCIProwGetLPPos(masterrows[j]) == -1 )
515 {
516 SCIPdebugMsg(scip, " Masterrow %s is not in LP (i=%d, j=%d) \n", SCIProwGetName(masterrows[j]), i, j);
517 j = nmasterrows;
518 continue;
519 }
520
521 slaveincrement = FALSE;
522 /* If one counter has already reached its limit, assign a huge number to the corresponding
523 * row index to simulate an always greater row position. */
524 if( i < nslaverows )
525 slaveindex = SCIProwGetIndex(slaverows[i]);
526 else
527 slaveindex = INT_MAX;
528
529 if( j < nmasterrows )
530 masterindex = SCIProwGetIndex(masterrows[j]);
531 else
532 masterindex = INT_MAX;
533
534 assert(0 <= slaveindex && 0 <= masterindex);
535
536 assert(slaveindex < INT_MAX || masterindex < INT_MAX);
537
538 /* the current row is the one with the smaller index */
539 if( slaveindex <= masterindex )
540 {
541 rowpos = SCIProwGetLPPos(slaverows[i]);
542 row = slaverows[i];
543 slaveincrement = TRUE;
544 masterincrement = (slaveindex == masterindex);
545 }
546 else
547 {
548 assert(j < nmasterrows);
549
550 rowpos = SCIProwGetLPPos(masterrows[j]);
551 row = masterrows[j];
552 masterincrement = TRUE;
553 }
554 assert(row != NULL);
555
556 /* only global rows need to be valid */
557 if( rowpos >= 0 && !SCIProwIsLocal(row) )
558 {
559 SCIP_Real effect;
560 SCIP_Real side;
561 SCIP_Bool left;
562
563 /* effect is the effect on the row activity by shifting the variables by 1 in the respective directions */
564 effect = 0.0;
565 if( slaveindex <= masterindex )
566 effect += (slavecolvals[i] * (int)slavedirection);
567 if( masterindex <= slaveindex )
568 effect += (mastercolvals[j] * (int)masterdirection);
569 left = effect < 0.0;
570 side = left ? SCIProwGetLhs(row) : SCIProwGetRhs(row);
571
572 /* only non-zero effects and finite bounds need to be considered */
573 if( !SCIPisZero(scip, effect) && !SCIPisInfinity(scip, left ? -side : side) )
574 {
575 SCIP_Real newval;
576
577 /* effect does not equal zero, the bound is determined as maximum positive integer such that
578 * feasibility of this constraint is maintained
579 */
580 assert( rowpos < nrows );
581 assert( SCIPisFeasGE(scip, activities[rowpos], SCIProwGetLhs(row)) && SCIPisFeasLE(scip, activities[rowpos], SCIProwGetRhs(row)) );
582 assert( effect );
583
584 SCIPdebugMsg(scip, " %g <= %g <= %g, bound = %g, effect = %g (%g * %d + %g * %d) (i=%d,j=%d)\n",
585 SCIProwGetLhs(row), activities[rowpos], SCIProwGetRhs(row), bound, effect,
586 slaveindex <= masterindex ? slavecolvals[i] : 0.0, (int)slavedirection,
587 masterindex <= slaveindex ? mastercolvals[j] : 0.0, (int)masterdirection, i, j);
588
589 newval = (side - activities[rowpos]) / effect;
590
591 /* update shifting distance */
592 if( newval < bound )
593 {
594 SCIP_Real activity;
595
596 activity = activities[rowpos] + effect * ceil(newval);
597
598 /* ensure that shifting preserves feasibility */
599 if( ( left && SCIPisFeasGE(scip, activity, side) ) || ( !left && SCIPisFeasLE(scip, activity, side) ) )
600 bound = ceil(newval);
601 else
602 bound = floor(newval);
603
604 /* due to numerical reasons, bound can be negative. A variable shift by a negative bound is not desired by
605 * the heuristic -> Return value zero */
606 if( bound <= 0.0 )
607 return 0.0;
608 }
609
610 assert( SCIPisFeasGE(scip, activities[rowpos] + effect * bound, SCIProwGetLhs(row)) && SCIPisFeasLE(scip, activities[rowpos] + effect * bound, SCIProwGetRhs(row)) );
611 assert( SCIPisFeasIntegral(scip, bound) );
612 }
613 else
614 {
615 SCIPdebugMsg(scip, " No influence of row %s, effect %g, master coeff: %g slave coeff: %g (i=%d, j=%d)\n",
616 SCIProwGetName(row), effect, mastercolvals[j], slavecolvals[i], i, j);
617 }
618 }
619 else
620 {
621 SCIPdebugMsg(scip, " Row %s is local.\n", SCIProwGetName(row));
622 }
623
624 /* increase the counters which belong to the corresponding row. Both counters are increased by
625 * 1 iff rowpos1 <= rowpos2 <= rowpos1 */
626 if( slaveincrement )
627 ++i;
628 if( masterincrement )
629 ++j;
630 }
631
632 /* we must not shift variables to infinity */
633 return SCIPisInfinity(scip, bound + MAX((int)masterdirection * mastersolval, (int)slavedirection * slavesolval)) ? 0.0 : bound;
634}
635
636
637/** Disposes variable with no heuristic relevancy, e.g., due to a fixed solution value, from its neighborhood block.
638 *
639 * The affected neighborhood block is reduced by 1.
640 */
641static
643 SCIP_VAR** vars, /**< problem variables */
644 int* blockend, /**< contains end index of block */
645 int varindex /**< variable index */
646 )
647{
648 assert(blockend != NULL);
649 assert(varindex <= *blockend);
650
651 vars[varindex] = vars[*blockend];
652 --(*blockend);
653}
654
655/** realizes the presolve independently from type of variables it's applied to */
656static
658 SCIP* scip, /**< current scip */
659 SCIP_VAR** vars, /**< problem vars */
660 SCIP_VAR*** varspointer, /**< pointer to heuristic specific variable memory */
661 int nvars, /**< the number of variables */
662 int* nblocks, /**< pointer to store the number of detected blocks */
663 int* maxblocksize, /**< maximum size of a block */
664 int* nblockvars, /**< pointer to store the number of block variables */
665 int** blockstart, /**< pointer to store the array of block start indices */
666 int** blockend, /**< pointer to store the array of block end indices */
667 SCIP_HEUR* heur, /**< the heuristic */
668 SCIP_HEURDATA* heurdata /**< the heuristic data */
669 )
670{
671 int startindex;
672
673 assert(scip != NULL);
674 assert(vars != NULL);
675 assert(nvars >= 2);
676 assert(nblocks != NULL);
677 assert(maxblocksize != NULL);
678 assert(nblockvars != NULL);
679 assert(blockstart != NULL);
680 assert(blockend != NULL);
681 assert(heur != NULL);
682 assert(heurdata != NULL);
683
684 /* allocate the heuristic specific variables */
685 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, varspointer, vars, nvars));
686
687 /* sort the variables with respect to their columns */
688 SCIPsortPtr((void**)(*varspointer), SCIPvarcolComp, nvars);
689
690 /* start determining blocks, i.e. a set of at least two variables which share most of their row set.
691 * If there is none, heuristic does not need to be executed.
692 */
693 startindex = 0;
694 *nblocks = 0;
695 *maxblocksize = 0;
696 *nblockvars = 0;
697
698 SCIP_CALL( SCIPallocBlockMemoryArray(scip, blockstart, nvars/2) );
699 SCIP_CALL( SCIPallocBlockMemoryArray(scip, blockend, nvars/2) );
700
701 /* loop over variables and compare neighbors */
702 for( int v = 1; v < nvars; ++v )
703 {
704 if( !checkConstraintMatching(scip, (*varspointer)[startindex], (*varspointer)[v], heurdata->matchingrate) )
705 {
706 /* current block has its last variable at position v-1. If v differs from startindex by at least 2,
707 * a block is detected. Update the data correspondingly */
708 if( v - startindex >= 2 )
709 {
710 assert(*nblocks < nvars/2);
711 (*nblockvars) += v - startindex;
712 (*maxblocksize) = MAX((*maxblocksize), v - startindex);
713 (*blockstart)[*nblocks] = startindex;
714 (*blockend)[*nblocks] = v - 1;
715 (*nblocks)++;
716 }
717 startindex = v;
718 }
719 else if( v == nvars - 1 && v - startindex >= 1 )
720 {
721 assert(*nblocks < nvars/2);
722 (*nblockvars) += v - startindex + 1;
723 (*maxblocksize) = MAX((*maxblocksize), v - startindex + 1);
724 (*blockstart)[*nblocks] = startindex;
725 (*blockend)[*nblocks] = v;
726 (*nblocks)++;
727 }
728 }
729
730 /* reallocate memory with respect to the number of found blocks; if there were none, free the memory */
731 if( *nblocks > 0 )
732 {
733 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, blockstart, nvars/2, *nblocks) );
734 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, blockend, nvars/2, *nblocks) );
735 }
736 else
737 {
738 SCIPfreeBlockMemoryArray(scip, blockstart, nvars/2);
739 SCIPfreeBlockMemoryArray(scip, blockend, nvars/2);
740
741 *blockstart = NULL;
742 *blockend = NULL;
743 }
744
745 return SCIP_OKAY;
746}
747
748/** initializes the required structures for execution of heuristic.
749 *
750 * If objective coefficient functions are not all equal, each Binary and Integer variables are sorted
751 * into heuristic-specific arrays with respect to their lexicographical column order,
752 * where every zero in a column is interpreted as zero and every nonzero as '1'.
753 * After the sorting, the variables are compared with respect to user parameter matchingrate and
754 * the heuristic specific blocks are determined.
755 */
756static
758 SCIP* scip, /**< current scip instance */
759 SCIP_HEUR* heur, /**< heuristic */
760 SCIP_HEURDATA* heurdata /**< the heuristic data */
761 )
762{
763 int nbinvars;
764 int nintvars;
765 int nvars;
766 SCIP_VAR** vars;
767 int nbinblockvars;
768 int nintblockvars;
769 int maxbinblocksize;
770 int maxintblocksize;
771
772 assert(scip != NULL);
773 assert(heurdata != NULL);
774
775 /* ensure that method is not executed if presolving was already applied once in current branch and bound process */
776 if( heurdata->presolved )
777 return SCIP_OKAY;
778
779 /* get necessary variable information, i.e. number of binary and integer variables */
780 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
781
782#ifdef SCIP_STATISTIC
783 /* update statistics */
784 heurdata->ntotalbinvars += nbinvars;
785#endif
786
787 /* if number of binary problem variables exceeds 2, they are subject to 2-optimization algorithm, hence heuristic
788 * calls innerPresolve method to detect necessary structures. */
789 if( nbinvars >= 2 )
790 {
791 SCIP_CALL( innerPresolve(scip, vars, &(heurdata->binvars), nbinvars, &(heurdata->nbinblocks), &maxbinblocksize,
792 &nbinblockvars, &(heurdata->binblockstart), &(heurdata->binblockend), heur, heurdata) );
793
794#ifdef SCIP_STATISTIC
795 /* update statistics */
796 heurdata->binnblocks += heurdata->nbinblocks;
797 heurdata->binnblockvars += nbinblockvars;
798 heurdata->maxbinblocksize = MAX(maxbinblocksize, heurdata->maxbinblocksize);
799
800 SCIPstatisticMessage(" Twoopt BINARY presolving finished with <%d> blocks, <%d> block variables \n",
801 heurdata->nbinblocks, nbinblockvars);
802#endif
803 }
804
805 heurdata->nbinvars = nbinvars;
806 heurdata->execute = nbinvars > 1 && heurdata->nbinblocks > 0;
807
808 if( heurdata->intopt && nintvars > 1 )
809 {
810 SCIP_CALL( innerPresolve(scip, &(vars[nbinvars]), &(heurdata->intvars), nintvars, &(heurdata->nintblocks), &maxintblocksize,
811 &nintblockvars, &(heurdata->intblockstart), &(heurdata->intblockend),
812 heur, heurdata) );
813
814 heurdata->execute = heurdata->execute || heurdata->nintblocks > 0;
815
816#ifdef SCIP_STATISTIC
817 /* update statistics */
818 heurdata->intnblocks += heurdata->nintblocks;
819 heurdata->intnblockvars += nintblockvars;
820 heurdata->ntotalintvars += nintvars;
821 heurdata->maxintblocksize = MAX(maxintblocksize, heurdata->maxintblocksize);
822 SCIPstatisticMessage(" Twoopt Integer presolving finished with <%d> blocks, <%d> block variables \n",
823 heurdata->nintblocks, nintblockvars);
824 SCIPstatisticMessage(" INTEGER coefficients are all equal \n");
825#endif
826 }
827 heurdata->nintvars = nintvars;
828
829 /* presolving is finished, heuristic data is updated*/
830 heurdata->presolved = TRUE;
831 SCIPheurSetData(heur, heurdata);
832
833 return SCIP_OKAY;
834}
835
836/*
837 * Callback methods of primal heuristic
838 */
839
840/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
841static
842SCIP_DECL_HEURCOPY(heurCopyTwoopt)
843{ /*lint --e{715}*/
844 assert(scip != NULL);
845 assert(heur != NULL);
846 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
847
848 /* call inclusion method of primal heuristic */
850
851 return SCIP_OKAY;
852}
853
854/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
855static
856SCIP_DECL_HEURFREE(heurFreeTwoopt)
857{ /*lint --e{715}*/
858 SCIP_HEURDATA* heurdata;
859
860 assert(heur != NULL);
861 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
862 assert(scip != NULL);
863
864 /* free heuristic data */
865 heurdata = SCIPheurGetData(heur);
866 assert(heurdata != NULL);
867
868 SCIPfreeBlockMemory(scip, &heurdata);
869 SCIPheurSetData(heur, NULL);
870
871 return SCIP_OKAY;
872}
873
874/** initialization method of primal heuristic (called after problem was transformed) */
875static
876SCIP_DECL_HEURINIT(heurInitTwoopt)
877{
878 SCIP_HEURDATA* heurdata;
879 assert(heur != NULL);
880 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
881 assert(scip != NULL);
882
883 heurdata = SCIPheurGetData(heur);
884 assert(heurdata != NULL);
885
886 /* heuristic has not run yet, all heuristic specific data is set to initial values */
887 heurdata->nbinvars = 0;
888 heurdata->nintvars = 0;
889 heurdata->lastsolindex = -1;
890 heurdata->presolved = FALSE;
891 heurdata->nbinblocks = 0;
892 heurdata->nintblocks = 0;
893
894 /* create random number generator */
895 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
897
898#ifdef SCIP_STATISTIC
899 /* initialize statistics */
900 heurdata->binnexchanges = 0;
901 heurdata->intnexchanges = 0;
902 heurdata->binnblockvars = 0;
903 heurdata->intnblockvars = 0;
904 heurdata->binnblocks = 0;
905 heurdata->intnblocks = 0;
906
907 heurdata->maxbinblocksize = 0;
908 heurdata->maxintblocksize = 0;
909
910 heurdata->ntotalbinvars = 0;
911 heurdata->ntotalintvars = 0;
912 heurdata->nruns = 0;
913#endif
914
915 /* all pointers are initially set to NULL. Since presolving
916 * of the heuristic requires a lot of calculation time on some instances,
917 * but might not be needed e.g. if problem is infeasible, presolving is applied
918 * when heuristic is executed for the first time
919 */
920 heurdata->binvars = NULL;
921 heurdata->intvars = NULL;
922 heurdata->binblockstart = NULL;
923 heurdata->binblockend = NULL;
924 heurdata->intblockstart = NULL;
925 heurdata->intblockend = NULL;
926
927 SCIPheurSetData(heur, heurdata);
928
929 return SCIP_OKAY;
930}
931
932/* Realizes the 2-optimization algorithm, which tries to improve incumbent solution
933 * by shifting pairs of variables which share a common row set.
934 */
935static
937 SCIP* scip, /**< current SCIP instance */
938 SCIP_SOL* worksol, /**< working solution */
939 SCIP_VAR** vars, /**< binary or integer variables */
940 int* blockstart, /**< contains start indices of blocks */
941 int* blockend, /**< contains end indices of blocks */
942 int nblocks, /**< the number of blocks */
943 OPTTYPE opttype, /**< are binaries or integers optimized */
944 SCIP_Real* activities, /**< the LP-row activities */
945 int nrows, /**< the number of LP rows */
946 SCIP_Bool* improvement, /**< was there a successful shift? */
947 SCIP_Bool* varboundserr, /**< has the current incumbent already been cut off */
948 SCIP_HEURDATA* heurdata /**< the heuristic data */
949 )
950{ /*lint --e{715}*/
951 SCIP_Real* objchanges;
952 SCIP_VAR** bestmasters;
953 SCIP_VAR** bestslaves;
954 int* bestdirections;
955 int arraysize;
956 int npairs = 0;
957
958 assert(scip != NULL);
959 assert(nblocks > 0);
960 assert(blockstart != NULL && blockend != NULL);
961 assert(varboundserr != NULL);
962 assert(activities != NULL);
963 assert(worksol != NULL);
964 assert(improvement != NULL);
965
966 *varboundserr = FALSE;
967
972 arraysize = DEFAULT_ARRAYSIZE;
973
974 /* iterate over blocks */
975 for( int b = 0; b < nblocks; ++b )
976 {
977 int blocklen;
978
979 blocklen = blockend[b] - blockstart[b] + 1;
980
981 /* iterate over variables in current block */
982 for( int m = 0; m < blocklen; ++m )
983 {
984 /* determine the new master variable for heuristic's optimization method */
985 SCIP_VAR* master;
986 SCIP_Real masterobj;
987 SCIP_Real mastersolval;
988 SCIP_Real bestimprovement;
989 SCIP_Real bestbound;
990 int bestslavepos;
991 int firstslave;
992 int nslaves;
993 int bestdirection;
994 DIRECTION bestmasterdir;
995 DIRECTION bestslavedir;
996
997 master = vars[blockstart[b] + m]; /*lint !e679*/
998 masterobj = SCIPvarGetObj(master);
999 mastersolval = SCIPgetSolVal(scip, worksol, master);
1000
1001 /* due to cuts or fixings of solution values, worksol might not be feasible w.r.t. its bounds.
1002 * Exit method in that case. */
1003 if( SCIPisFeasGT(scip, mastersolval, SCIPvarGetUbGlobal(master)) || SCIPisFeasLT(scip, mastersolval, SCIPvarGetLbGlobal(master)) )
1004 {
1005 *varboundserr = TRUE;
1006 SCIPdebugMsg(scip, "Solution has violated variable bounds for var %s: %g <= %g <= %g \n",
1007 SCIPvarGetName(master), SCIPvarGetLbGlobal(master), mastersolval, SCIPvarGetUbGlobal(master));
1008 goto TERMINATE;
1009 }
1010
1011 /* if variable has fixed solution value, it is deleted from heuristic array */
1013 {
1014 disposeVariable(vars, &(blockend[b]), blockstart[b] + m);
1015 --blocklen;
1016 continue;
1017 }
1018 else if( SCIPvarGetStatus(master) != SCIP_VARSTATUS_COLUMN )
1019 continue;
1020
1021 assert(SCIPisFeasIntegral(scip, mastersolval));
1022
1023 assert(opttype == OPTTYPE_INTEGER || (SCIPisFeasLE(scip, mastersolval, 1.0) || SCIPisFeasGE(scip, mastersolval, 0.0)));
1024
1025 /* initialize the data of the best available shift */
1026 bestimprovement = 0.0;
1027 bestslavepos = -1;
1028 bestbound = 0.0;
1029 bestmasterdir = DIRECTION_NONE;
1030 bestslavedir = DIRECTION_NONE;
1031 bestdirection = -1;
1032
1033 /* in blocks with more than heurdata->maxnslaves variables, a slave candidate region is chosen */
1034 if( heurdata->maxnslaves >= 0 && blocklen > heurdata->maxnslaves )
1035 firstslave = SCIPrandomGetInt(heurdata->randnumgen, blockstart[b] + m, blockend[b]);
1036 else
1037 firstslave = blockstart[b] + m + 1;
1038
1039 nslaves = MIN((heurdata->maxnslaves == -1 ? INT_MAX : heurdata->maxnslaves), blocklen);
1040
1041 /* Loop over block and determine a slave shift candidate for master variable.
1042 * If more than one candidate is available, choose the shift which improves objective function
1043 * the most. */
1044 for( int s = 0; s < nslaves; ++s )
1045 {
1046 SCIP_VAR* slave;
1047 SCIP_Real slaveobj;
1048 SCIP_Real slavesolval;
1049 SCIP_Real changedobj;
1050 SCIP_Real diffdirbound;
1051 SCIP_Real equaldirbound;
1052 int directions;
1053 int slaveindex;
1054
1055 slaveindex = (firstslave + s - blockstart[b]) % blocklen;
1056 slaveindex += blockstart[b];
1057
1058 /* in case of a small block, we do not want to try possible pairings twice */
1059 if( (blocklen <= heurdata->maxnslaves || heurdata->maxnslaves == -1) && slaveindex < blockstart[b] + m )
1060 break;
1061 /* master and slave should not be the same variable */
1062 if( slaveindex == blockstart[b] + m )
1063 continue;
1064
1065 /* get the next slave variable */
1066 slave = vars[slaveindex];
1067 slaveobj = SCIPvarGetObj(slave);
1068 slavesolval = SCIPgetSolVal(scip, worksol, slave);
1069 changedobj = 0.0;
1070
1071 assert(SCIPvarGetType(master) == SCIPvarGetType(slave));
1072 assert(SCIPisFeasIntegral(scip, slavesolval));
1073 assert(opttype == OPTTYPE_INTEGER || (SCIPisFeasLE(scip, mastersolval, 1.0) || SCIPisFeasGE(scip, mastersolval, 0.0)));
1074
1075 /* solution is not feasible w.r.t. the variable bounds, stop optimization in this case */
1076 if( SCIPisFeasGT(scip, slavesolval, SCIPvarGetUbGlobal(slave)) || SCIPisFeasLT(scip, slavesolval, SCIPvarGetLbGlobal(slave)) )
1077 {
1078 *varboundserr = TRUE;
1079 SCIPdebugMsg(scip, "Solution has violated variable bounds for var %s: %g <= %g <= %g \n",
1080 SCIPvarGetName(slave), SCIPvarGetLbGlobal(slave), slavesolval, SCIPvarGetUbGlobal(slave));
1081 goto TERMINATE;
1082 }
1083
1084 /* if solution value of the variable is fixed, delete it from the remaining candidates in the block */
1086 {
1087 disposeVariable(vars, &(blockend[b]), slaveindex);
1088 --blocklen;
1089 continue;
1090 }
1091 else if( SCIPvarGetStatus(master) != SCIP_VARSTATUS_COLUMN )
1092 continue;
1093
1094 /* determine the shifting direction to improve the objective function */
1095 /* The heuristic chooses the shifting direction and the corresponding maximum nonnegative
1096 * integer shift value for the two variables which preserves feasibility and improves
1097 * the objective function value. */
1098 directions = -1;
1099 diffdirbound = 0.0;
1100 equaldirbound = 0.0;
1101
1102 if( SCIPisPositive(scip, slaveobj - masterobj) )
1103 {
1104 diffdirbound = determineBound(scip, worksol, master, DIRECTION_UP, slave, DIRECTION_DOWN, activities, nrows);
1105 directions = 2;
1106 /* the improvement of objective function is calculated */
1107 changedobj = (masterobj - slaveobj) * diffdirbound;
1108 }
1109 else if( SCIPisPositive(scip, masterobj - slaveobj) )
1110 {
1111 diffdirbound = determineBound(scip, worksol, master, DIRECTION_DOWN, slave, DIRECTION_UP, activities, nrows);
1112 directions = 1;
1113 changedobj = (slaveobj - masterobj) * diffdirbound;
1114 }
1115
1116 if( SCIPisPositive(scip, -(masterobj + slaveobj)) )
1117 {
1118 equaldirbound = determineBound(scip, worksol, master, DIRECTION_UP, slave, DIRECTION_UP, activities, nrows);
1119 if( (masterobj + slaveobj) * equaldirbound < changedobj )
1120 {
1121 changedobj = (masterobj + slaveobj) * equaldirbound;
1122 directions = 3;
1123 }
1124 }
1125 else if( SCIPisPositive(scip, masterobj + slaveobj) )
1126 {
1127 equaldirbound = determineBound(scip, worksol, master, DIRECTION_DOWN, slave, DIRECTION_DOWN, activities, nrows);
1128 if( -(masterobj + slaveobj) * equaldirbound < changedobj )
1129 {
1130 changedobj = -(masterobj + slaveobj) * equaldirbound;
1131 directions = 0;
1132 }
1133 }
1134 assert(SCIPisFeasIntegral(scip, equaldirbound));
1135 assert(SCIPisFeasIntegral(scip, diffdirbound));
1136 assert(SCIPisFeasGE(scip, equaldirbound, 0.0));
1137 assert(SCIPisFeasGE(scip, diffdirbound, 0.0));
1138
1139 /* choose the candidate which improves the objective function the most */
1140 if( (SCIPisFeasGT(scip, equaldirbound, 0.0) || SCIPisFeasGT(scip, diffdirbound, 0.0))
1141 && changedobj < bestimprovement )
1142 {
1143 bestimprovement = changedobj;
1144 bestslavepos = slaveindex;
1145 bestdirection = directions;
1146
1147 /* the most promising shift, i.e., the one which can improve the objective
1148 * the most, is recorded by the integer 'directions'. It is recovered via the use
1149 * of a binary representation of the four different combinations for the shifting directions
1150 * of two variables */
1151 if( directions / 2 == 1 )
1152 bestmasterdir = DIRECTION_UP;
1153 else
1154 bestmasterdir = DIRECTION_DOWN;
1155
1156 if( directions % 2 == 1 )
1157 bestslavedir = DIRECTION_UP;
1158 else
1159 bestslavedir = DIRECTION_DOWN;
1160
1161 if( bestmasterdir == bestslavedir )
1162 bestbound = equaldirbound;
1163 else
1164 bestbound = diffdirbound;
1165 }
1166 }
1167
1168 /* choose the most promising candidate, if one exists */
1169 if( bestslavepos >= 0 )
1170 {
1171 if( npairs == arraysize )
1172 {
1173 SCIP_CALL( SCIPreallocBufferArray(scip, &bestmasters, 2 * arraysize) );
1174 SCIP_CALL( SCIPreallocBufferArray(scip, &bestslaves, 2 * arraysize) );
1175 SCIP_CALL( SCIPreallocBufferArray(scip, &objchanges, 2 * arraysize) );
1176 SCIP_CALL( SCIPreallocBufferArray(scip, &bestdirections, 2 * arraysize) );
1177 arraysize = 2 * arraysize;
1178 }
1179 assert( npairs < arraysize );
1180
1181 bestmasters[npairs] = master;
1182 bestslaves[npairs] = vars[bestslavepos];
1183 objchanges[npairs] = ((int)bestslavedir * SCIPvarGetObj(bestslaves[npairs]) + (int)bestmasterdir * masterobj) * bestbound;
1184 bestdirections[npairs] = bestdirection;
1185
1186 assert(objchanges[npairs] < 0);
1187
1188 SCIPdebugMsg(scip, " Saved candidate pair {%s=%g, %s=%g} with objectives <%g>, <%g> to be set to {%g, %g} %d\n",
1189 SCIPvarGetName(master), mastersolval, SCIPvarGetName(bestslaves[npairs]), SCIPgetSolVal(scip, worksol, bestslaves[npairs]) ,
1190 masterobj, SCIPvarGetObj(bestslaves[npairs]), mastersolval + (int)bestmasterdir * bestbound, SCIPgetSolVal(scip, worksol, bestslaves[npairs])
1191 + (int)bestslavedir * bestbound, bestdirections[npairs]);
1192
1193 ++npairs;
1194 }
1195 }
1196 }
1197
1198 if( npairs == 0 )
1199 goto TERMINATE;
1200
1201 SCIPsortRealPtrPtrInt(objchanges, (void**)bestmasters, (void**)bestslaves, bestdirections, npairs);
1202
1203 for( int b = 0; b < npairs; ++b )
1204 {
1205 SCIP_VAR* master;
1206 SCIP_VAR* slave;
1207 SCIP_Real mastersolval;
1208 SCIP_Real slavesolval;
1209 SCIP_Real masterobj;
1210 SCIP_Real slaveobj;
1212 DIRECTION masterdir;
1213 DIRECTION slavedir;
1214
1215 master = bestmasters[b];
1216 slave = bestslaves[b];
1217 mastersolval = SCIPgetSolVal(scip, worksol, master);
1218 slavesolval = SCIPgetSolVal(scip, worksol, slave);
1219 masterobj =SCIPvarGetObj(master);
1220 slaveobj = SCIPvarGetObj(slave);
1221
1222 assert(0 <= bestdirections[b] && bestdirections[b] < 4);
1223
1224 if( bestdirections[b] / 2 == 1 )
1225 masterdir = DIRECTION_UP;
1226 else
1227 masterdir = DIRECTION_DOWN;
1228
1229 if( bestdirections[b] % 2 == 1 )
1230 slavedir = DIRECTION_UP;
1231 else
1232 slavedir = DIRECTION_DOWN;
1233
1234 bound = determineBound(scip, worksol, master, masterdir, slave, slavedir, activities, nrows);
1235
1236 if( !SCIPisZero(scip, bound) )
1237 {
1238 SCIP_Bool feasible;
1239#ifndef NDEBUG
1240 SCIP_Real changedobj;
1241#endif
1242
1243 SCIPdebugMsg(scip, " Promising candidates {%s=%g, %s=%g} with objectives <%g>, <%g> to be set to {%g, %g}\n",
1244 SCIPvarGetName(master), mastersolval, SCIPvarGetName(slave), slavesolval,
1245 masterobj, slaveobj, mastersolval + (int)masterdir * bound, slavesolval + (int)slavedir * bound);
1246
1247#ifndef NDEBUG
1248 /* the improvement of objective function is calculated */
1249 changedobj = ((int)slavedir * slaveobj + (int)masterdir * masterobj) * bound;
1250 assert( SCIPisPositive(scip, -changedobj) );
1251#endif
1252
1254 /* try to change the solution values of the variables */
1255 feasible = FALSE;
1256 SCIP_CALL( shiftValues(scip, master, slave, mastersolval, masterdir, slavesolval, slavedir, bound,
1257 activities, nrows, &feasible) );
1258
1259 if( feasible )
1260 {
1261 /* The variables' solution values were successfully shifted and can hence be updated. */
1262 assert(SCIPisFeasIntegral(scip, mastersolval + ((int)masterdir * bound)));
1263 assert(SCIPisFeasIntegral(scip, slavesolval + ((int)slavedir * bound)));
1264
1265 SCIP_CALL( SCIPsetSolVal(scip, worksol, master, mastersolval + (int)masterdir * bound) );
1266 SCIP_CALL( SCIPsetSolVal(scip, worksol, slave, slavesolval + (int)slavedir * bound) );
1267 SCIPdebugMsg(scip, " Feasible shift: <%s>[%g, %g] (obj: %f) <%f> --> <%f>\n",
1268 SCIPvarGetName(master), SCIPvarGetLbGlobal(master), SCIPvarGetUbGlobal(master), masterobj, mastersolval, SCIPgetSolVal(scip, worksol, master));
1269 SCIPdebugMsg(scip, " <%s>[%g, %g] (obj: %f) <%f> --> <%f>\n",
1270 SCIPvarGetName(slave), SCIPvarGetLbGlobal(slave), SCIPvarGetUbGlobal(slave), slaveobj, slavesolval, SCIPgetSolVal(scip, worksol, slave));
1271
1272#ifdef SCIP_STATISTIC
1273 /* update statistics */
1274 if( opttype == OPTTYPE_BINARY )
1275 ++(heurdata->binnexchanges);
1276 else
1277 ++(heurdata->intnexchanges);
1278#endif
1279
1280 *improvement = TRUE;
1281 }
1282 }
1283 }
1284 TERMINATE:
1285 SCIPfreeBufferArray(scip, &bestdirections);
1286 SCIPfreeBufferArray(scip, &objchanges);
1287 SCIPfreeBufferArray(scip, &bestslaves);
1288 SCIPfreeBufferArray(scip, &bestmasters);
1289
1290 return SCIP_OKAY;
1291}
1292
1293/** deinitialization method of primal heuristic (called before transformed problem is freed) */
1294static
1295SCIP_DECL_HEUREXIT(heurExitTwoopt)
1296{
1297 SCIP_HEURDATA* heurdata;
1298
1299 heurdata = SCIPheurGetData(heur);
1300 assert(heurdata != NULL);
1301
1302 /*ensure that initialization was successful */
1303 assert(heurdata->nbinvars <= 1 || heurdata->binvars != NULL);
1304
1305#ifdef SCIP_STATISTIC
1306 /* print relevant statistics to console */
1308 " Twoopt Binary Statistics : "
1309 "%6.2g %6.2g %4.2g %4.0g %6d (blocks/run, variables/run, varpercentage, avg. block size, max block size) \n",
1310 heurdata->nruns == 0 ? 0.0 : (SCIP_Real)heurdata->binnblocks/(heurdata->nruns),
1311 heurdata->nruns == 0 ? 0.0 : (SCIP_Real)heurdata->binnblockvars/(heurdata->nruns),
1312 heurdata->ntotalbinvars == 0 ? 0.0 : (SCIP_Real)heurdata->binnblockvars/(heurdata->ntotalbinvars) * 100.0,
1313 heurdata->binnblocks == 0 ? 0.0 : heurdata->binnblockvars/(SCIP_Real)(heurdata->binnblocks),
1314 heurdata->maxbinblocksize);
1315
1317 " Twoopt Integer statistics : "
1318 "%6.2g %6.2g %4.2g %4.0g %6d (blocks/run, variables/run, varpercentage, avg block size, max block size) \n",
1319 heurdata->nruns == 0 ? 0.0 : (SCIP_Real)heurdata->intnblocks/(heurdata->nruns),
1320 heurdata->nruns == 0 ? 0.0 : (SCIP_Real)heurdata->intnblockvars/(heurdata->nruns),
1321 heurdata->ntotalintvars == 0 ? 0.0 : (SCIP_Real)heurdata->intnblockvars/(heurdata->ntotalintvars) * 100.0,
1322 heurdata->intnblocks == 0 ? 0.0 : heurdata->intnblockvars/(SCIP_Real)(heurdata->intnblocks),
1323 heurdata->maxintblocksize);
1324
1326 " Twoopt results : "
1327 "%6d %6d %4d %4.2g (runs, binary exchanges, Integer shiftings, matching rate)\n",
1328 heurdata->nruns,
1329 heurdata->binnexchanges,
1330 heurdata->intnexchanges,
1331 heurdata->matchingrate);
1332
1333 /* set statistics to initial values*/
1334 heurdata->binnblockvars = 0;
1335 heurdata->binnblocks = 0;
1336 heurdata->intnblocks = 0;
1337 heurdata->intnblockvars = 0;
1338 heurdata->binnexchanges = 0;
1339 heurdata->intnexchanges = 0;
1340#endif
1341
1342 /* free the allocated memory for the binary variables */
1343 if( heurdata->binvars != NULL )
1344 {
1345 SCIPfreeBlockMemoryArray(scip, &heurdata->binvars, heurdata->nbinvars);
1346 }
1347
1348 if( heurdata->nbinblocks > 0 )
1349 {
1350 assert(heurdata->binblockstart != NULL);
1351 assert(heurdata->binblockend != NULL);
1352
1353 SCIPfreeBlockMemoryArray(scip, &heurdata->binblockstart, heurdata->nbinblocks);
1354 SCIPfreeBlockMemoryArray(scip, &heurdata->binblockend, heurdata->nbinblocks);
1355 }
1356 heurdata->nbinvars = 0;
1357 heurdata->nbinblocks = 0;
1358
1359 if( heurdata->nintblocks > 0 )
1360 {
1361 assert(heurdata->intblockstart != NULL);
1362 assert(heurdata->intblockend != NULL);
1363
1364 SCIPfreeBlockMemoryArray(scip, &heurdata->intblockstart, heurdata->nintblocks);
1365 SCIPfreeBlockMemoryArray(scip, &heurdata->intblockend, heurdata->nintblocks);
1366 }
1367
1368 /* free the allocated memory for the integers */
1369 if( heurdata->intvars != NULL )
1370 {
1371 SCIPfreeBlockMemoryArray(scip, &heurdata->intvars, heurdata->nintvars);
1372 }
1373
1374 heurdata->nbinblocks = 0;
1375 heurdata->nintblocks = 0;
1376 heurdata->nbinvars = 0;
1377 heurdata->nintvars = 0;
1378
1379 assert(heurdata->binvars == NULL);
1380 assert(heurdata->intvars == NULL);
1381
1382 /* free random number generator */
1383 SCIPfreeRandom(scip, &heurdata->randnumgen);
1384
1385 SCIPheurSetData(heur, heurdata);
1386
1387 return SCIP_OKAY;
1388}
1389
1390/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
1391static
1392SCIP_DECL_HEURINITSOL(heurInitsolTwoopt)
1393{
1394 SCIP_HEURDATA* heurdata;
1395 assert(heur != NULL);
1396 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1397 assert(scip != NULL);
1398
1399 /* get heuristic data */
1400 heurdata = SCIPheurGetData(heur);
1401
1402 assert(heurdata != NULL);
1403 assert(heurdata->binvars == NULL && heurdata->intvars == NULL);
1404 assert(heurdata->binblockstart == NULL && heurdata->binblockend == NULL);
1405 assert(heurdata->intblockstart == NULL && heurdata->intblockend == NULL);
1406
1407 /* set heuristic data to initial values, but increase the total number of runs */
1408 heurdata->nbinvars = 0;
1409 heurdata->nintvars = 0;
1410 heurdata->lastsolindex = -1;
1411 heurdata->presolved = FALSE;
1412
1413#ifdef SCIP_STATISTIC
1414 ++(heurdata->nruns);
1415#endif
1416
1417 SCIPheurSetData(heur, heurdata);
1418
1419 return SCIP_OKAY;
1420}
1421
1422
1423/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
1424static
1425SCIP_DECL_HEUREXITSOL(heurExitsolTwoopt)
1426{
1427 SCIP_HEURDATA* heurdata;
1428 int nbinvars;
1429 int nintvars;
1430
1431 assert(heur != NULL);
1432 assert(scip != NULL);
1433 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1434 assert(scip != NULL);
1435
1436 /* get heuristic data */
1437 heurdata = SCIPheurGetData(heur);
1438
1439 assert(heurdata != NULL);
1440
1441 nbinvars = heurdata->nbinvars;
1442 nintvars = heurdata->nintvars;
1443
1444 /* free the allocated memory for the binary variables */
1445 if( heurdata->binvars != NULL )
1446 {
1447 SCIPfreeBlockMemoryArray(scip, &heurdata->binvars, nbinvars);
1448 }
1449 if( heurdata->binblockstart != NULL )
1450 {
1451 assert(heurdata->binblockend != NULL);
1452
1453 SCIPfreeBlockMemoryArray(scip, &heurdata->binblockstart, heurdata->nbinblocks);
1454 SCIPfreeBlockMemoryArray(scip, &heurdata->binblockend, heurdata->nbinblocks);
1455 }
1456 heurdata->nbinvars = 0;
1457 heurdata->nbinblocks = 0;
1458
1459 if( heurdata->intblockstart != NULL )
1460 {
1461 assert(heurdata->intblockend != NULL);
1462
1463 SCIPfreeBlockMemoryArray(scip, &heurdata->intblockstart, heurdata->nintblocks);
1464 SCIPfreeBlockMemoryArray(scip, &heurdata->intblockend, heurdata->nintblocks);
1465 }
1466 heurdata->nintblocks = 0;
1467
1468 /* free the allocated memory for the integers */
1469 if( heurdata->intvars != NULL )
1470 {
1471 SCIPfreeBlockMemoryArray(scip, &heurdata->intvars, nintvars);
1472 }
1473
1474 heurdata->nintvars = 0;
1475
1476 assert(heurdata->binvars == NULL && heurdata->intvars == NULL);
1477 assert(heurdata->binblockstart == NULL && heurdata->binblockend == NULL);
1478 assert(heurdata->intblockstart == NULL && heurdata->intblockend == NULL);
1479
1480 /* set heuristic data */
1481 SCIPheurSetData(heur, heurdata);
1482
1483 return SCIP_OKAY;
1484}
1485
1486/** execution method of primal heuristic */
1487static
1488SCIP_DECL_HEUREXEC(heurExecTwoopt)
1489{ /*lint --e{715}*/
1490 SCIP_HEURDATA* heurdata;
1491 SCIP_SOL* bestsol;
1492 SCIP_SOL* worksol;
1493 SCIP_ROW** lprows;
1494 SCIP_Real* activities;
1495 SCIP_COL** cols;
1496 int ncols;
1497 int nbinvars;
1498 int nintvars;
1499 int ndiscvars;
1500 int nlprows;
1501 int ncolsforsorting;
1502 SCIP_Bool improvement;
1503 SCIP_Bool presolthiscall;
1504 SCIP_Bool varboundserr;
1505
1506 assert(heur != NULL);
1507 assert(scip != NULL);
1508 assert(result != NULL);
1509
1510 /* get heuristic data */
1511 heurdata = SCIPheurGetData(heur);
1512 assert(heurdata != NULL);
1513
1514 *result = SCIP_DIDNOTRUN;
1515
1516 /* we need an LP */
1517 if( SCIPgetNLPRows(scip) == 0 )
1518 return SCIP_OKAY;
1519
1520 bestsol = SCIPgetBestSol(scip);
1521
1522 /* ensure that heuristic has not already been processed on current incumbent */
1523 if( bestsol == NULL || heurdata->lastsolindex == SCIPsolGetIndex(bestsol) )
1524 return SCIP_OKAY;
1525
1526 heurdata->lastsolindex = SCIPsolGetIndex(bestsol);
1527
1528 /* we can only work on solutions valid in the transformed space */
1529 if( SCIPsolIsOriginal(bestsol) )
1530 return SCIP_OKAY;
1531
1532#ifdef SCIP_DEBUG
1533 SCIP_CALL( SCIPprintSol(scip, bestsol, NULL, TRUE) );
1534#endif
1535
1536 /* ensure that the user defined number of nodes after last best solution has been reached, return otherwise */
1537 if( (SCIPgetNNodes(scip) - SCIPsolGetNodenum(bestsol)) < heurdata->waitingnodes )
1538 return SCIP_OKAY;
1539
1540 presolthiscall = FALSE;
1541 SCIP_CALL( SCIPgetLPColsData(scip,&cols, &ncols) );
1542 ndiscvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1543 ncolsforsorting = MIN(ncols, ndiscvars);
1544
1545 /* ensure that heuristic specific presolve is applied when heuristic is executed first */
1546 if( !heurdata->presolved )
1547 {
1548 SCIP_CALL( SCIPgetLPColsData(scip,&cols, &ncols) );
1549
1550 for( int i = 0; i < ncolsforsorting; ++i )
1551 SCIPcolSort(cols[i]);
1552
1553 SCIP_CALL( presolveTwoOpt(scip, heur, heurdata) );
1554 presolthiscall = TRUE;
1555 }
1556
1557 assert(heurdata->presolved);
1558
1559 SCIPdebugMsg(scip, " Twoopt heuristic is %sexecuting.\n", heurdata->execute ? "" : "not ");
1560 /* ensure that presolve has detected structures in the problem to which the 2-optimization can be applied.
1561 * That is if variables exist which share a common set of LP-rows. */
1562 if( !heurdata->execute )
1563 return SCIP_OKAY;
1564
1565 nbinvars = heurdata->nbinvars;
1566 nintvars = heurdata->nintvars;
1567 ndiscvars = nbinvars + nintvars;
1568
1569 /* we need to be able to start diving from current node in order to resolve the LP
1570 * with continuous or implicit integer variables
1571 */
1573 return SCIP_OKAY;
1574
1575 /* problem satisfies all necessary conditions for 2-optimization heuristic, execute heuristic! */
1576 *result = SCIP_DIDNOTFIND;
1577
1578 /* initialize a working solution as a copy of the current incumbent to be able to store
1579 * possible improvements obtained by 2-optimization */
1580 SCIP_CALL( SCIPcreateSolCopy(scip, &worksol, bestsol) );
1581 SCIPsolSetHeur(worksol, heur);
1582
1583 /* get the LP row activities from current incumbent bestsol */
1584 SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
1585 SCIP_CALL( SCIPallocBufferArray(scip, &activities, nlprows) );
1586
1587 for( int i = 0; i < nlprows; ++i )
1588 {
1589 SCIP_ROW* row;
1590
1591 row = lprows[i];
1592 assert(row != NULL);
1593 assert(SCIProwGetLPPos(row) == i);
1594 SCIPdebugMsg(scip, " Row <%d> is %sin LP: \n", i, SCIProwGetLPPos(row) >= 0 ? "" : "not ");
1596 activities[i] = SCIPgetRowSolActivity(scip, row, bestsol);
1597
1598 /* Heuristic does not provide infeasibility recovery, thus if any constraint is violated,
1599 * execution has to be terminated.
1600 */
1601 if( !SCIProwIsLocal(row) && (SCIPisFeasLT(scip, activities[i], SCIProwGetLhs(row))
1602 || SCIPisFeasGT(scip, activities[i], SCIProwGetRhs(row))) )
1603 goto TERMINATE;
1604 }
1605
1606 if( !presolthiscall )
1607 {
1608 for( int i = 0; i < ncolsforsorting; ++i )
1609 SCIPcolSort(cols[i]);
1610 }
1611 SCIPdebugMsg(scip, " Twoopt heuristic has initialized activities and sorted rows! \n");
1612
1613 /* start with binary optimization */
1614 improvement = FALSE;
1615 varboundserr = FALSE;
1616
1617 if( heurdata->nbinblocks > 0 )
1618 {
1619 SCIP_CALL( optimize(scip, worksol, heurdata->binvars, heurdata->binblockstart, heurdata->binblockend, heurdata->nbinblocks,
1620 OPTTYPE_BINARY, activities, nlprows, &improvement, &varboundserr, heurdata) );
1621
1622 SCIPdebugMsg(scip, " Binary Optimization finished!\n");
1623 }
1624
1625 if( varboundserr )
1626 goto TERMINATE;
1627
1628 /* ensure that their are at least two integer variables which do not have the same coefficient
1629 * in the objective function. In one of these cases, the heuristic will automatically skip the
1630 * integer variable optimization */
1631 if( heurdata->nintblocks > 0 )
1632 {
1633 assert(heurdata->intopt);
1634 SCIP_CALL( optimize(scip, worksol, heurdata->intvars, heurdata->intblockstart, heurdata->intblockend, heurdata->nintblocks,
1635 OPTTYPE_INTEGER, activities, nlprows, &improvement, &varboundserr, heurdata) );
1636
1637 SCIPdebugMsg(scip, " Integer Optimization finished!\n");
1638 }
1639
1640 if( ! improvement || varboundserr )
1641 goto TERMINATE;
1642
1643 if( SCIPgetNVars(scip) == ndiscvars )
1644 {
1645 /* the problem is a pure IP, hence, no continuous or implicit variables are left for diving.
1646 * try if new working solution is feasible in original problem */
1647 SCIP_Bool success;
1648#ifndef NDEBUG
1649 SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
1650#else
1651 SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
1652#endif
1653
1654 if( success )
1655 {
1656 SCIPdebugMsg(scip, "found feasible shifted solution:\n");
1657 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, worksol, NULL, FALSE) ) );
1658 heurdata->lastsolindex = SCIPsolGetIndex(bestsol);
1659 *result = SCIP_FOUNDSOL;
1660
1661#ifdef SCIP_STATISTIC
1662 SCIPstatisticMessage("***Twoopt improved solution found by %10s . \n",
1663 SCIPsolGetHeur(bestsol) != NULL ? SCIPheurGetName(SCIPsolGetHeur(bestsol)) :"Tree");
1664#endif
1665 }
1666 }
1667 /* fix the integer variables and start diving to optimize continuous variables with respect to reduced domain */
1668 else
1669 {
1670 SCIP_VAR** allvars;
1671 SCIP_Bool lperror;
1672#ifdef NDEBUG
1673 SCIP_RETCODE retstat;
1674#endif
1675
1676 SCIPdebugMsg(scip, "shifted solution should be feasible -> solve LP to fix continuous variables to best values\n");
1677
1678 allvars = SCIPgetVars(scip);
1679
1680#ifdef SCIP_DEBUG
1681 for( int i = ndiscvars; i < SCIPgetNVars(scip); ++i )
1682 {
1683 SCIPdebugMsg(scip, " Cont. variable <%s>, status %d with bounds [%g <= %g <= x <= %g <= %g]\n",
1684 SCIPvarGetName(allvars[i]), SCIPvarGetStatus(allvars[i]), SCIPvarGetLbGlobal(allvars[i]), SCIPvarGetLbLocal(allvars[i]), SCIPvarGetUbLocal(allvars[i]),
1685 SCIPvarGetUbGlobal(allvars[i]));
1686 }
1687#endif
1688
1689 /* start diving to calculate the LP relaxation */
1691
1692 /* set the bounds of the variables: fixed for integers, global bounds for continuous */
1693 for( int i = 0; i < SCIPgetNVars(scip); ++i )
1694 {
1695 if( SCIPvarGetStatus(allvars[i]) == SCIP_VARSTATUS_COLUMN )
1696 {
1697 SCIP_CALL( SCIPchgVarLbDive(scip, allvars[i], SCIPvarGetLbGlobal(allvars[i])) );
1698 SCIP_CALL( SCIPchgVarUbDive(scip, allvars[i], SCIPvarGetUbGlobal(allvars[i])) );
1699 }
1700 }
1701
1702 /* apply this after global bounds to not cause an error with intermediate empty domains */
1703 for( int i = 0; i < ndiscvars; ++i )
1704 {
1705 if( SCIPvarGetStatus(allvars[i]) == SCIP_VARSTATUS_COLUMN )
1706 {
1707 SCIP_Real solval;
1708
1709 solval = SCIPgetSolVal(scip, worksol, allvars[i]);
1710
1711 assert(SCIPvarGetType(allvars[i]) != SCIP_VARTYPE_CONTINUOUS && SCIPisFeasIntegral(scip, solval));
1712
1713 SCIP_CALL( SCIPchgVarLbDive(scip, allvars[i], solval) );
1714 SCIP_CALL( SCIPchgVarUbDive(scip, allvars[i], solval) );
1715 }
1716 }
1717 for( int i = 0; i < ndiscvars; ++i )
1718 {
1719 assert( SCIPisFeasEQ(scip, SCIPgetVarLbDive(scip, allvars[i]), SCIPgetVarUbDive(scip, allvars[i])) );
1720 }
1721 /* solve LP */
1722 SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
1723
1724 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
1725 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
1726#ifdef NDEBUG
1727 retstat = SCIPsolveDiveLP(scip, -1, &lperror, NULL);
1728 if( retstat != SCIP_OKAY )
1729 {
1730 SCIPwarningMessage(scip, "Error while solving LP in Twoopt heuristic; LP solve terminated with code <%d>\n",retstat);
1731 }
1732#else
1733 SCIP_CALL( SCIPsolveDiveLP(scip, -1, &lperror, NULL) );
1734#endif
1735
1736 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
1737 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
1738
1739 /* check if this is a feasible solution */
1740 if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
1741 {
1742 SCIP_Bool success;
1743
1744 /* copy the current LP solution to the working solution */
1745 SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
1746
1747 /* check solution for feasibility */
1748#ifndef NDEBUG
1749 SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
1750#else
1751 SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
1752#endif
1753
1754 if( success )
1755 {
1756 SCIPdebugMsg(scip, "found feasible shifted solution:\n");
1757 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, worksol, NULL, FALSE) ) );
1758 heurdata->lastsolindex = SCIPsolGetIndex(bestsol);
1759 *result = SCIP_FOUNDSOL;
1760
1761#ifdef SCIP_STATISTIC
1762 SCIPstatisticMessage("*** Twoopt improved solution found by %10s . \n",
1763 SCIPsolGetHeur(bestsol) != NULL ? SCIPheurGetName(SCIPsolGetHeur(bestsol)) :"Tree");
1764#endif
1765 }
1766 }
1767
1768 /* terminate the diving */
1770 }
1771
1772 TERMINATE:
1773 SCIPdebugMsg(scip, "Termination of Twoopt heuristic\n");
1774 SCIPfreeBufferArray(scip, &activities);
1775 SCIP_CALL( SCIPfreeSol(scip, &worksol) );
1776
1777 return SCIP_OKAY;
1778}
1779
1780/*
1781 * primal heuristic specific interface methods
1782 */
1783
1784/** creates the twoopt primal heuristic and includes it in SCIP */
1786 SCIP* scip /**< SCIP data structure */
1787 )
1788{
1789 SCIP_HEURDATA* heurdata;
1790 SCIP_HEUR* heur;
1791
1792 /* create Twoopt primal heuristic data */
1793 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1794
1795 /* include primal heuristic */
1798 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTwoopt, heurdata) );
1799
1800 assert(heur != NULL);
1801
1802 /* set non-NULL pointers to callback methods */
1803 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTwoopt) );
1804 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeTwoopt) );
1805 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitTwoopt) );
1806 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitTwoopt) );
1807 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolTwoopt) );
1808 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolTwoopt) );
1809
1810 /* include boolean flag intopt */
1811 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/twoopt/intopt", " Should Integer-2-Optimization be applied or not?",
1812 &heurdata->intopt, TRUE, DEFAULT_INTOPT, NULL, NULL) );
1813
1814 /* include parameter waitingnodes */
1815 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/twoopt/waitingnodes", "user parameter to determine number of "
1816 "nodes to wait after last best solution before calling heuristic",
1817 &heurdata->waitingnodes, TRUE, DEFAULT_WAITINGNODES, 0, 10000, NULL, NULL));
1818
1819 /* include parameter maxnslaves */
1820 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/twoopt/maxnslaves", "maximum number of slaves for one master variable",
1821 &heurdata->maxnslaves, TRUE, DEFAULT_MAXNSLAVES, -1, 1000000, NULL, NULL) );
1822
1823 /* include parameter matchingrate */
1824 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/twoopt/matchingrate",
1825 "parameter to determine the percentage of rows two variables have to share before they are considered equal",
1826 &heurdata->matchingrate, TRUE, DEFAULT_MATCHINGRATE, 0.0, 1.0, NULL, NULL) );
1827
1828 return SCIP_OKAY;
1829}
static long bound
SCIP_VAR ** b
Definition: circlepacking.c:65
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define ABS(x)
Definition: def.h:235
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_CALL(x)
Definition: def.h:374
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
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:83
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
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:57
SCIP_RETCODE SCIPincludeHeurTwoopt(SCIP *scip)
Definition: heur_twoopt.c:1785
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:17126
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17161
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17151
void SCIPcolSort(SCIP_COL *col)
Definition: lp.c:3435
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:242
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
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:117
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:226
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2419
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2451
SCIP_Real SCIPgetVarLbDive(SCIP *scip, SCIP_VAR *var)
Definition: scip_lp.c:2616
SCIP_Real SCIPgetVarUbDive(SCIP *scip, SCIP_VAR *var)
Definition: scip_lp.c:2645
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition: scip_lp.c:2242
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_lp.c:2678
SCIP_RETCODE SCIPendDive(SCIP *scip)
Definition: scip_lp.c:2291
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip_lp.c:471
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:626
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17501
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17401
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
int SCIProwGetIndex(SCIP_ROW *row)
Definition: lp.c:17361
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2144
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:474
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1631
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
Definition: sol.c:2784
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2804
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2721
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2835
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:2954
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:882
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
Definition: sol.c:2849
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17789
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10108
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortRealPtrPtrInt(SCIP_Real *realarray, void **ptrarray1, void **ptrarray2, int *intarray, int len)
static SCIP_Real determineBound(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *master, DIRECTION masterdirection, SCIP_VAR *slave, DIRECTION slavedirection, SCIP_Real *activities, int nrows)
Definition: heur_twoopt.c:405
static SCIP_DECL_HEURINITSOL(heurInitsolTwoopt)
Definition: heur_twoopt.c:1392
Direction
Definition: heur_twoopt.c:137
@ DIRECTION_DOWN
Definition: heur_twoopt.c:139
@ DIRECTION_UP
Definition: heur_twoopt.c:138
@ DIRECTION_NONE
Definition: heur_twoopt.c:140
static void disposeVariable(SCIP_VAR **vars, int *blockend, int varindex)
Definition: heur_twoopt.c:642
static SCIP_DECL_HEUREXIT(heurExitTwoopt)
Definition: heur_twoopt.c:1295
#define HEUR_TIMING
Definition: heur_twoopt.c:63
static SCIP_DECL_HEURFREE(heurFreeTwoopt)
Definition: heur_twoopt.c:856
#define HEUR_FREQOFS
Definition: heur_twoopt.c:60
#define HEUR_DESC
Definition: heur_twoopt.c:56
enum Direction DIRECTION
Definition: heur_twoopt.c:142
#define DEFAULT_MATCHINGRATE
Definition: heur_twoopt.c:69
static SCIP_DECL_HEUREXEC(heurExecTwoopt)
Definition: heur_twoopt.c:1488
#define DEFAULT_WAITINGNODES
Definition: heur_twoopt.c:68
static SCIP_Bool checkConstraintMatching(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real matchingrate)
Definition: heur_twoopt.c:307
static SCIP_DECL_SORTPTRCOMP(SCIPvarcolComp)
Definition: heur_twoopt.c:298
static SCIP_DECL_HEURCOPY(heurCopyTwoopt)
Definition: heur_twoopt.c:842
#define HEUR_DISPCHAR
Definition: heur_twoopt.c:57
#define HEUR_MAXDEPTH
Definition: heur_twoopt.c:61
#define HEUR_PRIORITY
Definition: heur_twoopt.c:58
static int varColCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: heur_twoopt.c:256
#define HEUR_NAME
Definition: heur_twoopt.c:55
static SCIP_DECL_HEUREXITSOL(heurExitsolTwoopt)
Definition: heur_twoopt.c:1425
#define DEFAULT_ARRAYSIZE
Definition: heur_twoopt.c:72
enum Opttype OPTTYPE
Definition: heur_twoopt.c:133
#define DEFAULT_RANDSEED
Definition: heur_twoopt.c:73
#define DEFAULT_MAXNSLAVES
Definition: heur_twoopt.c:71
static SCIP_DECL_HEURINIT(heurInitTwoopt)
Definition: heur_twoopt.c:876
static SCIP_RETCODE shiftValues(SCIP *scip, SCIP_VAR *master, SCIP_VAR *slave, SCIP_Real mastersolval, DIRECTION masterdir, SCIP_Real slavesolval, DIRECTION slavedir, SCIP_Real shiftval, SCIP_Real *activities, int nrows, SCIP_Bool *feasible)
Definition: heur_twoopt.c:153
#define DEFAULT_INTOPT
Definition: heur_twoopt.c:67
#define HEUR_FREQ
Definition: heur_twoopt.c:59
static SCIP_RETCODE innerPresolve(SCIP *scip, SCIP_VAR **vars, SCIP_VAR ***varspointer, int nvars, int *nblocks, int *maxblocksize, int *nblockvars, int **blockstart, int **blockend, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur_twoopt.c:657
static SCIP_RETCODE optimize(SCIP *scip, SCIP_SOL *worksol, SCIP_VAR **vars, int *blockstart, int *blockend, int nblocks, OPTTYPE opttype, SCIP_Real *activities, int nrows, SCIP_Bool *improvement, SCIP_Bool *varboundserr, SCIP_HEURDATA *heurdata)
Definition: heur_twoopt.c:936
#define HEUR_USESSUBSCIP
Definition: heur_twoopt.c:64
Opttype
Definition: heur_twoopt.c:129
@ OPTTYPE_INTEGER
Definition: heur_twoopt.c:131
@ OPTTYPE_BINARY
Definition: heur_twoopt.c:130
static SCIP_RETCODE presolveTwoOpt(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur_twoopt.c:757
Primal heuristic to improve incumbent solution by flipping pairs of variables.
memory allocation routines
public methods for primal heuristics
public methods for LP management
public methods for message output
#define SCIPstatisticMessage
Definition: pub_message.h:123
#define SCIPdebug(x)
Definition: pub_message.h:93
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for primal CIP solutions
public methods for problem variables
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for random numbers
public methods for solutions
public methods for querying solving statistics
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:51