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-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}*/
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
175{ /*lint --e{715}*/
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
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{
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,
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;
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) */
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);
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);
590
591 /* copy the labels */
594
595 SCIPdebugMsg(scip, "try to assign %d linking constraints\n", nlinkconss);
596
597 /* reassign linking constraints */
599
601
603
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 */
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);
649 SCIP_CALL( SCIPcreateOrigSol(subscip, &newsol, NULL) );
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
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
741
743
744 /* initializing the problem copy*/
746
747 /* - create the variable mapping hash map
748 * - create a problem copy of main SCIP
749 */
750 if( SCIPheurGetData(heur)->original )
751 {
754 FALSE, FALSE, TRUE, success) );
755 }
756 else
757 {
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 */
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 */
799 *success = FALSE;
801 {
802 SCIP_CALL( SCIPcreateSol(scipcopy, &startsol, heur) );
803 for( v = 0; v < nvars; v++ )
804 {
806 subvar = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[v]);
807 if( subvar != NULL )
808 {
810 }
811 }
812
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 */
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 */
839 status = SCIPgetStatus(scipcopy);
840
841 /* copy solution to main scip */
842 if( status == SCIP_STATUS_BESTSOLLIMIT || status == SCIP_STATUS_OPTIMAL )
843 {
845
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);
860 SCIPfreeBufferArray(scip, &subvars);
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 {
914 SCIP_Real oldcoeff;
915
916 binfo.block = b;
917 binfo.otherblock = b2;
918 binfo.linkvaridx = linkvaridx;
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
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);
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}*/
983
985 SCIPheurSetData(heur, NULL);
986
987 assert(heurdata != NULL);
988
990
991 return SCIP_OKAY;
992}
993
994
995/** execution method of primal heuristic */
997{ /*lint --e{715}*/
998 char name[SCIP_MAXSTRLEN];
999 char info[SCIP_MAXSTRLEN];
1001 PROBLEM* problem;
1003 SCIP_DECOMP* decomp;
1005 SCIP_VAR** vars;
1008 SCIP_CONS** conss;
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;
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
1058
1059 problem = NULL;
1061 sortedconss = NULL;
1062 varlabels = NULL;
1063 conslabels = NULL;
1064 consssize = NULL;
1066 linkvars = NULL;
1071 varonlyobj = 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);
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);
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 */
1170
1173 SCIP_CALL( SCIPallocBufferArray(scip, &consssize, nblocks + 1) );
1174
1175 SCIPdecompGetConsLabels(decomp, conss, conslabels, nconss);
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 */
1186
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 */
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
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
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 */
1252
1253 b = 0;
1254 for( i = 0; i < nvars; i++ )
1255 {
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
1272 k = 0;
1273 for( b = 0; b < problem->nblocks; b++ )
1274 {
1275 var = SCIPfindVar((problem->blocks[b]).subscip, vname);
1276 if( var != NULL )
1277 {
1278 linkvartoblocks[i].indexes[k] = b;
1279 linkvartoblocks[i].size = k + 1;
1280 k++;
1281 }
1282 }
1283 }
1284
1285 /* check whether there is enough time left */
1286 SCIP_CALL( getTimeLeft(scip, &timeleft) );
1287 if( timeleft <= 0 )
1288 {
1289 SCIPdebugMsg(scip, "no time left\n");
1290 goto TERMINATE;
1291 }
1292
1293 /* init varonlyobj; true if variable is only part of the objective function */
1295 for( i = 0; i < numlinkvars; ++i)
1296 varonlyobj[i] = TRUE;
1297
1298 /* init and fill block to linking variables set */
1299 for( b = 0; b < problem->nblocks; b++ )
1300 {
1302 blocktolinkvars[b].size = 0;
1303
1304 k = 0;
1305 for( i = 0; i < numlinkvars; i++ )
1306 {
1307 SCIP_VAR* var;
1308 const char* vname;
1309
1311 var = SCIPfindVar((problem->blocks[b]).subscip, vname);
1312 if( var != NULL )
1313 {
1314 varonlyobj[i] = FALSE;
1315 blocktolinkvars[b].indexes[k] = i;
1316 blocktolinkvars[b].size = k + 1;
1317 k++;
1318 }
1319 }
1320 }
1321
1322 /* init arrays for slack variables and coupling constraints */
1323 for( b = 0; b < problem->nblocks; b++ )
1324 {
1325 SCIP_CALL( SCIPallocBufferArray(scip, &((problem->blocks[b]).slackspos), blocktolinkvars[b].size * (nblocks - 1)) );
1326 SCIP_CALL( SCIPallocBufferArray(scip, &((problem->blocks[b]).slacksneg), blocktolinkvars[b].size * (nblocks - 1)) );
1327 SCIP_CALL( SCIPallocBufferArray(scip, &((problem->blocks[b]).couplingcons), blocktolinkvars[b].size * (nblocks - 1)) );
1328 }
1329
1332 tmpcouplingcoef[0] = 1.0;
1333 tmpcouplingcoef[1] = 1.0;
1334 tmpcouplingcoef[2] = -1.0;
1335
1336 /* count hashtable entries */
1337 nentries = 0;
1338 for( b = 0; b < problem->nblocks; b++ )
1339 {
1340 for( i = 0; i < blocktolinkvars[b].size; i++ )
1341 {
1342 int linkvaridx = blocktolinkvars[b].indexes[i];
1343 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1344 {
1345 if( linkvartoblocks[linkvaridx].indexes[k] != b )
1346 nentries++;
1347 }
1348 }
1349 }
1350
1354
1355 /* extend submips */
1356 SCIPdebugMsg(scip, "Extending %d block models\n", problem->nblocks);
1357 for( b = 0; b < problem->nblocks; b++ )
1358 {
1360 int nblockvars;
1361
1362 blockvars = SCIPgetVars((problem->blocks[b]).subscip);
1363 nblockvars = SCIPgetNVars((problem->blocks[b]).subscip);
1364
1365 /* set objective function of each block to zero */
1366 for( i = 0; i < nblockvars; i++ )
1367 {
1368 SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, blockvars[i], 0.0) );
1369 }
1370
1371 /* add two slack variables for each linking variable in block */
1372 for( i = 0; i < blocktolinkvars[b].size; i++ )
1373 {
1374 int linkvaridx;
1375 linkvaridx = blocktolinkvars[b].indexes[i];
1376
1377 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1378 {
1379 int b2;
1380 b2 = linkvartoblocks[linkvaridx].indexes[k];
1381
1382 /* handle different blocks with common linking variable */
1383 if( b2 != b )
1384 {
1388 binfo->block = b;
1389 binfo->otherblock = b2;
1390 binfo->linkvaridx = linkvaridx;
1391 binfo->linkvar = SCIPfindVar((problem->blocks[b]).subscip, SCIPvarGetName(linkvars[linkvaridx]));
1392 j = (problem->blocks[b]).ncoupling;
1393
1394 /* create positive slack variable */
1395 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_slackpos_block_%d", SCIPvarGetName(linkvars[linkvaridx]), b2);
1396 (problem->blocks[b]).slackspos[j] = NULL;
1397 SCIP_CALL( SCIPcreateVarBasic((problem->blocks[b]).subscip,
1398 &((problem->blocks[b]).slackspos[j]), name,
1400 SCIP_CALL( SCIPaddVar((problem->blocks[b]).subscip, (problem->blocks[b]).slackspos[j]) );
1401 assert((problem->blocks[b]).slackspos[j] != NULL);
1402 binfo->slackposobjcoeff = 1.0;
1403 binfo->slackposvar = (problem->blocks[b]).slackspos[j];
1404
1405 /* create negative slack variable */
1406 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_slackneg_block_%d", SCIPvarGetName(linkvars[linkvaridx]), b2);
1407 (problem->blocks[b]).slacksneg[j] = NULL;
1408 SCIP_CALL( SCIPcreateVarBasic((problem->blocks[b]).subscip,
1409 &((problem->blocks[b]).slacksneg[j]), name,
1411 SCIP_CALL( SCIPaddVar((problem->blocks[b]).subscip, (problem->blocks[b]).slacksneg[j]) );
1412 assert((problem->blocks[b]).slacksneg[j] != NULL);
1413 binfo->slacknegobjcoeff = 1.0;
1414 binfo->slacknegvar = (problem->blocks[b]).slacksneg[j];
1415
1416 /* fill variables for linking constraint */
1417 tmpcouplingvars[0] = binfo->linkvar;
1418 tmpcouplingvars[1] = binfo->slackposvar;
1419 tmpcouplingvars[2] = binfo->slacknegvar;
1420
1421 /* create linking constraint */
1422 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_coupling_block_%d",
1423 SCIPvarGetName(linkvars[linkvaridx]), b2);
1424 (problem->blocks[b]).couplingcons[j] = NULL;
1425
1426 /* create linking constraint with initial side equal to zero (or lower bound of linking variable) */
1428 {
1429 SCIP_Real initval;
1430 SCIP_Real lb;
1431
1432 lb = SCIPvarGetLbOriginal(binfo->linkvar);
1433 initval = MAX(lb, 0.0);
1434
1435 SCIP_CALL( SCIPcreateConsBasicLinear((problem->blocks[b]).subscip, &((problem->blocks[b]).couplingcons[j]),
1437
1438 /* set initial value of linking variable */
1439 binfo->linkvarval = initval;
1440 }
1441
1442 /* create linking constraint with initial side equal to LP solution (rounded if variable is integer) */
1444 {
1445 SCIP_Real initval;
1446
1447 initval = SCIPvarGetLPSol(linkvars[linkvaridx]);
1450
1451 SCIP_CALL( SCIPcreateConsBasicLinear((problem->blocks[b]).subscip, &((problem->blocks[b]).couplingcons[j]),
1453
1454 /* set initial value of linking variable */
1455 binfo->linkvarval = initval;
1456 }
1457
1458 SCIP_CALL( SCIPaddCons((problem->blocks[b]).subscip, (problem->blocks[b]).couplingcons[j]) );
1459 assert((problem->blocks[b]).couplingcons[j] != NULL);
1460 binfo->couplingCons = (problem->blocks[b]).couplingcons[j];
1461
1462 (problem->blocks[b]).ncoupling++;
1463
1464 /* feed hashtable */
1466 }
1467 }
1468 }
1469 }
1471
1472#ifdef PADM_WRITE_PROBLEMS
1473 /* write extended submips */
1474 for( b = 0; b < problem->nblocks; b++ )
1475 {
1476 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "extended_block_%d.lp", b);
1477 SCIP_CALL( SCIPwriteOrigProblem((problem->blocks[b]).subscip, name, NULL, FALSE) );
1478 }
1479#endif
1480
1481 /* determine threshold for penalty coefficients via maximum norm */
1483 for( i = 0; i < nvars; i++ )
1484 {
1485 SCIP_Real obj;
1486
1488 if( obj > slackthreshold )
1490 }
1491
1492 /* ------------------------------------------------------------------------------------------------- */
1493
1494 /* check whether there is enough time left */
1495 SCIP_CALL( getTimeLeft(scip, &timeleft) );
1496 if( timeleft <= 0 )
1497 {
1498 SCIPdebugMsg(scip, "no time left\n");
1499 goto TERMINATE;
1500 }
1501
1502 SCIPdebugMsg(scip, "Starting iterations\n");
1503 SCIPdebugMsg(scip, "PIt\tADMIt\tSlacks\tInfo\n");
1504
1505 piter = 0;
1506 increasedslacks = 0;
1507 (void) SCIPsnprintf(info, SCIP_MAXSTRLEN, "-");
1508 solved = FALSE;
1509 istimeleft = TRUE;
1510
1511 /* Penalty loop */
1512 while( !solved && piter < heurdata->penaltyiterations && istimeleft )
1513 {
1514 piter++;
1516 aiter = 0;
1517
1518 /* Alternating direction method loop */
1519 while( solutionsdiffer && aiter < heurdata->admiterations && istimeleft )
1520 {
1521 aiter++;
1523 SCIPdebugMsg(scip, "%d\t%d\t%d\t%s\n", piter, aiter, increasedslacks, info);
1524
1525 /* Loop through the blocks and solve each sub-SCIP, potentially multiple times */
1526 for( b = 0; b < problem->nblocks; b++ )
1527 {
1528 for( i = 0; i < blocktolinkvars[b].size; i++ )
1529 {
1530 int linkvaridx;
1531 linkvaridx = blocktolinkvars[b].indexes[i];
1532
1533 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1534 {
1535 int b2;
1536 b2 = linkvartoblocks[linkvaridx].indexes[k];
1537
1538 if( b2 != b )
1539 {
1544
1545 SCIP_CONS* couplingcons;
1546 SCIP_Real newrhs;
1547
1548 binfo.block = b;
1549 binfo.otherblock = b2;
1550 binfo.linkvaridx = linkvaridx;
1551
1553 assert(binfoout != NULL);
1554 couplingcons = binfoout->couplingCons;
1555
1556 /* interchange blocks b and b2 for getting new right hand side */
1557 binfo2.block = b2;
1558 binfo2.otherblock = b;
1559 binfo2.linkvaridx = linkvaridx;
1561 assert(binfo2out != NULL);
1562 newrhs = binfo2out->linkvarval;
1563
1564 /* change side of coupling constraint equation with linking variable value of the other block */
1565 SCIP_CALL( SCIPchgLhsLinear((problem->blocks[b]).subscip, couplingcons, newrhs) );
1566 SCIP_CALL( SCIPchgRhsLinear((problem->blocks[b]).subscip, couplingcons, newrhs) );
1567
1568 /* change penalty coefficients of slack variables */
1569 SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, binfoout->slackposvar, binfoout->slackposobjcoeff) );
1570 SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, binfoout->slacknegvar, binfoout->slacknegobjcoeff) );
1571 }
1572 }
1573 }
1574
1575 /* increase slack penalty coeffs until each subproblem can be solved to optimality */
1576 do
1577 {
1578 SCIP_Longint nnodes;
1579 int iteration;
1580
1581#ifdef PADM_WRITE_PROBLEMS
1582 SCIPdebugMsg(scip, "write subscip of block %d in piter=%d and aiter=%d\n", b, piter, aiter);
1583 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "blockproblem_%d_%d_%d.lp", b, piter, aiter);
1584 SCIP_CALL( SCIPwriteOrigProblem((problem->blocks[b]).subscip, name, NULL, FALSE) );
1585#endif
1586
1587 SCIP_CALL( SCIPsetRealParam((problem->blocks[b]).subscip, "limits/gap", gap) );
1588
1589 /* reuse old solution if available */
1590 SCIP_CALL( reuseSolution((problem->blocks[b]).subscip, &problem->blocks[b]) );
1591
1592 /* update time and memory limit of subproblem */
1593 SCIP_CALL( SCIPcopyLimits(scip, (problem->blocks[b]).subscip) );
1594
1595 /* stop if there are not enough nodes left */
1596 if( nodesleft < heurdata->minnodes )
1597 {
1598 SCIPdebugMsg(scip, "Node limit reached.\n");
1599 goto TERMINATE;
1600 }
1601
1602 /* update node limit of subproblem
1603 * in the first iterations we have a smaller node limit
1604 */
1605 iteration = ((piter - 1) * heurdata->admiterations) + aiter;
1606 nnodes = (SCIP_Longint)SCIPceil(scip, (problem->blocks[b]).size * nodesleft * ( 1 - pow(heurdata->nodefac, (double)iteration) ));
1607 nnodes = MAX( heurdata->minnodes, nnodes );
1608 SCIP_CALL( SCIPsetLongintParam((problem->blocks[b]).subscip, "limits/nodes", nnodes) );
1609
1610 /* solve block
1611 *
1612 * errors in solving the subproblem should not kill the overall solving process;
1613 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1614 */
1615 SCIP_CALL_ABORT( SCIPsolve((problem->blocks[b]).subscip) );
1616 status = SCIPgetStatus((problem->blocks[b]).subscip);
1617
1618 /* subtract used nodes from the total nodelimit */
1619 nodesleft -= (SCIP_Longint)SCIPceil(scip, SCIPgetNNodes((problem->blocks[b]).subscip) * (problem->blocks[b]).size);
1620
1621 /* check solution if one of the four cases occurs
1622 * - solution is optimal
1623 * - solution reached gaplimit
1624 * - node limit reached with at least one feasible solution
1625 * - time limit is reached but best solution needs no slack variables (no dual solution available)
1626 */
1627 if( status == SCIP_STATUS_OPTIMAL || status == SCIP_STATUS_GAPLIMIT ||
1628 (status == SCIP_STATUS_NODELIMIT && SCIPgetNSols((problem->blocks[b]).subscip) > 0) ||
1629 (status == SCIP_STATUS_TIMELIMIT && SCIPgetNSols((problem->blocks[b]).subscip) > 0 &&
1630 SCIPisEQ(scip, SCIPgetSolOrigObj((problem->blocks[b]).subscip, SCIPgetBestSol((problem->blocks[b]).subscip)), 0.0) ) )
1631 {
1632 SCIPdebugMsg(scip, "Block is optimal or reached gaplimit or nodelimit.\n");
1633
1634 if( status == SCIP_STATUS_TIMELIMIT )
1635 {
1636 SCIPdebugMsg(scip, "Block reached time limit with at least one feasible solution.\n");
1637 istimeleft = FALSE;
1638 }
1639
1640 for( i = 0; i < blocktolinkvars[b].size; i++ )
1641 {
1642 int linkvaridx;
1643 linkvaridx = blocktolinkvars[b].indexes[i];
1644
1645 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1646 {
1647 int b2;
1648 b2 = linkvartoblocks[linkvaridx].indexes[k];
1649
1650 if( b2 != b )
1651 {
1652 SCIP_SOL* sol;
1655 SCIP_VAR* var;
1656 SCIP_Real val;
1657
1658 binfo.block = b;
1659 binfo.otherblock = b2;
1660 binfo.linkvaridx = linkvaridx;
1662 assert(binfoout != NULL);
1663
1664 sol = SCIPgetBestSol((problem->blocks[b]).subscip);
1665 assert(sol != NULL);
1666 var = binfoout->linkvar;
1667 val = SCIPgetSolVal((problem->blocks[b]).subscip, sol, var);
1668
1669 if( !EPSEQ(binfoout->linkvarval, val, SCIP_DEFAULT_EPSILON) )
1671
1672 binfoout->linkvarval = val;
1673 }
1674 }
1675 }
1676 }
1677 else if( status == SCIP_STATUS_UNBOUNDED )
1678 {
1679 SCIPdebugMsg(scip, "Block is unbounded.\n");
1680 for( i = 0; i < blocktolinkvars[b].size; i++ )
1681 {
1682 int linkvaridx;
1683 linkvaridx = blocktolinkvars[b].indexes[i];
1684
1685 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1686 {
1687 int b2;
1688 b2 = linkvartoblocks[linkvaridx].indexes[k];
1689
1690 if( b2 != b )
1691 {
1694
1695 binfo.block = b;
1696 binfo.otherblock = b2;
1697 binfo.linkvaridx = linkvaridx;
1699 assert(binfoout != NULL);
1700
1701 /* increase penalty coefficients to obtain a bounded subproblem */
1702 binfoout->slackposobjcoeff *= 10.0;
1703 binfoout->slacknegobjcoeff *= 10.0;
1704 SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, binfoout->slackposvar, binfoout->slackposobjcoeff) );
1705 SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, binfoout->slacknegvar, binfoout->slacknegobjcoeff) );
1706 }
1707 }
1708 }
1709 }
1710 else if( status == SCIP_STATUS_TIMELIMIT )
1711 {
1712 SCIPdebugMsg(scip, "Block reached time limit. No optimal solution available.\n");
1713 goto TERMINATE;
1714 }
1715 else
1716 {
1717 SCIPdebugMsg(scip, "Block solving status %d not supported\n", status);
1718 goto TERMINATE;
1719 }
1720
1721 /* free solving data in order to change problem */
1722 SCIP_CALL( SCIPfreeTransform((problem->blocks[b]).subscip) );
1723 }
1724 while( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_GAPLIMIT &&
1725 !(status == SCIP_STATUS_NODELIMIT && SCIPgetNSols((problem->blocks[b]).subscip) > 0) &&
1726 !(status == SCIP_STATUS_TIMELIMIT && SCIPgetNSols((problem->blocks[b]).subscip) > 0 &&
1727 SCIPisEQ(scip, SCIPgetSolOrigObj((problem->blocks[b]).subscip, SCIPgetBestSol((problem->blocks[b]).subscip)), 0.0) ) );
1728 }
1729 }
1730
1731 /* check wether problem has been solved and if not update penalty coeffs */
1732 doscaling = FALSE;
1733 solved = TRUE;
1734 increasedslacks = 0;
1736 for( b = 0; b < problem->nblocks; b++ )
1737 {
1738 for( i = 0; i < blocktolinkvars[b].size; i++ )
1739 {
1740 int linkvaridx;
1741 linkvaridx = blocktolinkvars[b].indexes[i];
1742
1743 for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1744 {
1745 int b2;
1746 b2 = linkvartoblocks[linkvaridx].indexes[k];
1747
1748 if( b2 != b )
1749 {
1750 SCIP_SOL* sol;
1753 SCIP_Real slackposval;
1754 SCIP_Real slacknegval;
1755
1756 binfo.block = b;
1757 binfo.otherblock = b2;
1758 binfo.linkvaridx = linkvaridx;
1760 assert(binfoout != NULL);
1761
1762 sol = SCIPgetBestSol((problem->blocks[b]).subscip);
1763 slackposval = SCIPgetSolVal((problem->blocks[b]).subscip, sol, binfoout->slackposvar);
1764 slacknegval = SCIPgetSolVal((problem->blocks[b]).subscip, sol, binfoout->slacknegvar);
1765
1766 /* increase penalty coefficient of positive slack variable */
1767 if( SCIPisGT(scip, slackposval, 0.0) )
1768 {
1769 binfoout->slackposobjcoeff *= 10.0;
1770
1771 if( binfoout->slackposobjcoeff > slackthreshold )
1772 doscaling = TRUE;
1773
1774 if( binfoout->slackposobjcoeff > maxpenalty )
1775 maxpenalty = binfoout->slackposobjcoeff;
1776
1777 solved = FALSE;
1779 }
1780
1781 /* increase penalty coefficient of negative slack variable */
1782 if( SCIPisGT(scip, slacknegval, 0.0) )
1783 {
1784 binfoout->slacknegobjcoeff *= 10.0;
1785
1786 if( binfoout->slacknegobjcoeff > slackthreshold )
1787 doscaling = TRUE;
1788
1789 if( binfoout->slacknegobjcoeff > maxpenalty )
1790 maxpenalty = binfoout->slacknegobjcoeff;
1791
1792 solved = FALSE;
1794 }
1795 }
1796 }
1797 }
1798 }
1799
1800 /* should sigmoid scaling be applied to the penalty parameters? */
1801 if( doscaling && heurdata->scaling )
1802 {
1803 SCIPdebugMsg(scip, "rescale penalty parameters\n");
1804
1805 /* reset counter */
1806 increasedslacks = 0;
1807
1808 /* rescale penalty parameters */
1810 }
1811
1812 /* adapt in some cases the gap parameter */
1813 if( (aiter == 1 && solutionsdiffer == FALSE) || (doscaling && heurdata->scaling) )
1814 {
1815 SCIP_Real mingap = 0.001; //todo
1816 SCIP_Real newgap = MAX(gap * 0.5, mingap);
1817
1818 if( newgap >= mingap )
1819 {
1820 if( doscaling && heurdata->scaling )
1821 (void) SCIPsnprintf(info, SCIP_MAXSTRLEN, "scale, %f", newgap);
1822 else
1823 (void) SCIPsnprintf(info, SCIP_MAXSTRLEN, "%f", newgap);
1824
1825 gap = newgap;
1826 }
1827 }
1828
1829 /* free solution process data */
1830 if( !solved )
1831 for( b = 0; b < problem->nblocks; b++ )
1832 {
1833 SCIP_CALL( SCIPfreeTransform((problem->blocks[b]).subscip) );
1834 }
1835 }
1836
1837 /* copy solution if present */
1838 if( solved )
1839 {
1841 SCIP_Real* blocksolvals;
1842
1843 assert(increasedslacks == 0);
1844
1846 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1847
1848 for( b = 0; b < problem->nblocks; b++ )
1849 {
1852 int nblockvars;
1853
1854 /* get solution of block variables (without slack variables) */
1855 blocksol = SCIPgetBestSol((problem->blocks[b]).subscip);
1856 assert(blocksol != NULL);
1857 blockvars = (problem->blocks[b]).subvars;
1858 nblockvars = (problem->blocks[b]).nsubvars;
1859 SCIP_CALL( SCIPgetSolVals((problem->blocks[b]).subscip, blocksol, nblockvars, blockvars, blocksolvals) );
1860
1861 for( i = 0; i < nblockvars; i++ )
1862 {
1864 SCIP_Real solval;
1865
1867 solval = blocksolvals[i];
1869 }
1870 }
1871
1872 /* treat variables with no constraints; set value of variable to bound */
1873 for( i = 0; i < numlinkvars; i++ )
1874 {
1875 if( varonlyobj[i] )
1876 {
1877 SCIP_Real fixedvalue;
1878 if( SCIPvarGetObj(linkvars[i]) < 0 )
1879 {
1882 break; // todo: maybe we should return the status UNBOUNDED instead
1883 }
1884 else
1885 {
1888 break; // todo: maybe we should return the status UNBOUNDED instead
1889 }
1891 }
1892 }
1893
1894 SCIPdebugMsg(scip, "Objective value %.2f\n", SCIPgetSolOrigObj(scip, newsol));
1895
1896 /* fix linking variables and reoptimize with original objective function */
1897 if( heurdata->reoptimize )
1898 {
1902
1903 if( success )
1904 {
1906 if( !success )
1907 {
1908 SCIPdebugMsg(scip, "Reoptimizing solution failed\n");
1909 }
1910 else
1911 {
1912 SCIPdebugMsg(scip, "Reoptimizing solution successful\n");
1914 }
1915 }
1916 }
1917
1918 /* if reoptimization is turned off or reoptimization found no solution, try initial solution */
1919 if( *result != SCIP_FOUNDSOL )
1920 {
1922 if( !success )
1923 {
1924 SCIPdebugMsg(scip, "Solution copy failed\n");
1925 }
1926 else
1927 {
1928 SCIPdebugMsg(scip, "Solution copy successful\n");
1930 }
1931 }
1932 else
1933 {
1935 }
1936
1938 }
1939 else
1940 {
1941 SCIPdebugMsg(scip, "maximum number of penalty loops reached\n");
1943 }
1944
1945TERMINATE:
1946 /* release variables, constraints and free memory */
1947 if( problem != NULL )
1948 {
1949 for( b = 0; b < problem->nblocks; b++ )
1950 {
1951 BLOCK curr_block = problem->blocks[b];
1952 for( i = 0; i < (problem->blocks[b]).ncoupling; i++ )
1953 {
1954 SCIP_CALL( SCIPreleaseCons(curr_block.subscip, &curr_block.couplingcons[i]) );
1955 SCIP_CALL( SCIPreleaseVar(curr_block.subscip, &curr_block.slackspos[i]) );
1956 SCIP_CALL( SCIPreleaseVar(curr_block.subscip, &curr_block.slacksneg[i]) );
1957 }
1958 }
1959 }
1960
1961 if( htable != NULL )
1963
1964 if( blockinfolist != NULL )
1966
1967 if( tmpcouplingcoef != NULL )
1969
1970 if( tmpcouplingvars != NULL )
1972
1973 if( problem != NULL )
1974 {
1975 for( b = problem->nblocks - 1; b >= 0; b-- )
1976 {
1977 if( problem->blocks[b].couplingcons != NULL )
1978 {
1979 SCIPfreeBufferArray(scip, &problem->blocks[b].couplingcons);
1980 SCIPfreeBufferArray(scip, &problem->blocks[b].slacksneg);
1981 SCIPfreeBufferArray(scip, &problem->blocks[b].slackspos);
1982 }
1983 }
1984 }
1985
1986 if( varonlyobj != NULL )
1988
1989 if( problem != NULL && blocktolinkvars != NULL )
1990 {
1991 for( b = problem->nblocks -1; b >= 0; b-- )
1992 {
1993 if( blocktolinkvars[b].indexes != NULL )
1995 }
1996 }
1997
1998 if( linkvars != NULL )
2000
2001 if( alllinkvartoblocks != NULL )
2003
2004 if( blocktolinkvars != NULL )
2006
2007 if( linkvartoblocks != NULL )
2009
2010 if( assigneddecomp != NULL )
2012
2013 if( consssize != NULL )
2014 SCIPfreeBufferArray(scip, &consssize);
2015
2016 if( conslabels != NULL )
2018
2019 if( varlabels != NULL )
2021
2022 if( sortedconss != NULL )
2024
2025 if( problem != NULL )
2026 {
2027 SCIP_CALL( freeProblem(&problem, nblocks) );
2028 }
2029
2030 SCIPdebugMsg(scip, "Leave padm heuristic\n");
2031 return SCIP_OKAY;
2032}
2033
2034/*
2035 * primal heuristic specific interface methods
2036 */
2037
2038/** creates the PADM primal heuristic and includes it in SCIP */
2040 SCIP* scip /**< SCIP data structure */
2041 )
2042{
2044 SCIP_HEUR* heur = NULL;
2045
2046 /* create PADM primal heuristic data */
2048
2049 /* include primal heuristic */
2050
2051 /* use SCIPincludeHeurBasic() plus setter functions if you want to set callbacks one-by-one and your code should
2052 * compile independent of new callbacks being added in future SCIP versions
2053 */
2057
2058 assert(heur != NULL);
2059
2060 /* set non fundamental callbacks via setter functions */
2063
2064 /* add padm primal heuristic parameters */
2065 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
2066 "maximum number of nodes to regard in all subproblems",
2068
2069 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
2070 "minimum number of nodes to regard in one subproblem",
2072
2073 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodefac",
2074 "factor to control nodelimits of subproblems", &heurdata->nodefac, TRUE, DEFAULT_NODEFAC, 0.0, 0.99, NULL, NULL) );
2075
2076 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/admiterations",
2077 "maximal number of ADM iterations in each penalty loop", &heurdata->admiterations, TRUE, DEFAULT_ADMIT, 1, 100, NULL, NULL) );
2078
2079 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/penaltyiterations",
2080 "maximal number of penalty iterations", &heurdata->penaltyiterations, TRUE, DEFAULT_PENALTYIT, 1, 100000, NULL, NULL) );
2081
2082 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/gap",
2083 "mipgap at start", &heurdata->gap, TRUE, DEFAULT_GAP, 0.0, 16.0, NULL, NULL) );
2084
2085 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reoptimize",
2086 "should the problem get reoptimized with the original objective function?", &heurdata->reoptimize, FALSE, TRUE, NULL, NULL) );
2087
2088 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/scaling",
2089 "enable sigmoid rescaling of penalty parameters", &heurdata->scaling, TRUE, TRUE, NULL, NULL) );
2090
2091 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/assignlinking",
2092 "should linking constraints be assigned?", &heurdata->assignlinking, FALSE, TRUE, NULL, NULL) );
2093
2094 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/original",
2095 "should the original problem be used? This is only for testing and not recommended!", &heurdata->original, TRUE, FALSE, NULL, NULL) );
2096
2097 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/timing",
2098 "should the heuristic run before or after the processing of the node? (0: before, 1: after, 2: both)",
2099 &heurdata->timing, FALSE, 0, 0, 2, NULL, NULL) );
2100
2101 return SCIP_OKAY;
2102}
SCIP_VAR ** b
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_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)
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: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
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: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:2039
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 SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
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 SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
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 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)
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: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:1250
SCIP_Bool SCIPdoNotMultaggr(SCIP *scip)
Definition scip_var.c:8577
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:4515
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10877
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:938
static SCIP_RETCODE initProblem(SCIP *scip, PROBLEM **problem, int nblocks)
Definition heur_padm.c:258
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_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
#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
#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
#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 Problem PROBLEM
Definition heur_padm.c:107
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.
static SCIP_VAR ** vars
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
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 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
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:105
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
#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