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 |
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) |
#define HEUR_NAME "padm" |
Definition at line 84 of file heur_padm.c.
#define HEUR_DESC "penalty alternating direction method primal heuristic" |
Definition at line 85 of file heur_padm.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 86 of file heur_padm.c.
#define HEUR_PRIORITY 70000 |
Definition at line 87 of file heur_padm.c.
#define HEUR_FREQ 0 |
Definition at line 88 of file heur_padm.c.
#define HEUR_FREQOFS 0 |
Definition at line 89 of file heur_padm.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 90 of file heur_padm.c.
#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_AFTERNODE |
Definition at line 91 of file heur_padm.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 92 of file heur_padm.c.
#define COUPLINGSIZE 3 |
Definition at line 94 of file heur_padm.c.
Referenced by reuseSolution(), and SCIP_DECL_HEUREXEC().
#define DEFAULT_MINNODES 50LL |
Definition at line 95 of file heur_padm.c.
#define DEFAULT_MAXNODES 5000LL |
Definition at line 96 of file heur_padm.c.
#define DEFAULT_NODEFAC 0.8 |
Definition at line 97 of file heur_padm.c.
Referenced by SCIPincludeHeurPADM().
#define DEFAULT_ADMIT 4 |
Definition at line 98 of file heur_padm.c.
Referenced by SCIPincludeHeurPADM().
#define DEFAULT_PENALTYIT 100 |
Definition at line 99 of file heur_padm.c.
Referenced by SCIPincludeHeurPADM().
#define DEFAULT_GAP 2.0 |
Definition at line 100 of file heur_padm.c.
Referenced by SCIPincludeHeurPADM().
|
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.
|
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().
|
static |
initializes one block
problem | problem structure |
Definition at line 206 of file heur_padm.c.
References assert(), 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().
|
static |
frees component structure
block | block structure |
Definition at line 235 of file heur_padm.c.
References assert(), Block::ncoupling, NULL, Block::problem, SCIP_CALL, SCIP_OKAY, SCIPfree(), SCIPfreeBufferArray, Block::subscip, and Block::subvars.
Referenced by freeProblem().
|
static |
initializes subproblem structure
scip | SCIP data structure |
problem | pointer to problem structure |
nblocks | number of blocks |
Definition at line 258 of file heur_padm.c.
References assert(), NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPdebugMessage, SCIPduplicateMemoryArray, SCIPgetProbName(), and SCIPsnprintf().
Referenced by createAndSplitProblem().
|
static |
frees subproblem structure
problem | pointer to problem to free |
nblocks | number of blocks in decomposition |
Definition at line 288 of file heur_padm.c.
References assert(), c, freeBlock(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPfreeMemoryArray.
Referenced by createAndSplitProblem(), and SCIP_DECL_HEUREXEC().
|
static |
creates a sub-SCIP for the given variables and constraints
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().
|
static |
copies the given constraints and the corresponding variables to the given sub-SCIP
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 assert(), FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPconsGetHdlr(), SCIPconsIsActive(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPcopyProb(), SCIPgetConsCopy(), SCIPreleaseCons(), and TRUE.
Referenced by blockCreateSubscip().
|
static |
creates the subscip for a given block
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 assert(), copyToSubscip(), createSubscip(), FALSE, i, Block::nsubvars, NULL, Block::number, Block::problem, SCIP_Bool, 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().
|
static |
creates problem structure and split it into blocks
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 assert(), b, blockCreateSubscip(), freeProblem(), initBlock(), initProblem(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapFree(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copies labels to newdecomp and assigns linking constraints if possible
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 assert(), NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIPassignDecompLinkConss(), SCIPcomputeDecompStats(), SCIPcomputeDecompVarsLabels(), SCIPdebugMsg, SCIPdecompGetConsLabels(), SCIPdecompGetVarsLabels(), SCIPdecompSetConsLabels(), SCIPdecompSetVarsLabels(), SCIPsortIntPtr(), TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
computes feasible solution from last stored solution of the block
subscip | SCIP data structure |
block | block structure |
Definition at line 614 of file heur_padm.c.
References assert(), c, Block::couplingcons, COUPLINGSIZE, Block::ncoupling, NULL, nvars, 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, Block::slackspos, and sol.
Referenced by SCIP_DECL_HEUREXEC().
|
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.
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 assert(), FALSE, NULL, nvars, SCIP_Bool, 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(), sol, TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
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].
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 assert(), b, blockinfo::block, i, 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().
|
static |
returns the available time limit that is left
scip | SCIP data structure |
time | pointer to store remaining time |
Definition at line 938 of file heur_padm.c.
References assert(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPinfinity(), and SCIPisInfinity().
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 965 of file heur_padm.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurPADM().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 980 of file heur_padm.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
execution method of primal heuristic
Definition at line 996 of file heur_padm.c.
References assert(), assignLinking(), b, blockinfo::block, blockinfo::couplingCons, Block::couplingcons, COUPLINGSIZE, createAndSplitProblem(), EPSEQ, FALSE, freeProblem(), getTimeLeft(), HEUR_NAME, heurdata, i, set::indexes, blockinfo::linkvar, blockinfo::linkvaridx, blockinfo::linkvarval, MAX, nnodes, NULL, nvars, obj, blockinfo::otherblock, REALABS, reoptimize(), result, 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, sol, Block::subscip, TRUE, var, and vars.