Detailed Description

dynamic partition search

Author: Katrin Halbig

The dynamic partition search (DPS) is a construction heuristic which additionally needs a user decomposition with linking constraints only.

This heuristic splits the problem into several sub-SCIPs according to the given decomposition. Thereby the linking constraints with their right-hand and left-hand sides are also split. DPS searches for a partition of the sides on the blocks so that a feasible solution is obtained. For each block the parts of the original linking constraints are extended by slack variables. Moreover, the objective function is replaced by the sum of these additional variables weighted by penalty parameters lambda. If all blocks have an optimal solution of zero, the algorithm terminates with a feasible solution for the main problem. Otherwise, the partition and the penalty parameters are updated, and the sub-SCIPs are solved again.

A detailed description can be found in K. Halbig, A. Göß and D. Weninger (2023). Exploiting user-supplied Decompositions inside Heuristics. https://optimization-online.org/?p=23386

Definition in file heur_dps.c.

#include "scip/heur_dps.h"
#include "scip/pub_dcmp.h"
#include "scip/pub_heur.h"
#include "scip/pub_misc.h"
#include "scip/scipdefplugins.h"
#include "scip/scip_cons.h"
#include "scip/scip_dcmp.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"

Go to the source code of this file.

Data Structures
struct	Blockproblem

struct	Linking

Macros
#define	HEUR_NAME "dps"

#define	HEUR_DESC "primal heuristic for decomposable MIPs"

#define	HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS

#define	HEUR_PRIORITY 75000

#define	HEUR_FREQ -1

#define	HEUR_FREQOFS 0

#define	HEUR_MAXDEPTH -1

#define	HEUR_TIMING SCIP_HEURTIMING_BEFORENODE \| SCIP_HEURTIMING_AFTERNODE

#define	HEUR_USESSUBSCIP TRUE

#define	DEFAULT_MAXIT 50

#define	DEFAULT_PENALTY 100.0

#define	EVENTHDLR_NAME "Dps"

#define	EVENTHDLR_DESC "event handler for " HEUR_NAME " heuristic"

Typedefs
typedef struct Blockproblem	BLOCKPROBLEM

typedef struct Linking	LINKING

Functions
static SCIP_RETCODE	assignLinking (SCIP scip, SCIP_DECOMP newdecomp, SCIP_VAR vars, SCIP_CONS conss, int varlabels, int conslabels, int nvars, int nconss, int nlinkvars)

static SCIP_RETCODE	createSubscip (SCIP scip, SCIP *subscip)

static SCIP_RETCODE	copyToSubscip (SCIP scip, SCIP subscip, const char name, SCIP_VAR vars, SCIP_CONS conss, SCIP_HASHMAP varsmap, SCIP_HASHMAP conssmap, int nvars, int nconss, SCIP_Bool success)

static SCIP_RETCODE	createBlockproblem (SCIP scip, BLOCKPROBLEM blockproblem, LINKING linkings, SCIP_CONS conss, SCIP_VAR vars, int nconss, int nvars, SCIP_CONS linkingconss, int nlinking, int blocknumber, SCIP_Bool *success)

static SCIP_RETCODE	createAndSplitProblem (SCIP scip, SCIP_HEURDATA heurdata, SCIP_DECOMP decomp, BLOCKPROBLEM blockproblem, LINKING linkings, SCIP_VAR vars, SCIP_CONS conss, SCIP_Bool success)

static SCIP_RETCODE	roundPartition (SCIP scip, LINKING linking, BLOCKPROBLEM **blockproblem, SCIP_Bool roundbyrhs)

static SCIP_RETCODE	initCurrent (SCIP scip, LINKING linkings, BLOCKPROBLEM blockproblem, SCIP_HEURTIMING heurtiming, int nlinking, SCIP_Bool success)

static SCIP_RETCODE	calculateShift (SCIP scip, BLOCKPROBLEM blockproblem, LINKING linking, SCIP_Real *shift, int nviolatedblocksrhs, int nviolatedblockslhs, SCIP_Bool update)

static SCIP_RETCODE	updatePartition (SCIP scip, LINKING linkings, BLOCKPROBLEM blockproblem, int nviolatedblocksrhs, int nviolatedblockslhs, int nlinking, int nblocks, int iteration, SCIP_Bool oneupdate)

static SCIP_RETCODE	updateLambda (SCIP scip, SCIP_HEURDATA heurdata, LINKING linkings, BLOCKPROBLEM blockproblem, int nviolatedblocksrhs, int nviolatedblockslhs, int nlinking)

static SCIP_RETCODE	reuseSolution (LINKING linkings, BLOCKPROBLEM blockproblem, int nblocks)

static SCIP_RETCODE	reoptimize (SCIP scip, SCIP_HEUR heur, SCIP_SOL sol, BLOCKPROBLEM blockproblem, int nblocks, SCIP_Bool limits, SCIP_SOL newsol, SCIP_Bool success)

static	SCIP_DECL_EVENTEXEC (eventExecDps)

static	SCIP_DECL_HEURCOPY (heurCopyDps)

static	SCIP_DECL_HEURFREE (heurFreeDps)

static	SCIP_DECL_HEUREXEC (heurExecDps)

SCIP_RETCODE	SCIPincludeHeurDps (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "dps"

Definition at line 62 of file heur_dps.c.

Referenced by createBlockproblem(), SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), and SCIPincludeHeurDps().

◆ HEUR_DESC

#define HEUR_DESC "primal heuristic for decomposable MIPs"

Definition at line 63 of file heur_dps.c.

Referenced by SCIPincludeHeurDps().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS

Definition at line 64 of file heur_dps.c.

Referenced by SCIPincludeHeurDps().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 75000

Definition at line 65 of file heur_dps.c.

Referenced by SCIPincludeHeurDps().

◆ HEUR_FREQ

#define HEUR_FREQ -1

Definition at line 66 of file heur_dps.c.

Referenced by SCIPincludeHeurDps().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 67 of file heur_dps.c.

Referenced by SCIPincludeHeurDps().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 68 of file heur_dps.c.

Referenced by SCIPincludeHeurDps().

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_AFTERNODE

Definition at line 69 of file heur_dps.c.

Referenced by SCIPincludeHeurDps().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 70 of file heur_dps.c.

Referenced by SCIPincludeHeurDps().

◆ DEFAULT_MAXIT

#define DEFAULT_MAXIT 50

maximum number of iterations

Definition at line 72 of file heur_dps.c.

Referenced by SCIPincludeHeurDps().

◆ DEFAULT_PENALTY

#define DEFAULT_PENALTY 100.0

multiplier for absolute increase of penalty parameters

Definition at line 73 of file heur_dps.c.

Referenced by SCIPincludeHeurDps().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME "Dps"

Definition at line 76 of file heur_dps.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIP_DECL_HEUREXEC().

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC "event handler for " HEUR_NAME " heuristic"

Definition at line 77 of file heur_dps.c.

Referenced by SCIP_DECL_HEUREXEC().

Typedef Documentation

◆ BLOCKPROBLEM

typedef struct Blockproblem BLOCKPROBLEM

Definition at line 111 of file heur_dps.c.

◆ LINKING

typedef struct Linking LINKING

Definition at line 131 of file heur_dps.c.

Function Documentation

◆ assignLinking()

static SCIP_RETCODE assignLinking	(	SCIP *	scip,
		SCIP_DECOMP *	newdecomp,
		SCIP_VAR **	vars,
		SCIP_CONS **	conss,
		int *	varlabels,
		int *	conslabels,
		int	nvars,
		int	nconss,
		int	nlinkvars
	)

static

assigns linking variables to last block

The labels are copied to newdecomp and the linking variables are assigned to the last block (i.e., highest block label). Constraint labels and statistics are recomputed.

Parameters

scip	SCIP data structure
newdecomp	decomposition with assigned linking variables
vars	sorted array of variables
conss	sorted array of constraints
varlabels	sorted array of variable labels
conslabels	sorted array of constraint labels
nvars	number of variables
nconss	number of constraints
nlinkvars	number of linking variables

Definition at line 143 of file heur_dps.c.

References NULL, SCIP_CALL, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIPcomputeDecompConsLabels(), SCIPcomputeDecompStats(), SCIPdebugMsg, SCIPdecompGetConsLabels(), SCIPdecompGetNBorderVars(), SCIPdecompGetVarsLabels(), SCIPdecompSetConsLabels(), SCIPdecompSetVarsLabels(), SCIPsortIntPtr(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ createSubscip()

static SCIP_RETCODE createSubscip	(	SCIP *	scip,
		SCIP **	subscip
	)

static

creates a sub-SCIP and sets parameters

Parameters

scip	main SCIP data structure
subscip	pointer to store created sub-SCIP

Definition at line 217 of file heur_dps.c.

References FALSE, NULL, 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 SCIP_DECL_HEUREXEC().

◆ copyToSubscip()

static SCIP_RETCODE copyToSubscip	(	SCIP *	scip,
		SCIP *	subscip,
		const char *	name,
		SCIP_VAR **	vars,
		SCIP_CONS **	conss,
		SCIP_HASHMAP *	varsmap,
		SCIP_HASHMAP *	conssmap,
		int	nvars,
		int	nconss,
		SCIP_Bool *	success
	)

static

copies the given variables and constraints to the given sub-SCIP

Parameters

scip	source SCIP
subscip	target SCIP
name	name for copied problem
vars	array of variables to copy
conss	array of constraints to copy
varsmap	hashmap for copied variables
conssmap	hashmap for copied constraints
nvars	number of variables to copy
nconss	number of constraints to copy
success	was copying successful?

Definition at line 270 of file heur_dps.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPABORT, SCIPaddCons(), SCIPconsGetHdlr(), SCIPconsIsActive(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPcreateProb(), SCIPdebugMsg, SCIPgetConsCopy(), SCIPgetNOrigVars(), SCIPgetVarCopy(), SCIPreleaseCons(), and SCIPwarningMessage().

Referenced by createBlockproblem().

◆ createBlockproblem()

static SCIP_RETCODE createBlockproblem	(	SCIP *	scip,
		BLOCKPROBLEM *	blockproblem,
		LINKING **	linkings,
		SCIP_CONS **	conss,
		SCIP_VAR **	vars,
		int	nconss,
		int	nvars,
		SCIP_CONS **	linkingconss,
		int	nlinking,
		int	blocknumber,
		SCIP_Bool *	success
	)

static

creates the subscip for a given block

Parameters

scip	SCIP data structure
blockproblem	blockproblem that should be created
linkings	linkings that will be (partially) initialized
conss	sorted array of constraints of this block
vars	sorted array of variables of this block
nconss	number of constraints of this block
nvars	number of variables of this block
linkingconss	linking constraints in the original problem
nlinking	number of linking constraints in the original problem
blocknumber	number of block that should be created
success	pointer to store whether creation was successful

Definition at line 349 of file heur_dps.c.

References Linking::blockconss, Linking::blocknumbers, Blockproblem::blockscip, copyToSubscip(), FALSE, Linking::haslhs, Linking::hasrhs, HEUR_NAME, Blockproblem::linkingconss, Blockproblem::linkingindices, MAX, Linking::maxactivity, Linking::minactivity, Linking::nblocks, Blockproblem::nblockvars, Blockproblem::nlinking, Linking::nslacks, Linking::nslacksperblock, Blockproblem::nslackvars, NULL, Blockproblem::origobj, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_NEGATED, SCIP_VARTYPE_CONTINUOUS, SCIP_VERBLEVEL_FULL, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPchgVarObj(), SCIPconsGetHdlr(), SCIPconsGetLhs(), SCIPconsGetName(), SCIPconsGetRhs(), SCIPconshdlrGetName(), SCIPcreateConsBasicLinear(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPfreeBufferArray, SCIPgetConsNVars(), SCIPgetConsVals(), SCIPgetConsVars(), SCIPgetNegatedVar(), SCIPgetNVars(), SCIPgetProbName(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPinfinity(), SCIPisInfinity(), SCIPisLE(), SCIPreallocBufferArray, SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNegationVar(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPverbMessage(), Linking::slacks, Blockproblem::slackvars, and TRUE.

Referenced by createAndSplitProblem().

◆ createAndSplitProblem()

static SCIP_RETCODE createAndSplitProblem	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		SCIP_DECOMP *	decomp,
		BLOCKPROBLEM **	blockproblem,
		LINKING **	linkings,
		SCIP_VAR **	vars,
		SCIP_CONS **	conss,
		SCIP_Bool *	success
	)

static

creates data structures and splits problem into blocks

Parameters

scip	SCIP data structure
heurdata	heuristic data
decomp	decomposition data structure
blockproblem	array of blockproblem data structures
linkings	array of linking data structures
vars	sorted array of variables
conss	sorted array of constraints
success	pointer to store whether splitting was successful

Definition at line 660 of file heur_dps.c.

References createBlockproblem(), SCIP_Decomp::nblocks, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdecompGetConssSize(), SCIPdecompGetVarsSize(), and SCIPfreeBufferArray.

Referenced by SCIP_DECL_HEUREXEC().

◆ roundPartition()

static SCIP_RETCODE roundPartition	(	SCIP *	scip,
		LINKING *	linking,
		BLOCKPROBLEM **	blockproblem,
		SCIP_Bool	roundbyrhs
	)

static

rounds partition for one linking constraint to integer value if variables and coefficients are integer

changes only currentrhs/currentlhs

Parameters

scip	SCIP data structure
linking	one linking data structure
blockproblem	array of blockproblem data structures
roundbyrhs	round by right hand side?

Definition at line 713 of file heur_dps.c.

References b, Linking::blockconss, Linking::blocknumbers, Blockproblem::blockscip, Linking::currentlhs, Linking::currentrhs, Linking::haslhs, Linking::hasrhs, Linking::nblocks, Linking::nslacksperblock, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetConsNVars(), SCIPgetConsVals(), SCIPgetConsVars(), SCIPisGE(), SCIPisGT(), SCIPisIntegral(), SCIPsortIntIntReal(), SCIPsortIntReal(), SCIPsortRealInt(), and SCIPvarGetType().

Referenced by initCurrent(), and updatePartition().

◆ initCurrent()

static SCIP_RETCODE initCurrent	(	SCIP *	scip,
		LINKING **	linkings,
		BLOCKPROBLEM **	blockproblem,
		SCIP_HEURTIMING	heurtiming,
		int	nlinking,
		SCIP_Bool *	success
	)

static

calculates initial partition and sets rhs/lhs in blockproblems

Parameters

scip	SCIP data structure of main scip
linkings	array of linking data structures
blockproblem	array of blockproblem data structures
heurtiming	current point in the node solving process
nlinking	number of linking constraints
success	pointer to store whether initialization was successful

Definition at line 874 of file heur_dps.c.

References b, Linking::blockconss, Linking::blocknumbers, Blockproblem::blockscip, Linking::currentlhs, Linking::currentrhs, FALSE, Linking::haslhs, Linking::hasrhs, Linking::linkingcons, MAX, Linking::maxactivity, MIN, Linking::minactivity, Linking::nblocks, Linking::nslacksperblock, NULL, roundPartition(), SCIP_CALL, SCIP_HEURTIMING_AFTERNODE, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPchgLhsLinear(), SCIPchgRhsLinear(), SCIPconsGetLhs(), SCIPconsGetName(), SCIPconsGetRhs(), SCIPconsIsChecked(), SCIPdebugMsg, SCIPfindVar(), SCIPfreeBufferArray, SCIPgetConsNVars(), SCIPgetConsVals(), SCIPgetConsVars(), SCIPisEQ(), SCIPisGE(), SCIPisLE(), SCIPisZero(), SCIPvarGetLPSol(), and SCIPvarGetName().

Referenced by SCIP_DECL_HEUREXEC().

◆ calculateShift()

static SCIP_RETCODE calculateShift	(	SCIP *	scip,
		BLOCKPROBLEM **	blockproblem,
		LINKING *	linking,
		SCIP_Real **	shift,
		int *	nviolatedblocksrhs,
		int *	nviolatedblockslhs,
		SCIP_Bool *	update
	)

static

calculates shift

Parameters

scip	SCIP data structure of main scip
blockproblem	array of blockproblem data structures
linking	one linking data structure
shift	pointer to store direction vector
nviolatedblocksrhs	pointer to store number of blocks which violate rhs
nviolatedblockslhs	pointer to store number of blocks which violate lhs
update	should we update the partition?

Definition at line 1064 of file heur_dps.c.

References Linking::blocknumbers, Blockproblem::blockscip, Linking::currentlhs, Linking::currentrhs, FALSE, Linking::haslhs, Linking::hasrhs, MAX, Linking::maxactivity, MIN, Linking::minactivity, Linking::nblocks, Linking::nslacksperblock, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetSolVal(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), Linking::slacks, and TRUE.

Referenced by updatePartition().

◆ updatePartition()

static SCIP_RETCODE updatePartition	(	SCIP *	scip,
		LINKING **	linkings,
		BLOCKPROBLEM **	blockproblem,
		int **	nviolatedblocksrhs,
		int **	nviolatedblockslhs,
		int	nlinking,
		int	nblocks,
		int	iteration,
		SCIP_Bool *	oneupdate
	)

static

update partition

Parameters

scip	SCIP data structure of main scip
linkings	linking data structure
blockproblem	array of blockproblem data structures
nviolatedblocksrhs	pointer to store number of blocks which violate rhs
nviolatedblockslhs	pointer to store number of blocks which violate lhs
nlinking	number of linking constraints
nblocks	number of blocks
iteration	number of iteration
oneupdate	is at least partition of one constraint updated?

Definition at line 1227 of file heur_dps.c.

References Linking::blockconss, Linking::blocknumbers, Blockproblem::blockscip, BMSclearMemoryArray, calculateShift(), Linking::currentlhs, Linking::currentrhs, Linking::haslhs, Linking::hasrhs, Linking::nblocks, NULL, roundPartition(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPchgLhsLinear(), SCIPchgRhsLinear(), SCIPfreeBufferArray, SCIPisFeasZero(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ updateLambda()

static SCIP_RETCODE updateLambda	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		LINKING **	linkings,
		BLOCKPROBLEM **	blockproblem,
		int *	nviolatedblocksrhs,
		int *	nviolatedblockslhs,
		int	nlinking
	)

static

update penalty parameters lambda

if a linking constraint is violated two times in succession, the corresponding penalty parameter is increased in each block

Parameters

scip	SCIP data structure
heurdata	heuristic data
linkings	array of linking data structures
blockproblem	array of blockproblem data structures
nviolatedblocksrhs	number of blocks which violate rhs
nviolatedblockslhs	number of blocks which violate lhs
nlinking	number of linking constraints

Definition at line 1318 of file heur_dps.c.

References b, Linking::blocknumbers, Blockproblem::blockscip, Linking::haslhs, Linking::hasrhs, Linking::lastviolations, Linking::nblocks, Linking::nslacksperblock, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObj(), SCIPvarGetObj(), and Linking::slacks.

Referenced by SCIP_DECL_HEUREXEC().

◆ reuseSolution()

static SCIP_RETCODE reuseSolution	(	LINKING **	linkings,
		BLOCKPROBLEM **	blockproblem,
		int	nblocks
	)

static

computes feasible solution from last stored solution for each block and adds it to the solution storage

Parameters

linkings	array of linking data structures
blockproblem	array of blockproblem data structures
nblocks	number of blocks

Definition at line 1384 of file heur_dps.c.

References b, Linking::blocknumbers, Blockproblem::blockscip, Linking::haslhs, Linking::hasrhs, Blockproblem::linkingindices, MAX, Linking::nblocks, Blockproblem::nlinking, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddSolFree(), SCIPallocBufferArray, SCIPcreateOrigSol(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetActivityLinear(), SCIPgetLhsLinear(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetRhsLinear(), SCIPgetSolOrigObj(), SCIPgetSols(), SCIPgetSolVal(), SCIPgetSolVals(), SCIPgetVars(), SCIPisGE(), SCIPsetSolVal(), SCIPsetSolVals(), and Linking::slacks.

Referenced by SCIP_DECL_HEUREXEC().

◆ reoptimize()

static SCIP_RETCODE reoptimize	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_SOL *	sol,
		BLOCKPROBLEM **	blockproblem,
		int	nblocks,
		SCIP_Bool	limits,
		SCIP_SOL **	newsol,
		SCIP_Bool *	success
	)

static

reoptimizes the heuristic solution with original objective function

Parameters

scip	SCIP data structure
heur	pointer to heuristic
sol	heuristic solution
blockproblem	array of blockproblem data structures
nblocks	number of blockproblems
limits	should strict limits be set?
newsol	pointer to store improved solution
success	pointer to store whether reoptimization was successful

Definition at line 1504 of file heur_dps.c.

References b, Blockproblem::blockscip, FALSE, Linking::nblocks, Blockproblem::nblockvars, NULL, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_OPTIMAL, SCIPallocBufferArray, SCIPchgVarLb(), SCIPchgVarObj(), SCIPchgVarUb(), SCIPcopyLimits(), SCIPcreateSol(), SCIPfindVar(), SCIPfreeBufferArray, SCIPfreeTransform(), SCIPgetBestSol(), SCIPgetNOrigVars(), SCIPgetNSols(), SCIPgetOrigVars(), SCIPgetRealParam(), SCIPgetSolVals(), SCIPgetStatus(), SCIPgetTotalTime(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetPresolving(), SCIPsetRealParam(), SCIPsetSeparating(), SCIPsetSolVal(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPtransformProb(), SCIPvarGetName(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecDps )

static

Definition at line 1688 of file heur_dps.c.

References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetDualbound(), SCIPgetNSols(), SCIPinterruptSolve(), and SCIPisFeasGT().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyDps )

static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 1714 of file heur_dps.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurDps().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeDps )

static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 1728 of file heur_dps.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecDps )

static

execution method of primal heuristic

Definition at line 1747 of file heur_dps.c.

References assignLinking(), b, Linking::blockconss, Linking::blocknumbers, Blockproblem::blockscip, BMSclearMemoryArray, createAndSplitProblem(), createSubscip(), Linking::currentlhs, Linking::currentrhs, EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, Linking::haslhs, Linking::hasrhs, HEUR_NAME, initCurrent(), Linking::lastviolations, Linking::linkingcons, Linking::maxactivity, Linking::minactivity, Linking::nblocks, Blockproblem::nblockvars, Blockproblem::nlinking, Linking::nslacks, Linking::nslacksperblock, Blockproblem::nslackvars, NULL, reoptimize(), reuseSolution(), SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_DECOMP_LINKCONS, SCIP_DECOMP_LINKVAR, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, SCIP_HEURTIMING_AFTERNODE, SCIP_HEURTIMING_BEFORENODE, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_Real, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_UNBOUNDED, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPblkmem(), SCIPcatchEvent(), SCIPcomputeDecompStats(), SCIPcopyLimits(), SCIPcreateSol(), SCIPdebugMsg, SCIPdecompCreate(), SCIPdecompFree(), SCIPdecompGetConsLabels(), SCIPdecompGetNBlocks(), SCIPdecompGetNBorderConss(), SCIPdecompGetNBorderVars(), SCIPdecompGetVarsLabels(), SCIPdecompIsOriginal(), SCIPdecompPrintStats(), SCIPdecompUseBendersLabels(), SCIPdropEvent(), SCIPduplicateBufferArray, SCIPerrorMessage, SCIPfindVar(), SCIPfree(), SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeSol(), SCIPfreeTransform(), SCIPgetBestSol(), SCIPgetBoolParam(), SCIPgetConss(), SCIPgetDecomps(), SCIPgetIntParam(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNConss(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetOrigVars(), SCIPgetPrimalbound(), SCIPgetRealParam(), SCIPgetSolOrigObj(), SCIPgetSolVals(), SCIPgetSolvingTime(), SCIPgetStatus(), SCIPgetVars(), SCIPheurGetData(), SCIPheurGetNCalls(), SCIPincludeEventhdlrBasic(), SCIPisParamFixed(), SCIPisZero(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetSolVal(), SCIPsolve(), SCIPsortIntPtr(), SCIPtransformProb(), SCIPtrySolFree(), SCIPvarGetName(), Linking::slacks, TRUE, updateLambda(), and updatePartition().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_MAXIT

◆ DEFAULT_PENALTY

◆ EVENTHDLR_NAME

◆ EVENTHDLR_DESC

Typedef Documentation

◆ BLOCKPROBLEM

◆ LINKING

Function Documentation

◆ assignLinking()

◆ createSubscip()

◆ copyToSubscip()

◆ createBlockproblem()

◆ createAndSplitProblem()

◆ roundPartition()

◆ initCurrent()

◆ calculateShift()

◆ updatePartition()

◆ updateLambda()

◆ reuseSolution()

◆ reoptimize()

◆ SCIP_DECL_EVENTEXEC()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEUREXEC()