SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_dps.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-2023 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_dps.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief dynamic partition search
28 * @author Katrin Halbig
29 *
30 * The dynamic partition search (DPS) is a construction heuristic which additionally needs a
31 * user decomposition with linking constraints only.
32 *
33 * This heuristic splits the problem into several sub-SCIPs according to the given decomposition. Thereby the linking constraints
34 * with their right-hand and left-hand sides are also split. DPS searches for a partition of the sides on the blocks
35 * so that a feasible solution is obtained.
36 * For each block the parts of the original linking constraints are extended by slack variables. Moreover, the objective function
37 * is replaced by the sum of these additional variables weighted by penalty parameters lambda. If all blocks have an optimal solution
38 * of zero, the algorithm terminates with a feasible solution for the main problem. Otherwise, the partition and the penalty parameters
39 * are updated, and the sub-SCIPs are solved again.
40 */
41
42/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
43
44#include "scip/heur_dps.h"
45#include "scip/pub_dcmp.h"
46#include "scip/pub_heur.h"
47#include "scip/pub_misc.h"
48#include "scip/scipdefplugins.h"
49#include "scip/scip_cons.h"
50#include "scip/scip_dcmp.h"
51#include "scip/scip_general.h"
52#include "scip/scip_heur.h"
53#include "scip/scip_mem.h"
54#include "scip/scip_message.h"
55#include "scip/scip_param.h"
56#include "scip/scip_prob.h"
57
58
59#define HEUR_NAME "dps"
60#define HEUR_DESC "primal heuristic for decomposable MIPs"
61#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
62#define HEUR_PRIORITY 75000
63#define HEUR_FREQ -1
64#define HEUR_FREQOFS 0
65#define HEUR_MAXDEPTH -1
66#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
67#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
68
69#define DEFAULT_MAXIT 50 /**< maximum number of iterations */
70#define DEFAULT_PENALTY 100.0 /**< multiplier for absolute increase of penalty parameters */
71
72/* event handler properties */
73#define EVENTHDLR_NAME "Dps"
74#define EVENTHDLR_DESC "event handler for " HEUR_NAME " heuristic"
75
76/*
77 * Data structures
78 */
79
80/** primal heuristic data */
81struct SCIP_HeurData
82{
83 SCIP_CONS** linkingconss; /**< linking constraints */
84 int nlinking; /**< number of linking constraints */
85 int nblocks; /**< number of blocks */
86 int maxit; /**< maximal number of iterations */
87 SCIP_Real maxlinkscore; /**< maximal linking score of used decomposition (equivalent to percentage of linking constraints) */
88 SCIP_Real penalty; /**< multiplier for absolute increase of penalty parameters */
89 SCIP_Bool reoptimize; /**< should the problem get reoptimized with the original objective function? */
90 SCIP_Bool reuse; /**< should solutions get reused in subproblems? */
91};
92
93/** data related to one block */
95{
96 SCIP* blockscip; /**< SCIP data structure */
97 SCIP_VAR** slackvars; /**< slack variables */
98 SCIP_CONS** linkingconss; /**< linking constraints */
99 int* linkingindices; /**< indices of linking constraints in original problem */
100 int nlinking; /**< number of linking constraints */
101 int nblockvars; /**< number of block variables */
102 int nslackvars; /**< number of slack variables */
103 SCIP_Real* origobj; /**< original objective coefficients */
104};
106
107/** data related to one linking constraint */
109{
110 SCIP_CONS* linkingcons; /**< corresponding linking constraint of original problem */
111 SCIP_CONS** blockconss; /**< linking constraints of the blocks */
112 SCIP_VAR** slacks; /**< slackvars of the blocks */
113 SCIP_Real* minactivity; /**< minimal activity of constraint for each block */
114 SCIP_Real* maxactivity; /**< maximal activity of constraint for each block */
115 SCIP_Real* currentrhs; /**< current partition of rhs */
116 SCIP_Real* currentlhs; /**< current partition of lhs */
117 int* blocknumbers; /**< number of the blocks */
118 int nblocks; /**< number of blocks in which this linking constraint participates; dimension of arrays */
119 int nslacks; /**< number of slack variables */
120 int nslacksperblock; /**< 2, if ranged constraint; 1, if only rhs or lhs */
121 int lastviolations; /**< number of iterations in which the constraint was violated in succession */
122 SCIP_Bool hasrhs; /**< has linking constraint finite right-hand side? */
123 SCIP_Bool haslhs; /**< has linking constraint finite left-hand side? */
124};
125typedef struct Linking LINKING;
126
127/*
128 * Local methods
129 */
130
131/** assigns linking variables to last block
132 *
133 * The labels are copied to newdecomp and the linking variables are assigned to the last block (i.e., highest block label).
134 * Constraint labels and statistics are recomputed.
135 */
136static
138 SCIP* scip, /**< SCIP data structure */
139 SCIP_DECOMP* newdecomp, /**< decomposition with assigned linking variables */
140 SCIP_VAR** vars, /**< sorted array of variables */
141 SCIP_CONS** conss, /**< sorted array of constraints */
142 int* varlabels, /**< sorted array of variable labels */
143 int* conslabels, /**< sorted array of constraint labels */
144 int nvars, /**< number of variables */
145 int nconss, /**< number of constraints */
146 int nlinkvars /**< number of linking variables */
147 )
148{
149 int newlabel;
150 int v;
151
152 assert(scip != NULL);
154 assert(vars != NULL);
155 assert(conss != NULL);
158
159 /* copy the labels */
162
163 /* assign linking variables */
164 newlabel = varlabels[nvars - 1]; /* take always label of last block */
165 assert(newlabel >= 0);
166 for( v = 0; v < nlinkvars; v++ )
167 {
169 }
170 SCIPdebugMsg(scip, "assigned %d linking variables\n", nlinkvars);
171
172 /* recompute constraint labels and statistics */
176
177 /* get new labels and sort */
180 SCIPsortIntPtr(conslabels, (void**)conss, nconss);
182
183 /* After assigning the linking variables, blocks can have zero constraints.
184 * So the remaining variables are labeled as linking in SCIPcomputeDecompStats().
185 * We assign this variables to the same label as above.
186 */
187 if( nlinkvars >= 1 )
188 {
190 SCIPdebugMsg(scip, "assign again %d linking variables\n", nlinkvars);
191
192 for( v = 0; v < nlinkvars; v++ )
193 {
195 }
198
201 SCIPsortIntPtr(conslabels, (void**)conss, nconss);
203 }
205
206 return SCIP_OKAY;
207}
208
209/** creates a sub-SCIP and sets parameters */
210static
212 SCIP* scip, /**< main SCIP data structure */
213 SCIP** subscip /**< pointer to store created sub-SCIP */
214 )
215{
216 assert(scip != NULL);
217 assert(subscip != NULL);
218
219 /* create a new SCIP instance */
220 SCIP_CALL( SCIPcreate(subscip) );
222
223 SCIP_CALL( SCIPcopyLimits(scip, *subscip) );
224
225 /* avoid recursive calls */
226 SCIP_CALL( SCIPsetSubscipsOff(*subscip, TRUE) );
227
228 /* disable cutting plane separation */
230
231 /* disable expensive presolving */
233
234 /* disable expensive techniques */
235 SCIP_CALL( SCIPsetIntParam(*subscip, "misc/usesymmetry", 0) );
236
237 /* do not abort subproblem on CTRL-C */
238 SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/catchctrlc", FALSE) );
239
240#ifdef SCIP_DEBUG
241 /* for debugging, enable full output */
242 SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 5) );
243 SCIP_CALL( SCIPsetIntParam(*subscip, "display/freq", 100000000) );
244#else
245 /* disable statistic timing inside sub SCIP and output to console */
246 SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 0) );
247 SCIP_CALL( SCIPsetBoolParam(*subscip, "timing/statistictiming", FALSE) );
248#endif
249
250 /* speed up sub-SCIP by not checking dual LP feasibility */
251 SCIP_CALL( SCIPsetBoolParam(*subscip, "lp/checkdualfeas", FALSE) );
252
253 return SCIP_OKAY;
254}
255
256/** copies the given variables and constraints to the given sub-SCIP */
257static
259 SCIP* scip, /**< source SCIP */
260 SCIP* subscip, /**< target SCIP */
261 const char* name, /**< name for copied problem */
262 SCIP_VAR** vars, /**< array of variables to copy */
263 SCIP_CONS** conss, /**< array of constraints to copy */
264 SCIP_HASHMAP* varsmap, /**< hashmap for copied variables */
265 SCIP_HASHMAP* conssmap, /**< hashmap for copied constraints */
266 int nvars, /**< number of variables to copy */
267 int nconss, /**< number of constraints to copy */
268 SCIP_Bool* success /**< was copying successful? */
269 )
270{
273 int i;
274
275 assert(scip != NULL);
276 assert(subscip != NULL);
277 assert(vars != NULL);
278 assert(conss != NULL);
279 assert(varsmap != NULL);
280 assert(conssmap != NULL);
281 assert(success != NULL);
282
283 SCIPdebugMsg(scip, "copyToSubscip\n");
284
285 /* create problem in sub-SCIP */
286 SCIP_CALL( SCIPcreateProb(subscip, name, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
287
288 /* copy variables */
289 for( i = 0; i < nvars; ++i )
290 {
292
293 /* abort if variable was not successfully copied */
294 if( !(*success) )
295 {
296 SCIPwarningMessage(scip, "Abort heuristic dps since not all variables were successfully copied.\n");
297 SCIPABORT();
298 return SCIP_OKAY;
299 }
300 }
301 assert(nvars == SCIPgetNOrigVars(subscip));
302
303 /* copy constraints */
304 for( i = 0; i < nconss; ++i )
305 {
306 assert(conss[i] != NULL);
307 assert(!SCIPconsIsModifiable(conss[i]));
308 assert(SCIPconsIsActive(conss[i]));
309 assert(!SCIPconsIsDeleted(conss[i]));
310
311 /* copy the constraint */
316
317 /* abort if constraint was not successfully copied */
318 if( !(*success) )
319 return SCIP_OKAY;
320
321 SCIP_CALL( SCIPaddCons(subscip, newcons) );
322 SCIP_CALL( SCIPreleaseCons(subscip, &newcons) );
323 }
324
325 /* block constraint contains variables which are not part of this block
326 *
327 * todo: maybe they are part of the block, but it is not recognized, because they are, for example, negated or aggregated.
328 */
329 if( nvars != SCIPgetNOrigVars(subscip) )
330 *success = FALSE;
331
332 return SCIP_OKAY;
333}
334
335/** creates the subscip for a given block */
336static
338 SCIP* scip, /**< SCIP data structure */
339 BLOCKPROBLEM* blockproblem, /**< blockproblem that should be created */
340 LINKING** linkings, /**< linkings that will be (partially) initialized */
341 SCIP_CONS** conss, /**< sorted array of constraints of this block */
342 SCIP_VAR** vars, /**< sorted array of variables of this block */
343 int nconss, /**< number of constraints of this block */
344 int nvars, /**< number of variables of this block */
345 SCIP_CONS** linkingconss, /**< linking constraints in the original problem */
346 int nlinking, /**< number of linking constraints in the original problem */
347 int blocknumber, /**< number of block that should be created */
348 SCIP_Bool* success /**< pointer to store whether creation was successful */
349 )
350{
351 char name[SCIP_MAXSTRLEN];
354 SCIP_VAR** consvars; /* all vars in original linking cons */
355 SCIP_Real* consvals;
356 int nconsvars;
357 SCIP_VAR** blockvars; /* vars of current linking cons of current block */
358 SCIP_Real* blockvals;
359 int nblockvars;
360 SCIP_VAR** subvars; /* all vars of subscip */
361 int maxnconsvars; /* current size of arrays */
362 int c;
363 int v;
364
365 assert(scip != NULL);
367 assert(conss != NULL);
368 assert(vars != NULL);
369 assert(blockproblem->blockscip != NULL);
370
371 maxnconsvars = 20; /* start size; increase size if necessary */
372
373 SCIPdebugMsg(scip, "Create blockproblem %d\n", blocknumber);
374
375 /* create the variable/constraint mapping hash map */
378
379 /* get name of the original problem and add "comp_nr" */
381
382 SCIP_CALL( copyToSubscip(scip, blockproblem->blockscip, name, vars, conss, varsmap, conssmap,
383 nvars, nconss, success) );
384 if( !(*success) )
385 {
386 SCIPdebugMsg(scip, "Copy to subscip failed\n");
389
390 return SCIP_OKAY;
391 }
392
393 /* save number of variables that have a corresponding variable in original problem*/
394 blockproblem->nblockvars = SCIPgetNVars(blockproblem->blockscip);
395
396 /* save original objective and set objective to zero */
397 subvars = SCIPgetVars(blockproblem->blockscip);
398 for( v = 0; v < nvars; v++ )
399 {
400 blockproblem->origobj[v] = SCIPvarGetObj(subvars[v]);
401 SCIP_CALL( SCIPchgVarObj(blockproblem->blockscip, subvars[v], 0.0) );
402 }
403
404 /* allocate memory */
405 SCIP_CALL( SCIPallocBufferArray(blockproblem->blockscip, &blockvars, nvars + 2) ); /* two entries for the slack variables */
407 SCIP_CALL( SCIPallocBufferArray(blockproblem->blockscip, &consvars, maxnconsvars) );
409
410 /* find and add parts of linking constraints */
411 SCIPdebugMsg(scip, "add parts of linking constraints\n");
412 for( c = 0; c < nlinking; c++ )
413 {
414 const char* conshdlrname;
415 char consname[SCIP_MAXSTRLEN];
417 SCIP_Real rhs;
418 SCIP_Real lhs;
419 SCIP_Real minact;
420 SCIP_Real maxact;
421 SCIP_Bool mininfinite;
422 SCIP_Bool maxinfinite;
423
424 assert(linkingconss[c] != NULL);
425
426 newcons = NULL;
427
428#ifdef SCIP_MORE_DEBUG
429 SCIPdebugMsg(scip, "consider constraint %s\n", SCIPconsGetName(linkingconss[c]));
430 SCIPdebugPrintCons(scip, linkingconss[c], NULL);
431#endif
432
433 nblockvars = 0;
434
435 /* every constraint with linear representation is allowed */
437 if( !( (strcmp(conshdlrname, "linear") == 0) || (strcmp(conshdlrname, "setppc") == 0)
438 || (strcmp(conshdlrname, "logicor") == 0) || (strcmp(conshdlrname, "knapsack") == 0)
439 || (strcmp(conshdlrname, "varbound") == 0) ) )
440 {
441 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "Heuristic %s cannot handle linking constraints of type %s\n", HEUR_NAME, conshdlrname);
442 /* TODO which other types can we handle/transform in a linear constraint? */
443
444 *success = FALSE;
445 break; /* releases memory and breaks heuristic */
446 }
447
448 SCIP_CALL( SCIPgetConsNVars(scip, linkingconss[c], &nconsvars, success) );
449
450 /* reallocate memory if we have more variables than maxnconsvars */
451 if( nconsvars > maxnconsvars )
452 {
453 int newsize;
454
455 /* calculate new size */
456 newsize = SCIPcalcMemGrowSize(scip, MAX(2 * maxnconsvars, nconsvars)); /* at least double size */
457
458 SCIP_CALL( SCIPreallocBufferArray(blockproblem->blockscip, &consvars, newsize) );
461 }
462
463 SCIP_CALL( SCIPgetConsVars(scip, linkingconss[c], consvars, nconsvars, success) );
464 SCIP_CALL( SCIPgetConsVals(scip, linkingconss[c], consvals, nconsvars, success) );
465
466 if( !(*success) )
467 {
468 SCIPdebugMsg(scip, "Create blockproblem failed\n");
469 break; /* releases memory and breaks heuristic */
470 }
471
472 /* check if constraint contains variables of this block */
473 for( v = 0; v < nconsvars; v++ )
474 {
475 if( SCIPhashmapExists(varsmap, (void*)consvars[v]) )
476 {
477 blockvars[nblockvars] = (SCIP_VAR*) SCIPhashmapGetImage(varsmap, (void*)consvars[v]);
478 blockvals[nblockvars] = consvals[v];
479 ++nblockvars;
480 }
481 /* handle negated variables*/
482 else if( SCIPvarGetStatus(consvars[v]) == SCIP_VARSTATUS_NEGATED)
483 {
484 if( SCIPhashmapExists(varsmap, (void*)SCIPvarGetNegationVar(consvars[v])) ) /* negation exists in this block */
485 {
486 /* save negated variable */
490 blockvars[nblockvars] = negblockvar;
491 blockvals[nblockvars] = consvals[v];
492 ++nblockvars;
493 }
494 }
495 }
496
497 /* continue with next linking constraint if it has no part in current block */
498 if( nblockvars == 0 )
499 continue;
500
501 /* get rhs and/or lhs */
502 rhs = SCIPconsGetRhs(scip, linkingconss[c], success);
503 if( !(*success) )
504 {
505 SCIPdebugMsg(scip, "Create blockproblem failed\n");
506 return SCIP_OKAY;
507 }
508 lhs = SCIPconsGetLhs(scip, linkingconss[c], success);
509 if( !(*success) )
510 {
511 SCIPdebugMsg(scip, "Create blockproblem failed\n");
512 return SCIP_OKAY;
513 }
514 assert(!SCIPisInfinity(scip, rhs) || !SCIPisInfinity(scip, -lhs)); /* at least one side bounded */
515 assert(SCIPisLE(scip, lhs, rhs));
516
517 if( !SCIPisInfinity(scip, rhs) )
518 linkings[c]->hasrhs = TRUE;
519 if( !SCIPisInfinity(scip, -lhs) )
520 linkings[c]->haslhs = TRUE;
521 if( !SCIPisInfinity(scip, rhs) && !SCIPisInfinity(scip, -lhs))
522 linkings[c]->nslacksperblock = 2;
523 else
524 linkings[c]->nslacksperblock = 1;
525
526 /* add slack variable for rhs */
527 if( linkings[c]->hasrhs )
528 {
529 /* slack variable z_r >= 0 */
531 (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "z_r_%s", SCIPconsGetName(linkingconss[c]));
532 SCIP_CALL( SCIPcreateVarBasic(blockproblem->blockscip, &blockvars[nblockvars], varname,
534 blockvals[nblockvars] = -1.0;
535 SCIP_CALL( SCIPaddVar(blockproblem->blockscip, blockvars[nblockvars]) );
536#ifdef SCIP_MORE_DEBUG
537 SCIPdebugMsg(scip, "Add variable %s\n", SCIPvarGetName(blockvars[nblockvars]));
538#endif
539 linkings[c]->slacks[linkings[c]->nslacks] = blockvars[nblockvars];
540 blockproblem->slackvars[blockproblem->nslackvars] = blockvars[nblockvars];
541 ++blockproblem->nslackvars;
542 ++linkings[c]->nslacks;
543 ++nblockvars;
544 }
545
546 /* add slack variable for lhs */
547 if( linkings[c]->haslhs )
548 {
549 /* slack variable z_l >= 0 */
551 (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "z_l_%s", SCIPconsGetName(linkingconss[c]));
552 SCIP_CALL( SCIPcreateVarBasic(blockproblem->blockscip, &blockvars[nblockvars], varname,
554 blockvals[nblockvars] = 1.0;
555 SCIP_CALL( SCIPaddVar(blockproblem->blockscip, blockvars[nblockvars]) );
556#ifdef SCIP_MORE_DEBUG
557 SCIPdebugMsg(scip, "Add variable %s\n", SCIPvarGetName(blockvars[nblockvars]));
558#endif
559 linkings[c]->slacks[linkings[c]->nslacks] = blockvars[nblockvars];
560 blockproblem->slackvars[blockproblem->nslackvars] = blockvars[nblockvars];
561 ++blockproblem->nslackvars;
562 ++linkings[c]->nslacks;
563 ++nblockvars;
564 }
565
566 /* add linking constraint with slack variable */
567 (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s", SCIPconsGetName(linkingconss[c]));
568 SCIP_CALL( SCIPcreateConsBasicLinear(blockproblem->blockscip, &newcons, consname, nblockvars, blockvars, blockvals, lhs, rhs) );
570#ifdef SCIP_MORE_DEBUG
571 SCIPdebugMsg(blockproblem->blockscip, "add constraint %s\n", SCIPconsGetName(newcons));
573#endif
574
575 blockproblem->linkingconss[blockproblem->nlinking] = newcons;
576 linkings[c]->blockconss[linkings[c]->nblocks] = newcons;
577 linkings[c]->blocknumbers[linkings[c]->nblocks] = blocknumber;
578 blockproblem->linkingindices[blockproblem->nlinking] = c;
579
580 /* calculate minimal und maximal activity (exclude slack variables) */
581 minact = 0;
582 maxact = 0;
585 for( v = 0; v < nblockvars - linkings[c]->nslacksperblock && (!mininfinite || !maxinfinite); v++ )
586 {
587 SCIP_Real lb;
588 SCIP_Real ub;
591
592 if( blockvals[v] >= 0.0 )
593 {
596 if( !mininfinite )
597 minact += blockvals[v] * lb;
598 if( !maxinfinite )
599 maxact += blockvals[v] * ub;
600 }
601 else
602 {
605 if( !mininfinite )
606 minact += blockvals[v] * ub;
607 if( !maxinfinite )
608 maxact += blockvals[v] * lb;
609 }
610 }
611
612 if( mininfinite )
613 linkings[c]->minactivity[linkings[c]->nblocks] = -SCIPinfinity(scip);
614 else
615 linkings[c]->minactivity[linkings[c]->nblocks] = minact;
616 if( maxinfinite )
617 linkings[c]->maxactivity[linkings[c]->nblocks] = SCIPinfinity(scip);
618 else
619 linkings[c]->maxactivity[linkings[c]->nblocks] = maxact;
621
622 linkings[c]->nblocks++;
623 blockproblem->nlinking++;
624
625 for( v = 1; v <= linkings[c]->nslacksperblock; v++ )
626 {
627 SCIP_CALL( SCIPreleaseVar(blockproblem->blockscip, &blockvars[nblockvars - v]) );
628 }
629
631 }
632 assert(blockproblem->nlinking <= nlinking);
633
634 /* free memory */
636 SCIPfreeBufferArray(blockproblem->blockscip, &consvars);
639
642
643 return SCIP_OKAY;
644}
645
646/** creates data structures and splits problem into blocks */
647static
649 SCIP* scip, /**< SCIP data structure */
650 SCIP_HEURDATA* heurdata, /**< heuristic data */
651 SCIP_DECOMP* decomp, /**< decomposition data structure */
652 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
653 LINKING** linkings, /**< array of linking data structures */
654 SCIP_VAR** vars, /**< sorted array of variables */
655 SCIP_CONS** conss, /**< sorted array of constraints */
656 SCIP_Bool* success /**< pointer to store whether splitting was successful */
657 )
658{
659 int* nconssblock;
660 int* nvarsblock;
661 int conssoffset;
662 int varsoffset;
663 int i; /* blocknumber */
664
665 assert(scip != NULL);
666 assert(heurdata != NULL);
667 assert(vars != NULL);
668 assert(conss != NULL);
669
672 SCIP_CALL( SCIPdecompGetVarsSize(decomp, nvarsblock, heurdata->nblocks + 1) );
673 SCIP_CALL( SCIPdecompGetConssSize(decomp, nconssblock, heurdata->nblocks + 1) );
674 assert(0 == nvarsblock[0]);
675
676 varsoffset = 0;
677 conssoffset = 0;
678
679 for( i = 0; i < heurdata->nblocks; i++)
680 {
683
685 heurdata->linkingconss, heurdata->nlinking, i, success) );
686 if( !(*success) )
687 break;
688 }
689
692
693 return SCIP_OKAY;
694}
695
696/** rounds partition for one linking constraint to integer value if variables and coefficients are integer
697 *
698 * changes only currentrhs/currentlhs
699 */
700static
702 SCIP* scip, /**< SCIP data structure */
703 LINKING* linking, /**< one linking data structure */
704 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
705 SCIP_Bool roundbyrhs /**< round by right hand side? */
706 )
707{
708 SCIP_Real* fracPart;
709 int* sorting;
710 int* isinteger;
711 SCIP_Real sumbefor; /* includes value at idx */
712 SCIP_Real sumafter;
713 SCIP_Real diff;
714 int nnonintblocks; /* number of non integer blocks */
715 int idx;
716 int b;
717 int i;
718 int k;
719
720 assert(scip != NULL);
721 assert(linking != NULL);
723
724 nnonintblocks = 0;
725 idx = 0;
726
728 SCIP_CALL( SCIPallocBufferArray(scip, &sorting, linking->nblocks) );
729 SCIP_CALL( SCIPallocBufferArray(scip, &isinteger, linking->nblocks) );
730
731 /* get integer blocks and fractional parts */
732 for( b = 0; b < linking->nblocks; b++ )
733 {
734 SCIP* subscip;
737 SCIP_Real* blockvals;
738 int nblockvars;
739 int length; /* number of block variables without slack variables */
740 SCIP_Bool success;
741
742 subscip = blockproblem[linking->blocknumbers[b]]->blockscip;
743 blockcons = linking->blockconss[b];
744 sorting[b] = b; /* store current sorting to sort back */
745
746 SCIP_CALL( SCIPgetConsNVars(subscip, blockcons, &nblockvars, &success) );
750
751 SCIP_CALL( SCIPgetConsVars(subscip, blockcons, blockvars, nblockvars, &success) );
753 SCIP_CALL( SCIPgetConsVals(subscip, blockcons, blockvals, nblockvars, &success) );
755
756 /* get number of block variables in this constraint without slack variables */
757 length = nblockvars - linking->nslacksperblock;
758
759 /* get blocks with integer value */
760 isinteger[b] = 1;
761 for( i = 0; i < length; i++ )
762 {
764 {
765 isinteger[b] = 0;
767 break;
768 }
769 }
770
771 /* get fractional part of blockconstraints */
772 if( roundbyrhs )
773 fracPart[b] = linking->currentrhs[b] - floor(linking->currentrhs[b]); /* do not use SCIPfrac()! */
774 else
775 fracPart[b] = linking->currentlhs[b] - floor(linking->currentlhs[b]);
776
779 }
780
781 /* sort non-integer blocks to the front */
782 SCIPsortIntIntReal(isinteger, sorting, fracPart, linking->nblocks);
783
784 /* sort by fractional part */
787
788 /* detect blocks for rounding down and rounding up:
789 * integer blocks with small fractional parts are rounded down
790 * integer blocks with big fractional parts are rounded up
791 */
792
793 sumbefor = 0.0;
794 sumafter = 0.0;
795
796 for( i = 0; i < linking->nblocks - nnonintblocks; i++ )
798
799 for( i = 0; i < linking->nblocks - nnonintblocks; i++ )
800 {
803
804 if( sumbefor >= sumafter )
805 {
806 for( k = 0; k <= i; k++ )
808
809 for( k = i + 1; k < linking->nblocks - nnonintblocks; k++ )
811
812 idx = i;
813 break;
814 }
815 }
817 assert(SCIPisGE(scip, diff, 0.0));
818
819 /* add difference to last non integer block */
820 for( i = nnonintblocks - 1; i >= 0; i-- )
821 {
822 if( SCIPisGT(scip, diff, 0.0) )
823 {
824 fracPart[i] = diff;
825 diff = 0;
826 }
827 else
828 fracPart[i] = 0;
829 }
830
831 /* add difference to last rounded down block if no non integer block exists */
832 if( SCIPisGT(scip, diff, 0.0))
833 {
834 assert(nnonintblocks == 0);
835 fracPart[idx] += diff;
836 }
837
838 /* sort back */
839 SCIPsortIntReal(sorting, fracPart, linking->nblocks);
840
841 /* round partition
842 * if we have a ranged constraint, both sides get rounded in the same way
843 */
844 for( b = 0; b < linking->nblocks; b++ )
845 {
846 if( linking->hasrhs )
847 linking->currentrhs[b] += fracPart[b];
848
849 if( linking->haslhs )
850 linking->currentlhs[b] += fracPart[b];
851 }
852
853 SCIPfreeBufferArray(scip, &isinteger);
854 SCIPfreeBufferArray(scip, &sorting);
856
857 return SCIP_OKAY;
858}
859
860/** calculates initial partition and sets rhs/lhs in blockproblems */
861static
863 SCIP* scip, /**< SCIP data structure of main scip */
864 LINKING** linkings, /**< array of linking data structures */
865 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
866 int nlinking, /**< number of linking constraints */
867 SCIP_Bool* success /**< pointer to store whether initialization was successful */
868 )
869{
871 SCIP_Real rhs;
872 SCIP_Real lhs;
873 SCIP_Real residualrhs;
874 SCIP_Real residuallhs;
875 SCIP_Real goalvalue;
876 int c;
877 int b;
878
879 assert(scip != NULL);
880 assert(linkings != NULL);
882 assert(nlinking > 0);
883
884 SCIPdebugMsg(scip, "initialize partition\n");
885
886 /* for each linking constraint the rhs/lhs is split between the blocks */
887 for( c = 0; c < nlinking; c++ )
888 {
889 linking = linkings[c];
890 rhs = SCIPconsGetRhs(scip, linking->linkingcons, success);
891 assert(*success);
892 lhs = SCIPconsGetLhs(scip, linking->linkingcons, success);
893 assert(*success);
894 residualrhs = rhs;
895 residuallhs = lhs;
896
897 /* equal parts for each block with respect to minimal/maximal activity */
898 if( linking->hasrhs || linking->haslhs )
899 {
900 if( linking->hasrhs )
901 {
902 for( b = 0; b < linking->nblocks; b++ )
903 {
904 goalvalue = residualrhs / (linking->nblocks - b);
905 linking->currentrhs[b] = MIN(MAX(goalvalue, linking->minactivity[b]), linking->maxactivity[b]);
906 residualrhs -= linking->currentrhs[b];
907 }
908 /* add residual partition to first block */
909 linking->currentrhs[0] += residualrhs;
910 }
911 if( linking->haslhs )
912 {
913 for( b = 0; b < linking->nblocks; b++ )
914 {
915 goalvalue = residuallhs / (linking->nblocks - b);
916 linking->currentlhs[b] = MIN(MAX(goalvalue, linking->minactivity[b]), linking->maxactivity[b]);
917 residuallhs -= linking->currentlhs[b];
918 }
919 /* add residual partition to first block */
920 linking->currentlhs[0] += residuallhs;
921 }
922 }
923 else
924 {
925 assert(linking->nblocks == 0 && !SCIPconsIsChecked(linking->linkingcons));
926 }
927
929
930 /* set sides in blockproblem at initial partition */
931 for( b = 0; b < linking->nblocks; b++ )
932 {
933 if( linking->hasrhs )
934 {
935 SCIP_CALL( SCIPchgRhsLinear(blockproblem[linking->blocknumbers[b]]->blockscip,
936 linking->blockconss[b], linking->currentrhs[b]) );
937#ifdef SCIP_MORE_DEBUG
938 SCIPdebugMsg(scip, "change rhs of %s in block %d to %f\n",
939 SCIPconsGetName(linking->linkingcons), linking->blocknumbers[b], linking->currentrhs[b]);
940#endif
941 }
942 if( linking->haslhs )
943 {
944 SCIP_CALL( SCIPchgLhsLinear(blockproblem[linking->blocknumbers[b]]->blockscip,
945 linking->blockconss[b], linking->currentlhs[b]) );
946#ifdef SCIP_MORE_DEBUG
947 SCIPdebugMsg(scip, "change lhs of %s in block %d to %f\n",
948 SCIPconsGetName(linking->linkingcons), linking->blocknumbers[b], linking->currentlhs[b]);
949#endif
950 }
951 }
952 }
953
954 return SCIP_OKAY;
955}
956
957/** update partition */
958static
960 SCIP* scip, /**< SCIP data structure of main scip */
961 LINKING* linking, /**< one linking data structure */
962 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
963 int* nviolatedblocksrhs, /**< pointer to store number of blocks which violate rhs */
964 int* nviolatedblockslhs, /**< pointer to store number of blocks which violate lhs */
965 int iteration /**< number of iteration */
966 )
967{
968 SCIP_Real* shift; /* direction vector */
971 SCIP_Real sumviols = 0.0;
972 int v;
973
974 assert(scip != NULL);
975 assert(linking != NULL);
977 assert(iteration >= 0);
978
981
982 SCIP_CALL( SCIPallocBufferArray(scip, &shift, linking->nblocks) );
983 BMSclearMemoryArray(shift, linking->nblocks);
984 if( linking->hasrhs )
985 {
987 }
988 if( linking->haslhs )
989 {
991 }
992
993 /* get violated blocks and calculate shift */
994 for( v = 0; v < linking->nblocks; v++ )
995 {
996 SCIP* subscip;
998 SCIP_Real slackval;
999
1000 subscip = blockproblem[linking->blocknumbers[v]]->blockscip;
1001 subsol = SCIPgetBestSol(subscip);
1002
1003 /* if we have ranged constraints, the slack variables of the rhs are in front;
1004 * get slack variable of block; save violated blocks
1005 */
1006 if( linking->hasrhs )
1007 {
1008 slackval = SCIPgetSolVal(subscip, subsol, linking->slacks[v * linking->nslacksperblock]);
1009
1010 /* block is violated */
1012 {
1013 (*nviolatedblocksrhs)++;
1014
1015 shift[v] += slackval;
1016 sumviols += slackval;
1017 }
1018 else
1019 {
1020 nonviolatedblocksrhs[v - *nviolatedblocksrhs] = v; /*lint !e644*/
1021 }
1022 }
1023 if( linking->haslhs )
1024 {
1025 slackval = SCIPgetSolVal(subscip, subsol, linking->slacks[(v * linking->nslacksperblock) + linking->nslacksperblock - 1]);
1026
1027 /* block is violated */
1029 {
1030 (*nviolatedblockslhs)++;
1031
1032 shift[v] -= slackval;
1033 sumviols -= slackval;
1034 }
1035 else
1036 {
1037 nonviolatedblockslhs[v - *nviolatedblockslhs] = v; /*lint !e644*/
1038 }
1039 }
1040 }
1041
1042 /* linking constraint is in no block violated or always violated -> do not update partition */
1044 linking->nblocks == *nviolatedblocksrhs || linking->nblocks == *nviolatedblockslhs )
1045 {
1046 /* free memory */
1047 if( linking->haslhs )
1049 if( linking->hasrhs )
1051 SCIPfreeBufferArray(scip, &shift);
1052 return SCIP_OKAY;
1053 }
1054
1055 /* set values of non violated blocks */
1057 {
1058 /* rhs of original linking constraint is violated */
1059 SCIP_Real residual = sumviols;
1060 SCIP_Real part;
1061 SCIP_Real shift_tmp;
1062
1063 assert(linking->hasrhs);
1065
1066 /* substract from each non violated block the same amount with respect to minimal/maximal activity,
1067 * so that the shift is zero in sum
1068 */
1069 for( v = 0; v < linking->nblocks - *nviolatedblocksrhs; v++ )
1070 {
1071 part = linking->currentrhs[nonviolatedblocksrhs[v]] - residual/(linking->nblocks - *nviolatedblocksrhs - v);
1072 part = MIN(MAX(part, linking->minactivity[nonviolatedblocksrhs[v]]), linking->maxactivity[nonviolatedblocksrhs[v]]);
1073 shift_tmp = part - linking->currentrhs[nonviolatedblocksrhs[v]];
1075 shift[nonviolatedblocksrhs[v]] += shift_tmp;
1076 }
1077 if( !SCIPisZero(scip, residual) )
1078 {
1079 /* assign residual to first block */
1080 shift[nonviolatedblocksrhs[0]] -= residual;
1081 }
1082 }
1084 {
1085 /* lhs of original linking constraint is violated */
1086 SCIP_Real residual = sumviols;
1087 SCIP_Real part;
1088 SCIP_Real shift_tmp;
1089
1090 assert(linking->haslhs);
1092
1093 /* add to each non violated block the same amount with respect to minimal/maximal activity,
1094 * so that the shift is zero in sum
1095 */
1096 for( v = 0; v < linking->nblocks - *nviolatedblockslhs; v++ )
1097 {
1098 part = linking->currentlhs[nonviolatedblockslhs[v]] - residual/(linking->nblocks - *nviolatedblockslhs - v);
1099 part = MIN(MAX(part, linking->minactivity[nonviolatedblockslhs[v]]), linking->maxactivity[nonviolatedblockslhs[v]]);
1100 shift_tmp = part - linking->currentlhs[nonviolatedblockslhs[v]];
1102 shift[nonviolatedblockslhs[v]] += shift_tmp;
1103 }
1104 if( !SCIPisZero(scip, residual) )
1105 {
1106 /* assign residual to first block */
1107 shift[nonviolatedblockslhs[0]] -= residual;
1108 }
1109 }
1110
1111#ifdef SCIP_DEBUG
1112 SCIP_Real sum = 0.0;
1113 /* check sum of shift; must be zero */
1114 for( v = 0; v < linking->nblocks; v++ )
1115 sum += shift[v];
1116 assert(SCIPisZero(scip, sum));
1117#endif
1118
1119 /* add shift to both sides */
1120 for( v = 0; v < linking->nblocks; v++)
1121 {
1122 if( linking->hasrhs )
1123 linking->currentrhs[v] += shift[v];
1124
1125 if( linking->haslhs )
1126 linking->currentlhs[v] += shift[v];
1127 }
1128
1129 SCIP_CALL( roundPartition(scip, linking, blockproblem, ((linking->hasrhs && (*nviolatedblocksrhs != 0)) || !linking->haslhs)) );
1130
1131 /* set sides in blockproblems to new partition */
1132 for( v = 0; v < linking->nblocks; v++ )
1133 {
1134 SCIP* subscip;
1135 subscip = blockproblem[linking->blocknumbers[v]]->blockscip;
1136
1137 if( linking->hasrhs )
1138 {
1139 SCIP_CALL( SCIPchgRhsLinear(subscip, linking->blockconss[v], linking->currentrhs[v]) );
1140 }
1141 if( linking->haslhs )
1142 {
1143 SCIP_CALL( SCIPchgLhsLinear(subscip, linking->blockconss[v], linking->currentlhs[v]) );
1144 }
1145 }
1146
1147 /* free memory */
1148 if( linking->haslhs )
1150 if( linking->hasrhs )
1152 SCIPfreeBufferArray(scip, &shift);
1153
1154 return SCIP_OKAY;
1155}
1156
1157/** update penalty parameters lambda
1158 *
1159 * if a linking constraint is violated two times in succession, the corresponding penalty parameter is increased in each block
1160 */
1161static
1163 SCIP* scip, /**< SCIP data structure */
1164 SCIP_HEURDATA* heurdata, /**< heuristic data */
1165 LINKING** linkings, /**< array of linking data structures */
1166 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
1167 int* nviolatedblocksrhs, /**< number of blocks which violate rhs */
1168 int* nviolatedblockslhs, /**< number of blocks which violate lhs */
1169 int nlinking /**< number of linking constraints */
1170 )
1171{
1172 SCIP_VAR* slackvar;
1173 SCIP_Real old_obj;
1174 SCIP_Real new_obj;
1175 int c;
1176 int b;
1177
1178 assert(scip != NULL);
1179 assert(linkings != NULL);
1181
1182 for( c = 0; c < nlinking; c++ )
1183 {
1186
1187 /* skip constraint if it is not violated */
1189 {
1190 linkings[c]->lastviolations = 0; /* reset flag */
1191 continue;
1192 }
1193
1194 /* add number of violated blocks multiplied with parameter "penalty" to lambda (initial value is 1) */
1195 for( b = 0; b < linkings[c]->nblocks; b++ )
1196 {
1197 SCIP* subscip;
1198 subscip = blockproblem[linkings[c]->blocknumbers[b]]->blockscip;
1199 assert(subscip != NULL);
1200
1201 if( linkings[c]->hasrhs && (nviolatedblocksrhs[c] >= 1) && (linkings[c]->lastviolations >= 1) )
1202 {
1203 slackvar = linkings[c]->slacks[b * linkings[c]->nslacksperblock];
1204 old_obj = SCIPvarGetObj(slackvar);
1206
1207 SCIP_CALL( SCIPchgVarObj(subscip, slackvar, new_obj) );
1208 }
1209 if( linkings[c]->haslhs && (nviolatedblockslhs[c] >= 1) && (linkings[c]->lastviolations >= 1) )
1210 {
1211 slackvar = linkings[c]->slacks[b * linkings[c]->nslacksperblock + linkings[c]->nslacksperblock - 1];
1212 old_obj = SCIPvarGetObj(slackvar);
1214
1215 SCIP_CALL( SCIPchgVarObj(subscip, slackvar, new_obj) );
1216 }
1217 }
1218
1219 /* update number of violations in the last iterations */
1220 linkings[c]->lastviolations += 1;
1221 }
1222
1223 return SCIP_OKAY;
1224}
1225
1226/** computes feasible solution from last stored solution for each block and adds it to the solution storage */
1227static
1229 LINKING** linkings, /**< array of linking data structures */
1230 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
1231 int nblocks /**< number of blocks */
1232 )
1233{
1234 SCIP_SOL** sols;
1235 SCIP_SOL* sol; /* solution of block that will be repaired */
1238 SCIP_Real* blockvals;
1239 int nsols;
1240 int nvars;
1241 int b;
1242 int c;
1243 int i;
1244 SCIP_Bool success;
1245
1246 assert(linkings != NULL);
1248
1249 for( b = 0; b < nblocks; b++ )
1250 {
1251 SCIP* subscip;
1252
1253 subscip = blockproblem[b]->blockscip;
1254 nsols = SCIPgetNSols(subscip);
1255
1256 /* no solution in solution candidate storage found */
1257 if( nsols == 0 )
1258 return SCIP_OKAY;
1259
1260 /* take last solution */
1261 sols = SCIPgetSols(subscip);
1262 sol = sols[nsols - 1];
1263
1264 /* copy the solution */
1265 nvars = SCIPgetNVars(subscip);
1266 blockvars = SCIPgetVars(subscip);
1269 SCIP_CALL( SCIPcreateOrigSol(subscip, &newsol, NULL) );
1271
1272 /* correct each coupling constraint:
1273 * lhs <= orig_var - z_r + z_l <= rhs
1274 * adapt slack variables so that constraint is feasible
1275 */
1276 for( c = 0; c < blockproblem[b]->nlinking; c++ )
1277 {
1278 LINKING* linking; /* linking data structure of this constraint */
1279 SCIP_VAR* rvar; /* slack variable z_r */
1280 SCIP_VAR* lvar; /* slack variable z_l */
1281 SCIP_Real rval; /* value of slack variable z_r */
1282 SCIP_Real lval; /* value of slack variable z_l */
1283 SCIP_Real activitycons; /* activity of constraint*/
1284 SCIP_Real activity; /* activity of constraint without slack variables */
1285 SCIP_Real rhs; /* current right hand side */
1286 SCIP_Real lhs; /* current left hand side */
1287
1288 linking = linkings[blockproblem[b]->linkingindices[c]];
1289 rhs = SCIPgetRhsLinear(subscip, blockproblem[b]->linkingconss[c]);
1290 lhs = SCIPgetLhsLinear(subscip, blockproblem[b]->linkingconss[c]);
1291 assert(SCIPisGE(subscip, rhs, lhs));
1292
1293 activitycons = SCIPgetActivityLinear(subscip, blockproblem[b]->linkingconss[c], sol);
1294
1295 /* get slack variables and subtract their value from the activity;
1296 * calculate and set values of slack variables
1297 */
1298 for( i = 0; i < linking->nblocks; i++ )
1299 {
1300 if( linking->blocknumbers[i] == b )
1301 {
1302 if( linking->hasrhs && linking->haslhs )
1303 {
1304 rvar = linking->slacks[2 * i];
1305 lvar = linking->slacks[2 * i + 1];
1306 rval = SCIPgetSolVal(subscip, sol, rvar);
1307 lval = SCIPgetSolVal(subscip, sol, lvar);
1308 activity = activitycons + rval - lval;
1309 SCIP_CALL( SCIPsetSolVal(subscip, newsol, rvar, MAX(0.0, activity - rhs)) );
1310 SCIP_CALL( SCIPsetSolVal(subscip, newsol, lvar, MAX(0.0, lhs - activity)) );
1311 }
1312 else if( linking->hasrhs )
1313 {
1314 rvar = linking->slacks[i];
1315 rval = SCIPgetSolVal(subscip, sol, rvar);
1316 activity = activitycons + rval;
1317 SCIP_CALL( SCIPsetSolVal(subscip, newsol, rvar, MAX(0.0, activity - rhs)) );
1318 }
1319 else /* linking->haslhs */
1320 {
1321 assert(linking->haslhs);
1322 lvar = linking->slacks[i];
1323 lval = SCIPgetSolVal(subscip, sol, lvar);
1324 activity = activitycons - lval;
1325 SCIP_CALL( SCIPsetSolVal(subscip, newsol, lvar, MAX(0.0, lhs - activity)) );
1326 }
1327 break;
1328 }
1329 }
1330 }
1331
1332 SCIPdebugMsg(subscip, "Try adding solution with objective value %.2f\n", SCIPgetSolOrigObj(subscip, newsol));
1333 SCIP_CALL( SCIPaddSolFree(subscip, &newsol, &success) );
1334
1335 if( !success )
1336 SCIPdebugMsg(subscip, "Correcting solution failed\n"); /* maybe not better than old solutions */
1337 else
1338 SCIPdebugMsg(subscip, "Correcting solution successful\n");
1339
1340 SCIPfreeBufferArray(subscip, &blockvals);
1341 }
1342
1343 return SCIP_OKAY;
1344}
1345
1346/** reoptimizes the heuristic solution with original objective function */
1347static
1349 SCIP* scip, /**< SCIP data structure */
1350 SCIP_HEUR* heur, /**< pointer to heuristic */
1351 SCIP_SOL* sol, /**< heuristic solution */
1352 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
1353 int nblocks, /**< number of blockproblems */
1354 SCIP_SOL** newsol, /**< pointer to store improved solution */
1355 SCIP_Bool* success /**< pointer to store whether reoptimization was successful */
1356 )
1357{
1358 SCIP_Real time;
1359 SCIP_Real timesubscip;
1360 SCIP_Bool check;
1361 int b;
1362 int v;
1363
1364 assert(scip != NULL);
1365 assert(heur != NULL);
1366 assert(sol != NULL);
1368
1369 *success = FALSE;
1370 check = FALSE;
1371
1372 /* for each blockproblem:
1373 * - change back to original objective function
1374 * - fix slack variables to zero
1375 * - set limits and solve problem
1376 */
1377 for( b = 0; b < nblocks; b++ )
1378 {
1379 SCIP* subscip;
1381 int nvars;
1382
1383 subscip = blockproblem[b]->blockscip;
1384 timesubscip = SCIPgetTotalTime(subscip);
1385 blockvars = SCIPgetOrigVars(subscip);
1386 nvars = SCIPgetNOrigVars(subscip);
1387
1388 /* in order to change objective function */
1389 SCIP_CALL( SCIPfreeTransform(subscip) );
1390
1391 /* change back to original objective function */
1392 for( v = 0; v < blockproblem[b]->nblockvars; v++ )
1393 {
1394 SCIP_CALL( SCIPchgVarObj(subscip, blockvars[v], blockproblem[b]->origobj[v]) );
1395 }
1396
1397 /* fix slack variables to zero */
1398 for( v = blockproblem[b]->nblockvars; v < nvars; v++ )
1399 {
1400 SCIP_CALL( SCIPchgVarUb(subscip, blockvars[v], 0.0) );
1401 SCIP_CALL( SCIPchgVarLb(subscip, blockvars[v], 0.0) );
1402 }
1403
1404 /* do not abort subproblem on CTRL-C */
1405 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
1406
1407 /* forbid recursive call of heuristics and separators solving sub-SCIPs */
1408 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
1409
1410#ifdef SCIP_DEBUG
1411 /* for debugging, enable full output */
1412 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
1413 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
1414#else
1415 /* disable statistic timing inside sub SCIP and output to console */
1416 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1417 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
1418#endif
1419
1420 /* disable cutting plane separation */
1422
1423 /* disable expensive presolving */
1425
1426 /* disable expensive techniques */
1427 SCIP_CALL( SCIPsetIntParam(subscip, "misc/usesymmetry", 0) );
1428
1429 /* speed up sub-SCIP by not checking dual LP feasibility */
1430 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
1431
1432 /* set limits; do not use more time than the heuristic has already used for first solution */
1433 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
1434 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", 1LL) );
1435 SCIP_CALL( SCIPgetRealParam(subscip, "limits/time", &time) );
1436 if( timesubscip < time - 1.0 )
1437 {
1438 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timesubscip + 1.0) );
1439 }
1440 SCIP_CALL( SCIPtransformProb(subscip) );
1441 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", SCIPgetNSols(subscip) + 1) );
1442
1443 /* reoptimize problem */
1444 SCIP_CALL_ABORT( SCIPsolve(subscip) );
1445
1446 if( SCIPgetNSols(subscip) == 0 )
1447 {
1448 /* we found no solution */
1449 return SCIP_OKAY;
1450 }
1451 else if( SCIPgetStatus(subscip) == SCIP_STATUS_BESTSOLLIMIT || SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL )
1452 {
1453 check = TRUE;
1454 }
1455 }
1456
1457 if( !check )
1458 {
1459 /* we have no better solution */
1460 return SCIP_OKAY;
1461 }
1462
1463 /* create sol of main scip */
1465
1466 /* copy solution to main scip */
1467 for( b = 0; b < nblocks; b++ )
1468 {
1471 SCIP_Real* blocksolvals;
1472 int nblockvars;
1473
1474 /* get solution of block variables (without slack variables) */
1475 blocksol = SCIPgetBestSol(blockproblem[b]->blockscip);
1476 blockvars = SCIPgetOrigVars(blockproblem[b]->blockscip);
1477 nblockvars = blockproblem[b]->nblockvars;
1478
1480 SCIP_CALL( SCIPgetSolVals(blockproblem[b]->blockscip, blocksol, nblockvars, blockvars, blocksolvals) );
1481
1482 for( v = 0; v < nblockvars; v++ )
1483 {
1485
1488 }
1489
1491 }
1492
1493 *success = TRUE;
1494
1495 return SCIP_OKAY;
1496}
1497
1498
1499/* ---------------- Callback methods of event handler ---------------- */
1500
1501/* exec the event handler
1502 *
1503 * interrupt solution process of sub-SCIP if dual bound is greater than zero and a solution is available
1504 */
1505static
1507{
1508 assert(eventhdlr != NULL);
1509 assert(eventdata != NULL);
1511 assert(event != NULL);
1513
1514 SCIPdebugMsg(scip, "dual bound: %.2f\n", SCIPgetDualbound(scip));
1515
1517 {
1518 SCIPdebugMsg(scip, "DPS: interrupt subscip\n");
1520 }
1521
1522 return SCIP_OKAY;
1523}
1524
1525
1526/*
1527 * Callback methods of primal heuristic
1528 */
1529
1530/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1531static
1533{ /*lint --e{715}*/
1534 assert(scip != NULL);
1535 assert(heur != NULL);
1536 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1537
1538 /* call inclusion method of primal heuristic */
1540
1541 return SCIP_OKAY;
1542}
1543
1544/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1545static
1547{ /*lint --e{715}*/
1549
1550 assert(heur != NULL);
1551 assert(scip != NULL);
1552
1553 /* free heuristic data */
1554 heurdata = SCIPheurGetData(heur);
1555 assert(heurdata != NULL);
1556
1558 SCIPheurSetData(heur, NULL);
1559
1560 return SCIP_OKAY;
1561}
1562
1563/** execution method of primal heuristic */
1564static
1566{ /*lint --e{715}*/
1568 SCIP_DECOMP* decomp;
1570 SCIP_VAR** vars;
1571 SCIP_CONS** conss;
1572 SCIP_VAR** sortedvars;
1576 LINKING** linkings;
1577 int* sortedvarlabels;
1578 int* sortedconslabels;
1579 SCIP_EVENTHDLR* eventhdlr; /* event handler */
1580 SCIP_Real memory; /* in MB */
1581 SCIP_Real timelimit;
1582 SCIP_Real allslacksval;
1583 SCIP_Real blocksolval;
1584 SCIP_STATUS status;
1585 SCIP_Bool avoidmemout;
1586 SCIP_Bool disablemeasures;
1587 int maxgraphedge;
1588 int ndecomps;
1589 int nvars;
1590 int nconss;
1591 int nblocks;
1592 SCIP_Bool success;
1593 int b;
1594 int c;
1595 int k;
1596
1597 assert( heur != NULL );
1598 assert( scip != NULL );
1599 assert( result != NULL );
1600
1601 heurdata = SCIPheurGetData(heur);
1602 assert(heurdata != NULL);
1603
1606 linkings = NULL;
1607 eventhdlr = NULL;
1608
1610
1611 /* -------------------------------------------------------------------- */
1612 SCIPdebugMsg(scip, "initialize dps heuristic\n");
1613
1614 /* take the first transformed decomposition */
1615 SCIPgetDecomps(scip, &alldecomps, &ndecomps, FALSE);
1616 if( ndecomps == 0)
1617 return SCIP_OKAY;
1618
1619 decomp = alldecomps[0];
1620 assert(decomp != NULL);
1621 SCIPdebugMsg(scip, "First transformed decomposition is selected\n");
1622
1623 nblocks = SCIPdecompGetNBlocks(decomp);
1624 nconss = SCIPgetNConss(scip);
1626
1627 /* if problem has no constraints, no variables or less than two blocks, return */
1628 if( nconss == 0 || nvars == 0 || nblocks <= 1 )
1629 {
1630 SCIPdebugMsg(scip, "problem has no constraints, no variables or less than two blocks\n");
1631 return SCIP_OKAY;
1632 }
1633
1634 /* estimate required memory for all blocks and terminate if not enough memory is available */
1635 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memory) );
1636 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
1637 if( avoidmemout && (((SCIPgetMemUsed(scip) + SCIPgetMemExternEstim(scip))/1048576.0) * (nblocks/4.0 + 2) >= memory) )
1638 {
1639 SCIPdebugMsg(scip, "The estimated memory usage for %d blocks is too large.\n", nblocks);
1640 return SCIP_OKAY;
1641 }
1642
1643 /* we do not need the block decomposition graph and expensive measures of the decomposition statistics */
1644 SCIP_CALL( SCIPgetIntParam(scip, "decomposition/maxgraphedge", &maxgraphedge) );
1645 if( !SCIPisParamFixed(scip, "decomposition/maxgraphedge") )
1646 {
1647 SCIP_CALL( SCIPsetIntParam(scip, "decomposition/maxgraphedge", 0) );
1648 }
1649 SCIP_CALL( SCIPgetBoolParam(scip, "decomposition/disablemeasures", &disablemeasures) );
1650 if( !SCIPisParamFixed(scip, "decomposition/disablemeasures") )
1651 {
1652 SCIP_CALL( SCIPsetBoolParam(scip, "decomposition/disablemeasures", TRUE) );
1653 }
1654
1656 conss = SCIPgetConss(scip);
1661
1662 /* get labels and sort in increasing order */
1663 SCIPdecompGetVarsLabels(decomp, sortedvars, sortedvarlabels, nvars);
1665 SCIPsortIntPtr(sortedvarlabels, (void**)sortedvars, nvars);
1667
1669 {
1670 /* create new decomposition; don't change the decompositions in the decompstore */
1672
1675 decomp = assigneddecomp;
1676
1677 /* number of blocks can get smaller */
1678 nblocks = SCIPdecompGetNBlocks(decomp);
1679 }
1680 else
1681 {
1682 /* The decomposition statistics were computed during transformation of the decomposition store.
1683 * Since propagators can have changed the number of constraints/variables,
1684 * the statistics are no longer up-to-date and have to be recomputed.
1685 */
1687 nblocks = SCIPdecompGetNBlocks(decomp);
1688 }
1689
1690 /* reset parameters */
1691 SCIP_CALL( SCIPsetIntParam(scip, "decomposition/maxgraphedge", maxgraphedge) );
1692 SCIP_CALL( SCIPsetBoolParam(scip, "decomposition/disablemeasures", disablemeasures) );
1693
1694#ifdef SCIP_DEBUG
1695 char buffer[SCIP_MAXSTRLEN];
1696 SCIPdebugMsg(scip, "DPS used decomposition:\n%s\n", SCIPdecompPrintStats(decomp, buffer));
1697#endif
1698
1699 /* check properties of used decomposition */
1700 if( heurdata->maxlinkscore != 1.0 )
1701 {
1702 SCIP_Real linkscore;
1703 int nlinkconss;
1704
1706
1707 linkscore = (SCIP_Real)nlinkconss / (SCIP_Real)nconss;
1708
1709 if( linkscore > heurdata->maxlinkscore )
1710 {
1711 SCIPdebugMsg(scip, "decomposition has not the required properties\n");
1712 goto TERMINATE;
1713 }
1714 }
1715
1718 nblocks <= 1 )
1719 {
1720 SCIPdebugMsg(scip, "Problem has linking variables or no linking constraints or less than two blocks\n");
1721 goto TERMINATE;
1722 }
1723
1724 /* initialize heurdata */
1725 heurdata->linkingconss = sortedconss;
1726 heurdata->nlinking = SCIPdecompGetNBorderConss(decomp);
1727 heurdata->nblocks = nblocks;
1728
1729 /* allocate memory for blockproblems and initialize partially */
1731 for( b = 0; b < nblocks; b++ )
1732 {
1733 SCIP_CALL( SCIPallocBlockMemory(scip, &(blockproblem[b])) ); /*lint !e866*/
1734 SCIP_CALL( createSubscip(scip, &blockproblem[b]->blockscip) );
1735
1736 SCIP_CALL( SCIPallocBufferArray(scip, &blockproblem[b]->linkingconss, heurdata->nlinking) );
1737 SCIP_CALL( SCIPallocBufferArray(scip, &blockproblem[b]->linkingindices, heurdata->nlinking) );
1738 SCIP_CALL( SCIPallocBufferArray(scip, &blockproblem[b]->slackvars, heurdata->nlinking * 2) ); /* maximum two slacks per linking constraint */
1740 blockproblem[b]->nblockvars = 0;
1741 blockproblem[b]->nlinking = 0;
1742 blockproblem[b]->nslackvars = 0;
1743 }
1744
1745 /* allocate memory for linkings and initialize partially */
1747 for( c = 0; c < heurdata->nlinking; c++ )
1748 {
1749 SCIP_CALL( SCIPallocBlockMemory(scip, &(linkings[c])) ); /*lint !e866*/
1751 SCIP_CALL( SCIPallocBufferArray(scip, &(linkings[c])->slacks, heurdata->nblocks*2) ); /* maximum two slacks per block */
1755
1756 linkings[c]->linkingcons = heurdata->linkingconss[c];
1757 linkings[c]->currentrhs = NULL;
1758 linkings[c]->currentlhs = NULL;
1759 linkings[c]->nblocks = 0;
1760 linkings[c]->nslacks = 0;
1761 linkings[c]->nslacksperblock = 0;
1762 linkings[c]->lastviolations = 0;
1763 linkings[c]->hasrhs = FALSE;
1764 linkings[c]->haslhs = FALSE;
1765 }
1766
1768 if( !success )
1769 {
1770 SCIPdebugMsg(scip, "Create and split problem failed\n");
1771 goto TERMINATE;
1772 }
1773
1774 /* allocate memory for current partition*/
1775 for( c = 0; c < heurdata->nlinking; c++ )
1776 {
1777 if( linkings[c]->hasrhs )
1778 {
1780 }
1781
1782 if( linkings[c]->haslhs )
1783 {
1785 }
1786 }
1787
1788 /* initialize partition */
1790
1791 /* ------------------------------------------------------------------------ */
1792 SCIPdebugMsg(scip, "Start heuristik DPS\n");
1794
1795 for( k = 0; k < heurdata->maxit; k++ )
1796 {
1797 /* do not exceed the timelimit */
1798 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1799 if( (timelimit - SCIPgetSolvingTime(scip)) <= 0 )
1800 goto TERMINATE;
1801
1802 /* solve the subproblems */
1803 allslacksval = 0.0;
1804 for( b = 0; b < heurdata->nblocks; b++ )
1805 {
1806 SCIP* subscip;
1807 subscip = blockproblem[b]->blockscip;
1808
1809 /* update time and memory limit of subproblem */
1810 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
1811
1812 /* create event handler for LP events */
1813 if( k == 0 )
1814 {
1816 if( eventhdlr == NULL )
1817 {
1818 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
1819 return SCIP_PLUGINNOTFOUND;
1820 }
1821 }
1822
1823 /* catch LP events of sub-SCIP */
1824 SCIP_CALL( SCIPtransformProb(subscip) );
1826
1827 SCIPdebugMsg(scip, "Solve blockproblem %d\n", b);
1828 SCIP_CALL_ABORT( SCIPsolve(subscip) );
1829
1830 /* drop LP events of sub-SCIP */
1832
1833 /* get status and objective value if available */
1834 status = SCIPgetStatus(subscip);
1835 if( status == SCIP_STATUS_INFEASIBLE )
1836 {
1837 SCIPdebugMsg(scip, "Subproblem is infeasible\n");
1838 goto TERMINATE;
1839 }
1840 else if( status == SCIP_STATUS_UNBOUNDED )
1841 {
1842 SCIPdebugMsg(scip, "Subproblem is unbounded\n");
1843 goto TERMINATE;
1844 }
1845 else if( SCIPgetNSols(subscip) >= 1 )
1846 {
1848
1849 if( status == SCIP_STATUS_TIMELIMIT && !SCIPisZero(scip, blocksolval) )
1850 {
1851 SCIPdebugMsg(scip, "Subproblem reached timelimit without optimal solution\n");
1852 goto TERMINATE;
1853 }
1854 SCIPdebugMsg(scip, "Solution value: %f\n", blocksolval);
1856 }
1857 else
1858 {
1859 SCIPdebugMsg(scip, "No subproblem solution available\n");
1860 goto TERMINATE;
1861 }
1862 }
1863
1864 /* all slack variables are zero -> we found a feasible solution */
1866 {
1868
1869 SCIPdebugMsg(scip, "Feasible solution found after %i iterations\n", k);
1870
1871 /* create new solution */
1872 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1873 for( b = 0; b < heurdata->nblocks; b++ )
1874 {
1877 SCIP_Real* blocksolvals;
1878 int nblockvars;
1879
1880 /* get solution of block variables (without slack variables) */
1881 blocksol = SCIPgetBestSol(blockproblem[b]->blockscip);
1882 blockvars = SCIPgetOrigVars(blockproblem[b]->blockscip);
1883 nblockvars = blockproblem[b]->nblockvars;
1884
1886 SCIP_CALL( SCIPgetSolVals(blockproblem[b]->blockscip, blocksol, nblockvars, blockvars, blocksolvals) );
1887
1888 for( c = 0; c < nblockvars; c++ )
1889 {
1891
1894 }
1895
1897 }
1898
1899 /* if reoptimization is activated, fix partition and reoptimize with original objective function */
1900 if( heurdata->reoptimize )
1901 {
1905
1906 if( success )
1907 {
1909 if( success )
1910 {
1911 SCIPdebugMsg(scip, "Reoptimizing solution successful\n");
1913 }
1914 }
1915 }
1916
1917 /* if reoptimization is turned off or reoptimization found no solution, try initial solution */
1918 if( *result != SCIP_FOUNDSOL )
1919 {
1920 SCIPdebugMsg(scip, "Solution has value: %.2f\n", SCIPgetSolOrigObj(scip, newsol));
1922 if( success )
1923 {
1924 SCIPdebugMsg(scip, "Solution copy successful\n");
1926 }
1927 }
1928 else
1929 {
1931 }
1932
1933 goto TERMINATE;
1934 }
1935 /* current partition is not feasible:
1936 * - update partition
1937 * - update penalty parameters lambda
1938 * - reuse last solution
1939 */
1940 else
1941 {
1942 int* nviolatedblocksrhs; /* number of blocks which violate rhs for each linking constraint */
1943 int* nviolatedblockslhs; /* number of blocks which violate lhs for each linking constraint */
1944
1949
1950 SCIPdebugMsg(scip, "update partition\n");
1951 for( c = 0; c < heurdata->nlinking; c++ )
1952 {
1954 }
1955
1956 /* in order to change objective function */
1957 for( b = 0; b < heurdata->nblocks; b++ )
1958 {
1959 SCIP_CALL( SCIPfreeTransform(blockproblem[b]->blockscip) );
1960 }
1961
1962 SCIPdebugMsg(scip, "update lambda\n");
1964
1965 if( heurdata->reuse )
1966 {
1967 /* reuse old solution in each block if available */
1969 }
1970
1973 }
1974 }
1975 SCIPdebugMsg(scip, "maximum number of iterations reached\n");
1976
1977 /* ------------------------------------------------------------------------ */
1978 /* free memory */
1979TERMINATE:
1980 if( linkings != NULL )
1981 {
1982 for( c = heurdata->nlinking - 1; c >= 0; c-- )
1983 {
1984 if( linkings[c]->currentlhs != NULL )
1986
1987 if( linkings[c]->currentrhs != NULL )
1989 }
1990
1991 for( c = heurdata->nlinking - 1; c >= 0; c-- )
1992 {
1993 linkings[c]->linkingcons = NULL;
1999 SCIPfreeBlockMemory(scip, &(linkings[c])); /*lint !e866*/
2000 }
2002 }
2003
2004 if( blockproblem != NULL )
2005 {
2006 for( b = nblocks - 1; b >= 0; b-- )
2007 {
2008 SCIPfreeBufferArray(scip, &(blockproblem[b])->origobj);
2009 SCIPfreeBufferArray(scip, &(blockproblem[b])->slackvars);
2010 SCIPfreeBufferArray(scip, &(blockproblem[b])->linkingindices);
2011 SCIPfreeBufferArray(scip, &(blockproblem[b])->linkingconss);
2012 SCIP_CALL( SCIPfree(&blockproblem[b]->blockscip) );
2013 SCIPfreeBlockMemory(scip, &(blockproblem[b])); /*lint !e866*/
2014 }
2016 }
2017
2018 if( assigneddecomp != NULL )
2020
2021 if( sortedconslabels != NULL )
2023
2024 if( sortedvarlabels != NULL )
2026
2027 if( sortedconss != NULL )
2029
2030 if( sortedvars != NULL )
2031 SCIPfreeBufferArray(scip, &sortedvars);
2032
2033 SCIPdebugMsg(scip, "Leave DPS heuristic\n");
2034
2035 return SCIP_OKAY;
2036}
2037
2038
2039/*
2040 * primal heuristic specific interface methods
2041 */
2042
2043/** creates the dps primal heuristic and includes it in SCIP */
2045 SCIP* scip /**< SCIP data structure */
2046 )
2047{
2049 SCIP_HEUR* heur;
2050
2051 /* create dps primal heuristic data */
2053
2054 heur = NULL;
2055
2056 /* include primal heuristic */
2060
2061 assert(heur != NULL);
2062
2063 /* set non fundamental callbacks via setter functions */
2066
2067 /* add dps primal heuristic parameters */
2068 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxiterations",
2069 "maximal number of iterations", &heurdata->maxit, FALSE, DEFAULT_MAXIT, 1, INT_MAX, NULL, NULL) );
2070
2071 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxlinkscore",
2072 "maximal linking score of used decomposition (equivalent to percentage of linking constraints)",
2073 &heurdata->maxlinkscore, FALSE, 1.0, 0.0, 1.0, NULL, NULL) );
2074
2075 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/penalty",
2076 "multiplier for absolute increase of penalty parameters (0: no increase)",
2077 &heurdata->penalty, FALSE, DEFAULT_PENALTY, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2078
2079 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reoptimize",
2080 "should the problem get reoptimized with the original objective function?", &heurdata->reoptimize, FALSE, FALSE, NULL, NULL) );
2081
2082 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reuse",
2083 "should solutions get reused in subproblems?", &heurdata->reuse, FALSE, FALSE, NULL, NULL) );
2084
2085 return SCIP_OKAY;
2086}
SCIP_VAR ** b
#define SCIP_MAXSTRLEN
Definition def.h:302
#define SCIP_REAL_MAX
Definition def.h:187
#define SCIP_Real
Definition def.h:186
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIP_CALL_ABORT(x)
Definition def.h:367
#define SCIPABORT()
Definition def.h:360
#define SCIP_CALL(x)
Definition def.h:388
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid)
Definition scip_copy.c:1591
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition scip_copy.c:3292
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition scip_copy.c:711
SCIP_RETCODE SCIPcomputeDecompConsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition scip_dcmp.c:344
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition scip_dcmp.c:262
SCIP_RETCODE SCIPdecompSetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition dcmp.c:123
int SCIPdecompGetNBlocks(SCIP_DECOMP *decomp)
Definition dcmp.c:278
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition dcmp.c:172
SCIP_RETCODE SCIPdecompCreate(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition dcmp.c:56
SCIP_RETCODE SCIPdecompGetVarsSize(SCIP_DECOMP *decomp, int *varssize, int nlabels)
Definition dcmp.c:315
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition scip_dcmp.c:1135
char * SCIPdecompPrintStats(SCIP_DECOMP *decomp, char *strbuf)
Definition dcmp.c:454
SCIP_RETCODE SCIPdecompGetConssSize(SCIP_DECOMP *decomp, int *consssize, int nlabels)
Definition dcmp.c:348
void SCIPdecompGetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition dcmp.c:197
void SCIPdecompFree(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem)
Definition dcmp.c:98
int SCIPdecompGetNBorderVars(SCIP_DECOMP *decomp)
Definition dcmp.c:378
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition dcmp.c:148
SCIP_Bool SCIPdecompUseBendersLabels(SCIP_DECOMP *decomp)
Definition dcmp.c:268
int SCIPdecompGetNBorderConss(SCIP_DECOMP *decomp)
Definition dcmp.c:393
SCIP_Bool SCIPdecompIsOriginal(SCIP_DECOMP *decomp)
Definition dcmp.c:245
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition scip_prob.c:1668
const char * SCIPgetProbName(SCIP *scip)
Definition scip_prob.c:1067
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition scip_prob.c:2405
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition scip_prob.c:3088
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
int SCIPgetNConss(SCIP *scip)
Definition scip_prob.c:3042
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
int SCIPgetNOrigVars(SCIP *scip)
Definition scip_prob.c:2432
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition scip_prob.c:117
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
Definition scip_prob.c:2685
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3058
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3211
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3024
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3373
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition scip_param.c:250
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition scip_param.c:219
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 SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition scip_param.c:545
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 SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition scip_param.c:487
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition scip_param.c:883
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition scip_param.c:307
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition scip_param.c:932
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition scip_param.c:269
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition scip_param.c:429
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition scip_param.c:603
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition scip_param.c:958
SCIP_RETCODE SCIPincludeHeurDps(SCIP *scip)
Definition heur_dps.c:2044
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4180
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition scip_cons.c:2567
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition cons.c:8347
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition cons.c:8108
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition cons.c:8257
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition cons.c:8287
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition cons.c:8217
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition scip_cons.c:2523
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition cons.c:8277
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition cons.c:8149
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition cons.c:8307
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8088
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition cons.c:8337
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1119
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition cons.c:8267
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition cons.c:8357
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_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition event.c:1030
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition scip_event.c:286
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition scip_event.c:320
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition heur.c:1361
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 SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1450
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition heur.c:1371
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition scip_mem.c:126
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition scip_mem.c:100
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition scip_mem.h:132
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2313
SCIP_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition scip_sol.c:2999
int SCIPgetNSols(SCIP *scip)
Definition scip_sol.c:2214
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition scip_sol.c:565
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition scip_sol.c:1398
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition scip_sol.c:1263
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition scip_sol.c:2263
SCIP_RETCODE SCIPtrySolFree(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:3193
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1444
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1221
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1361
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition scip_solve.c:367
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPgetTotalTime(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:4676
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17360
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:4766
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17748
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:17910
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1248
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition scip_var.c:1527
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition var.c:17726
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:17900
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition scip_var.c:194
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition scip_var.c:4513
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortIntIntReal(int *intarray1, int *intarray2, SCIP_Real *realarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
static SCIP_RETCODE updateLambda(SCIP *scip, SCIP_HEURDATA *heurdata, LINKING **linkings, BLOCKPROBLEM **blockproblem, int *nviolatedblocksrhs, int *nviolatedblockslhs, int nlinking)
Definition heur_dps.c:1162
static SCIP_RETCODE initCurrent(SCIP *scip, LINKING **linkings, BLOCKPROBLEM **blockproblem, int nlinking, SCIP_Bool *success)
Definition heur_dps.c:862
static SCIP_RETCODE assignLinking(SCIP *scip, SCIP_DECOMP *newdecomp, SCIP_VAR **vars, SCIP_CONS **conss, int *varlabels, int *conslabels, int nvars, int nconss, int nlinkvars)
Definition heur_dps.c:137
static SCIP_RETCODE roundPartition(SCIP *scip, LINKING *linking, BLOCKPROBLEM **blockproblem, SCIP_Bool roundbyrhs)
Definition heur_dps.c:701
#define HEUR_TIMING
Definition heur_dps.c:66
#define HEUR_FREQOFS
Definition heur_dps.c:64
static SCIP_RETCODE reoptimize(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, BLOCKPROBLEM **blockproblem, int nblocks, SCIP_SOL **newsol, SCIP_Bool *success)
Definition heur_dps.c:1348
static SCIP_RETCODE updatePartition(SCIP *scip, LINKING *linking, BLOCKPROBLEM **blockproblem, int *nviolatedblocksrhs, int *nviolatedblockslhs, int iteration)
Definition heur_dps.c:959
#define HEUR_DESC
Definition heur_dps.c:60
static SCIP_RETCODE createSubscip(SCIP *scip, SCIP **subscip)
Definition heur_dps.c:211
#define DEFAULT_MAXIT
Definition heur_dps.c:69
#define HEUR_DISPCHAR
Definition heur_dps.c:61
#define HEUR_MAXDEPTH
Definition heur_dps.c:65
#define HEUR_PRIORITY
Definition heur_dps.c:62
static SCIP_RETCODE reuseSolution(LINKING **linkings, BLOCKPROBLEM **blockproblem, int nblocks)
Definition heur_dps.c:1228
#define HEUR_NAME
Definition heur_dps.c:59
static SCIP_RETCODE createBlockproblem(SCIP *scip, BLOCKPROBLEM *blockproblem, LINKING **linkings, SCIP_CONS **conss, SCIP_VAR **vars, int nconss, int nvars, SCIP_CONS **linkingconss, int nlinking, int blocknumber, SCIP_Bool *success)
Definition heur_dps.c:337
#define DEFAULT_PENALTY
Definition heur_dps.c:70
#define EVENTHDLR_DESC
Definition heur_dps.c:74
static SCIP_RETCODE createAndSplitProblem(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_DECOMP *decomp, BLOCKPROBLEM **blockproblem, LINKING **linkings, SCIP_VAR **vars, SCIP_CONS **conss, SCIP_Bool *success)
Definition heur_dps.c:648
#define HEUR_FREQ
Definition heur_dps.c:63
#define HEUR_USESSUBSCIP
Definition heur_dps.c:67
#define EVENTHDLR_NAME
Definition heur_dps.c:73
static SCIP_RETCODE copyToSubscip(SCIP *scip, SCIP *subscip, const char *name, SCIP_VAR **vars, SCIP_CONS **conss, SCIP_HASHMAP *varsmap, SCIP_HASHMAP *conssmap, int nvars, int nconss, SCIP_Bool *success)
Definition heur_dps.c:258
dynamic partition search
int c
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
static SCIP_VAR ** vars
#define NULL
Definition lpi_spx1.cpp:161
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:132
SCIP_Real SCIPconsGetLhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
SCIP_RETCODE SCIPgetConsVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int varssize, SCIP_Bool *success)
SCIP_Real SCIPconsGetRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition misc_linear.c:48
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
public methods for decompositions
public methods for primal heuristics
#define SCIPerrorMessage
Definition pub_message.h:64
#define SCIPdebugPrintCons(x, y, z)
public data structures and miscellaneous methods
public methods for constraint handler plugins and constraints
public methods for decompositions
general public methods
public methods for primal heuristic plugins and divesets
public methods for memory management
public methods for message handling
public methods for SCIP parameter handling
public methods for global and local (sub)problems
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
default SCIP plugins
SCIP * blockscip
Definition heur_dps.c:96
int * linkingindices
Definition heur_dps.c:99
SCIP_CONS ** linkingconss
Definition heur_dps.c:98
SCIP_VAR ** slackvars
Definition heur_dps.c:97
SCIP_Real * origobj
Definition heur_dps.c:103
SCIP_CONS * linkingcons
Definition heur_dps.c:110
int nslacksperblock
Definition heur_dps.c:120
SCIP_Bool haslhs
Definition heur_dps.c:123
SCIP_Real * maxactivity
Definition heur_dps.c:114
SCIP_Bool hasrhs
Definition heur_dps.c:122
SCIP_Real * currentrhs
Definition heur_dps.c:115
SCIP_VAR ** slacks
Definition heur_dps.c:112
SCIP_Real * minactivity
Definition heur_dps.c:113
int * blocknumbers
Definition heur_dps.c:117
SCIP_Real * currentlhs
Definition heur_dps.c:116
int nslacks
Definition heur_dps.c:119
int lastviolations
Definition heur_dps.c:121
int nblocks
Definition heur_dps.c:118
SCIP_CONS ** blockconss
Definition heur_dps.c:111
#define MAX(x, y)
Definition tclique_def.h:92
#define SCIP_DECOMP_LINKVAR
Definition type_dcmp.h:44
#define SCIP_DECOMP_LINKCONS
Definition type_dcmp.h:45
struct SCIP_EventData SCIP_EVENTDATA
Definition type_event.h:173
#define SCIP_DECL_EVENTEXEC(x)
Definition type_event.h:253
#define SCIP_EVENTTYPE_LPSOLVED
Definition type_event.h:101
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:96
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:76
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:104
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:162
@ SCIP_VERBLEVEL_FULL
@ SCIP_PARAMSETTING_OFF
@ SCIP_PARAMSETTING_FAST
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_FOUNDSOL
Definition type_result.h:56
@ SCIP_PLUGINNOTFOUND
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STATUS_OPTIMAL
Definition type_stat.h:61
@ SCIP_STATUS_BESTSOLLIMIT
Definition type_stat.h:57
@ SCIP_STATUS_UNBOUNDED
Definition type_stat.h:63
@ SCIP_STATUS_TIMELIMIT
Definition type_stat.h:51
@ SCIP_STATUS_INFEASIBLE
Definition type_stat.h:62
enum SCIP_Status SCIP_STATUS
Definition type_stat.h:67
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71
@ SCIP_VARSTATUS_NEGATED
Definition type_var.h:55