dptermsinterns.h File Reference

Detailed Description

Dynamic programming internals for Steiner tree (sub-) problems with small number of terminals.

Author

Daniel Rehfeldt

Internal methods and data structures for DP.

Definition in file dptermsinterns.h.

#include "scip/scip.h"
#include "scip/rbtree.h"
#include "graph.h"
#include "stpvector.h"
#include "stpbitset.h"
#include "stpprioqueue.h"

Go to the source code of this file.

Data Structures
struct	solution_trace
struct	dynamic_programming_subsolution
struct	dynamic_programming_graph
struct	dynamic_programming_misc
struct	dynamic_programming_reduced_costs
struct	dynamic_programming_solver

Macros
#define	SUBSOL_LT(key, subsol)   stpbitset_GT(key, subsol->bitkey)
#define	SUBSOL_GT(key, subsol)   stpbitset_LT(key, subsol->bitkey)

Typedefs
typedef struct dynamic_programming_search_tree	DPSTREE
typedef struct solution_trace	SOLTRACE
typedef struct dynamic_programming_subsolution	DPSUBSOL
typedef struct dynamic_programming_graph	DPGRAPH
typedef struct dynamic_programming_misc	DPMISC
typedef struct dynamic_programming_reduced_costs	DPREDCOST
typedef struct dynamic_programming_solver	DPSOLVER

Functions
static	SCIP_DEF_RBTREE_FIND (findSubsol, STP_Bitset, DPSUBSOL, SUBSOL_LT, SUBSOL_GT) static inline SCIP_RETCODE dpterms_dpsubsolInit(SCIP *scip
	SCIPallocBlockMemory (scip, subsol))
static void	dpterms_dpsubsolFree (SCIP *scip, DPSUBSOL **subsol)
SCIP_Bool	dpterms_intersectsEqualNaive (SCIP *, STP_Bitset, STP_Bitset, STP_Vectype(int), DPMISC *)
	STP_Vectype (int) dpterms_collectIntersectsNaive(SCIP *
DPMISC *SCIP_RETCODE	dpterms_streeInit (SCIP *, int, int, DPSTREE **)
void	dpterms_streeFree (SCIP *, DPSTREE **)
SCIP_RETCODE	dpterms_streeInsert (SCIP *, STP_Bitset, STP_Bitset, int64_t, DPSTREE *)
DPSTREE *SCIP_RETCODE	dpterms_coreSolve (SCIP *, GRAPH *, DPSOLVER *, SCIP_Bool *)

Variables
static DPSUBSOL **	subsol
	sub = *subsol
sub	bitkey = NULL
sub	traces = NULL
return	SCIP_OKAY
	STP_Bitset

Macro Definition Documentation

SUBSOL_LT

#define SUBSOL_LT	(		key,
			subsol
	)		stpbitset_GT(key, subsol->bitkey)

Definition at line 129 of file dptermsinterns.h.

SUBSOL_GT

#define SUBSOL_GT	(		key,
			subsol
	)		stpbitset_LT(key, subsol->bitkey)

Definition at line 130 of file dptermsinterns.h.

Typedef Documentation

DPSTREE

typedef struct dynamic_programming_search_tree DPSTREE

dynamic programming search tree

Definition at line 40 of file dptermsinterns.h.

SOLTRACE

typedef struct solution_trace SOLTRACE

trace for reconstructing a sub-solution

DPSUBSOL

typedef struct dynamic_programming_subsolution DPSUBSOL

sub-solution with extension

DPGRAPH

typedef struct dynamic_programming_graph DPGRAPH

compressed graph with less information

DPMISC

typedef struct dynamic_programming_misc DPMISC

additional data

DPREDCOST

typedef struct dynamic_programming_reduced_costs DPREDCOST

reduced cost data

DPSOLVER

typedef struct dynamic_programming_solver DPSOLVER

solver

Function Documentation

SCIP_DEF_RBTREE_FIND()

static SCIP_DEF_RBTREE_FIND ( findSubsol  , STP_Bitset  , DPSUBSOL  , SUBSOL_LT  , SUBSOL_GT    )

inlinestatic

initializes

SCIPallocBlockMemory()

SCIPallocBlockMemory	(	scip	,
		subsol
	)

Referenced by addAuxiliaryVariablesToMaster(), alnsIncludeNeighborhood(), assignAuxiliaryVariables(), catchVarEventCardinality(), COLORcreateConsStoreGraph(), COLORincludeConshdlrStoreGraph(), consdataCreate(), consdataCreateRedundant(), consdataCreateSuperindicator(), conshdlrdataCreate(), copyDimensions(), createAndAddAndCons(), createConsStoreGraphAtRoot(), createConstarray(), createData(), createDepthinfo(), createExprNode(), createNlhdlrExprData(), createPattern(), createReaderdata(), createScenarioData(), createSolTuple(), createSubproblems(), createTabooList(), createVararray(), DECL_NHINIT(), decompHorizonCreate(), detectNlhdlr(), ecaggrCreateEmpty(), exprdataCreate(), getEventData(), graph_initAncestors(), includeEventHdlrSync(), includeNeighborhoods(), initBranchruleData(), initConflictgraph(), initialiseLPSubproblem(), initImplGraphSOS1(), initProblem(), initTCliquegraph(), level2resultEqual(), linconsupgradeFree(), mcfnetworkCreate(), mod2MatrixAddCol(), mod2MatrixAddTransRow(), mpsinputCreate(), nlrowaggrCreate(), objimplicsCreate(), parseOutputDimensioninfo(), probdataCreate(), propdataCreate(), readerdataAddOutputvar(), readerdataCreate(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSTRANS(), SCIP_DECL_DISPINITSOL(), SCIP_DECL_EXPRCOPYDATA(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINIT(), SCIP_DECL_NLPICREATEPROBLEM(), SCIP_DECL_PROBCOPY(), SCIP_DECL_PROBTRANS(), SCIP_DECL_SEPAEXECLP(), SCIPaggrRowCopy(), SCIPaggrRowCreate(), SCIPbendersSolveSubproblemCIP(), SCIPbendersSolveSubproblemLP(), SCIPbendersStoreCut(), SCIPcreateConcurrent(), SCIPcreateConsCardinality(), SCIPcreateConsLOP(), SCIPcreateConsPseudobooleanWithConss(), SCIPcreateConsSOS1(), SCIPcreateConsSOS2(), SCIPcreateConsStp(), tsp::SCIPcreateConsSubtour(), SCIPcreateExprProduct(), SCIPcreateExprValue(), SCIPcreateProbColoring(), SCIPcreateProbCyc(), SCIPcreateRowprep(), SCIPgenVBoundAdd(), SCIPincludeBenderscutFeasalt(), SCIPincludeBenderscutInt(), SCIPincludeBenderscutNogood(), SCIPincludeBenderscutOpt(), SCIPincludeBendersDefault(), SCIPincludeBranchruleAllfullstrong(), SCIPincludeBranchruleCloud(), SCIPincludeBranchruleDistribution(), SCIPincludeBranchruleFullstrong(), SCIPincludeBranchruleInference(), SCIPincludeBranchruleMultAggr(), SCIPincludeBranchrulePscost(), SCIPincludeBranchruleRandom(), SCIPincludeBranchruleStrongcoloring(), SCIPincludeBranchruleVanillafullstrong(), SCIPincludeComprLargestrepr(), SCIPincludeComprWeakcompr(), SCIPincludeConshdlrBounddisjunction(), SCIPincludeConshdlrCardinality(), SCIPincludeConshdlrComponents(), SCIPincludeConshdlrDisjunction(), SCIPincludeConshdlrIndicator(), SCIPincludeConshdlrOrbisack(), SCIPincludeConshdlrOrbitope(), SCIPincludeConshdlrRpa(), SCIPincludeConshdlrSOS2(), SCIPincludeConshdlrSuperindicator(), SCIPincludeConshdlrSymresack(), SCIPincludeConshdlrViolatedCut(), SCIPincludeConsUpgradeNonlinear(), SCIPincludeCutselHybrid(), SCIPincludeEventHdlrBoundwriting(), SCIPincludeEventHdlrSofttimelimit(), SCIPincludeEventHdlrSolvingphase(), SCIPincludeHeurActconsdiving(), SCIPincludeHeurAlns(), SCIPincludeHeurBound(), SCIPincludeHeurCoefdiving(), SCIPincludeHeurCompletesol(), SCIPincludeHeurConflictdiving(), SCIPincludeHeurCrossover(), SCIPincludeHeurCycKerlin(), SCIPincludeHeurDins(), SCIPincludeHeurDps(), SCIPincludeHeurDualval(), SCIPincludeHeurFixandinfer(), SCIPincludeHeurFracdiving(), SCIPincludeHeurGuideddiving(), SCIPincludeHeurIndicator(), SCIPincludeHeurInit(), SCIPincludeHeurIntdiving(), SCIPincludeHeurLinesearchdiving(), SCIPincludeHeurListScheduling(), SCIPincludeHeurLocalbranching(), SCIPincludeHeurLpface(), SCIPincludeHeurMpec(), SCIPincludeHeurMultistart(), SCIPincludeHeurMutation(), SCIPincludeHeurObjpscostdiving(), SCIPincludeHeurOctane(), SCIPincludeHeurOfins(), SCIPincludeHeurOneopt(), SCIPincludeHeurOptcumulative(), SCIPincludeHeurPADM(), SCIPincludeHeurProximity(), SCIPincludeHeurPscostdiving(), SCIPincludeHeurRandrounding(), SCIPincludeHeurRedsize(), SCIPincludeHeurRens(), SCIPincludeHeurReoptsols(), SCIPincludeHeurRins(), SCIPincludeHeurRootsoldiving(), SCIPincludeHeurRounding(), SCIPincludeHeurShiftandpropagate(), SCIPincludeHeurSimplerounding(), SCIPincludeHeurSubNlp(), SCIPincludeHeurSync(), SCIPincludeHeurTrustregion(), SCIPincludeHeurTrySol(), SCIPincludeHeurTwoopt(), SCIPincludeHeurUndercover(), SCIPincludeHeurVeclendiving(), SCIPincludeHeurZeroobj(), SCIPincludeHeurZirounding(), SCIPincludeNlhdlrBilinear(), SCIPincludeNlhdlrConcave(), SCIPincludeNlhdlrConvex(), SCIPincludeNlhdlrPerspective(), SCIPincludeNlhdlrQuadratic(), SCIPincludeNlpSolverWorhp(), SCIPincludeNodeselBfs(), SCIPincludeNodeselEstimate(), SCIPincludeNodeselHybridestim(), SCIPincludeNodeselRestartdfs(), SCIPincludeNodeselUct(), SCIPincludePresolBoundshift(), SCIPincludePresolConvertinttobin(), SCIPincludePresolDomcol(), SCIPincludePresolDualcomp(), SCIPincludePresolDualinfer(), SCIPincludePresolDualsparsify(), SCIPincludePresolMILP(), SCIPincludePresolQPKKTref(), SCIPincludePresolSparsify(), SCIPincludePresolTworowbnd(), SCIPincludePricerBinpacking(), SCIPincludePricerColoring(), SCIPincludePricerRpa(), SCIPincludePropNlobbt(), SCIPincludePropRedcost(), SCIPincludePropSymmetry(), SCIPincludePropVbounds(), SCIPincludeReaderBnd(), SCIPincludeReaderCip(), SCIPincludeReaderCor(), SCIPincludeReaderLp(), SCIPincludeReaderMps(), SCIPincludeReaderPbm(), SCIPincludeReaderPpm(), SCIPincludeReaderSto(), SCIPincludeReaderTim(), SCIPincludeSepaCGMIP(), SCIPincludeSepaClique(), SCIPincludeSepaClosecuts(), SCIPincludeSepaConvexproj(), SCIPincludeSepaDisjunctive(), SCIPincludeSepaGauge(), SCIPincludeSepaGMI(), SCIPincludeSepaGomory(), SCIPincludeSepaImpliedbounds(), SCIPincludeSepaInterminor(), SCIPincludeSepaMinor(), SCIPincludeSepaMixing(), SCIPincludeSepaOddcycle(), SCIPincludeSepaZerohalf(), SCIPinitHeurOptcumulative(), SCIPinitRepresentation(), SCIPinsertBilinearTermImplicitNonlinear(), SCIPintListNodeAppendCopy(), SCIPintListNodeInsert(), SCIPlinConsStatsCreate(), SCIPvariableGraphCreate(), selectCandidateUsingSampling(), sepadataCreate(), smpsinputCreate(), solpool_addSol(), solpool_init(), stoinputCreate(), subtreeSumGapStoreNode(), tcliquegraphCreate(), timinputCreate(), updateArcData(), updateSymInfoConflictGraphSST(), and vardataCreate().

dpterms_dpsubsolFree()

static void dpterms_dpsubsolFree ( SCIP *  scip, DPSUBSOL **  subsol  )

inlinestatic

frees

Parameters

scip	SCIP data structure
subsol	solution

Definition at line 161 of file dptermsinterns.h.

References dynamic_programming_subsolution::bitkey, dpterms_intersectsEqualNaive(), SCIP_Bool, SCIPfreeBlockMemory, STP_Bitset, STP_Vectype(), stpbitset_free(), StpVecFree, sub, and subsol.

Referenced by dpiterFinalizeSol().

dpterms_intersectsEqualNaive()

SCIP_Bool dpterms_intersectsEqualNaive	(	SCIP *	scip,
		STP_Bitset	termsmark,
		STP_Bitset	rootsmark,
		STP_Vectype(int)	intersects,
		DPMISC *	dpmisc
	)

for debugging: checks whether given intersection is equal to naively computed one

Parameters

scip	SCIP data structure
termsmark	terminal mark
rootsmark	marks roots of extension trees
intersects	intersection indices
dpmisc	MISC DP data

Definition at line 340 of file dpterms_util.c.

References BMScopyMemoryArray, FALSE, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, SCIPsortDownInt(), STP_Vectype(), StpVecFree, StpVecGetSize, and TRUE.

Referenced by dpterms_dpsubsolFree().

STP_Vectype()

STP_Vectype

(

int

)

Referenced by dpterms_dpsubsolFree().

dpterms_streeInit()

DPMISC* SCIP_RETCODE dpterms_streeInit	(	SCIP *	scip,
		int	nterms,
		int	nnodes,
		DPSTREE **	dpstree
	)

initializes

Parameters

scip	SCIP data structure
nterms	number of terminals
nnodes	number of nodes
dpstree	initialize

Definition at line 533 of file dpterms_util.c.

References nnodes, nterms, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by dpsolverInitData().

dpterms_streeFree()

void dpterms_streeFree	(	SCIP *	scip,
		DPSTREE **	dpstree
	)

frees

Parameters

scip	SCIP data structure
dpstree	initialize

Definition at line 560 of file dpterms_util.c.

References SCIPfreeMemory, stpbitset_free(), StpVecFree, and StpVecGetSize.

Referenced by dpsolverFreeData().

dpterms_streeInsert()

SCIP_RETCODE dpterms_streeInsert	(	SCIP *	scip,
		STP_Bitset	termsmark,
		STP_Bitset	rootsmark,
		int64_t	nsubsets,
		DPSTREE *	dpstree
	)

inserts NOTE: dps-tree takes ownership of bitsets!

Parameters

scip	SCIP data structure
termsmark	terminal mark; will become OWNED
rootsmark	marks roots of extension trees; will become OWNED
nsubsets	number of subsets
dpstree	to insert to

Definition at line 449 of file dpterms_util.c.

References addLeaf(), bitsetsizesAreValid(), insertData(), NULL, SCIP_ERROR, SCIP_OKAY, SCIPdebugMessage, SCIPerrorMessage, dynamic_programming_search_tree_node::split_pos, STP_Bitset, STP_Vectype(), stpbitset_getPopcount(), stpbitset_print(), and streeCollectIntersects().

Referenced by subtreesAddNewFinalize().

dpterms_coreSolve()

DPSTREE* SCIP_RETCODE dpterms_coreSolve	(	SCIP *	scip,
		GRAPH *	graph,
		DPSOLVER *	dpsolver,
		SCIP_Bool *	wasSolved
	)

solves problem

Parameters

scip	SCIP data structure
graph	graph
dpsolver	solver
wasSolved	was problem solved to optimality?

Definition at line 1288 of file dpterms_core.c.

References dynamic_programming_solver::dpgraph, dpiterFinalizeSol(), dpiterFree(), dpiterGetNextSol(), dpiterInit(), dynamic_programming_solver::dpmisc, dynamic_programming_solver::dpstree, FALSE, dynamic_programming_misc::global_size, dynamic_programming_misc::opt_obj, propagateUBs(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisStopped(), dynamic_programming_solver::solpqueue, dynamic_programming_solver::soltree_root, stpprioqueue_isClean(), subtreesAddNew(), subtreesBuild(), subtreesExtend(), subtreesRemoveNonValids(), GRAPH::terms, and TRUE.

Referenced by dpsolverSolve().

Variable Documentation

subsol

DPSUBSOL** subsol

Initial value:

{
   DPSUBSOL* sub

< SCIP data structure < solution

Definition at line 148 of file dptermsinterns.h.

Referenced by combineWithIntersecting(), dpiterPopSol(), dpterms_dpsubsolFree(), sepafullAddSolForCand(), subscipGetSol(), subsolFree(), subsolInit(), termcompComputeSubgraphSol(), transferSolution(), and updatePartition().

sub

sub = *subsol

Definition at line 151 of file dptermsinterns.h.

Referenced by dpterms_dpsubsolFree(), graph_subinoutFree(), graph_subinoutInit(), initDefault(), SCIPlpiDelCols(), SCIPlpiDelColset(), SCIPlpiDelRows(), SCIPlpiDelRowset(), SCIPlpiGetBInvACol(), SCIPlpiGetBInvCol(), SCIPlpiGetBInvRow(), SCIPlpiScaleCol(), SCIPlpiScaleRow(), substpsolver_free(), substpsolver_initBC(), and substpsolver_initDP().

bitkey

sub bitkey = NULL

Definition at line 152 of file dptermsinterns.h.

traces

sub traces = NULL

Definition at line 153 of file dptermsinterns.h.

SCIP_OKAY

return SCIP_OKAY

Definition at line 155 of file dptermsinterns.h.

STP_Bitset

STP_Bitset

Definition at line 189 of file dptermsinterns.h.

Referenced by allExtensionsAreInvalid(), combineWithIntersecting(), dpiterAddNewPrepare(), dpterms_dpsubsolFree(), dpterms_streeInsert(), insertData(), STP_Vectype(), streeCollectIntersects(), subtreesExtend(), subtreesRemoveNonValids(), and updateIncumbent().