Scippy

SCIP

Solving Constraint Integer Programs

heur_shiftandpropagate.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_shiftandpropagate.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief shiftandpropagate primal heuristic
28 * @author Timo Berthold
29 * @author Gregor Hendel
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
36#include "scip/pub_event.h"
37#include "scip/pub_heur.h"
38#include "scip/pub_lp.h"
39#include "scip/pub_message.h"
40#include "scip/pub_misc.h"
41#include "scip/pub_misc_sort.h"
42#include "scip/pub_sol.h"
43#include "scip/pub_var.h"
44#include "scip/scip_event.h"
45#include "scip/scip_general.h"
46#include "scip/scip_heur.h"
47#include "scip/scip_lp.h"
48#include "scip/scip_mem.h"
49#include "scip/scip_message.h"
50#include "scip/scip_numerics.h"
51#include "scip/scip_param.h"
52#include "scip/scip_prob.h"
53#include "scip/scip_probing.h"
55#include "scip/scip_sol.h"
57#include "scip/scip_tree.h"
58#include "scip/scip_var.h"
59#include <string.h>
60
61#define HEUR_NAME "shiftandpropagate"
62#define HEUR_DESC "Pre-root heuristic to expand an auxiliary branch-and-bound tree and apply propagation techniques"
63#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP
64#define HEUR_PRIORITY 1000
65#define HEUR_FREQ 0
66#define HEUR_FREQOFS 0
67#define HEUR_MAXDEPTH -1
68#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
69#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
70
71#define DEFAULT_WEIGHT_INEQUALITY 1 /**< the heuristic row weight for inequalities */
72#define DEFAULT_WEIGHT_EQUALITY 3 /**< the heuristic row weight for equations */
73#define DEFAULT_RELAX TRUE /**< Should continuous variables be relaxed from the problem? */
74#define DEFAULT_PROBING TRUE /**< Is propagation of solution values enabled? */
75#define DEFAULT_ONLYWITHOUTSOL TRUE /**< Should heuristic only be executed if no primal solution was found, yet? */
76#define DEFAULT_NPROPROUNDS 10 /**< The default number of propagation rounds for each propagation used */
77#define DEFAULT_PROPBREAKER 65000 /**< fixed maximum number of propagations */
78#define DEFAULT_CUTOFFBREAKER 15 /**< fixed maximum number of allowed cutoffs before the heuristic stops */
79#define DEFAULT_RANDSEED 29 /**< the default random seed for random number generation */
80#define DEFAULT_SORTKEY 'v' /**< the default key for variable sorting */
81#define DEFAULT_SORTVARS TRUE /**< should variables be processed in sorted order? */
82#define DEFAULT_COLLECTSTATS TRUE /**< should variable statistics be collected during probing? */
83#define DEFAULT_STOPAFTERFEASIBLE TRUE /**< Should the heuristic stop calculating optimal shift values when no more rows are violated? */
84#define DEFAULT_PREFERBINARIES TRUE /**< Should binary variables be shifted first? */
85#define DEFAULT_SELECTBEST FALSE /**< should the heuristic choose the best candidate in every round? (set to FALSE for static order)? */
86#define DEFAULT_MAXCUTOFFQUOT 0.0 /**< maximum percentage of allowed cutoffs before stopping the heuristic */
87#define SORTKEYS "nrtuv"/**< options sorting key: (n)orms down, norms (u)p, (v)iolated rows decreasing,
88 * viola(t)ed rows increasing, or (r)andom */
89#define DEFAULT_NOZEROFIXING FALSE /**< should variables with a zero shifting value be delayed instead of being fixed? */
90#define DEFAULT_FIXBINLOCKS TRUE /**< should binary variables with no locks in one direction be fixed to that direction? */
91#define DEFAULT_BINLOCKSFIRST FALSE /**< should binary variables with no locks be preferred in the ordering? */
92#define DEFAULT_NORMALIZE TRUE /**< should coefficients and left/right hand sides be normalized by max row coeff? */
93#define DEFAULT_UPDATEWEIGHTS FALSE /**< should row weight be increased every time the row is violated? */
94#define DEFAULT_IMPLISCONTINUOUS TRUE /**< should implicit integer variables be treated as continuous variables? */
95#define DEFAULT_MINFIXINGRATELP 0.0 /**< minimum fixing rate over all variables (including continuous) to solve LP */
96
97#define EVENTHDLR_NAME "eventhdlrshiftandpropagate"
98#define EVENTHDLR_DESC "event handler to catch bound changes"
99#define EVENTTYPE_SHIFTANDPROPAGATE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED)
100
101
102/*
103 * Data structures
104 */
105
106/** primal heuristic data */
107struct SCIP_HeurData
108{
109 SCIP_COL** lpcols; /**< stores lp columns with discrete variables before cont. variables */
110 SCIP_RANDNUMGEN* randnumgen; /**< random number generation */
111 int* rowweights; /**< row weight storage */
112 SCIP_Bool relax; /**< should continuous variables be relaxed from the problem */
113 SCIP_Bool probing; /**< should probing be executed? */
114 SCIP_Bool onlywithoutsol; /**< Should heuristic only be executed if no primal solution was found, yet? */
115 int nlpcols; /**< the number of lp columns */
116 int nproprounds; /**< The default number of propagation rounds for each propagation used */
117 int cutoffbreaker; /**< the number of cutoffs before heuristic execution is stopped, or -1 for no
118 * limit */
119 SCIP_EVENTHDLR* eventhdlr; /**< event handler to register and process variable bound changes */
120
121 SCIP_Real maxcutoffquot; /**< maximum percentage of allowed cutoffs before stopping the heuristic */
122 SCIP_Real minfixingratelp; /**< minimum fixing rate over all variables (including continuous) to solve LP */
123 char sortkey; /**< the key by which variables are sorted */
124 SCIP_Bool sortvars; /**< should variables be processed in sorted order? */
125 SCIP_Bool collectstats; /**< should variable statistics be collected during probing? */
126 SCIP_Bool stopafterfeasible; /**< Should the heuristic stop calculating optimal shift values when no
127 * more rows are violated? */
128 SCIP_Bool preferbinaries; /**< Should binary variables be shifted first? */
129 SCIP_Bool nozerofixing; /**< should variables with a zero shifting value be delayed instead of being fixed? */
130 SCIP_Bool fixbinlocks; /**< should binary variables with no locks in one direction be fixed to that direction? */
131 SCIP_Bool binlocksfirst; /**< should binary variables with no locks be preferred in the ordering? */
132 SCIP_Bool normalize; /**< should coefficients be normalized by max row coeff for col norm? */
133 SCIP_Bool updateweights; /**< should row weight be increased every time the row is violated? */
134 SCIP_Bool impliscontinuous; /**< should implicit integer variables be treated as continuous variables? */
135 SCIP_Bool selectbest; /**< should the heuristic choose the best candidate in every round? (set to FALSE for static order)? */
137 SCIP_LPSOLSTAT lpsolstat; /**< the probing status after probing */
138 SCIP_Longint ntotaldomredsfound; /**< the total number of domain reductions during heuristic */
139 SCIP_Longint nlpiters; /**< number of LP iterations which the heuristic needed */
140 int nremainingviols; /**< the number of remaining violations */
141 int nprobings; /**< how many probings has the heuristic executed? */
142 int ncutoffs; /**< has the probing node been cutoff? */
143 )
144};
145
146/** status of a variable in heuristic transformation */
148{
149 TRANSFORMSTATUS_NONE = 0, /**< variable has not been transformed yet */
150 TRANSFORMSTATUS_LB = 1, /**< variable has been shifted by using lower bound (x-lb) */
151 TRANSFORMSTATUS_NEG = 2, /**< variable has been negated by using upper bound (ub-x) */
152 TRANSFORMSTATUS_FREE = 3 /**< variable does not have to be shifted */
155
156/** information about the matrix after its heuristic transformation */
157struct ConstraintMatrix
158{
159 SCIP_Real* rowmatvals; /**< matrix coefficients row by row */
160 int* rowmatind; /**< the indices of the corresponding variables */
161 int* rowmatbegin; /**< the starting indices of each row */
162 SCIP_Real* colmatvals; /**< matrix coefficients column by column */
163 int* colmatind; /**< the indices of the corresponding rows for each coefficient */
164 int* colmatbegin; /**< the starting indices of each column */
165 int* violrows; /**< the number of violated rows for every variable */
166 TRANSFORMSTATUS* transformstatus; /**< information about transform status of every discrete variable */
167 SCIP_Real* lhs; /**< left hand side vector after normalization */
168 SCIP_Real* rhs; /**< right hand side vector after normalization */
169 SCIP_Real* colnorms; /**< vector norms of all discrete problem variables after normalization */
170 SCIP_Real* upperbounds; /**< the upper bounds of every non-continuous variable after transformation*/
171 SCIP_Real* transformshiftvals; /**< values by which original discrete variable bounds were shifted */
172 int nnonzs; /**< number of nonzero column entries */
173 int nrows; /**< number of rows of matrix */
174 int ncols; /**< the number of columns in matrix (including continuous vars) */
175 int ndiscvars; /**< number of discrete problem variables */
176 SCIP_Bool normalized; /**< indicates if the matrix data has already been normalized */
177};
178typedef struct ConstraintMatrix CONSTRAINTMATRIX;
179
180struct SCIP_EventhdlrData
181{
182 CONSTRAINTMATRIX* matrix; /**< the constraint matrix of the heuristic */
183 SCIP_HEURDATA* heurdata; /**< heuristic data */
184 int* violatedrows; /**< all currently violated LP rows */
185 int* violatedrowpos; /**< position in violatedrows array for every row */
186 int* nviolatedrows; /**< pointer to the total number of currently violated rows */
187};
188
189struct SCIP_EventData
190{
191 int colpos; /**< column position of the event-related variable */
192};
193/*
194 * Local methods
195 */
196
197/** returns whether a given variable is counted as discrete, depending on the parameter impliscontinuous */
198static
200 SCIP_VAR* var, /**< variable to check for discreteness */
201 SCIP_Bool impliscontinuous /**< should implicit integer variables be counted as continuous? */
202 )
203{
204 return SCIPvarIsIntegral(var) && (SCIPvarGetType(var) != SCIP_VARTYPE_IMPLINT || !impliscontinuous);
205}
206
207/** returns whether a given column is counted as discrete, depending on the parameter impliscontinuous */
208static
210 SCIP_COL* col, /**< column to check for discreteness */
211 SCIP_Bool impliscontinuous /**< should implicit integer variables be counted as continuous? */
212 )
213{
214 return SCIPcolIsIntegral(col) && (!impliscontinuous || SCIPvarGetType(SCIPcolGetVar(col)) != SCIP_VARTYPE_IMPLINT);
215}
216
217/** returns nonzero values and corresponding columns of given row */
218static
220 CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
221 int rowindex, /**< index of the desired row */
222 SCIP_Real** valpointer, /**< pointer to store the nonzero coefficients of the row */
223 SCIP_Real* lhs, /**< lhs of the row */
224 SCIP_Real* rhs, /**< rhs of the row */
225 int** indexpointer, /**< pointer to store column indices which belong to the nonzeros */
226 int* nrowvals /**< pointer to store number of nonzeros in the desired row (or NULL) */
227 )
228{
229 int arrayposition;
230
231 assert(matrix != NULL);
232 assert(0 <= rowindex && rowindex < matrix->nrows);
233
234 arrayposition = matrix->rowmatbegin[rowindex];
235
236 if ( nrowvals != NULL )
237 {
238 if( rowindex == matrix->nrows - 1 )
239 *nrowvals = matrix->nnonzs - arrayposition;
240 else
241 *nrowvals = matrix->rowmatbegin[rowindex + 1] - arrayposition; /*lint !e679*/
242 }
243
244 if( valpointer != NULL )
245 *valpointer = &(matrix->rowmatvals[arrayposition]);
246 if( indexpointer != NULL )
247 *indexpointer = &(matrix->rowmatind[arrayposition]);
248
249 if( lhs != NULL )
250 *lhs = matrix->lhs[rowindex];
251
252 if( rhs != NULL )
253 *rhs = matrix->rhs[rowindex];
254}
255
256/** returns nonzero values and corresponding rows of given column */
257static
259 CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
260 int colindex, /**< the index of the desired column */
261 SCIP_Real** valpointer, /**< pointer to store the nonzero coefficients of the column */
262 int** indexpointer, /**< pointer to store row indices which belong to the nonzeros */
263 int* ncolvals /**< pointer to store number of nonzeros in the desired column */
264 )
265{
266 int arrayposition;
267
268 assert(matrix != NULL);
269 assert(0 <= colindex && colindex < matrix->ncols);
270
271 arrayposition = matrix->colmatbegin[colindex];
272
273 if( ncolvals != NULL )
274 {
275 if( colindex == matrix->ncols - 1 )
276 *ncolvals = matrix->nnonzs - arrayposition;
277 else
278 *ncolvals = matrix->colmatbegin[colindex + 1] - arrayposition; /*lint !e679*/
279 }
280 if( valpointer != NULL )
281 *valpointer = &(matrix->colmatvals[arrayposition]);
282
283 if( indexpointer != NULL )
284 *indexpointer = &(matrix->colmatind[arrayposition]);
285}
286
287/** relaxes a continuous variable from all its rows, which has influence
288 * on both the left and right hand side of the constraint.
289 */
290static
292 SCIP* scip, /**< current scip instance */
293 SCIP_VAR* var, /**< variable which is relaxed from the problem */
294 CONSTRAINTMATRIX* matrix /**< constraint matrix object */
295 )
296{
297 SCIP_ROW** colrows;
298 SCIP_COL* varcol;
299 SCIP_Real* colvals;
300 SCIP_Real ub;
301 SCIP_Real lb;
302 int ncolvals;
303 int r;
304
305 assert(var != NULL);
307
308 varcol = SCIPvarGetCol(var);
309 assert(varcol != NULL);
310
311 /* get nonzero values and corresponding rows of variable */
312 colvals = SCIPcolGetVals(varcol);
313 ncolvals = SCIPcolGetNLPNonz(varcol);
314 colrows = SCIPcolGetRows(varcol);
315
316 ub = SCIPvarGetUbGlobal(var);
317 lb = SCIPvarGetLbGlobal(var);
318
319 assert(colvals != NULL || ncolvals == 0);
320
321 SCIPdebugMsg(scip, "Relaxing variable <%s> with lb <%g> and ub <%g>\n",
322 SCIPvarGetName(var), lb, ub);
323
324 assert(matrix->normalized);
325 /* relax variable from all its constraints */
326 for( r = 0; r < ncolvals; ++r )
327 {
328 SCIP_ROW* colrow;
329 SCIP_Real lhs;
330 SCIP_Real rhs;
331 SCIP_Real lhsvarbound;
332 SCIP_Real rhsvarbound;
333 SCIP_Real colval;
334 int rowindex;
335
336 colrow = colrows[r];
337 rowindex = SCIProwGetLPPos(colrow);
338
339 if( rowindex == -1 )
340 break;
341
342 assert(colvals != NULL); /* to please flexelint */
343 colval = colvals[r];
344
345 assert(0 <= rowindex && rowindex < matrix->nrows);
346 getRowData(matrix, rowindex, NULL, &lhs, &rhs, NULL, NULL);
347 /* variables bound influence the lhs and rhs of current row depending on the sign
348 * of the variables coefficient.
349 */
350 if( SCIPisFeasPositive(scip, colval) )
351 {
352 lhsvarbound = ub;
353 rhsvarbound = lb;
354 }
355 else if( SCIPisFeasNegative(scip, colval) )
356 {
357 lhsvarbound = lb;
358 rhsvarbound = ub;
359 }
360 else
361 continue;
362
363 /* relax variable from the current row */
364 if( !SCIPisInfinity(scip, -matrix->lhs[rowindex]) && !SCIPisInfinity(scip, ABS(lhsvarbound)) )
365 matrix->lhs[rowindex] -= colval * lhsvarbound;
366 else
367 matrix->lhs[rowindex] = -SCIPinfinity(scip);
368
369 if( !SCIPisInfinity(scip, matrix->rhs[rowindex]) && !SCIPisInfinity(scip, ABS(rhsvarbound)) )
370 matrix->rhs[rowindex] -= colval * rhsvarbound;
371 else
372 matrix->rhs[rowindex] = SCIPinfinity(scip);
373
374 SCIPdebugMsg(scip, "Row <%s> changed:Coefficient <%g>, LHS <%g> --> <%g>, RHS <%g> --> <%g>\n",
375 SCIProwGetName(colrow), colval, lhs, matrix->lhs[rowindex], rhs, matrix->rhs[rowindex]);
376 } /*lint !e438*/
377}
378
379/** transforms bounds of a given variable s.t. its lower bound equals zero afterwards.
380 * If the variable already has lower bound zero, the variable is not transformed,
381 * if not, the variable's bounds are changed w.r.t. the smaller absolute value of its
382 * bounds in order to avoid numerical inaccuracies. If both lower and upper bound
383 * of the variable differ from infinity, there are two cases. If |lb| <= |ub|,
384 * the bounds are shifted by -lb, else a new variable ub - x replaces x.
385 * The transformation is memorized by the transform status of the variable s.t.
386 * retransformation is possible.
387 */
388static
390 SCIP* scip, /**< current scip instance */
391 CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
392 SCIP_HEURDATA* heurdata, /**< heuristic data */
393 int colpos /**< position of variable column in matrix */
394 )
395{
396 SCIP_COL* col;
397 SCIP_VAR* var;
398 SCIP_Real lb;
399 SCIP_Real ub;
400
401 SCIP_Bool negatecoeffs; /* do the row coefficients need to be negated? */
402 SCIP_Real deltashift; /* difference from previous transformation */
403
404 assert(matrix != NULL);
405 assert(0 <= colpos && colpos < heurdata->nlpcols);
406 col = heurdata->lpcols[colpos];
407 assert(col != NULL);
408 assert(SCIPcolIsInLP(col));
409
410 var = SCIPcolGetVar(col);
411 assert(var != NULL);
412 assert(SCIPvarIsIntegral(var));
413 lb = SCIPvarGetLbLocal(var);
414 ub = SCIPvarGetUbLocal(var);
415
416 negatecoeffs = FALSE;
417 /* if both lower and upper bound are -infinity and infinity, resp., this is reflected by a free transform status.
418 * If the lower bound is already zero, this is reflected by identity transform status. In both cases, none of the
419 * corresponding rows needs to be modified.
420 */
421 if( SCIPisInfinity(scip, -lb) && SCIPisInfinity(scip, ub) )
422 {
423 if( matrix->transformstatus[colpos] == TRANSFORMSTATUS_NEG )
424 negatecoeffs = TRUE;
425
426 deltashift = matrix->transformshiftvals[colpos];
427 matrix->transformshiftvals[colpos] = 0.0;
428 matrix->transformstatus[colpos] = TRANSFORMSTATUS_FREE;
429 }
430 else if( SCIPisLE(scip, REALABS(lb), REALABS(ub)) )
431 {
432 assert(!SCIPisInfinity(scip, REALABS(lb)));
433
434 matrix->transformstatus[colpos] = TRANSFORMSTATUS_LB;
435 deltashift = lb;
436 matrix->transformshiftvals[colpos] = lb;
437 }
438 else
439 {
440 assert(!SCIPisInfinity(scip, ub));
441 if( matrix->transformstatus[colpos] != TRANSFORMSTATUS_NEG )
442 negatecoeffs = TRUE;
443 matrix->transformstatus[colpos] = TRANSFORMSTATUS_NEG;
444 deltashift = ub;
445 matrix->transformshiftvals[colpos] = ub;
446 }
447
448 /* determine the upper bound for this variable in heuristic transformation (lower bound is implicit; always 0) */
449 if( !SCIPisInfinity(scip, ub) && !SCIPisInfinity(scip, lb) )
450 matrix->upperbounds[colpos] = MIN(ub - lb, SCIPinfinity(scip)); /*lint !e666*/
451 else
452 matrix->upperbounds[colpos] = SCIPinfinity(scip);
453
454 /* a real transformation is necessary. The variable x is either shifted by -lb or
455 * replaced by ub - x, depending on the smaller absolute of lb and ub.
456 */
457 if( !SCIPisFeasZero(scip, deltashift) || negatecoeffs )
458 {
459 SCIP_Real* vals;
460 int* rows;
461 int nrows;
462 int i;
463
464 assert(!SCIPisInfinity(scip, deltashift));
465
466 /* get nonzero values and corresponding rows of column */
467 getColumnData(matrix, colpos, &vals, &rows, &nrows);
468 assert(nrows == 0 ||(vals != NULL && rows != NULL));
469
470 /* go through rows and modify its lhs, rhs and the variable coefficient, if necessary */
471 for( i = 0; i < nrows; ++i )
472 {
473 int rowpos = rows[i];
474 assert(rowpos >= 0);
475 assert(rowpos < matrix->nrows);
476
477 if( !SCIPisInfinity(scip, -(matrix->lhs[rowpos])) )
478 matrix->lhs[rowpos] -= (vals[i]) * deltashift;
479
480 if( !SCIPisInfinity(scip, matrix->rhs[rowpos]) )
481 matrix->rhs[rowpos] -= (vals[i]) * deltashift;
482
483 if( negatecoeffs )
484 (vals[i]) = -(vals[i]);
485
486 assert(SCIPisFeasLE(scip, matrix->lhs[rowpos], matrix->rhs[rowpos]));
487 }
488 }
489 SCIPdebugMsg(scip, "Variable <%s> at colpos %d transformed. Status %d LB <%g> --> <%g>, UB <%g> --> <%g>\n",
490 SCIPvarGetName(var), colpos, matrix->transformstatus[colpos], lb, 0.0, ub, matrix->upperbounds[colpos]);
491}
492
493/** initializes copy of the original coefficient matrix and applies heuristic specific adjustments: normalizing row
494 * vectors, transforming variable domains such that lower bound is zero, and relaxing continuous variables.
495 */
496static
498 SCIP* scip, /**< current scip instance */
499 CONSTRAINTMATRIX* matrix, /**< constraint matrix object to be initialized */
500 SCIP_HEURDATA* heurdata, /**< heuristic data */
501 int* colposs, /**< position of columns according to variable type sorting */
502 int* nmaxrows, /**< maximum number of rows a variable appears in */
503 SCIP_Bool relax, /**< should continuous variables be relaxed from the problem? */
504 SCIP_Bool* initialized, /**< was the initialization successful? */
505 SCIP_Bool* infeasible /**< is the problem infeasible? */
506 )
507{
508 SCIP_ROW** lprows;
509 SCIP_COL** lpcols;
510 SCIP_Bool impliscontinuous;
511 int i;
512 int j;
513 int currentpointer;
514
515 int nrows;
516 int ncols;
517
518 assert(scip != NULL);
519 assert(matrix != NULL);
520 assert(initialized!= NULL);
521 assert(infeasible != NULL);
522 assert(nmaxrows != NULL);
523
524 SCIPdebugMsg(scip, "entering Matrix Initialization method of SHIFTANDPROPAGATE heuristic!\n");
525
526 /* get LP row data; column data is already initialized in heurdata */
527 SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nrows) );
528 lpcols = heurdata->lpcols;
529 ncols = heurdata->nlpcols;
530
531 matrix->nrows = nrows;
532 matrix->nnonzs = 0;
533 matrix->normalized = FALSE;
534 matrix->ndiscvars = 0;
535 *nmaxrows = 0;
536 impliscontinuous = heurdata->impliscontinuous;
537
538 /* count the number of nonzeros of the LP constraint matrix */
539 for( j = 0; j < ncols; ++j )
540 {
541 assert(lpcols[j] != NULL);
542 assert(SCIPcolGetLPPos(lpcols[j]) >= 0);
543
544 if( colIsDiscrete(lpcols[j], impliscontinuous) )
545 {
546 matrix->nnonzs += SCIPcolGetNLPNonz(lpcols[j]);
547 ++matrix->ndiscvars;
548 }
549 }
550
551 matrix->ncols = matrix->ndiscvars;
552
553 if( matrix->nnonzs == 0 )
554 {
555 SCIPdebugMsg(scip, "No matrix entries - Terminating initialization of matrix.\n");
556
557 *initialized = FALSE;
558
559 return SCIP_OKAY;
560 }
561
562 /* allocate memory for the members of heuristic matrix */
563 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatvals, matrix->nnonzs) );
564 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatind, matrix->nnonzs) );
565 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatvals, matrix->nnonzs) );
566 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatind, matrix->nnonzs) );
567 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatbegin, matrix->nrows) );
568 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatbegin, matrix->ncols) );
569 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->lhs, matrix->nrows) );
570 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rhs, matrix->nrows) );
571 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colnorms, matrix->ncols) );
572 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->violrows, matrix->ncols) );
573 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->transformstatus, matrix->ndiscvars) );
574 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->upperbounds, matrix->ndiscvars) );
575 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->transformshiftvals, matrix->ndiscvars) );
576
577 /* set transform status of variables */
578 for( j = 0; j < matrix->ndiscvars; ++j )
579 matrix->transformstatus[j] = TRANSFORMSTATUS_NONE;
580
581 currentpointer = 0;
582 *infeasible = FALSE;
583
584 /* initialize the rows vector of the heuristic matrix together with its corresponding
585 * lhs, rhs.
586 */
587 for( i = 0; i < nrows; ++i )
588 {
589 SCIP_COL** cols;
590 SCIP_ROW* row;
591 SCIP_Real* rowvals;
592 SCIP_Real constant;
593 int nrowlpnonz;
594
595 /* get LP row information */
596 row = lprows[i];
597 rowvals = SCIProwGetVals(row);
598 nrowlpnonz = SCIProwGetNLPNonz(row);
599 cols = SCIProwGetCols(row);
600 constant = SCIProwGetConstant(row);
601
603 assert(!SCIPisInfinity(scip, constant));
604
605 matrix->rowmatbegin[i] = currentpointer;
606
607 /* modify the lhs and rhs w.r.t to the rows constant */
608 if( !SCIPisInfinity(scip, -SCIProwGetLhs(row)) )
609 matrix->lhs[i] = SCIProwGetLhs(row) - constant;
610 else
611 matrix->lhs[i] = -SCIPinfinity(scip);
612
613 if( !SCIPisInfinity(scip, SCIProwGetRhs(row)) )
614 matrix->rhs[i] = SCIProwGetRhs(row) - constant;
615 else
616 matrix->rhs[i] = SCIPinfinity(scip);
617
618 /* in case of empty rows with a 0 < lhs <= 0.0 or 0.0 <= rhs < 0 we deduce the infeasibility of the problem */
619 if( nrowlpnonz == 0 && (SCIPisFeasPositive(scip, matrix->lhs[i]) || SCIPisFeasNegative(scip, matrix->rhs[i])) )
620 {
621 *infeasible = TRUE;
622 SCIPdebugMsg(scip, " Matrix initialization stopped because of row infeasibility! \n");
623 break;
624 }
625
626 /* row coefficients are normalized and copied to heuristic matrix */
627 for( j = 0; j < nrowlpnonz; ++j )
628 {
629 if( !colIsDiscrete(cols[j], impliscontinuous) )
630 continue;
631 assert(SCIPcolGetLPPos(cols[j]) >= 0);
632 assert(currentpointer < matrix->nnonzs);
633
634 matrix->rowmatvals[currentpointer] = rowvals[j];
635 matrix->rowmatind[currentpointer] = colposs[SCIPcolGetLPPos(cols[j])];
636
637 ++currentpointer;
638 }
639 }
640
641 matrix->normalized = TRUE;
642
643 if( *infeasible )
644 return SCIP_OKAY;
645
646 assert(currentpointer == matrix->nnonzs);
647
648 currentpointer = 0;
649
650 /* copy the nonzero coefficient data column by column to heuristic matrix */
651 for( j = 0; j < matrix->ncols; ++j )
652 {
653 SCIP_COL* currentcol;
654 SCIP_ROW** rows;
655 SCIP_Real* colvals;
656 int ncolnonz;
657
658 assert(SCIPcolGetLPPos(lpcols[j]) >= 0);
659
660 currentcol = lpcols[j];
661 assert(colIsDiscrete(currentcol, impliscontinuous));
662
663 colvals = SCIPcolGetVals(currentcol);
664 rows = SCIPcolGetRows(currentcol);
665 ncolnonz = SCIPcolGetNLPNonz(currentcol);
666 matrix->colnorms[j] = ncolnonz;
667
668 *nmaxrows = MAX(*nmaxrows, ncolnonz);
669
670 /* loop over all rows with nonzero coefficients in the column, transform them and add them to the heuristic matrix */
671 matrix->colmatbegin[j] = currentpointer;
672
673 for( i = 0; i < ncolnonz; ++i )
674 {
675 SCIP_Real normval = colvals[i];
676
677 assert(rows[i] != NULL);
678 assert(0 <= SCIProwGetLPPos(rows[i]));
679 assert(SCIProwGetLPPos(rows[i]) < nrows);
680 assert(currentpointer < matrix->nnonzs);
681 matrix->colmatvals[currentpointer] = colvals[i];
682 matrix->colmatind[currentpointer] = SCIProwGetLPPos(rows[i]);
683
684 if( heurdata->normalize )
685 normval /= SCIPgetRowMaxCoef(scip, rows[i]);
686
687 /* update the column norm for maximum normalized rows */
688 matrix->colnorms[j] += ABS(normval);
689 ++currentpointer;
690 }
691 }
692 assert(currentpointer == matrix->nnonzs);
693
694 /* each variable is either transformed, if it supposed to be integral, or relaxed */
695 for( j = 0; j < (relax ? ncols : matrix->ndiscvars); ++j )
696 {
697 SCIP_COL* col;
698
699 col = lpcols[j];
700 if( colIsDiscrete(col, impliscontinuous) )
701 {
702 matrix->transformshiftvals[j] = 0.0;
703 transformVariable(scip, matrix, heurdata, j);
704 }
705 else
706 {
707 SCIP_VAR* var;
708 var = SCIPcolGetVar(col);
709 assert(!varIsDiscrete(var, impliscontinuous));
710 relaxVar(scip, var, matrix);
711 }
712 }
713 *initialized = TRUE;
714
715 SCIPdebugMsg(scip, "Matrix initialized for %d discrete variables with %d cols, %d rows and %d nonzero entries\n",
716 matrix->ndiscvars, matrix->ncols, matrix->nrows, matrix->nnonzs);
717 return SCIP_OKAY;
718}
719
720/** frees all members of the heuristic matrix */
721static
723 SCIP* scip, /**< current SCIP instance */
724 CONSTRAINTMATRIX** matrix /**< constraint matrix object */
725 )
726{
727 assert(scip != NULL);
728 assert(matrix != NULL);
729
730 /* all fields are only allocated, if problem is not empty */
731 if( (*matrix)->nnonzs > 0 )
732 {
733 assert((*matrix) != NULL);
734 assert((*matrix)->rowmatbegin != NULL);
735 assert((*matrix)->rowmatvals != NULL);
736 assert((*matrix)->rowmatind != NULL);
737 assert((*matrix)->colmatbegin != NULL);
738 assert((*matrix)->colmatvals!= NULL);
739 assert((*matrix)->colmatind != NULL);
740 assert((*matrix)->lhs != NULL);
741 assert((*matrix)->rhs != NULL);
742 assert((*matrix)->transformstatus != NULL);
743 assert((*matrix)->transformshiftvals != NULL);
744
745 /* free all fields */
746 SCIPfreeBufferArray(scip, &((*matrix)->transformshiftvals));
747 SCIPfreeBufferArray(scip, &((*matrix)->upperbounds));
748 SCIPfreeBufferArray(scip, &((*matrix)->transformstatus));
749 SCIPfreeBufferArray(scip, &((*matrix)->violrows));
750 SCIPfreeBufferArray(scip, &((*matrix)->colnorms));
751 SCIPfreeBufferArray(scip, &((*matrix)->rhs));
752 SCIPfreeBufferArray(scip, &((*matrix)->lhs));
753 SCIPfreeBufferArray(scip, &((*matrix)->colmatbegin));
754 SCIPfreeBufferArray(scip, &((*matrix)->rowmatbegin));
755 SCIPfreeBufferArray(scip, &((*matrix)->colmatind));
756 SCIPfreeBufferArray(scip, &((*matrix)->colmatvals));
757 SCIPfreeBufferArray(scip, &((*matrix)->rowmatind));
758 SCIPfreeBufferArray(scip, &((*matrix)->rowmatvals));
759
760 (*matrix)->nrows = 0;
761 (*matrix)->ncols = 0;
762 }
763
764 /* free matrix */
765 SCIPfreeBuffer(scip, matrix);
766}
767
768/** updates the information about a row whenever violation status changes */
769static
771 SCIP* scip, /**< current SCIP instance */
772 CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
773 int rowindex, /**< index of the row */
774 int* violatedrows, /**< contains all violated rows */
775 int* violatedrowpos, /**< positions of rows in the violatedrows array */
776 int* nviolatedrows, /**< pointer to update total number of violated rows */
777 int* rowweights, /**< row weight storage */
778 SCIP_Bool updateweights /**< should row weight be increased every time the row is violated? */
779 )
780{
781 int* cols;
782 int ncols;
783 int c;
784 int violadd;
785 assert(matrix != NULL);
786 assert(violatedrows != NULL);
787 assert(violatedrowpos != NULL);
788 assert(nviolatedrows != NULL);
789
790 getRowData(matrix, rowindex, NULL, NULL, NULL, &cols, &ncols);
791 violadd = 0;
792
793 /* row is now violated. Enqueue it in the set of violated rows. */
794 if( violatedrowpos[rowindex] == -1 && (SCIPisFeasGT(scip, matrix->lhs[rowindex], 0.0) || SCIPisFeasLT(scip, matrix->rhs[rowindex], 0.0)) )
795 {
796 assert(*nviolatedrows < matrix->nrows);
797
798 violatedrows[*nviolatedrows] = rowindex;
799 violatedrowpos[rowindex] = *nviolatedrows;
800 ++(*nviolatedrows);
801 if( updateweights )
802 ++rowweights[rowindex];
803
804 violadd = 1;
805 }
806 /* row is now feasible. Remove it from the set of violated rows. */
807 else if( violatedrowpos[rowindex] >= 0 && SCIPisFeasLE(scip, matrix->lhs[rowindex], 0.0) && SCIPisFeasGE(scip, matrix->rhs[rowindex], 0.0) )
808 {
809 /* swap the row with last violated row */
810 if( violatedrowpos[rowindex] != *nviolatedrows - 1 )
811 {
812 assert(*nviolatedrows - 1 >= 0);
813 violatedrows[violatedrowpos[rowindex]] = violatedrows[*nviolatedrows - 1];
814 violatedrowpos[violatedrows[*nviolatedrows - 1]] = violatedrowpos[rowindex];
815 }
816
817 /* unlink the row from its position in the array and decrease number of violated rows */
818 violatedrowpos[rowindex] = -1;
819 --(*nviolatedrows);
820 violadd = -1;
821 }
822
823 /* increase or decrease the column violation counter */
824 for( c = 0; c < ncols; ++c )
825 {
826 matrix->violrows[cols[c]] += violadd;
827 assert(matrix->violrows[cols[c]] >= 0);
828 }
829}
830
831/** collects the necessary information about row violations for the zero-solution. That is,
832 * all solution values in heuristic transformation are zero.
833 */
834static
836 SCIP* scip, /**< current scip instance */
837 CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
838 int colidx, /**< column index for specific column, or -1 for all rows */
839 int* violatedrows, /**< violated rows */
840 int* violatedrowpos, /**< row positions of violated rows */
841 int* nviolatedrows, /**< pointer to store the number of violated rows */
842 int* rowweights, /**< weight array for every row */
843 SCIP_Bool updateweights /**< should row weight be increased every time the row is violated? */
844 )
845{
846 int nrows;
847 int* rowindices;
848 int i;
849
850 assert(matrix != NULL);
851 assert(violatedrows != NULL);
852 assert(violatedrowpos != NULL);
853 assert(nviolatedrows != NULL);
854 assert(-1 <= colidx && colidx < matrix->ncols);
855
856 /* check if we requested an update for a single variable, or if we want to (re)-initialize the whole violation info */
857 if( colidx >= 0 )
858 getColumnData(matrix, colidx, NULL, &rowindices, &nrows);
859 else
860 {
861 nrows = matrix->nrows;
862 rowindices = NULL;
863 *nviolatedrows = 0;
864
865 /* reinitialize the violated rows */
866 for( i = 0; i < nrows; ++i )
867 violatedrowpos[i] = -1;
868
869 /* clear the violated row counters for all variables */
870 BMSclearMemoryArray(matrix->violrows, matrix->ndiscvars);
871 }
872
873 assert(colidx < 0 || *nviolatedrows >= 0);
874 SCIPdebugMsg(scip, "Entering violation check for %d rows! \n", nrows);
875 /* loop over rows and check if it is violated */
876 for( i = 0; i < nrows; ++i )
877 {
878 int rowpos;
879 if( colidx >= 0 )
880 {
881 assert(rowindices != NULL);
882 rowpos = rowindices[i];
883 }
884 else
885 rowpos = i;
886 /* check, if zero solution violates this row */
887 checkRowViolation(scip, matrix, rowpos, violatedrows, violatedrowpos, nviolatedrows, rowweights, updateweights);
888
889 assert((violatedrowpos[rowpos] == -1 && SCIPisFeasGE(scip, matrix->rhs[rowpos], 0.0) && SCIPisFeasLE(scip, matrix->lhs[rowpos], 0.0))
890 || (violatedrowpos[rowpos] >= 0 &&(SCIPisFeasLT(scip, matrix->rhs[rowpos], 0.0) || SCIPisFeasGT(scip, matrix->lhs[rowpos], 0.0))));
891 }
892}
893
894/** retransforms solution values of variables according to their transformation status */
895static
897 SCIP* scip, /**< current scip instance */
898 CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
899 SCIP_VAR* var, /**< variable whose solution value has to be retransformed */
900 int varindex, /**< permutation of variable indices according to sorting */
901 SCIP_Real solvalue /**< solution value of the variable */
902 )
903{
904 TRANSFORMSTATUS status;
905
906 assert(matrix != NULL);
907 assert(var != NULL);
908
909 status = matrix->transformstatus[varindex];
910 assert(status != TRANSFORMSTATUS_NONE);
911
912 /* check if original variable has different bounds and transform solution value correspondingly */
913 if( status == TRANSFORMSTATUS_LB )
914 {
915 assert(!SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)));
916
917 return solvalue + matrix->transformshiftvals[varindex];
918 }
919 else if( status == TRANSFORMSTATUS_NEG )
920 {
921 assert(!SCIPisInfinity(scip, SCIPvarGetUbLocal(var)));
922 return matrix->transformshiftvals[varindex] - solvalue;
923 }
924 return solvalue;
925}
926
927/** determines the best shifting value of a variable
928 * @todo if there is already an incumbent solution, try considering the objective cutoff as additional constraint */
929static
931 SCIP* scip, /**< current scip instance */
932 CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
933 int varindex, /**< index of variable which should be shifted */
934 int direction, /**< the direction for this variable */
935 int* rowweights, /**< weighting of rows for best shift calculation */
936 SCIP_Real* steps, /**< buffer array to store the individual steps for individual rows */
937 int* violationchange, /**< buffer array to store the individual change of feasibility of row */
938 SCIP_Real* beststep, /**< pointer to store optimal shifting step */
939 int* rowviolations /**< pointer to store new weighted sum of row violations, i.e, v - f */
940 )
941{
942 SCIP_Real* vals;
943 int* rows;
944
945 SCIP_Real slacksurplus;
946 SCIP_Real upperbound;
947
948 int nrows;
949 int sum;
950 int i;
951
952 SCIP_Bool allzero;
953
954 assert(beststep != NULL);
955 assert(rowviolations != NULL);
956 assert(rowweights != NULL);
957 assert(steps != NULL);
958 assert(violationchange != NULL);
959 assert(direction == 1 || direction == -1);
960
961 upperbound = matrix->upperbounds[varindex];
962
963 /* get nonzero values and corresponding rows of variable */
964 getColumnData(matrix, varindex, &vals, &rows, &nrows);
965
966 /* loop over rows and calculate, which is the minimum shift to make this row feasible
967 * or the minimum shift to violate this row
968 */
969 allzero = TRUE;
970 slacksurplus = 0.0;
971 for( i = 0; i < nrows; ++i )
972 {
973 SCIP_Real lhs;
974 SCIP_Real rhs;
975 SCIP_Real val;
976 int rowpos;
977 SCIP_Bool rowisviolated;
978 int rowweight;
979
980 /* get the row data */
981 rowpos = rows[i];
982 assert(rowpos >= 0);
983 lhs = matrix->lhs[rowpos];
984 rhs = matrix->rhs[rowpos];
985 rowweight = rowweights[rowpos];
986 val = direction * vals[i];
987 assert(!SCIPisZero(scip, val));
988
989 /* determine if current row is violated or not */
990 rowisviolated = (SCIPisFeasLT(scip, rhs, 0.0) || SCIPisFeasLT(scip, -lhs, 0.0));
991
992 /* for a feasible row, determine the minimum integer value within the bounds of the variable by which it has to be
993 * shifted to make row infeasible.
994 */
995 if( !rowisviolated )
996 {
997 SCIP_Real maxfeasshift;
998
999 maxfeasshift = SCIPinfinity(scip);
1000
1001 /* feasibility can only be violated if the variable has a lock in the corresponding direction,
1002 * i.e. a positive coefficient for a "<="-constraint, a negative coefficient for a ">="-constraint.
1003 * if the variable has no lock in the current row, it can still help to increase the slack of this row;
1004 * we measure slack increase for shifting by one
1005 */
1006 if( val < 0.0 )
1007 {
1008 if( !SCIPisInfinity(scip, -lhs) )
1009 maxfeasshift = SCIPfeasFloor(scip, MIN(lhs, 0.0) / val);
1010 else
1011 slacksurplus -= val;
1012 }
1013 else
1014 {
1015 if( !SCIPisInfinity(scip, rhs) )
1016 maxfeasshift = SCIPfeasFloor(scip, MAX(rhs, 0.0) / val);
1017 else
1018 slacksurplus += val;
1019 }
1020
1021 /* check if the least violating shift lies within variable bounds and set corresponding array values */
1022 if( !SCIPisInfinity(scip, maxfeasshift) && SCIPisFeasLE(scip, maxfeasshift + 1.0, upperbound) )
1023 {
1024 steps[i] = maxfeasshift + 1.0;
1025 violationchange[i] = rowweight;
1026 allzero = FALSE;
1027 }
1028 else
1029 {
1030 steps[i] = upperbound;
1031 violationchange[i] = 0;
1032 }
1033 }
1034 /* for a violated row, determine the minimum integral value within the bounds of the variable by which it has to be
1035 * shifted to make row feasible.
1036 */
1037 else
1038 {
1039 SCIP_Real minfeasshift;
1040
1041 minfeasshift = SCIPinfinity(scip);
1042
1043 /* if coefficient has the right sign to make row feasible, determine the minimum integer to shift variable
1044 * to obtain feasibility
1045 */
1046 if( val < 0.0 )
1047 {
1048 if( SCIPisFeasLT(scip, rhs, 0.0) )
1049 minfeasshift = SCIPfeasCeil(scip, MIN(rhs, val) / val);
1050 }
1051 else
1052 {
1053 if( SCIPisFeasLT(scip, -lhs, 0.0) )
1054 minfeasshift = SCIPfeasCeil(scip, MAX(lhs, val) / val);
1055 }
1056
1057 /* check if the minimum feasibility recovery shift lies within variable bounds and set corresponding array
1058 * values
1059 */
1060 if( !SCIPisInfinity(scip, minfeasshift) && SCIPisFeasLE(scip, minfeasshift, upperbound) )
1061 {
1062 steps[i] = minfeasshift;
1063 violationchange[i] = -rowweight;
1064 allzero = FALSE;
1065 }
1066 else
1067 {
1068 steps[i] = upperbound;
1069 violationchange[i] = 0;
1070 }
1071 }
1072 }
1073
1074 /* in case that the variable cannot affect the feasibility of any row, in particular it cannot violate
1075 * a single row, but we can add slack to already feasible rows, we will do this
1076 */
1077 if( allzero )
1078 {
1079 if( ! SCIPisInfinity(scip, upperbound) && SCIPisGT(scip, slacksurplus, 0.0) )
1080 *beststep = direction * upperbound;
1081 else
1082 *beststep = 0.0;
1083
1084 return SCIP_OKAY;
1085 }
1086
1087 /* sorts rows by increasing value of steps */
1088 SCIPsortRealInt(steps, violationchange, nrows);
1089
1090 *beststep = 0.0;
1091 *rowviolations = 0;
1092 sum = 0;
1093
1094 /* best shifting step is calculated by summing up the violation changes for each relevant step and
1095 * taking the one which leads to the minimum sum. This sum measures the balance of feasibility recovering and
1096 * violating changes which will be obtained by shifting the variable by this step
1097 * note, the sums for smaller steps have to be taken into account for all bigger steps, i.e., the sums can be
1098 * computed iteratively
1099 */
1100 for( i = 0; i < nrows && !SCIPisInfinity(scip, steps[i]); ++i )
1101 {
1102 sum += violationchange[i];
1103
1104 /* if we reached the last entry for the current step value, we have finished computing its sum and
1105 * update the step defining the minimum sum
1106 */
1107 if( (i == nrows-1 || steps[i+1] > steps[i]) && sum < *rowviolations ) /*lint !e679*/
1108 {
1109 *rowviolations = sum;
1110 *beststep = direction * steps[i];
1111 }
1112 }
1113 assert(*rowviolations <= 0);
1114 assert(!SCIPisInfinity(scip, *beststep));
1115
1116 return SCIP_OKAY;
1117}
1118
1119/** updates transformation of a given variable by taking into account current local bounds. if the bounds have changed
1120 * since last update, updating the heuristic specific upper bound of the variable, its current transformed solution value
1121 * and all affected rows is necessary.
1122 */
1123static
1125 SCIP* scip, /**< current scip */
1126 CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
1127 SCIP_HEURDATA* heurdata, /**< heuristic data */
1128 int varindex, /**< index of variable in matrix */
1129 SCIP_Real lb, /**< local lower bound of the variable */
1130 SCIP_Real ub, /**< local upper bound of the variable */
1131 int* violatedrows, /**< violated rows */
1132 int* violatedrowpos, /**< violated row positions */
1133 int* nviolatedrows /**< pointer to store number of violated rows */
1134 )
1135{
1136 TRANSFORMSTATUS status;
1137 SCIP_Real deltashift;
1138 SCIP_Bool checkviolations;
1139
1140 assert(scip != NULL);
1141 assert(matrix != NULL);
1142 assert(0 <= varindex && varindex < matrix->ndiscvars);
1143
1144 /* deltashift is the difference between the old and new transformation value. */
1145 deltashift = 0.0;
1146 status = matrix->transformstatus[varindex];
1147
1148 SCIPdebugMsg(scip, " Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1149 matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);
1150
1151 checkviolations = FALSE;
1152 /* depending on the variable status, deltashift is calculated differently. */
1153 switch( status )
1154 {
1155 case TRANSFORMSTATUS_LB:
1156 if( SCIPisInfinity(scip, -lb) )
1157 {
1158 transformVariable(scip, matrix, heurdata, varindex);
1159 checkviolations = TRUE;
1160 }
1161 else
1162 {
1163 deltashift = lb - (matrix->transformshiftvals[varindex]);
1164 matrix->transformshiftvals[varindex] = lb;
1165 if( !SCIPisInfinity(scip, ub) )
1166 matrix->upperbounds[varindex] = ub - lb;
1167 else
1168 matrix->upperbounds[varindex] = SCIPinfinity(scip);
1169 }
1170 break;
1172 if( SCIPisInfinity(scip, ub) )
1173 {
1174 transformVariable(scip, matrix, heurdata, varindex);
1175 checkviolations = TRUE;
1176 }
1177 else
1178 {
1179 deltashift = (matrix->transformshiftvals[varindex]) - ub;
1180 matrix->transformshiftvals[varindex] = ub;
1181
1182 if( !SCIPisInfinity(scip, -lb) )
1183 matrix->upperbounds[varindex] = MIN(ub - lb, SCIPinfinity(scip)); /*lint !e666*/
1184 else
1185 matrix->upperbounds[varindex] = SCIPinfinity(scip);
1186 }
1187 break;
1189 /* in case of a free transform status, if one of the bounds has become finite, we want
1190 * to transform this variable to a variable with a lowerbound or a negated transform status */
1191 if( !SCIPisInfinity(scip, -lb) || !SCIPisInfinity(scip, ub) )
1192 {
1193 transformVariable(scip, matrix, heurdata, varindex);
1194
1195 /* violations have to be rechecked for rows in which variable appears */
1196 checkviolations = TRUE;
1197
1198 assert(matrix->transformstatus[varindex] == TRANSFORMSTATUS_LB || matrix->transformstatus[varindex] == TRANSFORMSTATUS_NEG);
1199 assert(SCIPisLE(scip, ABS(lb), ABS(ub)) || matrix->transformstatus[varindex] == TRANSFORMSTATUS_NEG);
1200 }
1201 break;
1202
1204 default:
1205 SCIPerrorMessage("Error: Invalid variable status <%d> in shift and propagagate heuristic, aborting!\n", status);
1206 SCIPABORT();
1207 return SCIP_INVALIDDATA; /*lint !e527*/
1208 }
1209 /* if the bound, by which the variable was shifted, has changed, deltashift is different from zero, which requires
1210 * an update of all affected rows
1211 */
1212 if( !SCIPisFeasZero(scip, deltashift) )
1213 {
1214 int i;
1215 int* rows;
1216 SCIP_Real* vals;
1217 int nrows;
1218
1219 /* get nonzero values and corresponding rows of variable */
1220 getColumnData(matrix, varindex, &vals, &rows, &nrows);
1221
1222 /* go through rows, update the rows w.r.t. the influence of the changed transformation of the variable */
1223 for( i = 0; i < nrows; ++i )
1224 {
1225 SCIPdebugMsg(scip, " update slacks of row<%d>: coefficient <%g>, %g <= 0 <= %g \n",
1226 rows[i], vals[i], matrix->lhs[rows[i]], matrix->rhs[rows[i]]);
1227
1228 if( !SCIPisInfinity(scip, -(matrix->lhs[rows[i]])) )
1229 matrix->lhs[rows[i]] -= (vals[i]) * deltashift;
1230
1231 if( !SCIPisInfinity(scip, matrix->rhs[rows[i]]) )
1232 matrix->rhs[rows[i]] -= (vals[i]) * deltashift;
1233 }
1234 checkviolations = TRUE;
1235 }
1236
1237 /* check and update information about violated rows, if necessary */
1238 if( checkviolations )
1239 checkViolations(scip, matrix, varindex, violatedrows, violatedrowpos, nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1240
1241 SCIPdebugMsg(scip, " Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1242 matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);
1243
1244 return SCIP_OKAY;
1245}
1246
1247/** comparison method for columns; binary < integer < implicit < continuous variables */
1248static
1249SCIP_DECL_SORTPTRCOMP(heurSortColsShiftandpropagate)
1250{
1251 SCIP_COL* col1;
1252 SCIP_COL* col2;
1253 SCIP_VAR* var1;
1254 SCIP_VAR* var2;
1255 SCIP_VARTYPE vartype1;
1256 SCIP_VARTYPE vartype2;
1257 int key1;
1258 int key2;
1259
1260 col1 = (SCIP_COL*)elem1;
1261 col2 = (SCIP_COL*)elem2;
1262 var1 = SCIPcolGetVar(col1);
1263 var2 = SCIPcolGetVar(col2);
1264 assert(var1 != NULL && var2 != NULL);
1265
1266 vartype1 = SCIPvarGetType(var1);
1267 vartype2 = SCIPvarGetType(var2);
1268
1269 switch (vartype1)
1270 {
1272 key1 = 1;
1273 break;
1275 key1 = 2;
1276 break;
1278 key1 = 3;
1279 break;
1281 key1 = 4;
1282 break;
1283 default:
1284 key1 = -1;
1285 SCIPerrorMessage("unknown variable type\n");
1286 SCIPABORT();
1287 break;
1288 }
1289 switch (vartype2)
1290 {
1292 key2 = 1;
1293 break;
1295 key2 = 2;
1296 break;
1298 key2 = 3;
1299 break;
1301 key2 = 4;
1302 break;
1303 default:
1304 key2 = -1;
1305 SCIPerrorMessage("unknown variable type\n");
1306 SCIPABORT();
1307 break;
1308 }
1309 return key1 - key2;
1310}
1311
1312/*
1313 * Callback methods of primal heuristic
1314 */
1315
1316/** deinitialization method of primal heuristic(called before transformed problem is freed) */
1317static
1318SCIP_DECL_HEUREXIT(heurExitShiftandpropagate)
1319{ /*lint --e{715}*/
1320 SCIP_HEURDATA* heurdata;
1321
1322 heurdata = SCIPheurGetData(heur);
1323 assert(heurdata != NULL);
1324
1325 /* free random number generator */
1326 SCIPfreeRandom(scip, &heurdata->randnumgen);
1327
1328 /* if statistic mode is enabled, statistics are printed to console */
1331 " DETAILS : %d violations left, %d probing status\n",
1332 heurdata->nremainingviols,
1333 heurdata->lpsolstat
1334 );
1336 " SHIFTANDPROPAGATE PROBING : %d probings, %" SCIP_LONGINT_FORMAT " domain reductions, ncutoffs: %d , LP iterations: %" SCIP_LONGINT_FORMAT " \n ",
1337 heurdata->nprobings,
1338 heurdata->ntotaldomredsfound,
1339 heurdata->ncutoffs,
1340 heurdata->nlpiters);
1341 );
1342
1343 return SCIP_OKAY;
1344}
1345
1346/** initialization method of primal heuristic(called after problem was transformed). We only need this method for
1347 * statistic mode of heuristic.
1348 */
1349static
1350SCIP_DECL_HEURINIT(heurInitShiftandpropagate)
1351{ /*lint --e{715}*/
1352 SCIP_HEURDATA* heurdata;
1353
1354 heurdata = SCIPheurGetData(heur);
1355
1356 assert(heurdata != NULL);
1357
1358 /* create random number generator */
1359 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
1361
1363 heurdata->lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
1364 heurdata->nremainingviols = 0;
1365 heurdata->nprobings = 0;
1366 heurdata->ntotaldomredsfound = 0;
1367 heurdata->ncutoffs = 0;
1368 heurdata->nlpiters = 0;
1369 )
1370 return SCIP_OKAY;
1371}
1372
1373/** destructor of primal heuristic to free user data(called when SCIP is exiting) */
1374static
1375SCIP_DECL_HEURFREE(heurFreeShiftandpropagate)
1376{ /*lint --e{715}*/
1377 SCIP_HEURDATA* heurdata;
1378 SCIP_EVENTHDLR* eventhdlr;
1379 SCIP_EVENTHDLRDATA* eventhdlrdata;
1380
1381 heurdata = SCIPheurGetData(heur);
1382 assert(heurdata != NULL);
1383 eventhdlr = heurdata->eventhdlr;
1384 assert(eventhdlr != NULL);
1385 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1386
1387 SCIPfreeBlockMemoryNull(scip, &eventhdlrdata);
1388
1389 /* free heuristic data */
1390 SCIPfreeBlockMemory(scip, &heurdata);
1391
1392 SCIPheurSetData(heur, NULL);
1393
1394 return SCIP_OKAY;
1395}
1396
1397
1398/** copy method for primal heuristic plugins(called when SCIP copies plugins) */
1399static
1400SCIP_DECL_HEURCOPY(heurCopyShiftandpropagate)
1401{ /*lint --e{715}*/
1402 assert(scip != NULL);
1403 assert(heur != NULL);
1404 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1405
1406 /* call inclusion method of primal heuristic */
1408
1409 return SCIP_OKAY;
1410}
1411
1412/** execution method of primal heuristic */
1413static
1414SCIP_DECL_HEUREXEC(heurExecShiftandpropagate)
1415{ /*lint --e{715}*/
1416 SCIP_HEURDATA* heurdata; /* heuristic data */
1417 SCIP_EVENTHDLR* eventhdlr; /* shiftandpropagate event handler */
1418 SCIP_EVENTHDLRDATA* eventhdlrdata; /* event handler data */
1419 SCIP_EVENTDATA** eventdatas; /* event data for every variable */
1420
1421 CONSTRAINTMATRIX* matrix; /* constraint matrix object */
1422 SCIP_COL** lpcols; /* lp columns */
1423 SCIP_SOL* sol; /* solution pointer */
1424 SCIP_Real* colnorms; /* contains Euclidean norms of column vectors */
1425
1426 SCIP_Real* steps; /* buffer arrays for best shift selection in main loop */
1427 int* violationchange;
1428
1429 int* violatedrows; /* the violated rows */
1430 int* violatedrowpos; /* the array position of a violated row, or -1 */
1431 int* permutation; /* reflects the position of the variables after sorting */
1432 int* violatedvarrows; /* number of violated rows for each variable */
1433 int* colposs; /* position of columns according to variable type sorting */
1434 int nlpcols; /* number of lp columns */
1435 int nviolatedrows; /* number of violated rows */
1436 int ndiscvars; /* number of non-continuous variables of the problem */
1437 int lastindexofsusp; /* last variable which has been swapped due to a cutoff */
1438 int nbinvars; /* number of binary variables */
1439#ifndef NDEBUG
1440 int nintvars = 0; /* number of integer variables */
1441#endif
1442 int i;
1443 int r;
1444 int v;
1445 int c;
1446 int ncutoffs; /* counts the number of cutoffs for this execution */
1447 int nprobings; /* counts the number of probings */
1448 int nlprows; /* the number LP rows */
1449 int nmaxrows; /* maximum number of LP rows of a variable */
1450
1451 SCIP_Bool initialized; /* has the matrix been initialized? */
1452 SCIP_Bool cutoff; /* has current probing node been cutoff? */
1453 SCIP_Bool probing; /* should probing be applied or not? */
1454 SCIP_Bool infeasible; /* FALSE as long as currently infeasible rows have variables left */
1455 SCIP_Bool impliscontinuous;
1456
1457 heurdata = SCIPheurGetData(heur);
1458 assert(heurdata != NULL);
1459
1460 eventhdlr = heurdata->eventhdlr;
1461 assert(eventhdlr != NULL);
1462
1463 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1464 assert(eventhdlrdata != NULL);
1465
1466 *result = SCIP_DIDNOTRUN;
1467 SCIPdebugMsg(scip, "entering execution method of shift and propagate heuristic\n");
1468
1469 /* heuristic is obsolete if there are only continuous variables */
1470 if( SCIPgetNVars(scip) - SCIPgetNContVars(scip) == 0 )
1471 return SCIP_OKAY;
1472
1473 /* stop execution method if there is already a primarily feasible solution at hand */
1474 if( SCIPgetBestSol(scip) != NULL && heurdata->onlywithoutsol )
1475 return SCIP_OKAY;
1476
1477 /* stop if there is no LP available */
1478 if ( ! SCIPhasCurrentNodeLP(scip) )
1479 return SCIP_OKAY;
1480
1482 {
1483 /* @note this call can have the side effect that variables are created */
1484 SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
1485
1486 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
1487 if( cutoff )
1488 {
1490 return SCIP_OKAY;
1491 }
1492
1494 }
1495
1496 SCIPstatistic( heurdata->nlpiters = SCIPgetNLPIterations(scip) );
1497
1498 nlprows = SCIPgetNLPRows(scip);
1499
1500 SCIP_CALL( SCIPgetLPColsData(scip, &lpcols, &nlpcols) );
1501 assert(nlpcols == 0 || lpcols != NULL);
1502
1503 /* we need an LP */
1504 if( nlprows == 0 || nlpcols == 0 )
1505 return SCIP_OKAY;
1506
1507 *result = SCIP_DIDNOTFIND;
1508 initialized = FALSE;
1509
1510 /* allocate lp column array */
1511 SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->lpcols, nlpcols) );
1512 heurdata->nlpcols = nlpcols;
1513
1514 impliscontinuous = heurdata->impliscontinuous;
1515
1516#ifndef NDEBUG
1517 BMSclearMemoryArray(heurdata->lpcols, nlpcols);
1518#endif
1519
1520 /* copy and sort the columns by their variable types (binary before integer before implicit integer before continuous) */
1521 BMScopyMemoryArray(heurdata->lpcols, lpcols, nlpcols);
1522
1523 SCIPsortPtr((void**)heurdata->lpcols, heurSortColsShiftandpropagate, nlpcols);
1524
1525 SCIP_CALL( SCIPallocBufferArray(scip, &colposs, nlpcols) );
1526
1527 /* we have to collect the number of different variable types before we start probing since during probing variable
1528 * can be created (e.g., cons_xor.c)
1529 */
1530 ndiscvars = 0;
1531 nbinvars = 0;
1532 for( c = 0; c < nlpcols; ++c )
1533 {
1534 SCIP_COL* col;
1535 SCIP_VAR* colvar;
1536
1537 col = heurdata->lpcols[c];
1538 assert(col != NULL);
1539 colvar = SCIPcolGetVar(col);
1540 assert(colvar != NULL);
1541
1542 if( varIsDiscrete(colvar, impliscontinuous) )
1543 ++ndiscvars;
1544 if( SCIPvarGetType(colvar) == SCIP_VARTYPE_BINARY )
1545 ++nbinvars;
1546#ifndef NDEBUG
1547 else if( SCIPvarGetType(colvar) == SCIP_VARTYPE_INTEGER )
1548 ++nintvars;
1549#endif
1550
1551 /* save the position of this column in the array such that it can be accessed as the "true" column position */
1552 assert(SCIPcolGetLPPos(col) >= 0);
1553 colposs[SCIPcolGetLPPos(col)] = c;
1554 }
1555 assert(nbinvars + nintvars <= ndiscvars);
1556
1557 /* start probing mode */
1559
1560 /* enables collection of variable statistics during probing */
1561 if( heurdata->collectstats )
1563 else
1565
1566 /* this should always be fulfilled because we perform shift and propagate only at the root node */
1568
1569 /* @todo check if this node is necessary (I don't think so) */
1571 ncutoffs = 0;
1572 nprobings = 0;
1573 nmaxrows = 0;
1574 infeasible = FALSE;
1575
1576 /* initialize heuristic matrix and working solution */
1577 SCIP_CALL( SCIPallocBuffer(scip, &matrix) );
1578 SCIP_CALL( initMatrix(scip, matrix, heurdata, colposs, &nmaxrows, heurdata->relax, &initialized, &infeasible) );
1579
1580 /* could not initialize matrix */
1581 if( !initialized || infeasible )
1582 {
1583 SCIPdebugMsg(scip, " MATRIX not initialized -> Execution of heuristic stopped! \n");
1584 goto TERMINATE;
1585 }
1586
1587 /* the number of discrete LP column variables can be less than the actual number of variables, if, e.g., there
1588 * are nonlinearities in the problem. The heuristic execution can be terminated in that case.
1589 */
1590 if( matrix->ndiscvars < ndiscvars )
1591 {
1592 SCIPdebugMsg(scip, "Not all discrete variables are in the current LP. Shiftandpropagate execution terminated.\n");
1593 goto TERMINATE;
1594 }
1595
1596 assert(nmaxrows > 0);
1597
1598 eventhdlrdata->matrix = matrix;
1599 eventhdlrdata->heurdata = heurdata;
1600
1601 SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
1602 SCIPsolSetHeur(sol, heur);
1603
1604 /* allocate arrays for execution method */
1605 SCIP_CALL( SCIPallocBufferArray(scip, &permutation, ndiscvars) );
1606 SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->rowweights, matrix->nrows) );
1607
1608 /* allocate necessary memory for best shift search */
1609 SCIP_CALL( SCIPallocBufferArray(scip, &steps, nmaxrows) );
1610 SCIP_CALL( SCIPallocBufferArray(scip, &violationchange, nmaxrows) );
1611
1612 /* allocate arrays to store information about infeasible rows */
1613 SCIP_CALL( SCIPallocBufferArray(scip, &violatedrows, matrix->nrows) );
1614 SCIP_CALL( SCIPallocBufferArray(scip, &violatedrowpos, matrix->nrows) );
1615
1616 eventhdlrdata->violatedrows = violatedrows;
1617 eventhdlrdata->violatedrowpos = violatedrowpos;
1618 eventhdlrdata->nviolatedrows = &nviolatedrows;
1619
1620 /* initialize arrays. Before sorting, permutation is the identity permutation */
1621 for( i = 0; i < ndiscvars; ++i )
1622 permutation[i] = i;
1623
1624 /* initialize row weights */
1625 for( r = 0; r < matrix->nrows; ++r )
1626 {
1627 if( !SCIPisInfinity(scip, -(matrix->lhs[r])) && !SCIPisInfinity(scip, matrix->rhs[r]) )
1628 heurdata->rowweights[r] = DEFAULT_WEIGHT_EQUALITY;
1629 else
1630 heurdata->rowweights[r] = DEFAULT_WEIGHT_INEQUALITY;
1631 }
1632 colnorms = matrix->colnorms;
1633
1634 assert(nbinvars >= 0);
1635 assert(nintvars >= 0);
1636
1637 /* check rows for infeasibility */
1638 checkViolations(scip, matrix, -1, violatedrows, violatedrowpos, &nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1639
1640 /* allocate memory for violatedvarrows array only if variable ordering relies on it */
1641 if( heurdata->sortvars && (heurdata->sortkey == 't' || heurdata->sortkey == 'v') )
1642 {
1643 SCIP_CALL( SCIPallocBufferArray(scip, &violatedvarrows, ndiscvars) );
1644 BMScopyMemoryArray(violatedvarrows, matrix->violrows, ndiscvars);
1645 }
1646 else
1647 violatedvarrows = NULL;
1648
1649 /* sort variables w.r.t. the sorting key parameter. Sorting is indirect, all matrix column data
1650 * stays in place, but permutation array gives access to the sorted order of variables
1651 */
1652 if( heurdata->sortvars )
1653 {
1654 switch (heurdata->sortkey)
1655 {
1656 case 'n':
1657 /* variable ordering w.r.t. column norms nonincreasing */
1658 if( heurdata->preferbinaries )
1659 {
1660 if( nbinvars > 0 )
1661 SCIPsortDownRealInt(colnorms, permutation, nbinvars);
1662 if( nbinvars < ndiscvars )
1663 SCIPsortDownRealInt(&colnorms[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1664 }
1665 else
1666 {
1667 SCIPsortDownRealInt(colnorms, permutation, ndiscvars);
1668 }
1669 SCIPdebugMsg(scip, "Variables sorted down w.r.t their normalized columns!\n");
1670 break;
1671 case 'u':
1672 /* variable ordering w.r.t. column norms nondecreasing */
1673 if( heurdata->preferbinaries )
1674 {
1675 if( nbinvars > 0 )
1676 SCIPsortRealInt(colnorms, permutation, nbinvars);
1677 if( nbinvars < ndiscvars )
1678 SCIPsortRealInt(&colnorms[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1679 }
1680 else
1681 {
1682 SCIPsortRealInt(colnorms, permutation, ndiscvars);
1683 }
1684 SCIPdebugMsg(scip, "Variables sorted w.r.t their normalized columns!\n");
1685 break;
1686 case 'v':
1687 /* variable ordering w.r.t. nonincreasing number of violated rows */
1688 assert(violatedvarrows != NULL);
1689 if( heurdata->preferbinaries )
1690 {
1691 if( nbinvars > 0 )
1692 SCIPsortDownIntInt(violatedvarrows, permutation, nbinvars);
1693 if( nbinvars < ndiscvars )
1694 SCIPsortDownIntInt(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1695 }
1696 else
1697 {
1698 SCIPsortDownIntInt(violatedvarrows, permutation, ndiscvars);
1699 }
1700
1701 SCIPdebugMsg(scip, "Variables sorted down w.r.t their number of currently infeasible rows!\n");
1702 break;
1703 case 't':
1704 /* variable ordering w.r.t. nondecreasing number of violated rows */
1705 assert(violatedvarrows != NULL);
1706 if( heurdata->preferbinaries )
1707 {
1708 if( nbinvars > 0 )
1709 SCIPsortIntInt(violatedvarrows, permutation, nbinvars);
1710 if( nbinvars < ndiscvars )
1711 SCIPsortIntInt(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1712 }
1713 else
1714 {
1715 SCIPsortIntInt(violatedvarrows, permutation, ndiscvars);
1716 }
1717
1718 SCIPdebugMsg(scip, "Variables sorted (upwards) w.r.t their number of currently infeasible rows!\n");
1719 break;
1720 case 'r':
1721 /* random sorting */
1722 if( heurdata->preferbinaries )
1723 {
1724 if( nbinvars > 0 )
1725 SCIPrandomPermuteIntArray(heurdata->randnumgen, permutation, 0, nbinvars - 1);
1726 if( nbinvars < ndiscvars )
1727 SCIPrandomPermuteIntArray(heurdata->randnumgen, &permutation[nbinvars], nbinvars - 1,
1728 ndiscvars - nbinvars - 1);
1729 }
1730 else
1731 {
1732 SCIPrandomPermuteIntArray(heurdata->randnumgen, permutation, 0, ndiscvars - 1);
1733 }
1734 SCIPdebugMsg(scip, "Variables permuted randomly!\n");
1735 break;
1736 default:
1737 SCIPdebugMsg(scip, "No variable permutation applied\n");
1738 break;
1739 }
1740 }
1741
1742 /* should binary variables without locks be treated first? */
1743 if( heurdata->binlocksfirst )
1744 {
1745 SCIP_VAR* var;
1746 int nbinwithoutlocks = 0;
1747
1748 /* count number of binaries without locks */
1749 if( heurdata->preferbinaries )
1750 {
1751 for( c = 0; c < nbinvars; ++c )
1752 {
1753 var = SCIPcolGetVar(heurdata->lpcols[permutation[c]]);
1756 ++nbinwithoutlocks;
1757 }
1758 }
1759 else
1760 {
1761 for( c = 0; c < ndiscvars; ++c )
1762 {
1763 var = SCIPcolGetVar(heurdata->lpcols[permutation[c]]);
1764 if( SCIPvarIsBinary(var) )
1765 {
1768 ++nbinwithoutlocks;
1769 }
1770 }
1771 }
1772
1773 if( nbinwithoutlocks > 0 )
1774 {
1775 SCIP_VAR* binvar;
1776 int b = 1;
1777 int tmp;
1778 c = 0;
1779
1780 /* if c reaches nbinwithoutlocks, then all binary variables without locks were sorted to the beginning of the array */
1781 while( c < nbinwithoutlocks && b < ndiscvars )
1782 {
1783 assert(c < b);
1784 assert(c < ndiscvars);
1785 assert(b < ndiscvars);
1786 var = SCIPcolGetVar(heurdata->lpcols[permutation[c]]);
1787 binvar = SCIPcolGetVar(heurdata->lpcols[permutation[b]]);
1788
1789 /* search for next variable which is not a binary variable without locks */
1792 {
1793 ++c;
1794 if( c >= nbinwithoutlocks )
1795 break;
1796 var = SCIPcolGetVar(heurdata->lpcols[permutation[c]]);
1797 }
1798 if( c >= nbinwithoutlocks )
1799 break;
1800
1801 /* search for next binary variable without locks (with position > c) */
1802 if( b <= c )
1803 {
1804 b = c + 1;
1805 binvar = SCIPcolGetVar(heurdata->lpcols[permutation[b]]);
1806 }
1807 while( !SCIPvarIsBinary(binvar) || (SCIPvarGetNLocksUpType(binvar, SCIP_LOCKTYPE_MODEL) > 0
1809 {
1810 ++b;
1811 assert(b < ndiscvars);
1812 binvar = SCIPcolGetVar(heurdata->lpcols[permutation[b]]);
1813 }
1814
1815 /* swap the two variables */
1816 tmp = permutation[b];
1817 permutation[b] = permutation[c];
1818 permutation[c] = tmp;
1819
1820 /* increase counters */
1821 ++c;
1822 ++b;
1823 }
1824 }
1825
1826#ifndef NDEBUG
1827 for( c = 0; c < ndiscvars; ++c )
1828 {
1829 assert((c < nbinwithoutlocks) == (SCIPvarIsBinary(SCIPcolGetVar(heurdata->lpcols[permutation[c]]))
1830 && (SCIPvarGetNLocksUpType(SCIPcolGetVar(heurdata->lpcols[permutation[c]]), SCIP_LOCKTYPE_MODEL) == 0
1831 || SCIPvarGetNLocksDownType(SCIPcolGetVar(heurdata->lpcols[permutation[c]]), SCIP_LOCKTYPE_MODEL) == 0)));
1832 }
1833#endif
1834 }
1835
1836 SCIP_CALL( SCIPallocBufferArray(scip, &eventdatas, matrix->ndiscvars) );
1837 BMSclearMemoryArray(eventdatas, matrix->ndiscvars);
1838
1839 /* initialize variable events to catch bound changes during propagation */
1840 for( c = 0; c < matrix->ndiscvars; ++c )
1841 {
1842 SCIP_VAR* var;
1843
1844 var = SCIPcolGetVar(heurdata->lpcols[c]);
1845 assert(var != NULL);
1846 assert(SCIPvarIsIntegral(var));
1847 assert(eventdatas[c] == NULL);
1848
1849 SCIP_CALL( SCIPallocBuffer(scip, &(eventdatas[c])) ); /*lint !e866*/
1850
1851 eventdatas[c]->colpos = c;
1852
1853 SCIP_CALL( SCIPcatchVarEvent(scip, var, EVENTTYPE_SHIFTANDPROPAGATE, eventhdlr, eventdatas[c], NULL) );
1854 }
1855
1856 cutoff = FALSE;
1857
1858 lastindexofsusp = -1;
1859 probing = heurdata->probing;
1860 infeasible = FALSE;
1861
1862 SCIPdebugMsg(scip, "SHIFT_AND_PROPAGATE heuristic starts main loop with %d violations and %d remaining variables!\n",
1863 nviolatedrows, ndiscvars);
1864
1865 assert(matrix->ndiscvars == ndiscvars);
1866
1867 /* loop over variables, shift them according to shifting criteria and try to reduce the global infeasibility */
1868 for( c = 0; c < ndiscvars; ++c )
1869 {
1870 SCIP_VAR* var;
1871 SCIP_Longint ndomredsfound;
1872 SCIP_Real optimalshiftvalue;
1873 SCIP_Real origsolval;
1874 SCIP_Real lb;
1875 SCIP_Real ub;
1876 int nviolations;
1877 int permutedvarindex;
1878 int j;
1879 SCIP_Bool marksuspicious;
1880
1881 if( heurdata->selectbest )
1882 { /* search for best candidate */
1883 j = c + 1;
1884 while( j < ndiscvars )
1885 {
1886 /* run through remaining variables and search for best candidate */
1887 if( matrix->violrows[permutation[c]] < matrix->violrows[permutation[j]] )
1888 {
1889 int tmp;
1890 tmp = permutation[c];
1891 permutation[c] = permutation[j];
1892 permutation[j] = tmp;
1893 }
1894 ++j;
1895 }
1896 }
1897 permutedvarindex = permutation[c];
1898 optimalshiftvalue = 0.0;
1899 nviolations = 0;
1900 var = SCIPcolGetVar(heurdata->lpcols[permutedvarindex]);
1901 lb = SCIPvarGetLbLocal(var);
1902 ub = SCIPvarGetUbLocal(var);
1903 assert(SCIPcolGetLPPos(SCIPvarGetCol(var)) >= 0);
1904 assert(SCIPvarIsIntegral(var));
1905
1906 /* check whether we hit some limit, e.g. the time limit, in between
1907 * since the check itself consumes some time, we only do it every tenth iteration
1908 */
1909 if( c % 10 == 0 && SCIPisStopped(scip) )
1910 goto TERMINATE2;
1911
1912 /* if propagation is enabled, check if propagation has changed the variables bounds
1913 * and update the transformed upper bound correspondingly
1914 * @todo this should not be necessary
1915 */
1916 if( heurdata->probing )
1917 {
1918 SCIP_CALL( updateTransformation(scip, matrix, heurdata, permutedvarindex,lb, ub, violatedrows, violatedrowpos,
1919 &nviolatedrows) );
1920 }
1921
1922 SCIPdebugMsg(scip, "Variable %s with local bounds [%g,%g], status <%d>, matrix bound <%g>\n",
1923 SCIPvarGetName(var), lb, ub, matrix->transformstatus[permutedvarindex], matrix->upperbounds[permutedvarindex]);
1924
1925 /* ignore variable if propagation fixed it (lb and ub will be zero) */
1926 if( SCIPisFeasZero(scip, matrix->upperbounds[permutedvarindex]) )
1927 {
1928 assert(!SCIPisInfinity(scip, ub));
1929 assert(SCIPisFeasEQ(scip, lb, ub));
1930
1931 SCIP_CALL( SCIPsetSolVal(scip, sol, var, ub) );
1932
1933 continue;
1934 }
1935
1936 marksuspicious = FALSE;
1937
1938 /* check whether the variable is binary and has no locks in one direction, so that we want to fix it to the
1939 * respective bound (only enabled by parameter)
1940 */
1941 if( heurdata->fixbinlocks && SCIPvarIsBinary(var)
1944 {
1946 origsolval = SCIPvarGetUbLocal(var);
1947 else
1948 {
1950 origsolval = SCIPvarGetLbLocal(var);
1951 }
1952 }
1953 else
1954 {
1955 /* only apply the computationally expensive best shift selection, if there is a violated row left */
1956 if( !heurdata->stopafterfeasible || nviolatedrows > 0 )
1957 {
1958 /* compute optimal shift value for variable */
1959 SCIP_CALL( getOptimalShiftingValue(scip, matrix, permutedvarindex, 1, heurdata->rowweights, steps, violationchange,
1960 &optimalshiftvalue, &nviolations) );
1961 assert(SCIPisFeasGE(scip, optimalshiftvalue, 0.0));
1962
1963 /* Variables with FREE transform have to be dealt with twice */
1964 if( matrix->transformstatus[permutedvarindex] == TRANSFORMSTATUS_FREE )
1965 {
1966 SCIP_Real downshiftvalue;
1967 int ndownviolations;
1968
1969 downshiftvalue = 0.0;
1970 ndownviolations = 0;
1971 SCIP_CALL( getOptimalShiftingValue(scip, matrix, permutedvarindex, -1, heurdata->rowweights, steps, violationchange,
1972 &downshiftvalue, &ndownviolations) );
1973
1974 assert(SCIPisLE(scip, downshiftvalue, 0.0));
1975
1976 /* compare to positive direction and select the direction which makes more rows feasible */
1977 if( ndownviolations < nviolations )
1978 {
1979 optimalshiftvalue = downshiftvalue;
1980 }
1981 }
1982 }
1983 else
1984 optimalshiftvalue = 0.0;
1985
1986 /* if zero optimal shift values are forbidden by the user parameter, delay the variable by marking it suspicious */
1987 if( heurdata->nozerofixing && nviolations > 0 && SCIPisFeasZero(scip, optimalshiftvalue) )
1988 marksuspicious = TRUE;
1989
1990 /* retransform the solution value from the heuristic transformation space */
1991 assert(varIsDiscrete(var, impliscontinuous));
1992 origsolval = retransformVariable(scip, matrix, var, permutedvarindex, optimalshiftvalue);
1993 }
1994 assert(SCIPisFeasGE(scip, origsolval, lb) && SCIPisFeasLE(scip, origsolval, ub));
1995
1996 /* check if propagation should still be performed
1997 * @todo do we need the hard coded value? we could use SCIP_MAXTREEDEPTH
1998 */
1999 if( nprobings > DEFAULT_PROPBREAKER )
2000 probing = FALSE;
2001
2002 /* if propagation is enabled, fix the variable to the new solution value and propagate the fixation
2003 * (to fix other variables and to find out early whether solution is already infeasible)
2004 */
2005 if( !marksuspicious && probing )
2006 {
2007 /* this assert should be always fulfilled because we run this heuristic at the root node only and do not
2008 * perform probing if nprobings is less than DEFAULT_PROPBREAKER (currently: 65000)
2009 */
2011
2013 SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) );
2014 ndomredsfound = 0;
2015
2016 SCIPdebugMsg(scip, " Shift %g(%g originally) is optimal, propagate solution\n", optimalshiftvalue, origsolval);
2017 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->nproprounds, &cutoff, &ndomredsfound) );
2018
2019 ++nprobings;
2020 SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2021 SCIPdebugMsg(scip, "Propagation finished! <%" SCIP_LONGINT_FORMAT "> domain reductions %s, <%d> probing depth\n", ndomredsfound, cutoff ? "CUTOFF" : "",
2023 }
2024 assert(!cutoff || probing);
2025
2026 /* propagation led to an empty domain, hence we backtrack and postpone the variable */
2027 if( cutoff )
2028 {
2029 assert(probing);
2030
2031 ++ncutoffs;
2032
2033 /* only continue heuristic if number of cutoffs occured so far is reasonably small */
2034 if( heurdata->cutoffbreaker >= 0 && ncutoffs >= ((heurdata->maxcutoffquot * SCIPgetProbingDepth(scip)) + heurdata->cutoffbreaker) )
2035 break;
2036
2037 cutoff = FALSE;
2038
2039 /* backtrack to the parent of the current node */
2040 assert(SCIPgetProbingDepth(scip) >= 1);
2042
2043 /* this assert should be always fulfilled because we run this heuristic at the root node only and do not
2044 * perform probing if nprobings is less than DEFAULT_PROPBREAKER (currently: 65000)
2045 */
2047
2048 /* if the variable upper and lower bound are equal to the solution value to which we tried to fix the variable,
2049 * we are trapped at an infeasible node and break; this can only happen due to an intermediate global bound change of the variable,
2050 * I guess
2051 */
2052 if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), origsolval) && SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), origsolval) )
2053 {
2054 cutoff = TRUE;
2055 break;
2056 }
2057 else if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), origsolval) && REALABS( origsolval ) < 1.0 / SCIPepsilon(scip) )
2058 {
2059 /* if the variable was set to one of its bounds, repropagate by tightening this bound by 1.0 into the
2060 * direction of the other bound, if possible; if the bound is too large (in abs value) do not even bother
2061 */
2062 assert(SCIPisFeasGE(scip, SCIPvarGetUbLocal(var), origsolval + 1.0));
2063
2064 ndomredsfound = 0;
2066 SCIP_CALL( SCIPchgVarLbProbing(scip, var, origsolval + 1.0) );
2067 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->nproprounds, &cutoff, &ndomredsfound) );
2068
2069 SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2070 }
2071 else if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), origsolval) && REALABS( origsolval ) < 1.0 / SCIPepsilon(scip) )
2072 {
2073 /* if the variable was set to one of its bounds, repropagate by tightening this bound by 1.0 into the
2074 * direction of the other bound, if possible; if the bound is too large (in abs value) do not even bother
2075 */
2076 assert(SCIPisFeasLE(scip, SCIPvarGetLbLocal(var), origsolval - 1.0));
2077
2078 ndomredsfound = 0;
2079
2081 SCIP_CALL( SCIPchgVarUbProbing(scip, var, origsolval - 1.0) );
2082 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->nproprounds, &cutoff, &ndomredsfound) );
2083
2084 SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2085 }
2086
2087 /* if the tightened bound again leads to a cutoff, both subproblems are proven infeasible and the heuristic
2088 * can be stopped */
2089 if( cutoff )
2090 {
2091 break;
2092 }
2093 else
2094 {
2095 /* since repropagation was successful, we indicate that this variable led to a cutoff in one direction */
2096 marksuspicious = TRUE;
2097 }
2098 }
2099
2100 if( marksuspicious )
2101 {
2102 /* mark the variable as suspicious */
2103 assert(permutedvarindex == permutation[c]);
2104
2105 ++lastindexofsusp;
2106 assert(lastindexofsusp >= 0 && lastindexofsusp <= c);
2107
2108 permutation[c] = permutation[lastindexofsusp];
2109 permutation[lastindexofsusp] = permutedvarindex;
2110
2111 SCIPdebugMsg(scip, " Suspicious variable! Postponed from pos <%d> to position <%d>\n", c, lastindexofsusp);
2112 }
2113 else
2114 {
2115 SCIPdebugMsg(scip, "Variable <%d><%s> successfully shifted by value <%g>!\n", permutedvarindex,
2116 SCIPvarGetName(var), optimalshiftvalue);
2117
2118 /* update solution */
2119 SCIP_CALL( SCIPsetSolVal(scip, sol, var, origsolval) );
2120
2121 /* only to ensure that some assertions can be made later on */
2122 if( !probing )
2123 {
2124 SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) );
2125 }
2126 }
2127 }
2128 SCIPdebugMsg(scip, "Heuristic finished with %d remaining violations and %d remaining variables!\n",
2129 nviolatedrows, lastindexofsusp + 1);
2130
2131 /* if constructed solution might be feasible, go through the queue of suspicious variables and set the solution
2132 * values
2133 */
2134 if( nviolatedrows == 0 && !cutoff )
2135 {
2136 SCIP_Bool stored;
2137 SCIP_Bool trysol;
2138 SCIP_Bool solvelp;
2139
2140 for( v = 0; v <= lastindexofsusp; ++v )
2141 {
2142 SCIP_VAR* var;
2143 SCIP_Real origsolval;
2144 int permutedvarindex;
2145
2146 /* get the column position of the variable */
2147 permutedvarindex = permutation[v];
2148 var = SCIPcolGetVar(heurdata->lpcols[permutedvarindex]);
2149 assert(varIsDiscrete(var, impliscontinuous));
2150
2151 /* update the transformation of the variable, since the bound might have changed after the last update. */
2152 if( heurdata->probing )
2153 SCIP_CALL( updateTransformation(scip, matrix, heurdata, permutedvarindex, SCIPvarGetLbLocal(var),
2154 SCIPvarGetUbLocal(var), violatedrows, violatedrowpos, &nviolatedrows) );
2155
2156 /* retransform the solution value from the heuristic transformed space, set the solution value accordingly */
2157 assert(varIsDiscrete(var, impliscontinuous));
2158 origsolval = retransformVariable(scip, matrix, var, permutedvarindex, 0.0);
2159 assert(SCIPisFeasGE(scip, origsolval, SCIPvarGetLbLocal(var))
2160 && SCIPisFeasLE(scip, origsolval, SCIPvarGetUbLocal(var)));
2161 SCIP_CALL( SCIPsetSolVal(scip, sol, var, origsolval) );
2162 SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) ); /* only to ensure that some assertions can be made later */
2163
2164 SCIPdebugMsg(scip, " Remaining variable <%s> set to <%g>; %d Violations\n", SCIPvarGetName(var), origsolval,
2165 nviolatedrows);
2166 }
2167
2168 /* Fixing of remaining variables led to infeasibility */
2169 if( nviolatedrows > 0 )
2170 goto TERMINATE2;
2171
2172 trysol = TRUE;
2173
2174 /* check if enough variables have been fixed (including continuous) to solve the remaining LP */
2175 if( nlpcols != matrix->ndiscvars )
2176 {
2177 SCIP_VAR** vars;
2178 int nvars = SCIPgetNVars(scip);
2179 int nminfixings = (int)(SCIPceil(scip, heurdata->minfixingratelp * nvars));
2180 int nfixedvars = ndiscvars;
2181
2182 vars = SCIPgetVars(scip);
2183
2184 /* count fixed variables */
2185 for( v = ndiscvars; v < nvars && nfixedvars < nminfixings; ++v )
2186 {
2187 if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
2188 ++nfixedvars;
2189 }
2190
2191 solvelp = (nfixedvars >= nminfixings);
2192 trysol = solvelp;
2193 SCIPdebugMsg(scip, "Fixed %d of %d (%.1f %%) variables after probing -> %s\n",
2194 nfixedvars, nvars, (100.0 * nfixedvars / (SCIP_Real)nvars),
2195 solvelp ? "continue and solve LP for remaining variables" : "terminate without LP");
2196 }
2197 else /* no need to solve an LP */
2198 solvelp = FALSE;
2199
2200 /* if the constructed solution might still be extendable to a feasible solution, try this by
2201 * solving the remaining LP
2202 */
2203 if( solvelp )
2204 {
2205 char strbuf[SCIP_MAXSTRLEN];
2206 /* case that remaining LP has to be solved */
2207 SCIP_Bool lperror;
2208 int ncols;
2209
2210#ifndef NDEBUG
2211 {
2212 SCIP_VAR** vars;
2213
2214 vars = SCIPgetVars(scip);
2215 assert(vars != NULL);
2216 /* ensure that all discrete variables in the remaining LP are fixed */
2217 for( v = 0; v < ndiscvars; ++v )
2218 {
2219 if( SCIPvarIsInLP(vars[v]) )
2220 {
2221 assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])));
2222 }
2223 }
2224 }
2225#endif
2226
2227 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
2228 * which the user sees no output; more detailed probing stats only in debug mode */
2229 ncols = SCIPgetNLPCols(scip);
2230 if( !SCIPisLPSolBasic(scip) && ncols > 1000 )
2231 {
2232 int nunfixedcols = SCIPgetNUnfixedLPCols(scip);
2233
2234 if( nunfixedcols > 0.5 * ncols )
2235 {
2237 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
2238 100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
2239 }
2240 }
2241 SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n",
2243 SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
2244
2245#ifdef SCIP_DEBUG
2246 SCIP_CALL( SCIPwriteLP(scip, "shiftandpropagatelp.mps") );
2247#endif
2248 /* solve LP;
2249 * errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
2250 * hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
2251 */
2252#ifdef NDEBUG
2253 {
2254 SCIP_RETCODE retstat;
2255 retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL);
2256 if( retstat != SCIP_OKAY )
2257 {
2258 SCIPwarningMessage(scip, "Error while solving LP in SHIFTANDPROPAGATE heuristic; LP solve terminated with code <%d>\n",
2259 retstat);
2260 }
2261 }
2262#else
2263 SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) );
2264#endif
2265
2266 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
2267 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
2268
2269 /* check if this is a feasible solution */
2270 if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
2271 {
2272 /* copy the current LP solution to the working solution */
2273 SCIP_CALL( SCIPlinkLPSol(scip, sol) );
2274 }
2275 else
2276 trysol = FALSE;
2277
2278 SCIPstatistic( heurdata->lpsolstat = SCIPgetLPSolstat(scip) );
2279 }
2280
2281 /* check solution for feasibility, and add it to solution store if possible.
2282 * None of integrality, feasibility of LP rows, variable bounds have to be checked, because they
2283 * are guaranteed by the heuristic at this stage.
2284 */
2285 if( trysol )
2286 {
2287 SCIP_Bool printreason;
2288 SCIP_Bool completely;
2289#ifdef SCIP_DEBUG
2290 printreason = TRUE;
2291#else
2292 printreason = FALSE;
2293#endif
2294#ifndef NDEBUG
2295 completely = TRUE; /*lint !e838*/
2296#else
2297 completely = FALSE;
2298#endif
2299
2300 /* we once also checked the variable bounds which should not be necessary */
2301 SCIP_CALL( SCIPtrySol(scip, sol, printreason, completely, FALSE, FALSE, FALSE, &stored) );
2302
2303 if( stored )
2304 {
2305 SCIPdebugMsg(scip, "found feasible shifted solution:\n");
2307 *result = SCIP_FOUNDSOL;
2308
2309 SCIPstatisticMessage(" Shiftandpropagate solution value: %16.9g \n", SCIPgetSolOrigObj(scip, sol));
2310 }
2311 }
2312 }
2313 else
2314 {
2315 SCIPdebugMsg(scip, "Solution constructed by heuristic is already known to be infeasible\n");
2316 }
2317
2318 SCIPstatistic( heurdata->nremainingviols = nviolatedrows; );
2319
2320 TERMINATE2:
2321 /* free allocated memory in reverse order of allocation */
2322 for( c = matrix->ndiscvars - 1; c >= 0; --c )
2323 {
2324 SCIP_VAR* var;
2325
2326 var = SCIPcolGetVar(heurdata->lpcols[c]);
2327 assert(var != NULL);
2328 assert(eventdatas[c] != NULL);
2329
2330 SCIP_CALL( SCIPdropVarEvent(scip, var, EVENTTYPE_SHIFTANDPROPAGATE, eventhdlr, eventdatas[c], -1) );
2331 SCIPfreeBuffer(scip, &(eventdatas[c]));
2332 }
2333 SCIPfreeBufferArray(scip, &eventdatas);
2334
2335 if( violatedvarrows != NULL )
2336 {
2337 assert(heurdata->sortkey == 'v' || heurdata->sortkey == 't');
2338 SCIPfreeBufferArray(scip, &violatedvarrows);
2339 }
2340 /* free all allocated memory */
2341 SCIPfreeBufferArray(scip, &violatedrowpos);
2342 SCIPfreeBufferArray(scip, &violatedrows);
2343 SCIPfreeBufferArray(scip, &violationchange);
2344 SCIPfreeBufferArray(scip, &steps);
2345 SCIPfreeBufferArray(scip, &heurdata->rowweights);
2346 SCIPfreeBufferArray(scip, &permutation);
2347 SCIP_CALL( SCIPfreeSol(scip, &sol) );
2348
2349 eventhdlrdata->nviolatedrows = NULL;
2350 eventhdlrdata->violatedrowpos = NULL;
2351 eventhdlrdata->violatedrows = NULL;
2352
2353 TERMINATE:
2354 /* terminate probing mode and free the remaining memory */
2356 heurdata->ncutoffs += ncutoffs;
2357 heurdata->nprobings += nprobings;
2358 heurdata->nlpiters = SCIPgetNLPIterations(scip) - heurdata->nlpiters;
2359 );
2360
2362 freeMatrix(scip, &matrix);
2363 SCIPfreeBufferArray(scip, &colposs);
2364 SCIPfreeBufferArray(scip, &heurdata->lpcols);
2365 eventhdlrdata->matrix = NULL;
2366
2367 return SCIP_OKAY;
2368}
2369
2370/** event handler execution method for the heuristic which catches all
2371 * events in which a lower or upper bound were tightened */
2372static
2373SCIP_DECL_EVENTEXEC(eventExecShiftandpropagate)
2374{ /*lint --e{715}*/
2375 SCIP_EVENTHDLRDATA* eventhdlrdata;
2376 SCIP_VAR* var;
2377 SCIP_COL* col;
2378 SCIP_Real lb;
2379 SCIP_Real ub;
2380 int colpos;
2381 CONSTRAINTMATRIX* matrix;
2382 SCIP_HEURDATA* heurdata;
2383
2384 assert(scip != NULL);
2385 assert(eventhdlr != NULL);
2386 assert(strcmp(EVENTHDLR_NAME, SCIPeventhdlrGetName(eventhdlr)) == 0);
2387
2388 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
2389 assert(eventhdlrdata != NULL);
2390
2391 matrix = eventhdlrdata->matrix;
2392
2393 heurdata = eventhdlrdata->heurdata;
2394 assert(heurdata != NULL && heurdata->lpcols != NULL);
2395
2396 colpos = eventdata->colpos;
2397
2398 assert(0 <= colpos && colpos < matrix->ndiscvars);
2399
2400 col = heurdata->lpcols[colpos];
2401 var = SCIPcolGetVar(col);
2402
2403 lb = SCIPvarGetLbLocal(var);
2404 ub = SCIPvarGetUbLocal(var);
2405
2406 SCIP_CALL( updateTransformation(scip, matrix, eventhdlrdata->heurdata, colpos, lb, ub, eventhdlrdata->violatedrows,
2407 eventhdlrdata->violatedrowpos, eventhdlrdata->nviolatedrows) );
2408
2409 return SCIP_OKAY;
2410}
2411
2412/*
2413 * primal heuristic specific interface methods
2414 */
2415
2416/** creates the shiftandpropagate primal heuristic and includes it in SCIP */
2418 SCIP* scip /**< SCIP data structure */
2419 )
2420{
2421 SCIP_HEURDATA* heurdata;
2422 SCIP_HEUR* heur;
2423 SCIP_EVENTHDLRDATA* eventhandlerdata;
2424 SCIP_EVENTHDLR* eventhdlr;
2425
2426 SCIP_CALL( SCIPallocBlockMemory(scip, &eventhandlerdata) );
2427 eventhandlerdata->matrix = NULL;
2428
2429 eventhdlr = NULL;
2431 eventExecShiftandpropagate, eventhandlerdata) );
2432 assert(eventhdlr != NULL);
2433
2434 /* create Shiftandpropagate primal heuristic data */
2435 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2436 heurdata->rowweights = NULL;
2437 heurdata->nlpcols = 0;
2438 heurdata->eventhdlr = eventhdlr;
2439
2440 /* include primal heuristic */
2443 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecShiftandpropagate, heurdata) );
2444
2445 assert(heur != NULL);
2446
2447 /* set non-NULL pointers to callback methods */
2448 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyShiftandpropagate) );
2449 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeShiftandpropagate) );
2450 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitShiftandpropagate) );
2451 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitShiftandpropagate) );
2452
2453 /* add shiftandpropagate primal heuristic parameters */
2454 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nproprounds",
2455 "The number of propagation rounds used for each propagation",
2456 &heurdata->nproprounds, TRUE, DEFAULT_NPROPROUNDS, -1, 1000, NULL, NULL) );
2457 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/relax", "Should continuous variables be relaxed?",
2458 &heurdata->relax, TRUE, DEFAULT_RELAX, NULL, NULL) );
2459 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/probing", "Should domains be reduced by probing?",
2460 &heurdata->probing, TRUE, DEFAULT_PROBING, NULL, NULL) );
2461 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/onlywithoutsol",
2462 "Should heuristic only be executed if no primal solution was found, yet?",
2463 &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
2464 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/cutoffbreaker", "The number of cutoffs before heuristic stops",
2465 &heurdata->cutoffbreaker, TRUE, DEFAULT_CUTOFFBREAKER, -1, 1000000, NULL, NULL) );
2466 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/sortkey",
2467 "the key for variable sorting: (n)orms down, norms (u)p, (v)iolations down, viola(t)ions up, or (r)andom",
2468 &heurdata->sortkey, TRUE, DEFAULT_SORTKEY, SORTKEYS, NULL, NULL) );
2469 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/sortvars", "Should variables be sorted for the heuristic?",
2470 &heurdata->sortvars, TRUE, DEFAULT_SORTVARS, NULL, NULL));
2471 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/collectstats", "should variable statistics be collected during probing?",
2472 &heurdata->collectstats, TRUE, DEFAULT_COLLECTSTATS, NULL, NULL) );
2473 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/stopafterfeasible",
2474 "Should the heuristic stop calculating optimal shift values when no more rows are violated?",
2475 &heurdata->stopafterfeasible, TRUE, DEFAULT_STOPAFTERFEASIBLE, NULL, NULL) );
2476 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/preferbinaries",
2477 "Should binary variables be shifted first?",
2478 &heurdata->preferbinaries, TRUE, DEFAULT_PREFERBINARIES, NULL, NULL) );
2479 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/nozerofixing",
2480 "should variables with a zero shifting value be delayed instead of being fixed?",
2481 &heurdata->nozerofixing, TRUE, DEFAULT_NOZEROFIXING, NULL, NULL) );
2482 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/fixbinlocks",
2483 "should binary variables with no locks in one direction be fixed to that direction?",
2484 &heurdata->fixbinlocks, TRUE, DEFAULT_FIXBINLOCKS, NULL, NULL) );
2485 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/binlocksfirst",
2486 "should binary variables with no locks be preferred in the ordering?",
2487 &heurdata->binlocksfirst, TRUE, DEFAULT_BINLOCKSFIRST, NULL, NULL) );
2488 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/normalize",
2489 "should coefficients be normalized by max row coeff for col norm?",
2490 &heurdata->normalize, TRUE, DEFAULT_NORMALIZE, NULL, NULL) );
2491 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/updateweights",
2492 "should row weight be increased every time the row is violated?",
2493 &heurdata->updateweights, TRUE, DEFAULT_UPDATEWEIGHTS, NULL, NULL) );
2494 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/impliscontinuous",
2495 "should implicit integer variables be treated as continuous variables?",
2496 &heurdata->impliscontinuous, TRUE, DEFAULT_IMPLISCONTINUOUS, NULL, NULL) );
2497 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/selectbest",
2498 "should the heuristic choose the best candidate in every round? (set to FALSE for static order)?",
2499 &heurdata->selectbest, TRUE, DEFAULT_SELECTBEST, NULL, NULL) );
2500 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcutoffquot",
2501 "maximum percentage of allowed cutoffs before stopping the heuristic",
2502 &heurdata->maxcutoffquot, TRUE, DEFAULT_MAXCUTOFFQUOT, 0.0, 2.0, NULL, NULL) );
2503 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingratelp",
2504 "minimum fixing rate over all variables (including continuous) to solve LP",
2505 &heurdata->minfixingratelp, TRUE, DEFAULT_MINFIXINGRATELP, 0.0, 1.0, NULL, NULL) );
2506
2507 return SCIP_OKAY;
2508}
SCIP_VAR ** b
Definition: circlepacking.c:65
SCIP_Real * r
Definition: circlepacking.c:59
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_MAXTREEDEPTH
Definition: def.h:316
#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 SCIPABORT()
Definition: def.h:346
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2172
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:167
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
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:10149
SCIP_RETCODE SCIPincludeHeurShiftandpropagate(SCIP *scip)
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:17093
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17042
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:17072
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17161
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17151
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:17140
SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)
Definition: lp.c:17115
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:334
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
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 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 SCIPflushLP(SCIP *scip)
Definition: scip_lp.c:148
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_lp.c:124
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip_lp.c:101
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
int SCIPgetNUnfixedLPCols(SCIP *scip)
Definition: scip_lp.c:548
int SCIPgetNLPCols(SCIP *scip)
Definition: scip_lp.c:527
SCIP_RETCODE SCIPwriteLP(SCIP *scip, const char *filename)
Definition: scip_lp.c:901
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:667
#define SCIPfreeBuffer(scip, ptr)
Definition: scip_mem.h:134
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBuffer(scip, ptr)
Definition: scip_mem.h:122
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBlockMemoryNull(scip, ptr)
Definition: scip_mem.h:109
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:198
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:301
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:225
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:165
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:820
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:418
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:260
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1922
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17238
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:17227
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17501
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
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17258
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17248
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
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_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_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
Definition: sol.c:2849
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(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 SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:434
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17789
void SCIPdisableVarHistory(SCIP *scip)
Definition: scip_var.c:8760
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
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
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8741
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
Definition: var.c:17800
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
#define DEFAULT_ONLYWITHOUTSOL
#define DEFAULT_NORMALIZE
static void relaxVar(SCIP *scip, SCIP_VAR *var, CONSTRAINTMATRIX *matrix)
#define DEFAULT_RELAX
static void transformVariable(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int colpos)
static SCIP_RETCODE getOptimalShiftingValue(SCIP *scip, CONSTRAINTMATRIX *matrix, int varindex, int direction, int *rowweights, SCIP_Real *steps, int *violationchange, SCIP_Real *beststep, int *rowviolations)
static void getRowData(CONSTRAINTMATRIX *matrix, int rowindex, SCIP_Real **valpointer, SCIP_Real *lhs, SCIP_Real *rhs, int **indexpointer, int *nrowvals)
static SCIP_DECL_SORTPTRCOMP(heurSortColsShiftandpropagate)
static void checkRowViolation(SCIP *scip, CONSTRAINTMATRIX *matrix, int rowindex, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)
#define DEFAULT_MINFIXINGRATELP
static SCIP_Bool colIsDiscrete(SCIP_COL *col, SCIP_Bool impliscontinuous)
#define HEUR_TIMING
#define DEFAULT_PROPBREAKER
#define DEFAULT_IMPLISCONTINUOUS
#define DEFAULT_PREFERBINARIES
#define HEUR_FREQOFS
#define DEFAULT_NPROPROUNDS
static SCIP_DECL_HEUREXEC(heurExecShiftandpropagate)
#define HEUR_DESC
#define DEFAULT_FIXBINLOCKS
@ TRANSFORMSTATUS_NONE
@ TRANSFORMSTATUS_FREE
@ TRANSFORMSTATUS_NEG
@ TRANSFORMSTATUS_LB
static SCIP_DECL_EVENTEXEC(eventExecShiftandpropagate)
static void freeMatrix(SCIP *scip, CONSTRAINTMATRIX **matrix)
#define DEFAULT_SELECTBEST
#define DEFAULT_BINLOCKSFIRST
static SCIP_RETCODE updateTransformation(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int varindex, SCIP_Real lb, SCIP_Real ub, int *violatedrows, int *violatedrowpos, int *nviolatedrows)
static SCIP_DECL_HEUREXIT(heurExitShiftandpropagate)
#define DEFAULT_SORTVARS
#define SORTKEYS
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_MAXCUTOFFQUOT
#define DEFAULT_CUTOFFBREAKER
enum TransformStatus TRANSFORMSTATUS
#define DEFAULT_WEIGHT_INEQUALITY
#define HEUR_NAME
#define DEFAULT_NOZEROFIXING
static SCIP_DECL_HEURCOPY(heurCopyShiftandpropagate)
#define DEFAULT_RANDSEED
static SCIP_DECL_HEURINIT(heurInitShiftandpropagate)
#define DEFAULT_SORTKEY
static void checkViolations(SCIP *scip, CONSTRAINTMATRIX *matrix, int colidx, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)
#define DEFAULT_UPDATEWEIGHTS
#define DEFAULT_COLLECTSTATS
#define EVENTHDLR_DESC
static SCIP_Real retransformVariable(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_VAR *var, int varindex, SCIP_Real solvalue)
static SCIP_Bool varIsDiscrete(SCIP_VAR *var, SCIP_Bool impliscontinuous)
struct ConstraintMatrix CONSTRAINTMATRIX
#define HEUR_FREQ
#define DEFAULT_WEIGHT_EQUALITY
static void getColumnData(CONSTRAINTMATRIX *matrix, int colindex, SCIP_Real **valpointer, int **indexpointer, int *ncolvals)
#define HEUR_USESSUBSCIP
#define EVENTHDLR_NAME
#define DEFAULT_STOPAFTERFEASIBLE
static SCIP_DECL_HEURFREE(heurFreeShiftandpropagate)
#define DEFAULT_PROBING
static SCIP_RETCODE initMatrix(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int *colposs, int *nmaxrows, SCIP_Bool relax, SCIP_Bool *initialized, SCIP_Bool *infeasible)
#define EVENTTYPE_SHIFTANDPROPAGATE
preroot heuristic that alternatingly fixes variables and propagates domains
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
public methods for managing events
public methods for primal heuristics
public methods for LP management
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPstatisticMessage
Definition: pub_message.h:123
#define SCIPdebug(x)
Definition: pub_message.h:93
#define SCIPstatistic(x)
Definition: pub_message.h:120
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 event handler plugins and event handlers
general public methods
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 the probing mode
public methods for random numbers
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:173
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:155
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:51
@ SCIP_LPSOLSTAT_NOTSOLVED
Definition: type_lp.h:42
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_VERBLEVEL_FULL
Definition: type_message.h:57
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_INTEGER
Definition: type_var.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_VARTYPE_IMPLINT
Definition: type_var.h:64
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:51
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:73