Scippy

SCIP

Solving Constraint Integer Programs

heur_padm.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_padm.c
26 * @brief PADM primal heuristic
27 * @author Dieter Weninger
28 * @author Katrin Halbig
29 *
30 * Primal heuristic based on ideas published in the papers
31 * "A Decomposition Heuristic for Mixed-Integer Supply Chain Problems" by Martin Schmidt, Lars Schewe, and Dieter Weninger,
32 * and "Exploiting user-supplied Decompositions inside Heuristics" by Katrin Halbig, Adrian Göß and Dieter Weninger.
33 *
34 * The penalty alternating direction method (PADM) heuristic is a construction heuristic which additionally needs a
35 * user decomposition with linking variables only.
36 *
37 * PADM splits the problem into several sub-SCIPs according to the decomposition, whereby the linking variables get
38 * copied and the difference is penalized. Then the sub-SCIPs are solved on an alternating basis until they arrive at
39 * the same values of the linking variables (ADM-loop). If they don't reconcile after a couple of iterations,
40 * the penalty parameters are increased (penalty-loop) and the sub-SCIPs are solved again on an alternating basis.
41 */
42
43/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44
45#include <assert.h>
46#include <string.h>
47
49#include "scip/cons_linear.h"
50#include "scip/debug.h"
51#include "scip/heur_padm.h"
52#include "scip/heuristics.h"
53#include "scip/pub_cons.h"
54#include "scip/pub_tree.h"
55#include "scip/pub_heur.h"
56#include "scip/pub_message.h"
57#include "scip/pub_misc.h"
59#include "scip/pub_sol.h"
60#include "scip/pub_var.h"
61#include "scip/scipdefplugins.h"
62#include "scip/scip_branch.h"
63#include "scip/scip_cons.h"
64#include "scip/scip_copy.h"
65#include "scip/scip_dcmp.h"
66#include "scip/scip_general.h"
67#include "scip/scip_heur.h"
68#include "scip/scip_lp.h"
69#include "scip/scip_mem.h"
70#include "scip/scip_message.h"
71#include "scip/scip_nodesel.h"
72#include "scip/scip_numerics.h"
73#include "scip/scip_param.h"
74#include "scip/scip_prob.h"
76#include "scip/scip_sol.h"
77#include "scip/scip_solve.h"
79#include "scip/scip_table.h"
80#include "scip/scip_timing.h"
81#include "scip/scip_tree.h"
82#include "scip/scip_var.h"
83
84#define HEUR_NAME "padm"
85#define HEUR_DESC "penalty alternating direction method primal heuristic"
86#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
87#define HEUR_PRIORITY 70000
88#define HEUR_FREQ 0
89#define HEUR_FREQOFS 0
90#define HEUR_MAXDEPTH -1
91#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_AFTERNODE
92#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
93
94#define COUPLINGSIZE 3
95#define DEFAULT_MINNODES 50LL
96#define DEFAULT_MAXNODES 5000LL
97#define DEFAULT_NODEFAC 0.8
98#define DEFAULT_ADMIT 4
99#define DEFAULT_PENALTYIT 100
100#define DEFAULT_GAP 2.0
101
102/*
103 * Data structures
104 */
105
106/** data related to one problem (see below) */
107typedef struct Problem PROBLEM;
108
109/** data related to one block */
110typedef struct Block
111{
112 PROBLEM* problem; /**< the problem this block belongs to */
113 SCIP* subscip; /**< sub-SCIP representing this block */
114 int number; /**< component number */
115 SCIP_VAR** subvars; /**< variables belonging to this block (without slack variables) */
116 int nsubvars; /**< number of variables belonging to this block (without slack variables) */
117 SCIP_VAR** slackspos; /**< positive slack variables */
118 SCIP_VAR** slacksneg; /**< negative slack variables */
119 SCIP_CONS** couplingcons; /**< coupling contraints */
120 int ncoupling; /**< number of coupling contraints (equal to positive/negative slack variables) */
121 SCIP_Real size; /**< share of total problem */
123
124/** data related to one problem */
125struct Problem
126{
127 SCIP* scip; /**< the SCIP instance this problem belongs to */
128 char* name; /**< name of the problem */
129 BLOCK* blocks; /**< blocks into which the problem will be divided */
130 int nblocks; /**< number of blocks */
131};
132
133/** set data structure */
134typedef struct set
135{
136 int size; /**< size of the set */
137 int* indexes; /**< set of indexes */
139
140/** data of one linking variable related to one block */
141typedef struct blockinfo
142{
143 int block; /**< index of this block */
144 int otherblock; /**< index of the other connected block */
145 int linkvaridx; /**< linking variable index */
146 SCIP_Real linkvarval; /**< value of linking variable */
147 SCIP_VAR* linkvar; /**< linking variable */
148 SCIP_Real slackposobjcoeff; /**< penalty coefficient of positive slack variable */
149 SCIP_VAR* slackposvar; /**< positive slack variable */
150 SCIP_Real slacknegobjcoeff; /**< penalty coefficient of negative slack variable */
151 SCIP_VAR* slacknegvar; /**< negative slack variable */
152 SCIP_CONS* couplingCons; /**< coupling contraint (equation) */
154
155/** returns TRUE iff both keys are equal */
156static
158{ /*lint --e{715}*/
159 BLOCKINFO* binfo1;
160 BLOCKINFO* binfo2;
161
162 binfo1 = (BLOCKINFO*) key1;
163 binfo2 = (BLOCKINFO*) key2;
164
165 if( binfo1->block != binfo2->block || binfo1->otherblock != binfo2->otherblock ||
166 binfo1->linkvaridx != binfo2->linkvaridx )
167 return FALSE;
168
169 return TRUE;
170}
171
172/** returns the hash value of the key */
173static
174SCIP_DECL_HASHKEYVAL(indexesHashval)
175{ /*lint --e{715}*/
176 BLOCKINFO* binfo;
177 binfo = (BLOCKINFO*) key;
178
179 return SCIPhashFour(SCIPrealHashCode((double)binfo->block), SCIPrealHashCode((double)binfo->otherblock),
180 SCIPrealHashCode((double)binfo->linkvaridx), SCIPrealHashCode((double)binfo->linkvaridx));
181}
182
183/** primal heuristic data */
184struct SCIP_HeurData
185{
186 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in all subproblems */
187 SCIP_Longint minnodes; /**< minimum number of nodes to regard in one subproblem */
188 int admiterations; /**< maximal number of ADM iterations in each penalty loop */
189 int penaltyiterations; /**< maximal number of penalty iterations */
190 int timing; /**< should the heuristic run before or after the processing of the node?
191 (0: before, 1: after, 2: both) */
192 SCIP_Real nodefac; /**< factor to control nodelimits of subproblems */
193 SCIP_Real gap; /**< mipgap at start */
194 SCIP_Bool reoptimize; /**< should the problem get reoptimized with the original objective function? */
195 SCIP_Bool scaling; /**< enable sigmoid rescaling of penalty parameters */
196 SCIP_Bool assignlinking; /**< should linking constraints be assigned? */
197 SCIP_Bool original; /**< should the original problem be used? */
198};
199
200/*
201 * Local methods
202 */
203
204/** initializes one block */
205static
207 PROBLEM* problem /**< problem structure */
208 )
209{
210 BLOCK* block;
211
212 assert(problem != NULL);
213 assert(problem->scip != NULL);
214
215 block = &problem->blocks[problem->nblocks];
216
217 block->problem = problem;
218 block->subscip = NULL;
219 block->subvars = NULL;
220 block->nsubvars = 0;
221 block->number = problem->nblocks;
222 block->slackspos = NULL;
223 block->slacksneg = NULL;
224 block->couplingcons = NULL;
225 block->ncoupling = 0;
226 block->size = 0;
227
228 ++problem->nblocks;
229
230 return SCIP_OKAY;
231}
232
233/** frees component structure */
234static
236 BLOCK* block /**< block structure */
237 )
238{
239 assert(block != NULL);
240
241 block->ncoupling = 0;
242
243 if( block->subvars != NULL )
244 {
245 SCIPfreeBufferArray(block->problem->scip, &(block->subvars));
246 }
247
248 if( block->subscip != NULL )
249 {
250 SCIP_CALL( SCIPfree(&block->subscip) );
251 }
252
253 return SCIP_OKAY;
254}
255
256/** initializes subproblem structure */
257static
259 SCIP* scip, /**< SCIP data structure */
260 PROBLEM** problem, /**< pointer to problem structure */
261 int nblocks /**< number of blocks */
262 )
263{
264 char name[SCIP_MAXSTRLEN];
265
266 assert(scip != NULL);
267 assert(problem != NULL);
268
270 assert(*problem != NULL);
271
272 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s", SCIPgetProbName(scip));
273
274 SCIP_CALL( SCIPduplicateMemoryArray(scip, &(*problem)->name, name, strlen(name) + 1) );
275
276 SCIPdebugMessage("initialized problem <%s>\n", (*problem)->name);
277
278 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*problem)->blocks, nblocks) );
279
280 (*problem)->scip = scip;
281 (*problem)->nblocks = 0;
282
283 return SCIP_OKAY;
284}
285
286/** frees subproblem structure */
287static
289 PROBLEM** problem, /**< pointer to problem to free */
290 int nblocks /**< number of blocks in decomposition */
291 )
292{
293 SCIP* scip;
294 int c;
295
296 assert(problem != NULL);
297 assert(*problem != NULL);
298
299 scip = (*problem)->scip;
300 assert(scip != NULL);
301
302 /* free all blocks */
303 for( c = nblocks - 1; c >= 0; --c )
304 {
305 SCIP_CALL( freeBlock(&(*problem)->blocks[c]) );
306 }
307 if( (*problem)->blocks != NULL )
308 {
309 SCIPfreeBlockMemoryArray(scip, &(*problem)->blocks, nblocks);
310 }
311
312 /* free problem name */
313 SCIPfreeMemoryArray(scip, &(*problem)->name);
314
315 /* free PROBLEM struct and set the pointer to NULL */
316 SCIPfreeBlockMemory(scip, problem);
317 *problem = NULL;
318
319 return SCIP_OKAY;
320}
321
322/** creates a sub-SCIP for the given variables and constraints */
323static
325 SCIP* scip, /**< main SCIP data structure */
326 SCIP** subscip /**< pointer to store created sub-SCIP */
327 )
328{
329 SCIP_Real infvalue;
330
331 /* create a new SCIP instance */
332 SCIP_CALL( SCIPcreate(subscip) );
333
335
336 /* copy value for infinity */
337 SCIP_CALL( SCIPgetRealParam(scip, "numerics/infinity", &infvalue) );
338 SCIP_CALL( SCIPsetRealParam(*subscip, "numerics/infinity", infvalue) );
339
340 SCIP_CALL( SCIPcopyLimits(scip, *subscip) );
341
342 /* avoid recursive calls */
343 SCIP_CALL( SCIPsetSubscipsOff(*subscip, TRUE) );
344
345 /* disable cutting plane separation */
347
348 /* disable expensive presolving */
350
351 /* disable expensive techniques */
352 SCIP_CALL( SCIPsetIntParam(*subscip, "misc/usesymmetry", 0) );
353
354 /* do not abort subproblem on CTRL-C */
355 SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/catchctrlc", FALSE) );
356
357#ifdef SCIP_DEBUG
358 /* for debugging, enable full output */
359 SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 5) );
360 SCIP_CALL( SCIPsetIntParam(*subscip, "display/freq", 100000000) );
361#else
362 /* disable statistic timing inside sub SCIP and output to console */
363 SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 0) );
364 SCIP_CALL( SCIPsetBoolParam(*subscip, "timing/statistictiming", FALSE) );
365#endif
366
367 return SCIP_OKAY;
368}
369
370/** copies the given constraints and the corresponding variables to the given sub-SCIP */
371static
373 SCIP* scip, /**< source SCIP */
374 SCIP* subscip, /**< target SCIP */
375 const char* name, /**< name for copied problem */
376 SCIP_CONS** conss, /**< constraints to copy */
377 SCIP_HASHMAP* varmap, /**< hashmap used for the copy process of variables */
378 SCIP_HASHMAP* consmap, /**< hashmap used for the copy process of constraints */
379 int nconss, /**< number of constraints to copy */
380 SCIP_Bool useorigprob, /**< do we use the original problem? */
381 SCIP_Bool* success /**< pointer to store whether copying was successful */
382 )
383{
384 SCIP_CONS* newcons;
385 int i;
386
387 assert(scip != NULL);
388 assert(subscip != NULL);
389 assert(conss != NULL);
390 assert(consmap != NULL);
391 assert(success != NULL);
392
393 *success = TRUE;
394 newcons = NULL;
395
396 /* create problem in sub-SCIP */
397 SCIP_CALL( SCIPcopyProb(scip, subscip, varmap, consmap, FALSE, name) );
398
399 /* copy constraints */
400 for( i = 0; i < nconss; ++i )
401 {
402 assert(conss[i] != NULL);
403
404 /* do not check this if we use the original problem
405 * Since constraints can be deleted etc. during presolving, these assertions would fail.
406 */
407 if( !useorigprob )
408 {
409 assert(!SCIPconsIsModifiable(conss[i]));
410 assert(SCIPconsIsActive(conss[i]));
411 assert(!SCIPconsIsDeleted(conss[i]));
412 }
413
414 /* copy the constraint */
415 SCIP_CALL( SCIPgetConsCopy(scip, subscip, conss[i], &newcons, SCIPconsGetHdlr(conss[i]), varmap, consmap, NULL,
416 SCIPconsIsInitial(conss[i]), SCIPconsIsSeparated(conss[i]), SCIPconsIsEnforced(conss[i]),
417 SCIPconsIsChecked(conss[i]), SCIPconsIsPropagated(conss[i]), FALSE, FALSE,
418 SCIPconsIsDynamic(conss[i]), SCIPconsIsRemovable(conss[i]), FALSE, FALSE, success) );
419
420 /* abort if constraint was not successfully copied */
421 if( !(*success) || newcons == NULL)
422 return SCIP_OKAY;
423
424 SCIP_CALL( SCIPaddCons(subscip, newcons) );
425 SCIP_CALL( SCIPreleaseCons(subscip, &newcons) );
426 }
427
428 return SCIP_OKAY;
429}
430
431/** creates the subscip for a given block */
432static
434 BLOCK* block, /**< block structure */
435 SCIP_HASHMAP* varmap, /**< variable hashmap used to improve performance */
436 SCIP_HASHMAP* consmap, /**< constraint hashmap used to improve performance */
437 SCIP_CONS** conss, /**< constraints contained in this block */
438 int nconss, /**< number of constraints contained in this block */
439 SCIP_Bool useorigprob, /**< do we use the original problem? */
440 SCIP_Bool* success /**< pointer to store whether the copying process was successful */
441 )
442{
443 char name[SCIP_MAXSTRLEN];
444 PROBLEM* problem;
445 SCIP* scip;
446 SCIP_VAR** subscipvars;
447 int nsubscipvars;
448 int i;
449
450 assert(block != NULL);
451 assert(varmap != NULL);
452 assert(consmap != NULL);
453 assert(conss != NULL);
454 assert(success != NULL);
455
456 problem = block->problem;
457 assert(problem != NULL);
458
459 scip = problem->scip;
460 assert(scip != NULL);
461
462 (*success) = TRUE;
463
464 SCIP_CALL( createSubscip(scip, &block->subscip) );
465
466 if( block->subscip != NULL )
467 {
468 /* get name of the original problem and add "comp_nr" */
469 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", problem->name, block->number);
470
471 SCIP_CALL( copyToSubscip(scip, block->subscip, name, conss, varmap, consmap, nconss, useorigprob, success) );
472
473 if( !(*success) )
474 {
475 SCIP_CALL( SCIPfree(&block->subscip) );
476 block->subscip = NULL;
477 }
478 else
479 {
480 /* save variables of subscip (without slack variables) */
481 nsubscipvars = SCIPgetNOrigVars(block->subscip);
482 subscipvars = SCIPgetOrigVars(block->subscip);
483 SCIP_CALL( SCIPallocBufferArray(scip, &(block->subvars), nsubscipvars) );
484 block->nsubvars = nsubscipvars;
485 for( i = 0; i < nsubscipvars; i++ )
486 block->subvars[i] = subscipvars[i];
487
488 /* calculate size of sub-SCIP with focus on the number of integer variables
489 * we use this value to determine the nodelimit
490 */
493 }
494 }
495 else
496 (*success) = FALSE;
497
498 SCIPdebugMsg(scip, "created subscip of block %d\n", block->number);
499
500 return SCIP_OKAY;
501}
502
503/** creates problem structure and split it into blocks */
504static
506 SCIP* scip, /**< SCIP data structure */
507 SCIP_CONS** sortedconss, /**< array of (checked) constraints sorted by blocks */
508 int nconss, /**< number of constraints */
509 int* consssize, /**< number of constraints per block (and border at index 0) */
510 int nblocks, /**< number of blocks */
511 PROBLEM** problem, /**< pointer to store problem structure */
512 SCIP_Bool useorigprob, /**< do we use the original problem? */
513 SCIP_Bool* success /**< pointer to store whether the process was successful */
514 )
515{
516 BLOCK* block;
517 SCIP_HASHMAP* varmap;
518 SCIP_HASHMAP* consmap;
519 SCIP_CONS** blockconss;
520 int nhandledconss;
521 int nblockconss;
522 int b;
523
524 (*success) = TRUE;
525
526 /* init subproblem data structure */
527 SCIP_CALL( initProblem(scip, problem, nblocks) );
528 assert((*problem)->blocks != NULL);
529
530 /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */
531 SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), nconss) );
532
533 for( b = 0; b < nblocks; b++ )
534 {
535 SCIP_CALL( initBlock(*problem) );
536 }
537
538 /* loop over all blocks and create subscips */
539 nhandledconss = 0;
540 for( b = 0; b < nblocks; b++ )
541 {
542 block = &(*problem)->blocks[b];
543
545
546 /* get block constraints */
547 blockconss = &(sortedconss[nhandledconss]);
548 nblockconss = consssize[b + 1];
549
550 /* build subscip for block */
551 SCIP_CALL( blockCreateSubscip(block, varmap, consmap, blockconss, nblockconss, useorigprob, success) );
552
553 SCIPhashmapFree(&varmap);
554 nhandledconss += nblockconss;
555
556 if( !(*success) )
557 break;
558 }
559
560 SCIPhashmapFree(&consmap);
561
562 if( !(*success) )
563 {
564 /* free subproblem data structure since not all blocks could be copied */
565 SCIP_CALL( freeProblem(problem, nblocks) );
566 }
567
568 return SCIP_OKAY;
569}
570
571/** copies labels to newdecomp and assigns linking constraints if possible*/
572static
574 SCIP* scip, /**< SCIP data structure */
575 SCIP_DECOMP* newdecomp, /**< decomposition with (partially) assigned linking constraints */
576 SCIP_VAR** vars, /**< array of variables */
577 SCIP_CONS** sortedconss, /**< sorted array of constraints */
578 int* varlabels, /**< array of variable labels */
579 int* conslabels, /**< sorted array of constraint labels */
580 int nvars, /**< number of variables */
581 int nconss, /**< number of constraints */
582 int nlinkconss /**< number of linking constraints */
583 )
584{
585 assert(scip != NULL);
586 assert(vars != NULL);
587 assert(sortedconss != NULL);
588 assert(varlabels != NULL);
589 assert(conslabels != NULL);
590
591 /* copy the labels */
592 SCIP_CALL( SCIPdecompSetVarsLabels(newdecomp, vars, varlabels, nvars) );
593 SCIP_CALL( SCIPdecompSetConsLabels(newdecomp, sortedconss, conslabels, nconss) );
594
595 SCIPdebugMsg(scip, "try to assign %d linking constraints\n", nlinkconss);
596
597 /* reassign linking constraints */
598 SCIP_CALL( SCIPassignDecompLinkConss(scip, newdecomp, &sortedconss[0], nlinkconss, NULL) );
599
600 SCIP_CALL( SCIPcomputeDecompVarsLabels(scip, newdecomp, sortedconss, nconss) );
601
603
604 SCIPdecompGetConsLabels(newdecomp, sortedconss, conslabels, nconss);
605 SCIPdecompGetVarsLabels(newdecomp, vars, varlabels, nvars);
606
607 SCIPsortIntPtr(conslabels, (void**)sortedconss, nconss);
608
609 return SCIP_OKAY;
610}
611
612/** computes feasible solution from last stored solution of the block*/
613static
615 SCIP* subscip, /**< SCIP data structure */
616 BLOCK* block /**< block structure*/
617 )
618{
619 SCIP_SOL** sols;
620 SCIP_SOL* sol; /* solution of block that will be repaired */
621 SCIP_SOL* newsol;
622 SCIP_VAR** blockvars;
623 SCIP_VAR** consvars;
624 SCIP_Real* blockvals;
625 int nsols;
626 int nvars;
627 int c;
628 SCIP_Bool success;
629
630 assert(subscip != NULL);
631 assert(block != NULL);
632
633 nsols = SCIPgetNSols(subscip);
634
635 /* no solution in solution candidate storage found */
636 if( nsols == 0 )
637 return SCIP_OKAY;
638
639 SCIP_CALL( SCIPallocBufferArray(subscip, &consvars, COUPLINGSIZE) );
640
641 sols = SCIPgetSols(subscip);
642 sol = sols[nsols - 1];
643
644 /* copy the solution */
645 nvars = SCIPgetNVars(subscip);
646 blockvars = SCIPgetVars(subscip);
647 SCIP_CALL( SCIPallocBufferArray(subscip, &blockvals, nvars) );
648 SCIP_CALL( SCIPgetSolVals(subscip, sol, nvars, blockvars, blockvals) );
649 SCIP_CALL( SCIPcreateOrigSol(subscip, &newsol, NULL) );
650 SCIP_CALL( SCIPsetSolVals(subscip, newsol, nvars, blockvars, blockvals) );
651
652 /* correct each coupling constraint;
653 * orig_var + slackpos - slackneg == side
654 * adapt slack variables so that constraint is feasible */
655 for( c = 0; c < block->ncoupling; c++ )
656 {
657 SCIP_Real solval; /* old solution values of variables; [0] original variable, [1] slackpos, [2] slackneg */
658 SCIP_Real side; /* current right hand side */
659 SCIP_Real diff;
660
661 SCIP_CALL( SCIPgetConsVars(subscip, block->couplingcons[c], consvars, COUPLINGSIZE, &success) );
662 solval = SCIPgetSolVal(subscip, sol, consvars[0]);
663
664 side = SCIPgetRhsLinear(subscip, block->couplingcons[c]);
665 assert(SCIPisEQ(subscip, SCIPgetRhsLinear(subscip, block->couplingcons[c]), SCIPgetLhsLinear(subscip, block->couplingcons[c])));
666
667 diff = side - solval;
668
669 /* slackpos is strict positiv */
670 if( diff > 0 )
671 {
672 SCIP_CALL( SCIPsetSolVal(subscip, newsol, block->slackspos[c], diff) );
673 SCIP_CALL( SCIPsetSolVal(subscip, newsol, block->slacksneg[c], 0.0) );
674 }
675 /* slackneg is strict positiv */
676 else if( diff < 0 )
677 {
678 SCIP_CALL( SCIPsetSolVal(subscip, newsol, block->slacksneg[c], -diff) );
679 SCIP_CALL( SCIPsetSolVal(subscip, newsol, block->slackspos[c], 0.0) );
680 }
681 /* no slack variable necessary */
682 else
683 {
684 SCIP_CALL( SCIPsetSolVal(subscip, newsol, block->slackspos[c], 0.0) );
685 SCIP_CALL( SCIPsetSolVal(subscip, newsol, block->slacksneg[c], 0.0) );
686 }
687 }
688
689 SCIPdebugMsg(subscip, "Try adding solution with objective value %.2f\n", SCIPgetSolOrigObj(subscip, newsol));
690 SCIP_CALL( SCIPaddSolFree(subscip, &newsol, &success) );
691
692 if( !success )
693 SCIPdebugMsg(subscip, "Correcting solution failed\n"); /* maybe not better than old solutions */
694 else
695 {
696 SCIPdebugMsg(subscip, "Correcting solution successful\n");
697 }
698
699 SCIPfreeBufferArray(subscip, &blockvals);
700 SCIPfreeBufferArray(subscip, &consvars);
701
702 return SCIP_OKAY;
703}
704
705/** reoptimizes the heuristic solution with original objective function
706 *
707 * Since the main algorithm of padm ignores the objective function, this method can be called to obtain better solutions.
708 * It copies the main scip, fixes the linking variables at the values of the already found solution
709 * and solves the new problem with small limits.
710 */
711static
713 SCIP* scip, /**< SCIP data structure */
714 SCIP_HEUR* heur, /**< pointer to heuristic*/
715 SCIP_SOL* sol, /**< heuristic solution */
716 SCIP_VAR** vars, /**< pointer to variables */
717 int nvars, /**< number of variables */
718 SCIP_VAR** linkvars, /**< pointer to linking variables */
719 int nlinkvars, /**< number of linking variables */
720 SCIP_SOL** newsol, /**< pointer to store improved solution */
721 SCIP_Bool* success /**< pointer to store whether reoptimization was successful */
722 )
723{
724 SCIP* scipcopy;
725 SCIP_SOL* startsol;
726 SCIP_HASHMAP* varmap;
727 SCIP_VAR** subvars;
728 SCIP_STATUS status;
729 SCIP_Real* linkvals;
730 SCIP_Real time;
731 int v;
732
733 assert(scip != NULL);
734 assert(heur != NULL);
735 assert(sol != NULL);
736 assert(vars != NULL);
737 assert(linkvars != NULL);
738
739 SCIP_CALL( SCIPallocBufferArray(scip, &linkvals, nlinkvars) );
740 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
741
742 SCIP_CALL( SCIPgetSolVals(scip, sol, nlinkvars, linkvars, linkvals) );
743
744 /* initializing the problem copy*/
745 SCIP_CALL( SCIPcreate(&scipcopy) );
746
747 /* - create the variable mapping hash map
748 * - create a problem copy of main SCIP
749 */
750 if( SCIPheurGetData(heur)->original )
751 {
753 SCIP_CALL( SCIPcopyOrigConsCompression(scip, scipcopy, varmap, NULL, "reopt_padm", linkvars, linkvals, nlinkvars,
754 FALSE, FALSE, TRUE, success) );
755 }
756 else
757 {
758 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scipcopy), SCIPgetNVars(scip)) );
759 SCIP_CALL( SCIPcopyConsCompression(scip, scipcopy, varmap, NULL, "reopt_padm", linkvars, linkvals, nlinkvars,
760 TRUE, FALSE, FALSE, TRUE, success) );
761 }
762 for( v = 0; v < nvars; v++ )
763 {
764 subvars[v] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[v]);
765 }
766
767 /* do not abort subproblem on CTRL-C */
768 SCIP_CALL( SCIPsetBoolParam(scipcopy, "misc/catchctrlc", FALSE) );
769
770 /* forbid recursive call of heuristics and separators solving sub-SCIPs */
771 SCIP_CALL( SCIPsetSubscipsOff(scipcopy, TRUE) );
772
773#ifdef SCIP_DEBUG
774 /* for debugging, enable full output */
775 SCIP_CALL( SCIPsetIntParam(scipcopy, "display/verblevel", 5) );
776 SCIP_CALL( SCIPsetIntParam(scipcopy, "display/freq", 100000000) );
777#else
778 /* disable statistic timing inside sub SCIP and output to console */
779 SCIP_CALL( SCIPsetIntParam(scipcopy, "display/verblevel", 0) );
780 SCIP_CALL( SCIPsetBoolParam(scipcopy, "timing/statistictiming", FALSE) );
781#endif
782
783 /* disable cutting plane separation */
785
786 /* disable expensive presolving but enable components presolver */
788 SCIP_CALL( SCIPsetIntParam(scipcopy, "constraints/components/maxprerounds", 1) );
789 SCIP_CALL( SCIPsetLongintParam(scipcopy, "constraints/components/nodelimit", 0LL) );
790
791 /* disable expensive techniques */
792 SCIP_CALL( SCIPsetIntParam(scipcopy, "misc/usesymmetry", 0) );
793
794 /* speed up sub-SCIP by not checking dual LP feasibility */
795 SCIP_CALL( SCIPsetBoolParam(scipcopy, "lp/checkdualfeas", FALSE) );
796
797 /* add heuristic solution as start solution */
798 SCIP_CALL( SCIPtransformProb(scipcopy) );
799 *success = FALSE;
801 {
802 SCIP_CALL( SCIPcreateSol(scipcopy, &startsol, heur) );
803 for( v = 0; v < nvars; v++ )
804 {
805 SCIP_VAR* subvar;
806 subvar = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[v]);
807 if( subvar != NULL )
808 {
809 SCIP_CALL( SCIPsetSolVal(scipcopy, startsol, subvar, SCIPgetSolVal(scip, sol, vars[v])) );
810 }
811 }
812
813 SCIP_CALL( SCIPtrySolFree(scipcopy, &startsol, FALSE, FALSE, FALSE, FALSE, FALSE, success) );
814 if( *success )
815 SCIPdebugMsg(scip, "set start solution\n");
816 else
817 SCIPdebugMsg(scip, "start solution for reoptimizing is not feasible\n");
818 }
819
820 /* set limits; do not use more time than the heuristic has already used */
821 SCIP_CALL( SCIPcopyLimits(scip, scipcopy) );
822 SCIP_CALL( SCIPsetLongintParam(scipcopy, "limits/nodes", 1LL) );
823 SCIP_CALL( SCIPgetRealParam(scipcopy, "limits/time", &time) );
824 if( SCIPheurGetTime(heur) < time - 1.0 )
825 {
826 SCIP_CALL( SCIPsetRealParam(scipcopy, "limits/time", SCIPheurGetTime(heur) + 1.0) );
827 }
828 if( *success )
829 {
830 SCIP_CALL( SCIPsetIntParam(scipcopy, "limits/bestsol", 2) ); /* first solution is start solution */
831 }
832 else
833 {
834 SCIP_CALL( SCIPsetIntParam(scipcopy, "limits/bestsol", 1) );
835 }
836
837 /* reoptimize problem */
838 SCIP_CALL_ABORT( SCIPsolve(scipcopy) );
839 status = SCIPgetStatus(scipcopy);
840
841 /* copy solution to main scip */
842 if( status == SCIP_STATUS_BESTSOLLIMIT || status == SCIP_STATUS_OPTIMAL )
843 {
844 SCIP_SOL* solcopy;
845
846 solcopy = SCIPgetBestSol(scipcopy);
847 SCIP_CALL( SCIPtranslateSubSol(scip, scipcopy, solcopy, heur, subvars, newsol) );
848
849 SCIPdebugMsg(scip, "Objective value of reoptimized solution %.2f\n", SCIPgetSolOrigObj(scip, *newsol));
850 *success = TRUE;
851 }
852 else
853 {
854 *success = FALSE;
855 }
856
857 /* free data */
858 SCIPhashmapFree(&varmap);
859 SCIP_CALL( SCIPfree(&scipcopy) );
860 SCIPfreeBufferArray(scip, &subvars);
861 SCIPfreeBufferArray(scip, &linkvals);
862
863 return SCIP_OKAY;
864}
865
866/** rescales the penalty parameters
867 *
868 * A sigmoid function is a function with an "S"-shaped graph, e.g. S(x) = x/(1+|x|).
869 * In order to avoid numerical instabilities due to large penalty parameters we rescale them
870 * using the sigmoid function
871 * S(x) = (x - shift)/(flatness + |x - shift|) * (range/2) + offset.
872 * The parameters are mapped into the more controllable interval [lowestslack, range + lowestslack].
873 */
874static
876 PROBLEM* problem, /**< block structure */
877 SET* linkvartoblocks, /**< linking variable to blocks set */
878 SET* blocktolinkvars, /**< block to linking variable set */
879 SCIP_HASHTABLE* htable, /**< hashtable containing blockinfo*/
880 SCIP_Real maxpenalty /**< maximum penalty parameter */
881 )
882{
883 SCIP_Real shift;
884 SCIP_Real lowestslack;
885 SCIP_Real range;
886 SCIP_Real offset;
887 SCIP_Real flatness;
888 int b;
889 int i;
890 int k;
891
892 shift = maxpenalty / 2.0;
893 lowestslack = 0.1;
894 range = 10.0;
895 offset = range / 2.0 + lowestslack;
896 flatness = maxpenalty / 10.0;
897
898 for( b = 0; b < problem->nblocks; b++ )
899 {
900 for( i = 0; i < blocktolinkvars[b].size; i++ )
901 {
902 int linkvaridx;
903 linkvaridx = blocktolinkvars[b].indexes[i];
904
905 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
906 {
907 int b2;
908 b2 = linkvartoblocks[linkvaridx].indexes[k];
909
910 if( b2 != b )
911 {
912 BLOCKINFO binfo;
913 BLOCKINFO* binfoout;
914 SCIP_Real oldcoeff;
915
916 binfo.block = b;
917 binfo.otherblock = b2;
918 binfo.linkvaridx = linkvaridx;
919 binfoout = (BLOCKINFO*) SCIPhashtableRetrieve(htable, (void*) &binfo);
920 assert(binfoout != NULL);
921
922 /* scale coefficient of positive slack variable */
923 oldcoeff = binfoout->slackposobjcoeff;
924 binfoout->slackposobjcoeff = ((oldcoeff - shift) / (flatness + REALABS(oldcoeff - shift))) * range / 2.0 + offset;
925
926 /* scale coefficient of negative slack variable */
927 oldcoeff = binfoout->slacknegobjcoeff;
928 binfoout->slacknegobjcoeff = ((oldcoeff - shift) / (flatness + REALABS(oldcoeff - shift))) * range / 2.0 + offset;
929 }
930 }
931 }
932 }
933 return SCIP_OKAY;
934}
935
936/** returns the available time limit that is left */
937static
939 SCIP* scip, /**< SCIP data structure */
940 SCIP_Real* time /**< pointer to store remaining time */
941 )
942{
943 SCIP_Real timelim;
944 SCIP_Real solvingtime;
945
946 assert(scip != NULL);
947
948 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelim) );
949 solvingtime = SCIPgetSolvingTime(scip);
950
951 if( !SCIPisInfinity(scip, timelim) )
952 *time = MAX(0.0, (timelim - solvingtime));
953 else
954 *time = SCIPinfinity(scip);
955
956 return SCIP_OKAY;
957}
958
959/*
960 * Callback methods of primal heuristic
961 */
962
963/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
964static
966{ /*lint --e{715}*/
967 assert(scip != NULL);
968 assert(heur != NULL);
969 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
970
971 /* call inclusion method of primal heuristic */
973
974 return SCIP_OKAY;
975}
976
977
978/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
979static
981{ /*lint --e{715}*/
982 SCIP_HEURDATA* heurdata;
983
984 heurdata = SCIPheurGetData(heur);
985 SCIPheurSetData(heur, NULL);
986
987 assert(heurdata != NULL);
988
989 SCIPfreeBlockMemory(scip, &heurdata);
990
991 return SCIP_OKAY;
992}
993
994
995/** execution method of primal heuristic */
996static SCIP_DECL_HEUREXEC(heurExecPADM)
997{ /*lint --e{715}*/
998 char name[SCIP_MAXSTRLEN];
999 char info[SCIP_MAXSTRLEN];
1000 SCIP_HEURDATA* heurdata;
1001 PROBLEM* problem;
1002 SCIP_DECOMP** alldecomps;
1003 SCIP_DECOMP* decomp;
1004 SCIP_DECOMP* assigneddecomp;
1005 SCIP_VAR** vars;
1006 SCIP_VAR** linkvars;
1007 SCIP_VAR** tmpcouplingvars;
1008 SCIP_CONS** conss;
1009 SCIP_CONS** sortedconss;
1010 SET* linkvartoblocks;
1011 SET* blocktolinkvars;
1012 BLOCKINFO* blockinfolist;
1013 SCIP_HASHTABLE* htable;
1014 int* varlabels;
1015 int* conslabels;
1016 int* consssize;
1017 int* alllinkvartoblocks; /* for efficient memory allocation */
1018 SCIP_Bool* varonlyobj;
1019 SCIP_Real* tmpcouplingcoef;
1020 SCIP_Real gap;
1021 SCIP_Real maxpenalty;
1022 SCIP_Real slackthreshold;
1023 SCIP_Real memory; /* in MB */
1024 SCIP_Real timeleft;
1025 SCIP_STATUS status;
1026 SCIP_Bool solutionsdiffer;
1027 SCIP_Bool solved;
1028 SCIP_Bool doscaling;
1029 SCIP_Bool istimeleft;
1030 SCIP_Bool success;
1031 SCIP_Bool avoidmemout;
1032 SCIP_Bool disablemeasures;
1033 int maxgraphedge;
1034 int ndecomps;
1035 int nconss;
1036 int nvars;
1037 int nblocks;
1038 int numlinkvars;
1039 int nentries;
1040 int aiter;
1041 int piter;
1042 int increasedslacks;
1043 int blockinfolistfill;
1044 SCIP_Longint nodesleft;
1045 int i;
1046 int b;
1047 int k;
1048 int j;
1049
1050 assert(scip != NULL);
1051 assert(heur != NULL);
1052 assert(result != NULL);
1053
1054 heurdata = SCIPheurGetData(heur);
1055 assert(heurdata != NULL);
1056
1057 *result = SCIP_DIDNOTRUN;
1058
1059 problem = NULL;
1060 assigneddecomp = NULL;
1061 sortedconss = NULL;
1062 varlabels = NULL;
1063 conslabels = NULL;
1064 consssize = NULL;
1065 alllinkvartoblocks = NULL;
1066 linkvars = NULL;
1067 linkvartoblocks = NULL;
1068 blocktolinkvars = NULL;
1069 tmpcouplingvars = NULL;
1070 tmpcouplingcoef = NULL;
1071 varonlyobj = NULL;
1072 blockinfolist = NULL;
1073 htable = NULL;
1074
1075 nodesleft = heurdata->maxnodes;
1076 gap = heurdata->gap;
1077
1078 if( (heurtiming & SCIP_HEURTIMING_BEFORENODE) && heurdata->timing !=1 )
1079 {
1080 SCIPdebugMsg(scip, "Initialize padm heuristic before node\n");
1081 }
1082 else if( (heurtiming & SCIP_HEURTIMING_AFTERNODE) && heurdata->timing >=1 )
1083 {
1084 SCIPdebugMsg(scip, "Initialize padm heuristic after node\n");
1085 }
1086 else
1087 {
1088 return SCIP_OKAY;
1089 }
1090
1091#ifdef PADM_WRITE_PROBLEMS
1092 SCIP_CALL( SCIPwriteOrigProblem(scip, "orig_problem", NULL, FALSE) );
1093 SCIP_CALL( SCIPwriteTransProblem(scip, "trans_problem", NULL, FALSE) );
1094#endif
1095
1096 /* take original problem (This is only for testing and not recommended!) */
1097 if( heurdata->original )
1098 {
1099 /* multiaggregation of variables has to be switched off */
1100 if( !SCIPdoNotMultaggr(scip) )
1101 {
1102 SCIPwarningMessage(scip, "Heuristic %s does not support multiaggregation when the original problem is used.\nPlease turn multiaggregation off to use this feature.\n", HEUR_NAME);
1103 return SCIP_OKAY;
1104 }
1105
1106 SCIPgetDecomps(scip, &alldecomps, &ndecomps, TRUE);
1107 if( ndecomps == 0)
1108 return SCIP_OKAY;
1109
1110 /* it takes the first decomposition */
1111 decomp = alldecomps[0];
1112 SCIPdebugMsg(scip, "First original decomposition is selected\n");
1113 assert(decomp != NULL);
1114
1115 nconss = SCIPgetNOrigConss(scip);
1116 conss = SCIPgetOrigConss(scip);
1117 nvars = SCIPgetNOrigVars(scip);
1118 vars = SCIPgetOrigVars(scip);
1119 }
1120 /* take transformed problem */
1121 else
1122 {
1123 SCIPgetDecomps(scip, &alldecomps, &ndecomps, FALSE);
1124 if( ndecomps == 0)
1125 return SCIP_OKAY;
1126
1127 /* it takes the first decomposition */
1128 decomp = alldecomps[0];
1129 SCIPdebugMsg(scip, "First transformed decomposition is selected\n");
1130 assert(decomp != NULL);
1131
1132 nconss = SCIPgetNConss(scip);
1133 conss = SCIPgetConss(scip);
1134 nvars = SCIPgetNVars(scip);
1135 vars = SCIPgetVars(scip);
1136 }
1137
1138 nblocks = SCIPdecompGetNBlocks(decomp);
1139
1140 /* if problem has no constraints, no variables or less than two blocks, return */
1141 if( nconss == 0 || nvars == 0 || nblocks <= 1 )
1142 {
1143 SCIPdebugMsg(scip, "problem has no constraints, no variables or less than two blocks\n");
1144 goto TERMINATE;
1145 }
1146
1147 /* estimate required memory for all blocks and terminate if not enough memory is available */
1148 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memory) );
1149 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
1150 if( avoidmemout && (((SCIPgetMemUsed(scip) + SCIPgetMemExternEstim(scip))/1048576.0) * nblocks >= memory) )
1151 {
1152 SCIPdebugMsg(scip, "The estimated memory usage for %d blocks is too large.\n", nblocks);
1153 goto TERMINATE;
1154 }
1155
1156 /* we do not need the block decomposition graph and expensive measures of the decomposition statistics */
1157 SCIP_CALL( SCIPgetIntParam(scip, "decomposition/maxgraphedge", &maxgraphedge) );
1158 if( !SCIPisParamFixed(scip, "decomposition/maxgraphedge") )
1159 {
1160 SCIP_CALL( SCIPsetIntParam(scip, "decomposition/maxgraphedge", 0) );
1161 }
1162 SCIP_CALL( SCIPgetBoolParam(scip, "decomposition/disablemeasures", &disablemeasures) );
1163 if( !SCIPisParamFixed(scip, "decomposition/disablemeasures") )
1164 {
1165 SCIP_CALL( SCIPsetBoolParam(scip, "decomposition/disablemeasures", TRUE) );
1166 }
1167
1168 /* don't change problem by sorting constraints */
1169 SCIP_CALL( SCIPduplicateBufferArray(scip, &sortedconss, conss, nconss) );
1170
1171 SCIP_CALL( SCIPallocBufferArray(scip, &varlabels, nvars) );
1172 SCIP_CALL( SCIPallocBufferArray(scip, &conslabels, nconss) );
1173 SCIP_CALL( SCIPallocBufferArray(scip, &consssize, nblocks + 1) );
1174
1175 SCIPdecompGetConsLabels(decomp, conss, conslabels, nconss);
1176 SCIPdecompGetVarsLabels(decomp, vars, varlabels, nvars);
1177
1178 /* sort constraints by blocks */
1179 SCIPsortIntPtr(conslabels, (void**)sortedconss, nconss);
1180
1181 /* try to assign linking constraints */
1182 if( heurdata->assignlinking && conslabels[0] == SCIP_DECOMP_LINKCONS )
1183 {
1184 /* create new decomposition; don't change the decompositions in the decompstore */
1185 SCIP_CALL( SCIPcreateDecomp(scip, &assigneddecomp, nblocks, heurdata->original, SCIPdecompUseBendersLabels(decomp)) );
1186
1187 SCIP_CALL( assignLinking(scip, assigneddecomp, vars, sortedconss, varlabels, conslabels, nvars, nconss, SCIPdecompGetNBorderConss(decomp)) );
1188 assert(SCIPdecompGetNBlocks(decomp) >= SCIPdecompGetNBlocks(assigneddecomp));
1189 decomp = assigneddecomp;
1190
1191 /* number of blocks can get smaller (since assigning constraints can lead to empty blocks) */
1192 nblocks = SCIPdecompGetNBlocks(decomp);
1193 }
1194 else
1195 {
1196 /* The decomposition statistics were computed during transformation of the decomposition store.
1197 * Since propagators can have changed the number of constraints/variables,
1198 * the statistics are no longer up-to-date and have to be recomputed.
1199 */
1201 nblocks = SCIPdecompGetNBlocks(decomp);
1202 }
1203
1204 /* reset parameters */
1205 SCIP_CALL( SCIPsetIntParam(scip, "decomposition/maxgraphedge", maxgraphedge) );
1206 SCIP_CALL( SCIPsetBoolParam(scip, "decomposition/disablemeasures", disablemeasures) );
1207
1208 /* @note the terms 'linking' and 'border' (constraints/variables) are used interchangeably */
1209
1210 if( SCIPdecompGetNBorderConss(decomp) != 0 )
1211 {
1212 SCIPdebugMsg(scip, "No support for linking contraints\n");
1213 goto TERMINATE;
1214 }
1215
1216 /* get number of linking variables */
1217 numlinkvars = SCIPdecompGetNBorderVars(decomp);
1218 SCIPdebugMsg(scip, "%d linking variables\n", numlinkvars);
1219
1220 if( numlinkvars == 0 )
1221 {
1222 SCIPdebugMsg(scip, "No linking variables\n");
1223 goto TERMINATE;
1224 }
1225
1226 *result = SCIP_DIDNOTFIND;
1227
1228 /* get for every block the number of constraints (first entry belongs to border) */
1229 SCIP_CALL( SCIPdecompGetConssSize(decomp, consssize, nblocks + 1) );
1230
1231 /* create blockproblems */
1232 SCIP_CALL( createAndSplitProblem(scip, sortedconss, nconss, consssize, nblocks, &problem, heurdata->original, &success) );
1233
1234 if( !success )
1235 {
1236 SCIPdebugMsg(scip, "Some subscips could not be created successfully.\n");
1237 goto TERMINATE;
1238 }
1239
1240 SCIP_CALL( SCIPallocBufferArray(scip, &linkvartoblocks, numlinkvars) );
1241 SCIP_CALL( SCIPallocBufferArray(scip, &blocktolinkvars, problem->nblocks) );
1242
1243 /* set pointer to NULL for safe memory release */
1244 for( i = 0; i < numlinkvars; i++ )
1245 linkvartoblocks[i].indexes = NULL;
1246 for( i = 0; i < problem->nblocks; i++ )
1247 blocktolinkvars[i].indexes = NULL;
1248
1249 /* extract linking variables and init linking variable to blocks set */
1250 SCIP_CALL( SCIPallocBufferArray(scip, &alllinkvartoblocks, problem->nblocks * numlinkvars) );
1251 SCIP_CALL( SCIPallocBufferArray(scip, &linkvars, numlinkvars) );
1252
1253 b = 0;
1254 for( i = 0; i < nvars; i++ )
1255 {
1256 if( varlabels[i] == SCIP_DECOMP_LINKVAR )
1257 {
1258 linkvars[b] = vars[i];
1259 linkvartoblocks[b].indexes = &alllinkvartoblocks[b * problem->nblocks];
1260 linkvartoblocks[b].size = 0;
1261 b++;
1262 }
1263 }
1264
1265 /* fill linking variable to blocks set */
1266 for( i = 0; i < numlinkvars; i++ )
1267 {
1268 SCIP_VAR* var;
1269 const char* vname;
1270
1271 assert(linkvartoblocks[i].indexes != NULL);
1272
1273 vname = SCIPvarGetName(linkvars[i]);
1274 k = 0;
1275 for( b = 0; b < problem->nblocks; b++ )
1276 {
1277 var = SCIPfindVar((problem->blocks[b]).subscip, vname);
1278 if( var != NULL )
1279 {
1280 linkvartoblocks[i].indexes[k] = b;
1281 linkvartoblocks[i].size = k + 1;
1282 k++;
1283 }
1284 }
1285 }
1286
1287 /* check whether there is enough time left */
1288 SCIP_CALL( getTimeLeft(scip, &timeleft) );
1289 if( timeleft <= 0 )
1290 {
1291 SCIPdebugMsg(scip, "no time left\n");
1292 goto TERMINATE;
1293 }
1294
1295 /* init varonlyobj; true if variable is only part of the objective function */
1296 SCIP_CALL( SCIPallocBufferArray(scip, &varonlyobj, numlinkvars) );
1297 for( i = 0; i < numlinkvars; ++i)
1298 varonlyobj[i] = TRUE;
1299
1300 /* init and fill block to linking variables set */
1301 for( b = 0; b < problem->nblocks; b++ )
1302 {
1303 SCIP_CALL( SCIPallocBufferArray(scip, &(blocktolinkvars[b].indexes), numlinkvars) );
1304 blocktolinkvars[b].size = 0;
1305
1306 k = 0;
1307 for( i = 0; i < numlinkvars; i++ )
1308 {
1309 SCIP_VAR* var;
1310 const char* vname;
1311
1312 vname = SCIPvarGetName(linkvars[i]);
1313 var = SCIPfindVar((problem->blocks[b]).subscip, vname);
1314 if( var != NULL )
1315 {
1316 varonlyobj[i] = FALSE;
1317 blocktolinkvars[b].indexes[k] = i;
1318 blocktolinkvars[b].size = k + 1;
1319 k++;
1320 }
1321 }
1322 }
1323
1324 /* init arrays for slack variables and coupling constraints */
1325 for( b = 0; b < problem->nblocks; b++ )
1326 {
1327 SCIP_CALL( SCIPallocBufferArray(scip, &((problem->blocks[b]).slackspos), blocktolinkvars[b].size * (nblocks - 1)) );
1328 SCIP_CALL( SCIPallocBufferArray(scip, &((problem->blocks[b]).slacksneg), blocktolinkvars[b].size * (nblocks - 1)) );
1329 SCIP_CALL( SCIPallocBufferArray(scip, &((problem->blocks[b]).couplingcons), blocktolinkvars[b].size * (nblocks - 1)) );
1330 }
1331
1332 SCIP_CALL( SCIPallocBufferArray(scip, &tmpcouplingvars, COUPLINGSIZE) );
1333 SCIP_CALL( SCIPallocBufferArray(scip, &tmpcouplingcoef, COUPLINGSIZE) );
1334 tmpcouplingcoef[0] = 1.0;
1335 tmpcouplingcoef[1] = 1.0;
1336 tmpcouplingcoef[2] = -1.0;
1337
1338 /* count hashtable entries */
1339 nentries = 0;
1340 for( b = 0; b < problem->nblocks; b++ )
1341 {
1342 for( i = 0; i < blocktolinkvars[b].size; i++ )
1343 {
1344 int linkvaridx = blocktolinkvars[b].indexes[i];
1345 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1346 {
1347 if( linkvartoblocks[linkvaridx].indexes[k] != b )
1348 nentries++;
1349 }
1350 }
1351 }
1352
1353 SCIP_CALL( SCIPallocBufferArray(scip, &blockinfolist, nentries) );
1354 SCIP_CALL( SCIPhashtableCreate(&htable, SCIPblkmem(scip), 1, SCIPhashGetKeyStandard, indexesEqual, indexesHashval, (void*) scip) );
1355 blockinfolistfill = 0;
1356
1357 /* extend submips */
1358 SCIPdebugMsg(scip, "Extending %d block models\n", problem->nblocks);
1359 for( b = 0; b < problem->nblocks; b++ )
1360 {
1361 SCIP_VAR** blockvars;
1362 int nblockvars;
1363
1364 blockvars = SCIPgetVars((problem->blocks[b]).subscip);
1365 nblockvars = SCIPgetNVars((problem->blocks[b]).subscip);
1366
1367 /* set objective function of each block to zero */
1368 for( i = 0; i < nblockvars; i++ )
1369 {
1370 SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, blockvars[i], 0.0) );
1371 }
1372
1373 /* add two slack variables for each linking variable in block */
1374 for( i = 0; i < blocktolinkvars[b].size; i++ )
1375 {
1376 int linkvaridx;
1377 linkvaridx = blocktolinkvars[b].indexes[i];
1378
1379 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1380 {
1381 int b2;
1382 b2 = linkvartoblocks[linkvaridx].indexes[k];
1383
1384 /* handle different blocks with common linking variable */
1385 if( b2 != b )
1386 {
1387 BLOCKINFO* binfo;
1388 binfo = &blockinfolist[blockinfolistfill];
1389 blockinfolistfill++;
1390 binfo->block = b;
1391 binfo->otherblock = b2;
1392 binfo->linkvaridx = linkvaridx;
1393 binfo->linkvar = SCIPfindVar((problem->blocks[b]).subscip, SCIPvarGetName(linkvars[linkvaridx]));
1394 j = (problem->blocks[b]).ncoupling;
1395
1396 /* create positive slack variable */
1397 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_slackpos_block_%d", SCIPvarGetName(linkvars[linkvaridx]), b2);
1398 (problem->blocks[b]).slackspos[j] = NULL;
1399 SCIP_CALL( SCIPcreateVarBasic((problem->blocks[b]).subscip,
1400 &((problem->blocks[b]).slackspos[j]), name,
1402 SCIP_CALL( SCIPaddVar((problem->blocks[b]).subscip, (problem->blocks[b]).slackspos[j]) );
1403 assert((problem->blocks[b]).slackspos[j] != NULL);
1404 binfo->slackposobjcoeff = 1.0;
1405 binfo->slackposvar = (problem->blocks[b]).slackspos[j];
1406
1407 /* create negative slack variable */
1408 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_slackneg_block_%d", SCIPvarGetName(linkvars[linkvaridx]), b2);
1409 (problem->blocks[b]).slacksneg[j] = NULL;
1410 SCIP_CALL( SCIPcreateVarBasic((problem->blocks[b]).subscip,
1411 &((problem->blocks[b]).slacksneg[j]), name,
1413 SCIP_CALL( SCIPaddVar((problem->blocks[b]).subscip, (problem->blocks[b]).slacksneg[j]) );
1414 assert((problem->blocks[b]).slacksneg[j] != NULL);
1415 binfo->slacknegobjcoeff = 1.0;
1416 binfo->slacknegvar = (problem->blocks[b]).slacksneg[j];
1417
1418 /* fill variables for linking constraint */
1419 tmpcouplingvars[0] = binfo->linkvar;
1420 tmpcouplingvars[1] = binfo->slackposvar;
1421 tmpcouplingvars[2] = binfo->slacknegvar;
1422
1423 /* create linking constraint */
1424 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_coupling_block_%d",
1425 SCIPvarGetName(linkvars[linkvaridx]), b2);
1426 (problem->blocks[b]).couplingcons[j] = NULL;
1427
1428 /* create linking constraint with initial side equal to zero (or lower bound of linking variable) */
1429 if( heurtiming & SCIP_HEURTIMING_BEFORENODE )
1430 {
1431 SCIP_Real initval;
1432 SCIP_Real lb;
1433
1434 lb = SCIPvarGetLbOriginal(binfo->linkvar);
1435 initval = MAX(lb, 0.0);
1436
1437 SCIP_CALL( SCIPcreateConsBasicLinear((problem->blocks[b]).subscip, &((problem->blocks[b]).couplingcons[j]),
1438 name, COUPLINGSIZE, tmpcouplingvars, tmpcouplingcoef, initval, initval) );
1439
1440 /* set initial value of linking variable */
1441 binfo->linkvarval = initval;
1442 }
1443
1444 /* create linking constraint with initial side equal to LP solution (rounded if variable is integer) */
1445 if( heurtiming & SCIP_HEURTIMING_AFTERNODE )
1446 {
1447 SCIP_Real initval;
1448
1449 initval = SCIPvarGetLPSol(linkvars[linkvaridx]);
1451 initval = SCIPround(scip, initval);
1452
1453 SCIP_CALL( SCIPcreateConsBasicLinear((problem->blocks[b]).subscip, &((problem->blocks[b]).couplingcons[j]),
1454 name, COUPLINGSIZE, tmpcouplingvars, tmpcouplingcoef, initval, initval) );
1455
1456 /* set initial value of linking variable */
1457 binfo->linkvarval = initval;
1458 }
1459
1460 SCIP_CALL( SCIPaddCons((problem->blocks[b]).subscip, (problem->blocks[b]).couplingcons[j]) );
1461 assert((problem->blocks[b]).couplingcons[j] != NULL);
1462 binfo->couplingCons = (problem->blocks[b]).couplingcons[j];
1463
1464 (problem->blocks[b]).ncoupling++;
1465
1466 /* feed hashtable */
1467 SCIP_CALL( SCIPhashtableSafeInsert(htable, (void*) binfo) );
1468 }
1469 }
1470 }
1471 }
1472 assert(nentries == SCIPhashtableGetNElements(htable));
1473
1474#ifdef PADM_WRITE_PROBLEMS
1475 /* write extended submips */
1476 for( b = 0; b < problem->nblocks; b++ )
1477 {
1478 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "extended_block_%d.lp", b);
1479 SCIP_CALL( SCIPwriteOrigProblem((problem->blocks[b]).subscip, name, NULL, FALSE) );
1480 }
1481#endif
1482
1483 /* determine threshold for penalty coefficients via maximum norm */
1484 slackthreshold = SCIP_REAL_MIN;
1485 for( i = 0; i < nvars; i++ )
1486 {
1487 SCIP_Real obj;
1488
1489 obj = REALABS(SCIPvarGetObj(vars[i]));
1490 if( obj > slackthreshold )
1491 slackthreshold = obj;
1492 }
1493
1494 /* ------------------------------------------------------------------------------------------------- */
1495
1496 /* check whether there is enough time left */
1497 SCIP_CALL( getTimeLeft(scip, &timeleft) );
1498 if( timeleft <= 0 )
1499 {
1500 SCIPdebugMsg(scip, "no time left\n");
1501 goto TERMINATE;
1502 }
1503
1504 SCIPdebugMsg(scip, "Starting iterations\n");
1505 SCIPdebugMsg(scip, "PIt\tADMIt\tSlacks\tInfo\n");
1506
1507 piter = 0;
1508 increasedslacks = 0;
1509 (void) SCIPsnprintf(info, SCIP_MAXSTRLEN, "-");
1510 solved = FALSE;
1511 istimeleft = TRUE;
1512
1513 /* Penalty loop */
1514 while( !solved && piter < heurdata->penaltyiterations && istimeleft )
1515 {
1516 piter++;
1517 solutionsdiffer = TRUE;
1518 aiter = 0;
1519
1520 /* Alternating direction method loop */
1521 while( solutionsdiffer && aiter < heurdata->admiterations && istimeleft )
1522 {
1523 aiter++;
1524 solutionsdiffer = FALSE;
1525 SCIPdebugMsg(scip, "%d\t%d\t%d\t%s\n", piter, aiter, increasedslacks, info);
1526
1527 /* Loop through the blocks and solve each sub-SCIP, potentially multiple times */
1528 for( b = 0; b < problem->nblocks; b++ )
1529 {
1530 for( i = 0; i < blocktolinkvars[b].size; i++ )
1531 {
1532 int linkvaridx;
1533 linkvaridx = blocktolinkvars[b].indexes[i];
1534
1535 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1536 {
1537 int b2;
1538 b2 = linkvartoblocks[linkvaridx].indexes[k];
1539
1540 if( b2 != b )
1541 {
1542 BLOCKINFO binfo;
1543 BLOCKINFO* binfoout;
1544 BLOCKINFO binfo2;
1545 BLOCKINFO* binfo2out;
1546
1547 SCIP_CONS* couplingcons;
1548 SCIP_Real newrhs;
1549
1550 binfo.block = b;
1551 binfo.otherblock = b2;
1552 binfo.linkvaridx = linkvaridx;
1553
1554 binfoout = (BLOCKINFO*) SCIPhashtableRetrieve(htable, (void *)&binfo);
1555 assert(binfoout != NULL);
1556 couplingcons = binfoout->couplingCons;
1557
1558 /* interchange blocks b and b2 for getting new right hand side */
1559 binfo2.block = b2;
1560 binfo2.otherblock = b;
1561 binfo2.linkvaridx = linkvaridx;
1562 binfo2out = (BLOCKINFO*) SCIPhashtableRetrieve(htable, (void*) &binfo2);
1563 assert(binfo2out != NULL);
1564 newrhs = binfo2out->linkvarval;
1565
1566 /* change side of coupling constraint equation with linking variable value of the other block */
1567 SCIP_CALL( SCIPchgLhsLinear((problem->blocks[b]).subscip, couplingcons, newrhs) );
1568 SCIP_CALL( SCIPchgRhsLinear((problem->blocks[b]).subscip, couplingcons, newrhs) );
1569
1570 /* change penalty coefficients of slack variables */
1571 SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, binfoout->slackposvar, binfoout->slackposobjcoeff) );
1572 SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, binfoout->slacknegvar, binfoout->slacknegobjcoeff) );
1573 }
1574 }
1575 }
1576
1577 /* increase slack penalty coeffs until each subproblem can be solved to optimality */
1578 do
1579 {
1581 int iteration;
1582
1583#ifdef PADM_WRITE_PROBLEMS
1584 SCIPdebugMsg(scip, "write subscip of block %d in piter=%d and aiter=%d\n", b, piter, aiter);
1585 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "blockproblem_%d_%d_%d.lp", b, piter, aiter);
1586 SCIP_CALL( SCIPwriteOrigProblem((problem->blocks[b]).subscip, name, NULL, FALSE) );
1587#endif
1588
1589 SCIP_CALL( SCIPsetRealParam((problem->blocks[b]).subscip, "limits/gap", gap) );
1590
1591 /* reuse old solution if available */
1592 SCIP_CALL( reuseSolution((problem->blocks[b]).subscip, &problem->blocks[b]) );
1593
1594 /* update time and memory limit of subproblem */
1595 SCIP_CALL( SCIPcopyLimits(scip, (problem->blocks[b]).subscip) );
1596
1597 /* stop if there are not enough nodes left */
1598 if( nodesleft < heurdata->minnodes )
1599 {
1600 SCIPdebugMsg(scip, "Node limit reached.\n");
1601 goto TERMINATE;
1602 }
1603
1604 /* update node limit of subproblem
1605 * in the first iterations we have a smaller node limit
1606 */
1607 iteration = ((piter - 1) * heurdata->admiterations) + aiter;
1608 nnodes = (SCIP_Longint)SCIPceil(scip, (problem->blocks[b]).size * nodesleft * ( 1 - pow(heurdata->nodefac, (double)iteration) ));
1609 nnodes = MAX( heurdata->minnodes, nnodes );
1610 SCIP_CALL( SCIPsetLongintParam((problem->blocks[b]).subscip, "limits/nodes", nnodes) );
1611
1612 /* solve block
1613 *
1614 * errors in solving the subproblem should not kill the overall solving process;
1615 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1616 */
1617 SCIP_CALL_ABORT( SCIPsolve((problem->blocks[b]).subscip) );
1618 status = SCIPgetStatus((problem->blocks[b]).subscip);
1619
1620 /* subtract used nodes from the total nodelimit */
1621 nodesleft -= (SCIP_Longint)SCIPceil(scip, SCIPgetNNodes((problem->blocks[b]).subscip) * (problem->blocks[b]).size);
1622
1623 /* check solution if one of the four cases occurs
1624 * - solution is optimal
1625 * - solution reached gaplimit
1626 * - node limit reached with at least one feasible solution
1627 * - time limit is reached but best solution needs no slack variables (no dual solution available)
1628 */
1629 if( status == SCIP_STATUS_OPTIMAL || status == SCIP_STATUS_GAPLIMIT ||
1630 (status == SCIP_STATUS_NODELIMIT && SCIPgetNSols((problem->blocks[b]).subscip) > 0) ||
1631 (status == SCIP_STATUS_TIMELIMIT && SCIPgetNSols((problem->blocks[b]).subscip) > 0 &&
1632 SCIPisEQ(scip, SCIPgetSolOrigObj((problem->blocks[b]).subscip, SCIPgetBestSol((problem->blocks[b]).subscip)), 0.0) ) )
1633 {
1634 SCIPdebugMsg(scip, "Block is optimal or reached gaplimit or nodelimit.\n");
1635
1636 if( status == SCIP_STATUS_TIMELIMIT )
1637 {
1638 SCIPdebugMsg(scip, "Block reached time limit with at least one feasible solution.\n");
1639 istimeleft = FALSE;
1640 }
1641
1642 for( i = 0; i < blocktolinkvars[b].size; i++ )
1643 {
1644 int linkvaridx;
1645 linkvaridx = blocktolinkvars[b].indexes[i];
1646
1647 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1648 {
1649 int b2;
1650 b2 = linkvartoblocks[linkvaridx].indexes[k];
1651
1652 if( b2 != b )
1653 {
1654 SCIP_SOL* sol;
1655 BLOCKINFO binfo;
1656 BLOCKINFO* binfoout;
1657 SCIP_VAR* var;
1658 SCIP_Real val;
1659
1660 binfo.block = b;
1661 binfo.otherblock = b2;
1662 binfo.linkvaridx = linkvaridx;
1663 binfoout = (BLOCKINFO *)SCIPhashtableRetrieve(htable, (void *)&binfo);
1664 assert(binfoout != NULL);
1665
1666 sol = SCIPgetBestSol((problem->blocks[b]).subscip);
1667 assert(sol != NULL);
1668 var = binfoout->linkvar;
1669 val = SCIPgetSolVal((problem->blocks[b]).subscip, sol, var);
1670
1671 if( !EPSEQ(binfoout->linkvarval, val, SCIP_DEFAULT_EPSILON) )
1672 solutionsdiffer = TRUE;
1673
1674 binfoout->linkvarval = val;
1675 }
1676 }
1677 }
1678 }
1679 else if( status == SCIP_STATUS_UNBOUNDED )
1680 {
1681 SCIPdebugMsg(scip, "Block is unbounded.\n");
1682 for( i = 0; i < blocktolinkvars[b].size; i++ )
1683 {
1684 int linkvaridx;
1685 linkvaridx = blocktolinkvars[b].indexes[i];
1686
1687 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1688 {
1689 int b2;
1690 b2 = linkvartoblocks[linkvaridx].indexes[k];
1691
1692 if( b2 != b )
1693 {
1694 BLOCKINFO binfo;
1695 BLOCKINFO* binfoout;
1696
1697 binfo.block = b;
1698 binfo.otherblock = b2;
1699 binfo.linkvaridx = linkvaridx;
1700 binfoout = (BLOCKINFO*) SCIPhashtableRetrieve(htable, (void*) &binfo);
1701 assert(binfoout != NULL);
1702
1703 /* increase penalty coefficients to obtain a bounded subproblem */
1704 binfoout->slackposobjcoeff *= 10.0;
1705 binfoout->slacknegobjcoeff *= 10.0;
1706 SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, binfoout->slackposvar, binfoout->slackposobjcoeff) );
1707 SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, binfoout->slacknegvar, binfoout->slacknegobjcoeff) );
1708 }
1709 }
1710 }
1711 }
1712 else if( status == SCIP_STATUS_TIMELIMIT )
1713 {
1714 SCIPdebugMsg(scip, "Block reached time limit. No optimal solution available.\n");
1715 goto TERMINATE;
1716 }
1717 else
1718 {
1719 SCIPdebugMsg(scip, "Block solving status %d not supported\n", status);
1720 goto TERMINATE;
1721 }
1722
1723 /* free solving data in order to change problem */
1724 SCIP_CALL( SCIPfreeTransform((problem->blocks[b]).subscip) );
1725 }
1726 while( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_GAPLIMIT &&
1727 !(status == SCIP_STATUS_NODELIMIT && SCIPgetNSols((problem->blocks[b]).subscip) > 0) &&
1728 !(status == SCIP_STATUS_TIMELIMIT && SCIPgetNSols((problem->blocks[b]).subscip) > 0 &&
1729 SCIPisEQ(scip, SCIPgetSolOrigObj((problem->blocks[b]).subscip, SCIPgetBestSol((problem->blocks[b]).subscip)), 0.0) ) );
1730 }
1731 }
1732
1733 /* check wether problem has been solved and if not update penalty coeffs */
1734 doscaling = FALSE;
1735 solved = TRUE;
1736 increasedslacks = 0;
1737 maxpenalty = SCIP_REAL_MIN;
1738 for( b = 0; b < problem->nblocks; b++ )
1739 {
1740 for( i = 0; i < blocktolinkvars[b].size; i++ )
1741 {
1742 int linkvaridx;
1743 linkvaridx = blocktolinkvars[b].indexes[i];
1744
1745 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1746 {
1747 int b2;
1748 b2 = linkvartoblocks[linkvaridx].indexes[k];
1749
1750 if( b2 != b )
1751 {
1752 SCIP_SOL* sol;
1753 BLOCKINFO binfo;
1754 BLOCKINFO* binfoout;
1755 SCIP_Real slackposval;
1756 SCIP_Real slacknegval;
1757
1758 binfo.block = b;
1759 binfo.otherblock = b2;
1760 binfo.linkvaridx = linkvaridx;
1761 binfoout = (BLOCKINFO*) SCIPhashtableRetrieve(htable, (void*) &binfo);
1762 assert(binfoout != NULL);
1763
1764 sol = SCIPgetBestSol((problem->blocks[b]).subscip);
1765 slackposval = SCIPgetSolVal((problem->blocks[b]).subscip, sol, binfoout->slackposvar);
1766 slacknegval = SCIPgetSolVal((problem->blocks[b]).subscip, sol, binfoout->slacknegvar);
1767
1768 /* increase penalty coefficient of positive slack variable */
1769 if( SCIPisGT(scip, slackposval, 0.0) )
1770 {
1771 binfoout->slackposobjcoeff *= 10.0;
1772
1773 if( binfoout->slackposobjcoeff > slackthreshold )
1774 doscaling = TRUE;
1775
1776 if( binfoout->slackposobjcoeff > maxpenalty )
1777 maxpenalty = binfoout->slackposobjcoeff;
1778
1779 solved = FALSE;
1780 increasedslacks++;
1781 }
1782
1783 /* increase penalty coefficient of negative slack variable */
1784 if( SCIPisGT(scip, slacknegval, 0.0) )
1785 {
1786 binfoout->slacknegobjcoeff *= 10.0;
1787
1788 if( binfoout->slacknegobjcoeff > slackthreshold )
1789 doscaling = TRUE;
1790
1791 if( binfoout->slacknegobjcoeff > maxpenalty )
1792 maxpenalty = binfoout->slacknegobjcoeff;
1793
1794 solved = FALSE;
1795 increasedslacks++;
1796 }
1797 }
1798 }
1799 }
1800 }
1801
1802 /* should sigmoid scaling be applied to the penalty parameters? */
1803 if( doscaling && heurdata->scaling )
1804 {
1805 SCIPdebugMsg(scip, "rescale penalty parameters\n");
1806
1807 /* reset counter */
1808 increasedslacks = 0;
1809
1810 /* rescale penalty parameters */
1811 SCIP_CALL( scalePenalties(problem, linkvartoblocks, blocktolinkvars, htable, maxpenalty) );
1812 }
1813
1814 /* adapt in some cases the gap parameter */
1815 if( (aiter == 1 && solutionsdiffer == FALSE) || (doscaling && heurdata->scaling) )
1816 {
1817 SCIP_Real mingap = 0.001; //todo
1818 SCIP_Real newgap = MAX(gap * 0.5, mingap);
1819
1820 if( newgap >= mingap )
1821 {
1822 if( doscaling && heurdata->scaling )
1823 (void) SCIPsnprintf(info, SCIP_MAXSTRLEN, "scale, %f", newgap);
1824 else
1825 (void) SCIPsnprintf(info, SCIP_MAXSTRLEN, "%f", newgap);
1826
1827 gap = newgap;
1828 }
1829 }
1830
1831 /* free solution process data */
1832 if( !solved )
1833 for( b = 0; b < problem->nblocks; b++ )
1834 {
1835 SCIP_CALL( SCIPfreeTransform((problem->blocks[b]).subscip) );
1836 }
1837 }
1838
1839 /* copy solution if present */
1840 if( solved )
1841 {
1842 SCIP_SOL* newsol;
1843 SCIP_Real* blocksolvals;
1844
1845 assert(increasedslacks == 0);
1846
1847 SCIP_CALL( SCIPallocBufferArray(scip, &blocksolvals, nvars) );
1848 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1849
1850 for( b = 0; b < problem->nblocks; b++ )
1851 {
1852 SCIP_SOL* blocksol;
1853 SCIP_VAR** blockvars;
1854 int nblockvars;
1855
1856 /* get solution of block variables (without slack variables) */
1857 blocksol = SCIPgetBestSol((problem->blocks[b]).subscip);
1858 assert(blocksol != NULL);
1859 blockvars = (problem->blocks[b]).subvars;
1860 nblockvars = (problem->blocks[b]).nsubvars;
1861 SCIP_CALL( SCIPgetSolVals((problem->blocks[b]).subscip, blocksol, nblockvars, blockvars, blocksolvals) );
1862
1863 for( i = 0; i < nblockvars; i++ )
1864 {
1865 SCIP_VAR* origvar;
1866 SCIP_Real solval;
1867
1868 origvar = SCIPfindVar(scip, SCIPvarGetName(blockvars[i]));
1869 solval = blocksolvals[i];
1870 SCIP_CALL_ABORT( SCIPsetSolVal(scip, newsol, origvar, solval) );
1871 }
1872 }
1873
1874 /* treat variables with no constraints; set value of variable to bound */
1875 for( i = 0; i < numlinkvars; i++ )
1876 {
1877 if( varonlyobj[i] )
1878 {
1879 SCIP_Real fixedvalue;
1880 if( SCIPvarGetObj(linkvars[i]) < 0 )
1881 {
1882 fixedvalue = SCIPvarGetUbLocal(linkvars[i]);
1883 if( SCIPisInfinity(scip, fixedvalue) )
1884 break; // todo: maybe we should return the status UNBOUNDED instead
1885 }
1886 else
1887 {
1888 fixedvalue = SCIPvarGetLbLocal(linkvars[i]);
1889 if( SCIPisInfinity(scip, fixedvalue) )
1890 break; // todo: maybe we should return the status UNBOUNDED instead
1891 }
1892 SCIP_CALL_ABORT( SCIPsetSolVal(scip, newsol, linkvars[i], fixedvalue) );
1893 }
1894 }
1895
1896 SCIPdebugMsg(scip, "Objective value %.2f\n", SCIPgetSolOrigObj(scip, newsol));
1897
1898 /* fix linking variables and reoptimize with original objective function */
1899 if( heurdata->reoptimize )
1900 {
1901 SCIP_SOL* improvedsol = NULL;
1902 SCIP_CALL( reoptimize(scip, heur, newsol, vars, nvars, linkvars, numlinkvars, &improvedsol, &success) );
1903 assert(improvedsol != NULL || success == FALSE);
1904
1905 if( success )
1906 {
1907 SCIP_CALL( SCIPtrySolFree(scip, &improvedsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
1908 if( !success )
1909 {
1910 SCIPdebugMsg(scip, "Reoptimizing solution failed\n");
1911 }
1912 else
1913 {
1914 SCIPdebugMsg(scip, "Reoptimizing solution successful\n");
1915 *result = SCIP_FOUNDSOL;
1916 }
1917 }
1918 }
1919
1920 /* if reoptimization is turned off or reoptimization found no solution, try initial solution */
1921 if( *result != SCIP_FOUNDSOL )
1922 {
1923 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
1924 if( !success )
1925 {
1926 SCIPdebugMsg(scip, "Solution copy failed\n");
1927 }
1928 else
1929 {
1930 SCIPdebugMsg(scip, "Solution copy successful\n");
1931 *result = SCIP_FOUNDSOL;
1932 }
1933 }
1934 else
1935 {
1936 SCIP_CALL( SCIPfreeSol(scip, &newsol) );
1937 }
1938
1939 SCIPfreeBufferArray(scip, &blocksolvals);
1940 }
1941 else
1942 {
1943 SCIPdebugMsg(scip, "maximum number of penalty loops reached\n");
1944 *result = SCIP_DIDNOTFIND;
1945 }
1946
1947TERMINATE:
1948 /* release variables, constraints and free memory */
1949 if( problem != NULL )
1950 {
1951 for( b = 0; b < problem->nblocks; b++ )
1952 {
1953 BLOCK curr_block = problem->blocks[b];
1954 for( i = 0; i < (problem->blocks[b]).ncoupling; i++ )
1955 {
1956 SCIP_CALL( SCIPreleaseCons(curr_block.subscip, &curr_block.couplingcons[i]) );
1957 SCIP_CALL( SCIPreleaseVar(curr_block.subscip, &curr_block.slackspos[i]) );
1958 SCIP_CALL( SCIPreleaseVar(curr_block.subscip, &curr_block.slacksneg[i]) );
1959 }
1960 }
1961 }
1962
1963 if( htable != NULL )
1964 SCIPhashtableFree(&htable);
1965
1966 if( blockinfolist != NULL )
1967 SCIPfreeBufferArray(scip, &blockinfolist);
1968
1969 if( tmpcouplingcoef != NULL )
1970 SCIPfreeBufferArray(scip, &tmpcouplingcoef);
1971
1972 if( tmpcouplingvars != NULL )
1973 SCIPfreeBufferArray(scip, &tmpcouplingvars);
1974
1975 if( problem != NULL )
1976 {
1977 for( b = problem->nblocks - 1; b >= 0; b-- )
1978 {
1979 if( problem->blocks[b].couplingcons != NULL )
1980 {
1981 SCIPfreeBufferArray(scip, &problem->blocks[b].couplingcons);
1982 SCIPfreeBufferArray(scip, &problem->blocks[b].slacksneg);
1983 SCIPfreeBufferArray(scip, &problem->blocks[b].slackspos);
1984 }
1985 }
1986 }
1987
1988 if( varonlyobj != NULL )
1989 SCIPfreeBufferArray(scip, &varonlyobj);
1990
1991 if( problem != NULL && blocktolinkvars != NULL )
1992 {
1993 for( b = problem->nblocks -1; b >= 0; b-- )
1994 {
1995 if( blocktolinkvars[b].indexes != NULL )
1996 SCIPfreeBufferArray(scip, &(blocktolinkvars[b].indexes));
1997 }
1998 }
1999
2000 if( linkvars != NULL )
2001 SCIPfreeBufferArray(scip, &linkvars);
2002
2003 if( alllinkvartoblocks != NULL )
2004 SCIPfreeBufferArray(scip, &alllinkvartoblocks);
2005
2006 if( blocktolinkvars != NULL )
2007 SCIPfreeBufferArray(scip, &blocktolinkvars);
2008
2009 if( linkvartoblocks != NULL )
2010 SCIPfreeBufferArray(scip, &linkvartoblocks);
2011
2012 if( assigneddecomp != NULL )
2013 SCIPfreeDecomp(scip, &assigneddecomp);
2014
2015 if( consssize != NULL )
2016 SCIPfreeBufferArray(scip, &consssize);
2017
2018 if( conslabels != NULL )
2019 SCIPfreeBufferArray(scip, &conslabels);
2020
2021 if( varlabels != NULL )
2022 SCIPfreeBufferArray(scip, &varlabels);
2023
2024 if( sortedconss != NULL )
2025 SCIPfreeBufferArray(scip, &sortedconss);
2026
2027 if( problem != NULL )
2028 {
2029 SCIP_CALL( freeProblem(&problem, nblocks) );
2030 }
2031
2032 SCIPdebugMsg(scip, "Leave padm heuristic\n");
2033 return SCIP_OKAY;
2034}
2035
2036/*
2037 * primal heuristic specific interface methods
2038 */
2039
2040/** creates the PADM primal heuristic and includes it in SCIP */
2042 SCIP* scip /**< SCIP data structure */
2043 )
2044{
2045 SCIP_HEURDATA* heurdata;
2046 SCIP_HEUR* heur = NULL;
2047
2048 /* create PADM primal heuristic data */
2049 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2050
2051 /* include primal heuristic */
2052
2053 /* use SCIPincludeHeurBasic() plus setter functions if you want to set callbacks one-by-one and your code should
2054 * compile independent of new callbacks being added in future SCIP versions
2055 */
2058 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecPADM, heurdata) );
2059
2060 assert(heur != NULL);
2061
2062 /* set non fundamental callbacks via setter functions */
2063 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyPADM) );
2064 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreePADM) );
2065
2066 /* add padm primal heuristic parameters */
2067 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
2068 "maximum number of nodes to regard in all subproblems",
2069 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
2070
2071 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
2072 "minimum number of nodes to regard in one subproblem",
2073 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
2074
2075 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodefac",
2076 "factor to control nodelimits of subproblems", &heurdata->nodefac, TRUE, DEFAULT_NODEFAC, 0.0, 0.99, NULL, NULL) );
2077
2078 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/admiterations",
2079 "maximal number of ADM iterations in each penalty loop", &heurdata->admiterations, TRUE, DEFAULT_ADMIT, 1, 100, NULL, NULL) );
2080
2081 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/penaltyiterations",
2082 "maximal number of penalty iterations", &heurdata->penaltyiterations, TRUE, DEFAULT_PENALTYIT, 1, 100000, NULL, NULL) );
2083
2084 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/gap",
2085 "mipgap at start", &heurdata->gap, TRUE, DEFAULT_GAP, 0.0, 16.0, NULL, NULL) );
2086
2087 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reoptimize",
2088 "should the problem get reoptimized with the original objective function?", &heurdata->reoptimize, FALSE, TRUE, NULL, NULL) );
2089
2090 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/scaling",
2091 "enable sigmoid rescaling of penalty parameters", &heurdata->scaling, TRUE, TRUE, NULL, NULL) );
2092
2093 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/assignlinking",
2094 "should linking constraints be assigned?", &heurdata->assignlinking, FALSE, TRUE, NULL, NULL) );
2095
2096 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/original",
2097 "should the original problem be used? This is only for testing and not recommended!", &heurdata->original, TRUE, FALSE, NULL, NULL) );
2098
2099 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/timing",
2100 "should the heuristic run before or after the processing of the node? (0: before, 1: after, 2: both)",
2101 &heurdata->timing, FALSE, 0, 0, 2, NULL, NULL) );
2102
2103 return SCIP_OKAY;
2104}
SCIP_VAR ** b
Definition: circlepacking.c:65
struct Problem PROBLEM
Constraint handler for linear constraints in their most general form, .
methods for debugging
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define SCIP_DEFAULT_EPSILON
Definition: def.h:179
#define SCIP_Real
Definition: def.h:173
#define EPSEQ(x, y, eps)
Definition: def.h:198
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL_ABORT(x)
Definition: def.h:353
#define SCIP_REAL_MIN
Definition: def.h:175
#define REALABS(x)
Definition: def.h:197
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define SCIP_CALL(x)
Definition: def.h:374
#define nnodes
Definition: gastrans.c:74
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_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_RETCODE SCIPcopyOrigConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:3137
SCIP_RETCODE SCIPcopyConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2969
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 SCIPcopyProb(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, const char *name)
Definition: scip_copy.c:527
SCIP_RETCODE SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
Definition: scip_copy.c:1408
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3296
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition: scip_dcmp.c:263
SCIP_RETCODE SCIPdecompSetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:124
int SCIPdecompGetNBlocks(SCIP_DECOMP *decomp)
Definition: dcmp.c:279
SCIP_RETCODE SCIPcomputeDecompVarsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:455
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:173
SCIP_RETCODE SCIPassignDecompLinkConss(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss, int *nskipconss)
Definition: scip_dcmp.c:550
void SCIPfreeDecomp(SCIP *scip, SCIP_DECOMP **decomp)
Definition: scip_dcmp.c:234
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1136
SCIP_RETCODE SCIPdecompGetConssSize(SCIP_DECOMP *decomp, int *consssize, int nlabels)
Definition: dcmp.c:349
void SCIPdecompGetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:198
SCIP_RETCODE SCIPcreateDecomp(SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: scip_dcmp.c:218
int SCIPdecompGetNBorderVars(SCIP_DECOMP *decomp)
Definition: dcmp.c:379
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:149
SCIP_Bool SCIPdecompUseBendersLabels(SCIP_DECOMP *decomp)
Definition: dcmp.c:269
int SCIPdecompGetNBorderConss(SCIP_DECOMP *decomp)
Definition: dcmp.c:394
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:339
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:498
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip_prob.c:601
int SCIPgetNOrigBinVars(SCIP *scip)
Definition: scip_prob.c:2459
int SCIPgetNOrigConss(SCIP *scip)
Definition: scip_prob.c:3134
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition: scip_prob.c:2405
int SCIPgetNOrigIntVars(SCIP *scip)
Definition: scip_prob.c:2486
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_CONS ** SCIPgetOrigConss(SCIP *scip)
Definition: scip_prob.c:3161
SCIP_RETCODE SCIPwriteTransProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip_prob.c:648
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
Definition: scip_prob.c:2685
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2346
#define SCIPhashFour(a, b, c, d)
Definition: pub_misc.h:556
SCIP_RETCODE SCIPhashtableSafeInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2579
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2296
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
static INLINE uint32_t SCIPrealHashCode(double x)
Definition: pub_misc.h:576
SCIP_Longint SCIPhashtableGetNElements(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2767
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:111
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:904
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:953
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:979
SCIP_RETCODE SCIPincludeHeurPADM(SCIP *scip)
Definition: heur_padm.c:2041
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8473
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8234
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8383
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8413
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8343
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2578
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8403
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8275
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8433
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8463
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8393
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8483
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_Real SCIPheurGetTime(SCIP_HEUR *heur)
Definition: heur.c:1641
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:126
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:100
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:76
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:80
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#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: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 SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition: scip_sol.c:2855
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:421
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1119
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2119
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:3050
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
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:222
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip_solve.c:3344
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Real SCIPvarGetLbOriginal(SCIP_VAR *var)
Definition: var.c:18024
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Bool SCIPdoNotMultaggr(SCIP *scip)
Definition: scip_var.c:8575
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18452
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
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)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
static SCIP_RETCODE getTimeLeft(SCIP *scip, SCIP_Real *time)
Definition: heur_padm.c:938
static SCIP_RETCODE initProblem(SCIP *scip, PROBLEM **problem, int nblocks)
Definition: heur_padm.c:258
static SCIP_DECL_HEURFREE(heurFreePADM)
Definition: heur_padm.c:980
static SCIP_RETCODE blockCreateSubscip(BLOCK *block, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_CONS **conss, int nconss, SCIP_Bool useorigprob, SCIP_Bool *success)
Definition: heur_padm.c:433
#define DEFAULT_MAXNODES
Definition: heur_padm.c:96
static SCIP_DECL_HASHKEYEQ(indexesEqual)
Definition: heur_padm.c:157
static SCIP_RETCODE initBlock(PROBLEM *problem)
Definition: heur_padm.c:206
#define HEUR_TIMING
Definition: heur_padm.c:91
#define DEFAULT_MINNODES
Definition: heur_padm.c:95
#define DEFAULT_NODEFAC
Definition: heur_padm.c:97
#define HEUR_FREQOFS
Definition: heur_padm.c:89
static SCIP_DECL_HEUREXEC(heurExecPADM)
Definition: heur_padm.c:996
#define HEUR_DESC
Definition: heur_padm.c:85
#define COUPLINGSIZE
Definition: heur_padm.c:94
static SCIP_RETCODE createSubscip(SCIP *scip, SCIP **subscip)
Definition: heur_padm.c:324
#define HEUR_DISPCHAR
Definition: heur_padm.c:86
static SCIP_DECL_HASHKEYVAL(indexesHashval)
Definition: heur_padm.c:174
#define HEUR_MAXDEPTH
Definition: heur_padm.c:90
#define HEUR_PRIORITY
Definition: heur_padm.c:87
struct set SET
#define HEUR_NAME
Definition: heur_padm.c:84
#define DEFAULT_ADMIT
Definition: heur_padm.c:98
static SCIP_RETCODE assignLinking(SCIP *scip, SCIP_DECOMP *newdecomp, SCIP_VAR **vars, SCIP_CONS **sortedconss, int *varlabels, int *conslabels, int nvars, int nconss, int nlinkconss)
Definition: heur_padm.c:573
struct Block BLOCK
static SCIP_RETCODE copyToSubscip(SCIP *scip, SCIP *subscip, const char *name, SCIP_CONS **conss, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, int nconss, SCIP_Bool useorigprob, SCIP_Bool *success)
Definition: heur_padm.c:372
static SCIP_RETCODE reuseSolution(SCIP *subscip, BLOCK *block)
Definition: heur_padm.c:614
static SCIP_RETCODE createAndSplitProblem(SCIP *scip, SCIP_CONS **sortedconss, int nconss, int *consssize, int nblocks, PROBLEM **problem, SCIP_Bool useorigprob, SCIP_Bool *success)
Definition: heur_padm.c:505
static SCIP_RETCODE scalePenalties(PROBLEM *problem, SET *linkvartoblocks, SET *blocktolinkvars, SCIP_HASHTABLE *htable, SCIP_Real maxpenalty)
Definition: heur_padm.c:875
static SCIP_DECL_HEURCOPY(heurCopyPADM)
Definition: heur_padm.c:965
#define DEFAULT_PENALTYIT
Definition: heur_padm.c:99
static SCIP_RETCODE freeBlock(BLOCK *block)
Definition: heur_padm.c:235
#define HEUR_FREQ
Definition: heur_padm.c:88
struct blockinfo BLOCKINFO
#define HEUR_USESSUBSCIP
Definition: heur_padm.c:92
static SCIP_RETCODE reoptimize(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, SCIP_VAR **vars, int nvars, SCIP_VAR **linkvars, int nlinkvars, SCIP_SOL **newsol, SCIP_Bool *success)
Definition: heur_padm.c:712
static SCIP_RETCODE freeProblem(PROBLEM **problem, int nblocks)
Definition: heur_padm.c:288
#define DEFAULT_GAP
Definition: heur_padm.c:100
PADM primal heuristic.
methods commonly used by primal heuristics
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public methods for managing constraints
public methods for primal heuristics
public methods for message output
#define SCIPdebugMessage
Definition: pub_message.h:96
public data structures and miscellaneous methods
methods for selecting (weighted) k-medians
public methods for primal CIP solutions
public methods for branch and bound tree
public methods for problem variables
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for decompositions
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 node selector plugins
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for random numbers
public methods for solutions
public solving methods
public methods for querying solving statistics
public methods for statistics table plugins
public methods for timing
public methods for the branch-and-bound tree
public methods for SCIP variables
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
default SCIP plugins
PROBLEM * problem
Definition: heur_padm.c:112
SCIP_VAR ** subvars
Definition: heur_padm.c:115
int ncoupling
Definition: heur_padm.c:120
SCIP_VAR ** slacksneg
Definition: heur_padm.c:118
SCIP_VAR ** slackspos
Definition: heur_padm.c:117
SCIP_Real size
Definition: heur_padm.c:121
SCIP_CONS ** couplingcons
Definition: heur_padm.c:119
int nsubvars
Definition: heur_padm.c:116
int number
Definition: heur_padm.c:114
SCIP * subscip
Definition: heur_padm.c:113
unsigned int original
Definition: struct_cons.h:80
SCIP_Bool original
Definition: struct_dcmp.h:62
SCIP_Real slackposobjcoeff
Definition: heur_padm.c:148
SCIP_VAR * slackposvar
Definition: heur_padm.c:149
int otherblock
Definition: heur_padm.c:144
int linkvaridx
Definition: heur_padm.c:145
SCIP_CONS * couplingCons
Definition: heur_padm.c:152
SCIP_VAR * slacknegvar
Definition: heur_padm.c:151
SCIP_VAR * linkvar
Definition: heur_padm.c:147
SCIP_Real slacknegobjcoeff
Definition: heur_padm.c:150
SCIP_Real linkvarval
Definition: heur_padm.c:146
int block
Definition: heur_padm.c:143
Definition: heur_padm.c:135
int size
Definition: heur_padm.c:136
int * indexes
Definition: heur_padm.c:137
#define SCIP_DECOMP_LINKVAR
Definition: type_dcmp.h:44
#define SCIP_DECOMP_LINKCONS
Definition: type_dcmp.h:45
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_PARAMSETTING_OFF
Definition: type_paramset.h:63
@ SCIP_PARAMSETTING_FAST
Definition: type_paramset.h:62
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_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_GAPLIMIT
Definition: type_stat.h:53
@ SCIP_STATUS_TIMELIMIT
Definition: type_stat.h:51
@ SCIP_STATUS_NODELIMIT
Definition: type_stat.h:44
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:67
#define SCIP_HEURTIMING_AFTERNODE
Definition: type_timing.h:96
#define SCIP_HEURTIMING_BEFORENODE
Definition: type_timing.h:78
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71