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