reduce_sol.c File Reference

Detailed Description

Reduction solution storage methods for Steiner problems.

Author

Daniel Rehfeldt

This file includes methods to save and retain solutions and sollocal bounds during the reduction process

A list of all interface methods can be found in reduce.h.

Definition in file reduce_sol.c.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "graph.h"
#include "reduce.h"
#include "heur_tm.h"
#include "solstp.h"
#include "scip/scip.h"
#include "portab.h"
#include "stpvector.h"

Go to the source code of this file.

Data Structures
struct	reduction_local_solution_storage
struct	reduction_solution_level
struct	reduction_solution_storage

Macros
#define	REDSOLVAL_UNSET   (-FARAWAY)

Typedefs
typedef struct reduction_solution_level	REDSOLLEVEL

Functions
static void	nodesolSetTrivial (const GRAPH *g, int *nodesol)
static SCIP_RETCODE	nodesolUpdate (SCIP *scip, GRAPH *g, SCIP_Real *solval, PATH *solpath, int *nodesol)
static SCIP_RETCODE	sollocalInitNodesol (SCIP *scip, int *nodesol_transfer, REDSOLLOCAL *sollocal)
static void	nodesolGetEdgeSol (const GRAPH *graph, const PATH *solpath, int *edgesol)
static SCIP_RETCODE	redlevelInit (SCIP *scip, int nnodes, REDSOLLEVEL **redlevel)
static void	redlevelFree (SCIP *scip, REDSOLLEVEL **redlevel)
static SCIP_Bool	redlevelIsClean (REDSOLLEVEL *redlevel)
static void	redlevelClean (SCIP *scip, REDSOLLEVEL *redlevel)
static int *	redlevelGetNodesol (REDSOLLEVEL *redlevel)
static SCIP_RETCODE	redlevelInitIncomplete (SCIP *scip, const REDSOL *redsol, REDSOLLEVEL *redlevel)
static SCIP_RETCODE	redlevelAddLocal (SCIP *scip, const GRAPH *g, REDSOLLEVEL *redlevel, REDSOLLOCAL **redsollocal_out)
static int	redsolGetNlevels (const REDSOL *redsol)
static REDSOLLEVEL *	redsolGetTopLevel (const REDSOL *redsol)
static REDSOLLEVEL *	redsolGetTopParentLevel (const REDSOL *redsol)
SCIP_RETCODE	reduce_sollocalInit (SCIP *scip, const GRAPH *g, REDSOLLOCAL **sollocal)
void	reduce_sollocalFree (SCIP *scip, REDSOLLOCAL **sollocal)
void	reduce_sollocalSetOffset (SCIP_Real offsetnew, REDSOLLOCAL *sollocal)
SCIP_RETCODE	reduce_sollocalRebuildTry (SCIP *scip, GRAPH *g, REDSOLLOCAL *sollocal)
SCIP_Bool	reduce_sollocalUsesNodesol (const REDSOLLOCAL *sollocal)
SCIP_RETCODE	reduce_sollocalUpdateNodesol (SCIP *scip, const int *edgesol, GRAPH *g, REDSOLLOCAL *sollocal)
void	reduce_sollocalUpdateUpperBound (SCIP_Real ubnew, REDSOLLOCAL *sollocal)
SCIP_Real	reduce_sollocalGetUpperBound (const REDSOLLOCAL *sollocal)
int *	reduce_sollocalGetSolnode (REDSOLLOCAL *sollocal)
SCIP_Real	reduce_sollocalGetUpperBoundWithOffset (const REDSOLLOCAL *sollocal)
SCIP_Bool	reduce_sollocalHasUpperBound (const REDSOLLOCAL *sollocal)
SCIP_RETCODE	reduce_solInit (SCIP *scip, const GRAPH *g, SCIP_Bool useNodeSol, REDSOL **redsol)
SCIP_RETCODE	reduce_solInitLocal (SCIP *scip, const GRAPH *g, REDSOL *redsol, REDSOLLOCAL **redsollocal_out)
void	reduce_solFinalizeLocal (SCIP *scip, const GRAPH *g, REDSOL *redsol)
void	reduce_solReInitLocal (const GRAPH *g, REDSOL *redsol)
void	reduce_solFree (SCIP *scip, REDSOL **redsol)
void	reduce_solPack (const GRAPH *g, const int *nodes_old2packed, int nnodes_packed, REDSOL *redsol)
SCIP_RETCODE	reduce_solLevelAdd (SCIP *scip, const GRAPH *g, REDSOL *redsol)
SCIP_RETCODE	reduce_solLevelTopUpdate (SCIP *scip, const GRAPH *subgraph, REDSOL *redsol)
void	reduce_solLevelTopRemove (SCIP *scip, REDSOL *redsol)
void	reduce_solLevelTopFinalize (SCIP *scip, GRAPH *g, REDSOL *redsol)
void	reduce_solLevelTopClean (SCIP *scip, REDSOL *redsol)
void	reduce_solLevelTopTransferSolBack (const int *nodemap_subToOrg, REDSOL *redsol)
SCIP_RETCODE	reduce_solLevelTopTransferSolTo (const int *nodemap_orgToTop, REDSOL *redsol)
void	reduce_solSetOffset (SCIP_Real offsetnew, REDSOL *redsol)
SCIP_Real	reduce_solGetOffset (const REDSOL *redsol)
SCIP_RETCODE	reduce_solAddNodesol (const GRAPH *g, const int *nodesol, REDSOL *redsol)
void	reduce_solGetNodesol (const GRAPH *g, REDSOL *redsol, int *nodesol)
SCIP_RETCODE	reduce_solGetEdgesol (SCIP *scip, GRAPH *g, REDSOL *redsol, SCIP_Real *solval, int *edgesol)
SCIP_Bool	reduce_solUsesNodesol (const REDSOL *redsol)
const int *	reduce_solGetNodesolPointer (const REDSOL *redsol)
SCIP_Real	reduce_solGetUpperBoundWithOffset (const REDSOL *redsol)
SCIP_Real *	reduce_solGetOffsetPointer (REDSOL *redsol)

Macro Definition Documentation

REDSOLVAL_UNSET

#define REDSOLVAL_UNSET   (-FARAWAY)

Definition at line 42 of file reduce_sol.c.

Referenced by redlevelClean(), redlevelInit(), redlevelIsClean(), reduce_solFinalizeLocal(), reduce_solGetUpperBoundWithOffset(), reduce_solLevelTopTransferSolBack(), reduce_sollocalInit(), reduce_sollocalRebuildTry(), reduce_sollocalUpdateNodesol(), reduce_solReInitLocal(), and sollocalInitNodesol().

Typedef Documentation

REDSOLLEVEL

typedef struct reduction_solution_level REDSOLLEVEL

single level representation (needed for decomposition of problem graph)

Function Documentation

nodesolSetTrivial()

static void nodesolSetTrivial ( const GRAPH *  g, int *  nodesol  )

static

updates node solution

Parameters

g	graph data structure
nodesol	solution array to be filled

Definition at line 87 of file reduce_sol.c.

References CONNECT, graph_get_nNodes(), Is_term, reduction_local_solution_storage::nnodes, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by reduce_solFinalizeLocal().

nodesolUpdate()

static SCIP_RETCODE nodesolUpdate ( SCIP *  scip, GRAPH *  g, SCIP_Real *  solval, PATH *  solpath, int *  nodesol  )

static

updates node solution

Parameters

scip	SCIP data structure
g	graph data structure
solval	FARAWAY if no valid solution build
solpath	path entry per node
nodesol	solution array to be filled

Definition at line 113 of file reduce_sol.c.

References BMScopyMemoryArray, GRAPH::cost, graph_get_nNodes(), graph_pc_isPcMw(), graph_printInfoReduced(), graph_typeIsSpgLike(), reduction_local_solution_storage::nnodes, reduction_local_solution_storage::nodesol, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreePcMw(), and TRUE.

Referenced by reduce_solGetEdgesol(), reduce_sollocalRebuildTry(), and reduce_sollocalUpdateNodesol().

sollocalInitNodesol()

static SCIP_RETCODE sollocalInitNodesol ( SCIP *  scip, int *  nodesol_transfer, REDSOLLOCAL *  sollocal  )

static

initializes node solution

Parameters

scip	SCIP data structure
nodesol_transfer	solution to be moved or NULL
sollocal	solution

Definition at line 166 of file reduce_sol.c.

References reduction_local_solution_storage::nnodes, reduction_local_solution_storage::nodesol, reduction_local_solution_storage::nodesol_ub, reduction_local_solution_storage::nodesol_use, REDSOLVAL_UNSET, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, TRUE, and UNKNOWN.

Referenced by redlevelAddLocal().

nodesolGetEdgeSol()

static void nodesolGetEdgeSol ( const GRAPH *  graph, const PATH *  solpath, int *  edgesol  )

static

gets edge solution after nodesolUpdate call

Parameters

graph	graph
solpath	stores solution
edgesol	solution array to be filled

Definition at line 202 of file reduce_sol.c.

References CONNECT, shortest_path::edge, graph_get_nEdges(), graph_get_nNodes(), reduction_local_solution_storage::nnodes, and UNKNOWN.

Referenced by reduce_solGetEdgesol().

redlevelInit()

static SCIP_RETCODE redlevelInit ( SCIP *  scip, int  nnodes, REDSOLLEVEL **  redlevel  )

static

initializes

Parameters

scip	SCIP data structure
nnodes	number of nodes
redlevel	to be initialized

Definition at line 226 of file reduce_sol.c.

References reduction_local_solution_storage::nnodes, reduction_solution_level::nnodes, reduction_solution_level::nodesol, reduction_solution_level::nodesol_transfer, reduction_solution_level::nodesol_ub, reduction_solution_level::nodesol_use, NULL, reduction_solution_level::redsollocal, REDSOLVAL_UNSET, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, reduction_solution_level::solval_incomplete, reduction_solution_level::solval_postred, and TRUE.

Referenced by reduce_solInit(), and reduce_solLevelAdd().

redlevelFree()

static void redlevelFree ( SCIP *  scip, REDSOLLEVEL **  redlevel  )

static

frees

Parameters

scip	SCIP data structure
redlevel	to be freed

Definition at line 255 of file reduce_sol.c.

References reduction_solution_level::nodesol, reduction_solution_level::nodesol_transfer, reduction_solution_level::redsollocal, reduce_sollocalFree(), SCIPfreeMemory, and SCIPfreeMemoryArrayNull.

Referenced by reduce_solFree(), reduce_solLevelTopFinalize(), and reduce_solLevelTopRemove().

redlevelIsClean()

static SCIP_Bool redlevelIsClean ( REDSOLLEVEL *  redlevel )

static

Parameters

redlevel

to be cleaned

Definition at line 280 of file reduce_sol.c.

References EQ, FALSE, reduction_solution_level::nodesol, reduction_solution_level::redsollocal, REDSOLVAL_UNSET, reduction_solution_level::solval_incomplete, reduction_solution_level::solval_postred, and TRUE.

Referenced by redlevelClean(), and reduce_solLevelTopUpdate().

redlevelClean()

static void redlevelClean ( SCIP *  scip, REDSOLLEVEL *  redlevel  )

static

cleans

Parameters

scip	SCIP data structure
redlevel	to be cleaned

Definition at line 305 of file reduce_sol.c.

References reduction_solution_level::nodesol, reduction_solution_level::nodesol_use, redlevelIsClean(), reduction_solution_level::redsollocal, REDSOLVAL_UNSET, SCIPfreeMemoryArrayNull, reduction_solution_level::solval_incomplete, and reduction_solution_level::solval_postred.

Referenced by reduce_solLevelTopClean().

redlevelGetNodesol()

static int* redlevelGetNodesol ( REDSOLLEVEL *  redlevel )

static

gets node solution

Parameters

redlevel

to be cleaned

Definition at line 325 of file reduce_sol.c.

References reduction_solution_level::nodesol, reduction_solution_level::redsollocal, and reduce_sollocalGetSolnode().

Referenced by reduce_solLevelTopTransferSolBack(), and reduce_solLevelTopTransferSolTo().

redlevelInitIncomplete()

static SCIP_RETCODE redlevelInitIncomplete ( SCIP *  scip, const REDSOL *  redsol, REDSOLLEVEL *  redlevel  )

static

initializes incomplete info

Parameters

scip	SCIP data structure
redsol	reduction solution
redlevel	to be initialized

Definition at line 342 of file reduce_sol.c.

References EQ, reduction_solution_level::nnodes, SCIP_OKAY, SCIPdebugMessage, and reduction_solution_level::solval_incomplete.

Referenced by reduce_solLevelAdd().

redlevelAddLocal()

static SCIP_RETCODE redlevelAddLocal ( SCIP *  scip, const GRAPH *  g, REDSOLLEVEL *  redlevel, REDSOLLOCAL **  redsollocal_out  )

static

adds local solution

Parameters

scip	SCIP data structure
g	graph data structure
redlevel	level
redsollocal_out	pointer to newly initialized local

Definition at line 362 of file reduce_sol.c.

References reduction_solution_level::nnodes, reduction_solution_level::nodesol_transfer, reduction_solution_level::nodesol_use, NULL, reduction_solution_level::redsollocal, reduce_sollocalInit(), SCIP_CALL, SCIP_OKAY, and sollocalInitNodesol().

Referenced by reduce_solInitLocal().

redsolGetNlevels()

static int redsolGetNlevels ( const REDSOL *  redsol )

static

gets number of levels

Parameters

redsol

solution

Definition at line 399 of file reduce_sol.c.

References StpVecGetSize.

Referenced by redsolGetTopLevel(), redsolGetTopParentLevel(), reduce_solAddNodesol(), reduce_solFinalizeLocal(), reduce_solGetNodesol(), reduce_solGetNodesolPointer(), reduce_solGetUpperBoundWithOffset(), reduce_solInit(), reduce_solInitLocal(), reduce_solLevelAdd(), reduce_solLevelTopClean(), reduce_solLevelTopFinalize(), reduce_solLevelTopRemove(), and reduce_solLevelTopTransferSolBack().

redsolGetTopLevel()

static REDSOLLEVEL* redsolGetTopLevel ( const REDSOL *  redsol )

static

gets top level

Parameters

redsol

solution

Definition at line 415 of file reduce_sol.c.

References redsolGetNlevels().

Referenced by reduce_solFinalizeLocal(), reduce_solGetNodesolPointer(), reduce_solLevelAdd(), reduce_solLevelTopFinalize(), reduce_solLevelTopTransferSolBack(), reduce_solLevelTopTransferSolTo(), reduce_solLevelTopUpdate(), and reduce_solReInitLocal().

redsolGetTopParentLevel()

static REDSOLLEVEL* redsolGetTopParentLevel ( const REDSOL *  redsol )

static

gets parent of top level

Parameters

redsol

solution

Definition at line 429 of file reduce_sol.c.

References redsolGetNlevels().

Referenced by reduce_solLevelTopTransferSolBack(), and reduce_solLevelTopTransferSolTo().

reduce_sollocalInit()

SCIP_RETCODE reduce_sollocalInit	(	SCIP *	scip,
		const GRAPH *	g,
		REDSOLLOCAL **	sollocal
	)

initializes

Parameters

scip	SCIP data structure
g	graph data structure
sollocal	to initialize

Definition at line 447 of file reduce_sol.c.

References FALSE, FARAWAY, graph_get_nNodes(), graph_pc_isPcMw(), reduction_local_solution_storage::isPcMw, reduction_local_solution_storage::nnodes, reduction_local_solution_storage::nodesol, reduction_local_solution_storage::nodesol_ub, reduction_local_solution_storage::nodesol_use, NULL, reduction_local_solution_storage::offset, reduction_local_solution_storage::primalbound, REDSOLVAL_UNSET, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by redlevelAddLocal(), reduce_dc(), and reduce_hc().

reduce_sollocalFree()

void reduce_sollocalFree	(	SCIP *	scip,
		REDSOLLOCAL **	sollocal
	)

frees

Parameters

scip	SCIP data structure
sollocal	to free

Definition at line 472 of file reduce_sol.c.

References SCIPfreeMemory, and SCIPfreeMemoryArrayNull.

Referenced by redlevelFree(), reduce_dc(), reduce_hc(), and reduce_solFinalizeLocal().

reduce_sollocalSetOffset()

void reduce_sollocalSetOffset	(	SCIP_Real	offsetnew,
		REDSOLLOCAL *	sollocal
	)

sets offset NOTE: offset is only used within this structure!

Parameters

offsetnew	new offset
sollocal	sollocal

Definition at line 488 of file reduce_sol.c.

References EQ, FARAWAY, GE, reduction_local_solution_storage::isPcMw, reduction_local_solution_storage::offset, reduction_local_solution_storage::primalbound, and SCIPdebugMessage.

Referenced by redLoopInnerMw(), redLoopInnerPc(), redLoopInnerStp(), reduce_da(), reduce_impliedProfitBasedRpc(), reduce_redLoopMw(), reduce_redLoopPc(), reduce_solFinalizeLocal(), and reduce_solLevelTopFinalize().

reduce_sollocalRebuildTry()

SCIP_RETCODE reduce_sollocalRebuildTry	(	SCIP *	scip,
		GRAPH *	g,
		REDSOLLOCAL *	sollocal
	)

tries to rebuild solnode if possible and necessary

Parameters

scip	SCIP data structure
g	graph
sollocal	sollocal

Definition at line 507 of file reduce_sol.c.

References EQ, GRAPH::extended, FARAWAY, GE, graph_pc_2org(), graph_pc_2trans(), graph_pc_getNonLeafTermOffset(), graph_pc_isPc(), graph_pc_isPcMw(), GT, GRAPH::knots, reduction_local_solution_storage::nnodes, reduction_local_solution_storage::nodesol, reduction_local_solution_storage::nodesol_ub, nodesolUpdate(), reduction_local_solution_storage::offset, reduction_local_solution_storage::primalbound, REDSOLVAL_UNSET, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, and GRAPH::terms.

Referenced by redLoopInnerMw(), redLoopInnerPc(), reduce_da(), reduce_impliedProfitBasedRpc(), reduce_redLoopMw(), and reduce_redLoopPc().

reduce_sollocalUsesNodesol()

SCIP_Bool reduce_sollocalUsesNodesol

(

const REDSOLLOCAL *

sollocal

)

updates

Parameters

sollocal

sollocal

Definition at line 554 of file reduce_sol.c.

References reduction_local_solution_storage::nodesol_use.

Referenced by redbaseGetSolnode(), reduce_da(), reduce_daPcMw(), reduce_sollocalGetSolnode(), and reduce_sollocalUpdateNodesol().

reduce_sollocalUpdateNodesol()

SCIP_RETCODE reduce_sollocalUpdateNodesol	(	SCIP *	scip,
		const int *	edgesol,
		GRAPH *	g,
		REDSOLLOCAL *	sollocal
	)

updates

Parameters

scip	SCIP data structure
edgesol	incoming solution
g	graph data structure
sollocal	sollocal

Definition at line 565 of file reduce_sol.c.

References EQ, FARAWAY, graph_get_nNodes(), LT, reduction_local_solution_storage::nnodes, reduction_local_solution_storage::nodesol, reduction_local_solution_storage::nodesol_ub, nodesolUpdate(), REDSOLVAL_UNSET, reduce_sollocalUsesNodesol(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, solstp_getObj(), solstp_isValid(), and solstp_setVertexFromEdgeConn().

Referenced by reduce_da(), and reduce_daPcMw().

reduce_sollocalUpdateUpperBound()

void reduce_sollocalUpdateUpperBound	(	SCIP_Real	ubnew,
		REDSOLLOCAL *	sollocal
	)

sets new sollocal bound if better than old one

Parameters

ubnew	new upper bound, not including offset!
sollocal	sollocal

Definition at line 610 of file reduce_sol.c.

References FARAWAY, GE, LE, reduction_local_solution_storage::offset, reduction_local_solution_storage::primalbound, SCIP_Real, and SCIPdebugMessage.

Referenced by reduce_da(), reduce_daPcMw(), reduce_solFinalizeLocal(), and reduce_solLevelTopFinalize().

reduce_sollocalGetUpperBound()

SCIP_Real reduce_sollocalGetUpperBound

(

const REDSOLLOCAL *

sollocal

)

gets upper bound; not including (last set) offset

Parameters

sollocal

sollocal

Definition at line 633 of file reduce_sol.c.

References EQ, FARAWAY, GE_FEAS, MAX, reduction_local_solution_storage::offset, reduction_local_solution_storage::primalbound, and SCIPdebugMessage.

Referenced by redLoopInnerStp(), reduce_da(), reduce_daPcMw(), and reduce_impliedProfitBasedRpc().

reduce_sollocalGetSolnode()

int* reduce_sollocalGetSolnode

(

REDSOLLOCAL *

sollocal

)

gets array

Parameters

sollocal

sollocal

Definition at line 651 of file reduce_sol.c.

References reduction_local_solution_storage::nodesol, NULL, and reduce_sollocalUsesNodesol().

Referenced by redbaseGetSolnode(), redlevelGetNodesol(), redLoopInnerMw(), redLoopInnerPc(), reduce_impliedProfitBasedRpc(), reduce_redLoopMw(), and reduce_redLoopPc().

reduce_sollocalGetUpperBoundWithOffset()

SCIP_Real reduce_sollocalGetUpperBoundWithOffset

(

const REDSOLLOCAL *

sollocal

)

gets upper bound; including (last set) offset

Parameters

sollocal

sollocal

Definition at line 664 of file reduce_sol.c.

References reduction_local_solution_storage::primalbound.

Referenced by reduce_solFinalizeLocal().

reduce_sollocalHasUpperBound()

SCIP_Bool reduce_sollocalHasUpperBound

(

const REDSOLLOCAL *

sollocal

)

do we have a (non-trivial) primal bound?

Parameters

sollocal

sollocal

Definition at line 675 of file reduce_sol.c.

References EQ, FARAWAY, LE, and reduction_local_solution_storage::primalbound.

Referenced by reduce_solFinalizeLocal().

reduce_solInit()

SCIP_RETCODE reduce_solInit	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Bool	useNodeSol,
		REDSOL **	redsol
	)

initializes

Parameters

scip	SCIP data structure
g	graph data structure
useNodeSol	should solution be used? (additionally to solution value)
redsol	to be initialized

Definition at line 687 of file reduce_sol.c.

References graph_pc_isPcMw(), GRAPH::knots, reduction_solution_level::nodesol_use, NULL, redlevelInit(), redsolGetNlevels(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and StpVecPushBack.

Referenced by fixVarsRedbased(), graph_writeReductionRatioStatsLive(), reduceExact(), SCIPprobdataCreateFromGraph(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

reduce_solInitLocal()

SCIP_RETCODE reduce_solInitLocal	(	SCIP *	scip,
		const GRAPH *	g,
		REDSOL *	redsol,
		REDSOLLOCAL **	redsollocal_out
	)

adds local for given level; call before reduction loop

Parameters

scip	SCIP data structure
g	graph data structure
redsol	reduction solution
redsollocal_out	pointer to newly initialized local

Definition at line 717 of file reduce_sol.c.

References redlevelAddLocal(), redsolGetNlevels(), SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_redLoopMw(), reduce_redLoopPc(), reduce_redLoopStp(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

reduce_solFinalizeLocal()

void reduce_solFinalizeLocal	(	SCIP *	scip,
		const GRAPH *	g,
		REDSOL *	redsol
	)

finalizes local for given level; call after reduction loop

Parameters

scip	SCIP data structure
g	graph data structure
redsol	reduction solution

Definition at line 735 of file reduce_sol.c.

References EQ, FARAWAY, reduction_local_solution_storage::nodesol, reduction_solution_level::nodesol, reduction_local_solution_storage::nodesol_ub, reduction_solution_level::nodesol_ub, reduction_local_solution_storage::nodesol_use, nodesolSetTrivial(), NULL, reduction_local_solution_storage::offset, redsolGetNlevels(), redsolGetTopLevel(), reduction_solution_level::redsollocal, REDSOLVAL_UNSET, reduce_solGetOffset(), reduce_sollocalFree(), reduce_sollocalGetUpperBoundWithOffset(), reduce_sollocalHasUpperBound(), reduce_sollocalSetOffset(), reduce_sollocalUpdateUpperBound(), SCIP_CALL_ABORT, SCIP_Real, reduction_solution_level::solval_postred, and GRAPH::terms.

Referenced by reduce_redLoopMw(), reduce_redLoopPc(), reduce_redLoopStp(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

reduce_solReInitLocal()

void reduce_solReInitLocal	(	const GRAPH *	g,
		REDSOL *	redsol
	)

reinitalizes local after it has been finished

Parameters

g	graph data structure
redsol	reduction solution

Definition at line 793 of file reduce_sol.c.

References GRAPH::knots, reduction_solution_level::nnodes, reduction_solution_level::nodesol, reduction_solution_level::nodesol_transfer, reduction_solution_level::nodesol_ub, NULL, redsolGetTopLevel(), REDSOLVAL_UNSET, and reduction_solution_level::solval_postred.

Referenced by reduce_exec().

reduce_solFree()

void reduce_solFree	(	SCIP *	scip,
		REDSOL **	redsol
	)

frees

Parameters

scip	SCIP data structure
redsol	to be freed

Definition at line 818 of file reduce_sol.c.

References redlevelFree(), SCIPfreeMemory, StpVecFree, StpVecGetSize, StpVecIsEmpty, and StpVecPopBack.

Referenced by fixVarsRedbased(), graph_writeReductionRatioStatsLive(), reduceExact(), SCIPprobdataCreateFromGraph(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

reduce_solPack()

void reduce_solPack	(	const GRAPH *	g,
		const int *	nodes_old2packed,
		int	nnodes_packed,
		REDSOL *	redsol
	)

packs solution

Parameters

g	graph data structure
nodes_old2packed	map to packed node IDs
nnodes_packed	number of packed nodes
redsol	sollocal

Definition at line 846 of file reduce_sol.c.

References graph_get_nNodes(), graph_pc_isPcMw(), reduction_local_solution_storage::nnodes, reduction_solution_level::nnodes, reduction_local_solution_storage::nodesol, and reduction_solution_level::nodesol.

Referenced by graph_pack().

reduce_solLevelAdd()

SCIP_RETCODE reduce_solLevelAdd	(	SCIP *	scip,
		const GRAPH *	g,
		REDSOL *	redsol
	)

adds level

Parameters

scip	SCIP data structure
g	graph data structure
redsol	sollocal

Definition at line 897 of file reduce_sol.c.

References EQ, reduction_solution_level::nodesol_use, redlevelInit(), redlevelInitIncomplete(), redsolGetNlevels(), redsolGetTopLevel(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and StpVecPushBack.

Referenced by decomposeReduce().

reduce_solLevelTopUpdate()

SCIP_RETCODE reduce_solLevelTopUpdate	(	SCIP *	scip,
		const GRAPH *	subgraph,
		REDSOL *	redsol
	)

initializes level with given (sub) graph

Parameters

scip	SCIP data structure
subgraph	graph data structure
redsol	reduction solution

Definition at line 922 of file reduce_sol.c.

References graph_get_nNodes(), reduction_local_solution_storage::nnodes, reduction_solution_level::nnodes, redlevelIsClean(), redsolGetTopLevel(), and SCIP_OKAY.

Referenced by decomposeReduceSubDoIt().

reduce_solLevelTopRemove()

void reduce_solLevelTopRemove	(	SCIP *	scip,
		REDSOL *	redsol
	)

removes top level

Parameters

scip	SCIP data structure
redsol	reduction solution

Definition at line 940 of file reduce_sol.c.

References redlevelFree(), redsolGetNlevels(), and StpVecPopBack.

reduce_solLevelTopFinalize()

void reduce_solLevelTopFinalize	(	SCIP *	scip,
		GRAPH *	g,
		REDSOL *	redsol
	)

finalizes top level; also removes the level!

Parameters

scip	SCIP data structure
g	graph data structure
redsol	sollocal

Definition at line 956 of file reduce_sol.c.

References redlevelFree(), redsolGetNlevels(), redsolGetTopLevel(), reduction_solution_level::redsollocal, reduce_sollocalSetOffset(), reduce_sollocalUpdateUpperBound(), SCIPdebugMessage, reduction_solution_level::solval_incomplete, and StpVecPopBack.

Referenced by decomposeReduce().

reduce_solLevelTopClean()

void reduce_solLevelTopClean	(	SCIP *	scip,
		REDSOL *	redsol
	)

removes level

Parameters

scip	SCIP data structure
redsol	sollocal

Definition at line 997 of file reduce_sol.c.

References redlevelClean(), and redsolGetNlevels().

Referenced by decomposeReduceSubDoIt().

reduce_solLevelTopTransferSolBack()

void reduce_solLevelTopTransferSolBack	(	const int *	nodemap_subToOrg,
		REDSOL *	redsol
	)

merges level up

Parameters

nodemap_subToOrg	map
redsol	sollocal

Definition at line 1010 of file reduce_sol.c.

References CONNECT, EQ, FARAWAY, GE, GT, MAX, reduction_local_solution_storage::nnodes, reduction_solution_level::nnodes, reduction_local_solution_storage::nodesol_ub, reduction_solution_level::nodesol_ub, reduction_solution_level::nodesol_use, redlevelGetNodesol(), redsolGetNlevels(), redsolGetTopLevel(), redsolGetTopParentLevel(), reduction_solution_level::redsollocal, REDSOLVAL_UNSET, SCIPdebugMessage, reduction_solution_level::solval_incomplete, reduction_solution_level::solval_postred, and UNKNOWN.

Referenced by decomposeReduceSubDoIt().

reduce_solLevelTopTransferSolTo()

SCIP_RETCODE reduce_solLevelTopTransferSolTo	(	const int *	nodemap_orgToTop,
		REDSOL *	redsol
	)

transfers solution from parent to top level

Parameters

nodemap_orgToTop	map
redsol	sollocal

Definition at line 1067 of file reduce_sol.c.

References reduction_solution_level::nnodes, reduction_solution_level::nodesol_transfer, reduction_solution_level::nodesol_use, redlevelGetNodesol(), redsolGetTopLevel(), redsolGetTopParentLevel(), reduction_solution_level::redsollocal, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by decomposeReduceSubDoIt().

reduce_solSetOffset()

void reduce_solSetOffset	(	SCIP_Real	offsetnew,
		REDSOL *	redsol
	)

sets offset

Parameters

offsetnew	new offset
redsol	solution

Definition at line 1124 of file reduce_sol.c.

References GE.

Referenced by decomposeReduceSubDoIt().

reduce_solGetOffset()

SCIP_Real reduce_solGetOffset

(

const REDSOL *

redsol

)

gets

Parameters

redsol

solution

Definition at line 1137 of file reduce_sol.c.

Referenced by decomposeReduceSubDoIt(), fixVarsRedbased(), reduce_solFinalizeLocal(), reduce_stp(), reduceExact(), SCIPprobdataCreateFromGraph(), and SCIPStpHeurPruneRun().

reduce_solAddNodesol()

SCIP_RETCODE reduce_solAddNodesol	(	const GRAPH *	g,
		const int *	nodesol,
		REDSOL *	redsol
	)

adds (and possibly overwrites) nodesol

Parameters

g	graph data structure
nodesol	incoming solution
redsol	solution

Definition at line 1150 of file reduce_sol.c.

References BMScopyMemoryArray, GRAPH::knots, reduction_solution_level::nnodes, reduction_solution_level::nodesol_transfer, reduction_solution_level::nodesol_ub, redsolGetNlevels(), SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by reduceExact(), and SCIPStpHeurPruneRun().

reduce_solGetNodesol()

void reduce_solGetNodesol	(	const GRAPH *	g,
		REDSOL *	redsol,
		int *	nodesol
	)

gets

Parameters

g	graph data structure
redsol	solution
nodesol	solution array to be filled

Definition at line 1176 of file reduce_sol.c.

References BMScopyMemoryArray, GRAPH::knots, reduction_solution_level::nnodes, reduction_solution_level::nodesol, and redsolGetNlevels().

Referenced by reduceExact(), and SCIPStpHeurPruneRun().

reduce_solGetEdgesol()

SCIP_RETCODE reduce_solGetEdgesol	(	SCIP *	scip,
		GRAPH *	g,
		REDSOL *	redsol,
		SCIP_Real *	solval,
		int *	edgesol
	)

gets edge solution, if available, and solution value

Parameters

scip	SCIP data structure
g	graph data structure
redsol	solution
solval	FARAWAY if no solution available
edgesol	solution array to be filled

Definition at line 1197 of file reduce_sol.c.

References FARAWAY, graph_get_nNodes(), GRAPH::knots, LT, reduction_local_solution_storage::nnodes, reduction_solution_level::nodesol, reduction_solution_level::nodesol_ub, nodesolGetEdgeSol(), nodesolUpdate(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.

Referenced by addRedsol(), and computeReducedProbSolution().

reduce_solUsesNodesol()

SCIP_Bool reduce_solUsesNodesol

(

const REDSOL *

redsol

)

is node solution in use?

Parameters

redsol

solution

Definition at line 1236 of file reduce_sol.c.

Referenced by computeReducedProbSolution(), redbaseGetSolnode(), and reduce_solGetNodesolPointer().

reduce_solGetNodesolPointer()

const int* reduce_solGetNodesolPointer

(

const REDSOL *

redsol

)

gets

Parameters

redsol

solution

Definition at line 1248 of file reduce_sol.c.

References reduction_solution_level::nodesol, redsolGetNlevels(), redsolGetTopLevel(), and reduce_solUsesNodesol().

reduce_solGetUpperBoundWithOffset()

SCIP_Real reduce_solGetUpperBoundWithOffset

(

const REDSOL *

redsol

)

gets

Parameters

redsol

solution

Definition at line 1263 of file reduce_sol.c.

References EQ, FARAWAY, redsolGetNlevels(), REDSOLVAL_UNSET, SCIP_Real, and reduction_solution_level::solval_postred.

Referenced by presolveStp(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

reduce_solGetOffsetPointer()

SCIP_Real* reduce_solGetOffsetPointer

(

REDSOL *

redsol

)

gets

Parameters

redsol

solution

Definition at line 1285 of file reduce_sol.c.

Referenced by decomposeExactFixSol(), graph_pack(), redbaseGetOffsetPointer(), reduce_bidecomposition(), reduce_bidecompositionExact(), reduce_exec(), reduce_redLoopMw(), reduce_redLoopPc(), and sepafullReduceFromSols().