SCIP
Solving Constraint Integer Programs
heur_padm.c File Reference
Detailed Description
PADM primal heuristic.
Primal heuristic based on ideas published in the papers "A Decomposition Heuristic for Mixed-Integer Supply Chain Problems" by Martin Schmidt, Lars Schewe, and Dieter Weninger, and "Exploiting user-supplied Decompositions inside Heuristics" by Katrin Halbig, Adrian Göß and Dieter Weninger.
The penalty alternating direction method (PADM) heuristic is a construction heuristic which additionally needs a user decomposition with linking variables only.
PADM splits the problem into several sub-SCIPs according to the decomposition, whereby the linking variables get copied and the difference is penalized. Then the sub-SCIPs are solved on an alternating basis until they arrive at the same values of the linking variables (ADM-loop). If they don't reconcile after a couple of iterations, the penalty parameters are increased (penalty-loop) and the sub-SCIPs are solved again on an alternating basis.
Definition in file heur_padm.c.
#include <assert.h>#include <string.h>#include "blockmemshell/memory.h"#include "scip/cons_linear.h"#include "scip/debug.h"#include "scip/heur_padm.h"#include "scip/heuristics.h"#include "scip/pub_cons.h"#include "scip/pub_tree.h"#include "scip/pub_heur.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/pub_misc_select.h"#include "scip/pub_sol.h"#include "scip/pub_var.h"#include "scip/scipdefplugins.h"#include "scip/scip_branch.h"#include "scip/scip_cons.h"#include "scip/scip_copy.h"#include "scip/scip_dcmp.h"#include "scip/scip_general.h"#include "scip/scip_heur.h"#include "scip/scip_lp.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_nodesel.h"#include "scip/scip_numerics.h"#include "scip/scip_param.h"#include "scip/scip_prob.h"#include "scip/scip_randnumgen.h"#include "scip/scip_sol.h"#include "scip/scip_solve.h"#include "scip/scip_solvingstats.h"#include "scip/scip_table.h"#include "scip/scip_timing.h"#include "scip/scip_tree.h"#include "scip/scip_var.h"Go to the source code of this file.
Data Structures | |
| struct | Block |
| struct | set |
| struct | blockinfo |
Macros | |
| #define | HEUR_NAME "padm" |
| #define | HEUR_DESC "penalty alternating direction method primal heuristic" |
| #define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
| #define | HEUR_PRIORITY 70000 |
| #define | HEUR_FREQ 0 |
| #define | HEUR_FREQOFS 0 |
| #define | HEUR_MAXDEPTH -1 |
| #define | HEUR_TIMING SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_AFTERNODE |
| #define | HEUR_USESSUBSCIP TRUE |
| #define | COUPLINGSIZE 3 |
| #define | DEFAULT_MINNODES 50LL |
| #define | DEFAULT_MAXNODES 5000LL |
| #define | DEFAULT_NODEFAC 0.8 |
| #define | DEFAULT_ADMIT 4 |
| #define | DEFAULT_PENALTYIT 100 |
| #define | DEFAULT_GAP 2.0 |
Typedefs | |
| typedef struct Problem | PROBLEM |
| typedef struct Block | BLOCK |
| typedef struct set | SET |
| typedef struct blockinfo | BLOCKINFO |
Functions | |
| static | SCIP_DECL_HASHKEYEQ (indexesEqual) |
| static | SCIP_DECL_HASHKEYVAL (indexesHashval) |
| static SCIP_RETCODE | initBlock (PROBLEM *problem) |
| static SCIP_RETCODE | freeBlock (BLOCK *block) |
| static SCIP_RETCODE | initProblem (SCIP *scip, PROBLEM **problem, int nblocks) |
| static SCIP_RETCODE | freeProblem (PROBLEM **problem, int nblocks) |
| static SCIP_RETCODE | createSubscip (SCIP *scip, SCIP **subscip) |
| 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) |
| static SCIP_RETCODE | blockCreateSubscip (BLOCK *block, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_CONS **conss, int nconss, SCIP_Bool useorigprob, SCIP_Bool *success) |
| static SCIP_RETCODE | createAndSplitProblem (SCIP *scip, SCIP_CONS **sortedconss, int nconss, int *consssize, int nblocks, PROBLEM **problem, SCIP_Bool useorigprob, SCIP_Bool *success) |
| 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) |
| static SCIP_RETCODE | reuseSolution (SCIP *subscip, BLOCK *block) |
| 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) |
| static SCIP_RETCODE | scalePenalties (PROBLEM *problem, SET *linkvartoblocks, SET *blocktolinkvars, SCIP_HASHTABLE *htable, SCIP_Real maxpenalty) |
| static SCIP_RETCODE | getTimeLeft (SCIP *scip, SCIP_Real *time) |
| static | SCIP_DECL_HEURCOPY (heurCopyPADM) |
| static | SCIP_DECL_HEURFREE (heurFreePADM) |
| static | SCIP_DECL_HEUREXEC (heurExecPADM) |
| SCIP_RETCODE | SCIPincludeHeurPADM (SCIP *scip) |
Macro Definition Documentation
◆ HEUR_NAME
| #define HEUR_NAME "padm" |
Definition at line 84 of file heur_padm.c.
◆ HEUR_DESC
| #define HEUR_DESC "penalty alternating direction method primal heuristic" |
Definition at line 85 of file heur_padm.c.
◆ HEUR_DISPCHAR
| #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 86 of file heur_padm.c.
◆ HEUR_PRIORITY
| #define HEUR_PRIORITY 70000 |
Definition at line 87 of file heur_padm.c.
◆ HEUR_FREQ
| #define HEUR_FREQ 0 |
Definition at line 88 of file heur_padm.c.
◆ HEUR_FREQOFS
| #define HEUR_FREQOFS 0 |
Definition at line 89 of file heur_padm.c.
◆ HEUR_MAXDEPTH
| #define HEUR_MAXDEPTH -1 |
Definition at line 90 of file heur_padm.c.
◆ HEUR_TIMING
| #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_AFTERNODE |
Definition at line 91 of file heur_padm.c.
◆ HEUR_USESSUBSCIP
| #define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 92 of file heur_padm.c.
◆ COUPLINGSIZE
| #define COUPLINGSIZE 3 |
Definition at line 94 of file heur_padm.c.
◆ DEFAULT_MINNODES
| #define DEFAULT_MINNODES 50LL |
Definition at line 95 of file heur_padm.c.
◆ DEFAULT_MAXNODES
| #define DEFAULT_MAXNODES 5000LL |
Definition at line 96 of file heur_padm.c.
◆ DEFAULT_NODEFAC
| #define DEFAULT_NODEFAC 0.8 |
Definition at line 97 of file heur_padm.c.
◆ DEFAULT_ADMIT
| #define DEFAULT_ADMIT 4 |
Definition at line 98 of file heur_padm.c.
◆ DEFAULT_PENALTYIT
| #define DEFAULT_PENALTYIT 100 |
Definition at line 99 of file heur_padm.c.
◆ DEFAULT_GAP
| #define DEFAULT_GAP 2.0 |
Definition at line 100 of file heur_padm.c.
Typedef Documentation
◆ PROBLEM
| typedef struct Problem PROBLEM |
data related to one problem (see below)
Definition at line 107 of file heur_padm.c.
◆ BLOCK
◆ SET
◆ BLOCKINFO
Function Documentation
◆ SCIP_DECL_HASHKEYEQ()
|
static |
returns TRUE iff both keys are equal
Definition at line 157 of file heur_padm.c.
References blockinfo::block, FALSE, blockinfo::linkvaridx, blockinfo::otherblock, and TRUE.
◆ SCIP_DECL_HASHKEYVAL()
|
static |
returns the hash value of the key
Definition at line 174 of file heur_padm.c.
References blockinfo::block, blockinfo::linkvaridx, blockinfo::otherblock, SCIPhashFour, and SCIPrealHashCode().
◆ initBlock()
|
static |
initializes one block
- Parameters
-
problem problem structure
Definition at line 206 of file heur_padm.c.
References Block::couplingcons, Block::ncoupling, Block::nsubvars, NULL, Block::number, Block::problem, SCIP_OKAY, Block::size, Block::slacksneg, Block::slackspos, Block::subscip, and Block::subvars.
Referenced by createAndSplitProblem().
◆ freeBlock()
|
static |
frees component structure
- Parameters
-
block block structure
Definition at line 235 of file heur_padm.c.
References Block::ncoupling, NULL, Block::problem, SCIP_CALL, SCIP_OKAY, SCIPfree(), SCIPfreeBufferArray, Block::subscip, and Block::subvars.
Referenced by freeProblem().
◆ initProblem()
|
static |
initializes subproblem structure
- Parameters
-
scip SCIP data structure problem pointer to problem structure nblocks number of blocks
Definition at line 258 of file heur_padm.c.
References NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPdebugMessage, SCIPduplicateMemoryArray, SCIPgetProbName(), and SCIPsnprintf().
Referenced by createAndSplitProblem().
◆ freeProblem()
|
static |
frees subproblem structure
- Parameters
-
problem pointer to problem to free nblocks number of blocks in decomposition
Definition at line 288 of file heur_padm.c.
References freeBlock(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPfreeMemoryArray.
Referenced by createAndSplitProblem(), and SCIP_DECL_HEUREXEC().
◆ createSubscip()
|
static |
creates a sub-SCIP for the given variables and constraints
- Parameters
-
scip main SCIP data structure subscip pointer to store created sub-SCIP
Definition at line 324 of file heur_padm.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIPcopyLimits(), SCIPcreate(), SCIPgetRealParam(), SCIPincludeDefaultPlugins(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetPresolving(), SCIPsetRealParam(), SCIPsetSeparating(), SCIPsetSubscipsOff(), and TRUE.
Referenced by blockCreateSubscip().
◆ copyToSubscip()
|
static |
copies the given constraints and the corresponding variables to the given sub-SCIP
- Parameters
-
scip source SCIP subscip target SCIP name name for copied problem conss constraints to copy varmap hashmap used for the copy process of variables consmap hashmap used for the copy process of constraints nconss number of constraints to copy useorigprob do we use the original problem? success pointer to store whether copying was successful
Definition at line 372 of file heur_padm.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPconsGetHdlr(), SCIPconsIsActive(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPcopyProb(), SCIPgetConsCopy(), SCIPreleaseCons(), and TRUE.
Referenced by blockCreateSubscip().
◆ blockCreateSubscip()
|
static |
creates the subscip for a given block
- Parameters
-
block block structure varmap variable hashmap used to improve performance consmap constraint hashmap used to improve performance conss constraints contained in this block nconss number of constraints contained in this block useorigprob do we use the original problem? success pointer to store whether the copying process was successful
Definition at line 433 of file heur_padm.c.
References copyToSubscip(), createSubscip(), FALSE, Block::nsubvars, NULL, Block::number, Block::problem, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfree(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNOrigBinVars(), SCIPgetNOrigIntVars(), SCIPgetNOrigVars(), SCIPgetNVars(), SCIPgetOrigVars(), SCIPsnprintf(), Block::size, Block::subscip, Block::subvars, and TRUE.
Referenced by createAndSplitProblem().
◆ createAndSplitProblem()
|
static |
creates problem structure and split it into blocks
- Parameters
-
scip SCIP data structure sortedconss array of (checked) constraints sorted by blocks nconss number of constraints consssize number of constraints per block (and border at index 0) nblocks number of blocks problem pointer to store problem structure useorigprob do we use the original problem? success pointer to store whether the process was successful
Definition at line 505 of file heur_padm.c.
References b, blockCreateSubscip(), freeProblem(), initBlock(), initProblem(), NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapFree(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ assignLinking()
|
static |
copies labels to newdecomp and assigns linking constraints if possible
- Parameters
-
scip SCIP data structure newdecomp decomposition with (partially) assigned linking constraints vars array of variables sortedconss sorted array of constraints varlabels array of variable labels conslabels sorted array of constraint labels nvars number of variables nconss number of constraints nlinkconss number of linking constraints
Definition at line 573 of file heur_padm.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPassignDecompLinkConss(), SCIPcomputeDecompStats(), SCIPcomputeDecompVarsLabels(), SCIPdebugMsg, SCIPdecompGetConsLabels(), SCIPdecompGetVarsLabels(), SCIPdecompSetConsLabels(), SCIPdecompSetVarsLabels(), SCIPsortIntPtr(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ reuseSolution()
|
static |
computes feasible solution from last stored solution of the block
- Parameters
-
subscip SCIP data structure block block structure
Definition at line 614 of file heur_padm.c.
References Block::couplingcons, COUPLINGSIZE, Block::ncoupling, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddSolFree(), SCIPallocBufferArray, SCIPcreateOrigSol(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetConsVars(), SCIPgetLhsLinear(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetRhsLinear(), SCIPgetSolOrigObj(), SCIPgetSols(), SCIPgetSolVal(), SCIPgetSolVals(), SCIPgetVars(), SCIPisEQ(), SCIPsetSolVal(), SCIPsetSolVals(), Block::slacksneg, and Block::slackspos.
Referenced by SCIP_DECL_HEUREXEC().
◆ reoptimize()
|
static |
reoptimizes the heuristic solution with original objective function
Since the main algorithm of padm ignores the objective function, this method can be called to obtain better solutions. It copies the main scip, fixes the linking variables at the values of the already found solution and solves the new problem with small limits.
- Parameters
-
scip SCIP data structure heur pointer to heuristic sol heuristic solution vars pointer to variables nvars number of variables linkvars pointer to linking variables nlinkvars number of linking variables newsol pointer to store improved solution success pointer to store whether reoptimization was successful
Definition at line 712 of file heur_padm.c.
References FALSE, NULL, SCIP_CALL, SCIP_CALL_ABORT, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_OPTIMAL, SCIPallocBufferArray, SCIPblkmem(), SCIPcopyConsCompression(), SCIPcopyLimits(), SCIPcopyOrigConsCompression(), SCIPcreate(), SCIPcreateSol(), SCIPdebugMsg, SCIPfree(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNOrigVars(), SCIPgetNVars(), SCIPgetRealParam(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetSolVals(), SCIPgetStatus(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPheurGetTime(), SCIPinfinity(), SCIPisLT(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetPresolving(), SCIPsetRealParam(), SCIPsetSeparating(), SCIPsetSolVal(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPtransformProb(), SCIPtranslateSubSol(), SCIPtrySolFree(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ scalePenalties()
|
static |
rescales the penalty parameters
A sigmoid function is a function with an "S"-shaped graph, e.g. S(x) = x/(1+|x|). In order to avoid numerical instabilities due to large penalty parameters we rescale them using the sigmoid function S(x) = (x - shift)/(flatness + |x - shift|) * (range/2) + offset. The parameters are mapped into the more controllable interval [lowestslack, range + lowestslack].
- Parameters
-
problem block structure linkvartoblocks linking variable to blocks set blocktolinkvars block to linking variable set htable hashtable containing blockinfo maxpenalty maximum penalty parameter
Definition at line 875 of file heur_padm.c.
References b, blockinfo::block, set::indexes, blockinfo::linkvaridx, NULL, blockinfo::otherblock, REALABS, SCIP_OKAY, SCIP_Real, SCIPhashtableRetrieve(), set::size, blockinfo::slacknegobjcoeff, and blockinfo::slackposobjcoeff.
Referenced by SCIP_DECL_HEUREXEC().
◆ getTimeLeft()
|
static |
returns the available time limit that is left
- Parameters
-
scip SCIP data structure time pointer to store remaining time
Definition at line 938 of file heur_padm.c.
References MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPinfinity(), and SCIPisInfinity().
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 965 of file heur_padm.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurPADM().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 980 of file heur_padm.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 996 of file heur_padm.c.
References assignLinking(), b, blockinfo::block, Block::couplingcons, blockinfo::couplingCons, COUPLINGSIZE, createAndSplitProblem(), EPSEQ, FALSE, freeProblem(), getTimeLeft(), HEUR_NAME, set::indexes, blockinfo::linkvar, blockinfo::linkvaridx, blockinfo::linkvarval, MAX, nnodes, NULL, SCIP_Cons::original, SCIP_Decomp::original, blockinfo::otherblock, REALABS, reoptimize(), reuseSolution(), scalePenalties(), SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_DECOMP_LINKCONS, SCIP_DECOMP_LINKVAR, SCIP_DEFAULT_EPSILON, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_HEURTIMING_AFTERNODE, SCIP_HEURTIMING_BEFORENODE, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_VARTYPE_CONTINUOUS, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPblkmem(), SCIPceil(), SCIPchgLhsLinear(), SCIPchgRhsLinear(), SCIPchgVarObj(), SCIPcomputeDecompStats(), SCIPcopyLimits(), SCIPcreateConsBasicLinear(), SCIPcreateDecomp(), SCIPcreateSol(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPdecompGetConsLabels(), SCIPdecompGetConssSize(), SCIPdecompGetNBlocks(), SCIPdecompGetNBorderConss(), SCIPdecompGetNBorderVars(), SCIPdecompGetVarsLabels(), SCIPdecompUseBendersLabels(), SCIPdoNotMultaggr(), SCIPduplicateBufferArray, SCIPfindVar(), SCIPfreeBufferArray, SCIPfreeDecomp(), SCIPfreeSol(), SCIPfreeTransform(), SCIPgetBestSol(), SCIPgetBoolParam(), SCIPgetConss(), SCIPgetDecomps(), SCIPgetIntParam(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNConss(), SCIPgetNNodes(), SCIPgetNOrigConss(), SCIPgetNOrigVars(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetOrigConss(), SCIPgetOrigVars(), SCIPgetRealParam(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetSolVals(), SCIPgetStatus(), SCIPgetVars(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableGetNElements(), SCIPhashtableRetrieve(), SCIPhashtableSafeInsert(), SCIPheurGetData(), SCIPinfinity(), SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisParamFixed(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPround(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsetSolVal(), SCIPsnprintf(), SCIPsolve(), SCIPsortIntPtr(), SCIPtrySolFree(), SCIPvarGetLbLocal(), SCIPvarGetLbOriginal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPwarningMessage(), SCIPwriteOrigProblem(), SCIPwriteTransProblem(), set::size, blockinfo::slacknegobjcoeff, blockinfo::slacknegvar, blockinfo::slackposobjcoeff, blockinfo::slackposvar, Block::slacksneg, Block::slackspos, Block::subscip, and TRUE.