Detailed Description

several terminal-separator/exact solution reductions for Steiner tree problems

Author: Daniel Rehfeldt

This file implements terminal-separator based reduction techniques for Steiner tree problems. These techniques require to solve subproblems to optimality. See reduce_termsepada.c for related, but heuristic methods (based on dual-ascent).

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

Definition in file reduce_termsepafull.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "graph.h"
#include "solstp.h"
#include "reduce.h"
#include "mincut.h"
#include "portab.h"
#include "substpsolver.h"
#include "extreduce.h"
#include "stpvector.h"
#include "scip/scip.h"

Go to the source code of this file.

Data Structures
struct	terminal_separator_full

struct	bell_parititioner

Macros
#define	SEPARATOR_MAXSIZE 4

#define	SEPARATOR_MAXNCHECKS 75

#define	SEPARATOR_MINTERMRATIO 0.1

#define	SEPARATOR_MINEFFTERMRATIO 0.3

#define	COMPONENT_MAXNODESRATIO_2SEPA 0.5

#define	COMPONENT_MAXNODESRATIO_3SEPA 0.1

#define	COMPONENT_MAXNODESRATIO_4SEPA 0.025

#define	COMPONENT_MAXNODESRATIO_1CANDS 0.8

#define	COMPONENT_MAXNODESRATIO_2CANDS 0.33

#define	COMPONENT_MAXNODESRATIO_3CANDS 0.15

#define	COMPONENT_MAXNODESRATIO_4CANDS 0.08

#define	COMPONENT_MAXNODESRATIO_5PLUSCANDS 0.02

Typedefs
typedef struct terminal_separator_full	TSEPAFULL

typedef struct bell_parititioner	BPARTITIONS

Functions
static int	getPartitionNgroups (int nelems, const int *partition)

static void	getPartitionGroupsSizes (int nelems, int ngroups, const int partition, int groups_sizes)

static void	bpartitionsDebugPrintTop (const BPARTITIONS *bparitions)

static SCIP_RETCODE	bsubpartAdd (SCIP scip, int subsize, int maxgroupid, BPARTITIONS bparts)

static SCIP_RETCODE	bpartitionsCompute (SCIP scip, BPARTITIONS bparts)

static SCIP_RETCODE	bpartitionsInit (SCIP scip, int nelems, BPARTITIONS *bparitions)

static void	bpartitionsFree (SCIP scip, BPARTITIONS *bparitions)

static SCIP_RETCODE	sepafullInitDistdata (SCIP scip, TERMCOMP termcomp, TSEPAFULL *tsepafull)

static SCIP_RETCODE	sepafullInit (SCIP scip, GRAPH subgraph, TSEPAFULL **tsepafull)

static void	sepafullFree (SCIP scip, TSEPAFULL *tsepafull)

static void	sepafullAddSingleSolcandEdges (SCIP scip, int partitionidx, const TERMCOMP termcomp, BPARTITIONS bpartitions, TSEPAFULL tsepafull)

static SCIP_RETCODE	sepafullBuildSolcandsEdges (SCIP scip, TERMCOMP termcomp, TSEPAFULL *tsepafull)

static SCIP_RETCODE	sepafullBuildSolcands (SCIP scip, GRAPH orggraph, TERMCOMP termcomp, TSEPAFULL tsepafull, SCIP_Bool *success)

static SCIP_Bool	sepafullSolcandsArePromising (const TERMCOMP termcomp, const TSEPAFULL tsepafull)

static SCIP_RETCODE	solveSub (SCIP scip, const GRAPH subgraph, int *subedges_sol)

static SCIP_Bool	subSolIsRedundant (SCIP scip, const TERMCOMP termcomp, const int subsol, const int sepapartition, STP_Vectype(int) solcand_sepaedges)

static void	setSubBottleneckEdges (int cand, TERMCOMP termcomp, TSEPAFULL tsepafull)

static SCIP_RETCODE	sepafullAddSolForCand (SCIP scip, int cand, TERMCOMP termcomp, TSEPAFULL *tsepafull)

static SCIP_RETCODE	sepafullReduceFromSols (SCIP scip, GRAPH orggraph, REDBASE redbase, TSEPAFULL tsepafull, TERMCOMP termcomp, int nelims)

static SCIP_RETCODE	sepafullReduce (SCIP scip, GRAPH orggraph, REDBASE redbase, TSEPAFULL tsepafull, TERMCOMP termcomp, int nelims)

static SCIP_Bool	termcompIsPromising (const GRAPH g, const COMPBUILDER builder)

static SCIP_RETCODE	processComponent (SCIP scip, COMPBUILDER builder, GRAPH g, REDBASE redbase, int *nelims)

static SCIP_RETCODE	initHelpers (SCIP scip, const GRAPH g, COMPBUILDER builder, TERMSEPAS termsepas)

static void	freeHelpers (SCIP scip, COMPBUILDER builder, TERMSEPAS *termsepas)

SCIP_RETCODE	reduce_termsepaFull (SCIP scip, GRAPH g, int solnode, REDBASE redbase, int *nelims)

Macro Definition Documentation

◆ SEPARATOR_MAXSIZE

#define SEPARATOR_MAXSIZE 4

Definition at line 45 of file reduce_termsepafull.c.

Referenced by initHelpers(), and termcompIsPromising().

◆ SEPARATOR_MAXNCHECKS

#define SEPARATOR_MAXNCHECKS 75

Definition at line 46 of file reduce_termsepafull.c.

Referenced by initHelpers().

◆ SEPARATOR_MINTERMRATIO

#define SEPARATOR_MINTERMRATIO 0.1

Definition at line 47 of file reduce_termsepafull.c.

Referenced by initHelpers().

◆ SEPARATOR_MINEFFTERMRATIO

#define SEPARATOR_MINEFFTERMRATIO 0.3

Definition at line 48 of file reduce_termsepafull.c.

Referenced by initHelpers().

◆ COMPONENT_MAXNODESRATIO_2SEPA

#define COMPONENT_MAXNODESRATIO_2SEPA 0.5

Definition at line 49 of file reduce_termsepafull.c.

Referenced by termcompIsPromising().

◆ COMPONENT_MAXNODESRATIO_3SEPA

#define COMPONENT_MAXNODESRATIO_3SEPA 0.1

Definition at line 50 of file reduce_termsepafull.c.

Referenced by termcompIsPromising().

◆ COMPONENT_MAXNODESRATIO_4SEPA

#define COMPONENT_MAXNODESRATIO_4SEPA 0.025

Definition at line 51 of file reduce_termsepafull.c.

Referenced by sepafullSolcandsArePromising(), and termcompIsPromising().

◆ COMPONENT_MAXNODESRATIO_1CANDS

#define COMPONENT_MAXNODESRATIO_1CANDS 0.8

Definition at line 53 of file reduce_termsepafull.c.

Referenced by sepafullSolcandsArePromising().

◆ COMPONENT_MAXNODESRATIO_2CANDS

#define COMPONENT_MAXNODESRATIO_2CANDS 0.33

Definition at line 54 of file reduce_termsepafull.c.

Referenced by sepafullSolcandsArePromising().

◆ COMPONENT_MAXNODESRATIO_3CANDS

#define COMPONENT_MAXNODESRATIO_3CANDS 0.15

Definition at line 55 of file reduce_termsepafull.c.

Referenced by sepafullSolcandsArePromising().

◆ COMPONENT_MAXNODESRATIO_4CANDS

#define COMPONENT_MAXNODESRATIO_4CANDS 0.08

Definition at line 56 of file reduce_termsepafull.c.

◆ COMPONENT_MAXNODESRATIO_5PLUSCANDS

#define COMPONENT_MAXNODESRATIO_5PLUSCANDS 0.02

Definition at line 57 of file reduce_termsepafull.c.

Referenced by sepafullSolcandsArePromising().

Typedef Documentation

◆ TSEPAFULL

typedef struct terminal_separator_full TSEPAFULL

full terminal separator reduction data structure

◆ BPARTITIONS

typedef struct bell_parititioner BPARTITIONS

for computing all partitions of a given ground set

Function Documentation

◆ getPartitionNgroups()

static int getPartitionNgroups	(	int	nelems,
		const int *	partition
	)

static

Parameters

nelems	number of elements
partition	group id for each element; 0,1,...

Definition at line 95 of file reduce_termsepafull.c.

References SCIPdebugMessage.

Referenced by getPartitionGroupsSizes(), and subSolIsRedundant().

◆ getPartitionGroupsSizes()

static void getPartitionGroupsSizes	(	int	nelems,
		int	ngroups,
		const int *	partition,
		int *	groups_sizes
	)

static

Parameters

nelems	number of elements
ngroups	number of groups
partition	group id for each element; 0,1,...
groups_sizes	to be filled: size of each group

Definition at line 124 of file reduce_termsepafull.c.

References BMSclearMemoryArray, and getPartitionNgroups().

Referenced by subSolIsRedundant().

◆ bpartitionsDebugPrintTop()

static void bpartitionsDebugPrintTop ( const BPARTITIONS * bparitions )

static

prints top partition if SCIP_DEBUG is defined

Parameters

bparitions to print for

Definition at line 149 of file reduce_termsepafull.c.

References SCIPdebugMessage, and StpVecGetSize.

Referenced by bpartitionsCompute(), and bsubpartAdd().

◆ bsubpartAdd()

static SCIP_RETCODE bsubpartAdd	(	SCIP *	scip,
		int	subsize,
		int	maxgroupid,
		BPARTITIONS *	bparts
	)

static

recursive add NOTE: not extremely efficient, only meant for small sizes

Parameters

scip	SCIP data structure
subsize	size of subgroup
maxgroupid	maximum id for partition subset, also marks subset which will be further parititioned
bparts	bell partitions

Definition at line 171 of file reduce_termsepafull.c.

References BMScopyMemoryArray, bpartitionsDebugPrintTop(), SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, StpVecGetSize, and StpVecPushBack.

Referenced by bpartitionsCompute().

◆ bpartitionsCompute()

static SCIP_RETCODE bpartitionsCompute	(	SCIP *	scip,
		BPARTITIONS *	bparts
	)

static

computes partitions

Parameters

scip	SCIP data structure
bparts	bell partitions

Definition at line 249 of file reduce_termsepafull.c.

References bpartitionsDebugPrintTop(), bsubpartAdd(), SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, StpVecGetSize, and StpVecPushBack.

Referenced by sepafullBuildSolcandsEdges().

◆ bpartitionsInit()

static SCIP_RETCODE bpartitionsInit	(	SCIP *	scip,
		int	nelems,
		BPARTITIONS **	bparitions
	)

static

initializes

Parameters

scip	SCIP data structure
nelems	number of elements of ground set
bparitions	to initialize

Definition at line 296 of file reduce_termsepafull.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by sepafullBuildSolcandsEdges().

◆ bpartitionsFree()

static void bpartitionsFree	(	SCIP *	scip,
		BPARTITIONS **	bparitions
	)

static

frees

Parameters

scip	SCIP data structure
bparitions	to initialize

Definition at line 320 of file reduce_termsepafull.c.

References SCIPfreeMemory, SCIPfreeMemoryArrayNull, StpVecFree, and StpVecGetSize.

Referenced by sepafullBuildSolcandsEdges().

◆ sepafullInitDistdata()

static SCIP_RETCODE sepafullInitDistdata	(	SCIP *	scip,
		TERMCOMP *	termcomp,
		TSEPAFULL *	tsepafull
	)

static

sets up distance data for subgraph

Parameters

scip	SCIP data structure
termcomp	component
tsepafull	to initialize for

Definition at line 343 of file reduce_termsepafull.c.

References extreduce_distDataInit(), FALSE, graph_free_dcsr(), graph_init_dcsr(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, terminal_separator_component::subgraph, and TRUE.

Referenced by sepafullBuildSolcands().

◆ sepafullInit()

static SCIP_RETCODE sepafullInit	(	SCIP *	scip,
		GRAPH *	subgraph,
		TSEPAFULL **	tsepafull
	)

static

initializes

Parameters

scip	SCIP data structure
subgraph	component graph
tsepafull	to initialize

Definition at line 368 of file reduce_termsepafull.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by processComponent().

◆ sepafullFree()

static void sepafullFree	(	SCIP *	scip,
		TSEPAFULL **	tsepafull
	)

static

frees

Parameters

scip	SCIP data structure
tsepafull	to initialize

Definition at line 396 of file reduce_termsepafull.c.

References extreduce_distDataFree(), SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, StpVecFree, and StpVecGetSize.

Referenced by processComponent().

◆ sepafullAddSingleSolcandEdges()

static void sepafullAddSingleSolcandEdges	(	SCIP *	scip,
		int	partitionidx,
		const TERMCOMP *	termcomp,
		BPARTITIONS *	bpartitions,
		TSEPAFULL *	tsepafull
	)

static

add solution candidate edges from given partition

Parameters

scip	SCIP data structure
partitionidx	partition index for bpartitions
termcomp	component
bpartitions	partitions of separation terminals
tsepafull	full separator

Definition at line 436 of file reduce_termsepafull.c.

References BLOCKED, terminal_separator_component::builder, EAT_LAST, extreduce_distDataGetSdDouble(), FALSE, GRAPH::head, LE, terminal_separator_component::nodemap_subToOrg, terminial_component_initializer::nsepatterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, SCIPdebugMessage, SCIPisGE(), StpVecFree, StpVecGetSize, StpVecPopBack, StpVecPushBack, terminal_separator_component::subgraph, and TRUE.

Referenced by sepafullBuildSolcandsEdges().

◆ sepafullBuildSolcandsEdges()

static SCIP_RETCODE sepafullBuildSolcandsEdges	(	SCIP *	scip,
		TERMCOMP *	termcomp,
		TSEPAFULL *	tsepafull
	)

static

computes artificial edges for each solution candidate (and tries to rule-out some candidates already)

Parameters

scip	SCIP data structure
termcomp	component
tsepafull	full separator

Definition at line 516 of file reduce_termsepafull.c.

References bpartitionsCompute(), bpartitionsFree(), bpartitionsInit(), terminal_separator_component::builder, terminal_separator_component::nodemap_subToOrg, terminial_component_initializer::nsepatterms, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and sepafullAddSingleSolcandEdges().

Referenced by sepafullBuildSolcands().

◆ sepafullBuildSolcands()

static SCIP_RETCODE sepafullBuildSolcands	(	SCIP *	scip,
		GRAPH *	orggraph,
		TERMCOMP *	termcomp,
		TSEPAFULL *	tsepafull,
		SCIP_Bool *	success
	)

static

builds solution candidates (and tries to rule-out some already)

Parameters

scip	SCIP data structure
orggraph	graph data structure
termcomp	component
tsepafull	sepa
success	built?

Definition at line 551 of file reduce_termsepafull.c.

References BMScopyMemoryArray, GRAPH::cost, graph_get_nEdges(), reduce_termcompChangeSubgraphToBottleneck(), reduce_termcompChangeSubgraphToOrgCosts(), SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPdebugMessage, sepafullBuildSolcandsEdges(), sepafullInitDistdata(), and terminal_separator_component::subgraph.

Referenced by processComponent().

◆ sepafullSolcandsArePromising()

static SCIP_Bool sepafullSolcandsArePromising	(	const TERMCOMP *	termcomp,
		const TSEPAFULL *	tsepafull
	)

static

promising to do reductions?

Parameters

termcomp	component
tsepafull	sepa

Definition at line 594 of file reduce_termsepafull.c.

References terminal_separator_component::builder, COMPONENT_MAXNODESRATIO_1CANDS, COMPONENT_MAXNODESRATIO_2CANDS, COMPONENT_MAXNODESRATIO_3CANDS, COMPONENT_MAXNODESRATIO_4SEPA, COMPONENT_MAXNODESRATIO_5PLUSCANDS, FALSE, GT, terminial_component_initializer::nsepatterms, reduce_compbuilderGetSubNodesRatio(), SCIP_Real, SCIPdebugMessage, and TRUE.

Referenced by processComponent().

◆ solveSub()

static SCIP_RETCODE solveSub	(	SCIP *	scip,
		const GRAPH *	subgraph,
		int *	subedges_sol
	)

static

solves subproblem

Parameters

scip	SCIP data structure
subgraph	graph
subedges_sol	to store solution

Definition at line 645 of file reduce_termsepafull.c.

References graph_copy(), graph_printInfo(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, substpsolver_free(), substpsolver_getSolution(), substpsolver_initBC(), substpsolver_initHistory(), substpsolver_setMute(), substpsolver_setProbFullPresolve(), and substpsolver_solve().

Referenced by sepafullAddSolForCand().

◆ subSolIsRedundant()

static SCIP_Bool subSolIsRedundant	(	SCIP *	scip,
		const TERMCOMP *	termcomp,
		const int *	subsol,
		const int *	sepapartition,
		STP_Vectype(int)	solcand_sepaedges
	)

static

returns TRUE if sub-solution can be ruled out

Parameters

scip	SCIP data structure
termcomp	component
subsol	solution
sepapartition	partition
solcand_sepaedges	bottleneck edges

Definition at line 686 of file reduce_termsepafull.c.

References terminal_separator_component::builder, CONNECT, FALSE, flipedge, getPartitionGroupsSizes(), getPartitionNgroups(), graph_edge_isInRange(), GRAPH::head, terminial_component_initializer::nsepatterms, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, StpVecGetSize, terminal_separator_component::subgraph, GRAPH::tail, and TRUE.

Referenced by sepafullAddSolForCand().

◆ setSubBottleneckEdges()

static void setSubBottleneckEdges	(	int	cand,
		TERMCOMP *	termcomp,
		TSEPAFULL *	tsepafull
	)

static

sets weight for artificial bottleneck edges between separator terminals

Parameters

cand	candidate number
termcomp	component
tsepafull	full separation data

Definition at line 755 of file reduce_termsepafull.c.

References GRAPH::cost, flipedge, graph_edge_isInRange(), graph_edge_printInfo(), SCIP_Real, SCIPdebugMessage, STP_Vectype, StpVecGetSize, and terminal_separator_component::subgraph.

Referenced by sepafullAddSolForCand().

◆ sepafullAddSolForCand()

static SCIP_RETCODE sepafullAddSolForCand	(	SCIP *	scip,
		int	cand,
		TERMCOMP *	termcomp,
		TSEPAFULL *	tsepafull
	)

static

adds solution for candidate, or rules the solution out

Parameters

scip	SCIP data structure
cand	candidate number
termcomp	component
tsepafull	full separation data

Definition at line 785 of file reduce_termsepafull.c.

References BMScopyMemoryArray, GRAPH::cost, GRAPH::edges, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, setSubBottleneckEdges(), solstp_isValid(), solveSub(), STP_Vectype, StpVecGetSize, StpVecPushBack, terminal_separator_component::subgraph, subsol, and subSolIsRedundant().

Referenced by sepafullReduce().

◆ sepafullReduceFromSols()

static SCIP_RETCODE sepafullReduceFromSols	(	SCIP *	scip,
		GRAPH *	orggraph,
		REDBASE *	redbase,
		TSEPAFULL *	tsepafull,
		TERMCOMP *	termcomp,
		int *	nelims
	)

static

performs reductions based on solutions to feasible subproblem

Parameters

scip	SCIP data structure
orggraph	graph data structure
redbase	reduction base
tsepafull	full separation data
termcomp	component
nelims	number of eliminations

Definition at line 826 of file reduce_termsepafull.c.

References terminal_separator_component::builder, CONNECT, GRAPH::cost, terminal_separator_component::edgemap_subToOrg, EQ, flipedge, graph_edge_del(), graph_edge_isInRange(), graph_edge_printInfo(), graph_get_nEdges(), graph_knot_chg(), GRAPH::head, LT, terminal_separator_component::nodemap_subToOrg, terminial_component_initializer::nsepatterms, reduction_base::redsol, reduce_solGetOffsetPointer(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocClearMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, solstp_isValid(), STP_TERM, STP_Vectype, StpVecGetSize, terminal_separator_component::subgraph, GRAPH::tail, TRUE, and UNKNOWN.

Referenced by sepafullReduce().

◆ sepafullReduce()

static SCIP_RETCODE sepafullReduce	(	SCIP *	scip,
		GRAPH *	orggraph,
		REDBASE *	redbase,
		TSEPAFULL *	tsepafull,
		TERMCOMP *	termcomp,
		int *	nelims
	)

static

performs reductions

Parameters

scip	SCIP data structure
orggraph	graph data structure
redbase	reduction base
tsepafull	full separation data
termcomp	component
nelims	number of eliminations

Definition at line 933 of file reduce_termsepafull.c.

References SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, sepafullAddSolForCand(), and sepafullReduceFromSols().

Referenced by processComponent().

◆ termcompIsPromising()

static SCIP_Bool termcompIsPromising	(	const GRAPH *	g,
		const COMPBUILDER *	builder
	)

static

promising to perform reductions on given component?

Parameters

g	graph data structure
builder	terminal separator component initializer

Definition at line 961 of file reduce_termsepafull.c.

References COMPONENT_MAXNODESRATIO_2SEPA, COMPONENT_MAXNODESRATIO_3SEPA, COMPONENT_MAXNODESRATIO_4SEPA, FALSE, GT, terminial_component_initializer::nsepatterms, reduce_compbuilderGetSubNodesRatio(), SCIP_Real, SCIPdebugMessage, SEPARATOR_MAXSIZE, and TRUE.

Referenced by reduce_termsepaFull().

◆ processComponent()

static SCIP_RETCODE processComponent	(	SCIP *	scip,
		COMPBUILDER *	builder,
		GRAPH *	g,
		REDBASE *	redbase,
		int *	nelims
	)

static

processes subgraph associated with builder

Parameters

scip	SCIP data structure
builder	terminal separator component initializer
g	graph data structure
redbase	reduction base
nelims	number of eliminations

Definition at line 1002 of file reduce_termsepafull.c.

References terminial_component_initializer::ncomponentnodes, reduce_compbuilderPrintSeparators(), reduce_termcompBuildSubgraph(), reduce_termcompFree(), reduce_termcompInit(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, sepafullBuildSolcands(), sepafullFree(), sepafullInit(), sepafullReduce(), sepafullSolcandsArePromising(), and terminal_separator_component::subgraph.

Referenced by reduce_termsepaFull().

◆ initHelpers()

static SCIP_RETCODE initHelpers	(	SCIP *	scip,
		const GRAPH *	g,
		COMPBUILDER **	builder,
		TERMSEPAS **	termsepas
	)

static

initializes helpers

Parameters

scip	SCIP data structure
g	graph data structure
builder	to initialize
termsepas	to initialize

Definition at line 1042 of file reduce_termsepafull.c.

References graph_get_nVET(), graph_printInfoReduced(), mincut_termsepasInit(), NULL, reduce_compbuilderInit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SEPARATOR_MAXNCHECKS, SEPARATOR_MAXSIZE, SEPARATOR_MINEFFTERMRATIO, SEPARATOR_MINTERMRATIO, and GRAPH::terms.

Referenced by reduce_termsepaFull().

◆ freeHelpers()

static void freeHelpers	(	SCIP *	scip,
		COMPBUILDER **	builder,
		TERMSEPAS **	termsepas
	)

static

frees helper

Parameters

scip	SCIP data structure
builder	to initialize
termsepas	to initialize

Definition at line 1089 of file reduce_termsepafull.c.

References mincut_termsepasFree(), and reduce_compbuilderFree().

Referenced by reduce_termsepaFull().

◆ reduce_termsepaFull()

SCIP_RETCODE reduce_termsepaFull	(	SCIP *	scip,
		GRAPH *	g,
		int *	solnode,
		REDBASE *	redbase,
		int *	nelims
	)

terminal-separator reduction method using optimal (full) solution of sub-problems

Parameters

scip	SCIP data structure
g	graph data structure
solnode	solution nodes mark or NULL
redbase	reduction base
nelims	number of eliminations

Definition at line 1107 of file reduce_termsepafull.c.

References terminial_component_initializer::componentnumber, freeHelpers(), initHelpers(), mincut_findTerminalSeparators(), mincut_termsepasGetNall(), processComponent(), reduce_bidecompositionExact(), reduce_contract0Edges(), reduce_termsepaGetNextComp(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), termcompIsPromising(), GRAPH::terms, and TRUE.

Referenced by reduce_redLoopStp().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ SEPARATOR_MAXSIZE

◆ SEPARATOR_MAXNCHECKS

◆ SEPARATOR_MINTERMRATIO

◆ SEPARATOR_MINEFFTERMRATIO

◆ COMPONENT_MAXNODESRATIO_2SEPA

◆ COMPONENT_MAXNODESRATIO_3SEPA

◆ COMPONENT_MAXNODESRATIO_4SEPA

◆ COMPONENT_MAXNODESRATIO_1CANDS

◆ COMPONENT_MAXNODESRATIO_2CANDS

◆ COMPONENT_MAXNODESRATIO_3CANDS

◆ COMPONENT_MAXNODESRATIO_4CANDS

◆ COMPONENT_MAXNODESRATIO_5PLUSCANDS

Typedef Documentation

◆ TSEPAFULL

◆ BPARTITIONS

Function Documentation

◆ getPartitionNgroups()

◆ getPartitionGroupsSizes()

◆ bpartitionsDebugPrintTop()

◆ bsubpartAdd()

◆ bpartitionsCompute()

◆ bpartitionsInit()

◆ bpartitionsFree()

◆ sepafullInitDistdata()

◆ sepafullInit()

◆ sepafullFree()

◆ sepafullAddSingleSolcandEdges()

◆ sepafullBuildSolcandsEdges()

◆ sepafullBuildSolcands()

◆ sepafullSolcandsArePromising()

◆ solveSub()

◆ subSolIsRedundant()

◆ setSubBottleneckEdges()

◆ sepafullAddSolForCand()

◆ sepafullReduceFromSols()

◆ sepafullReduce()

◆ termcompIsPromising()

◆ processComponent()

◆ initHelpers()

◆ freeHelpers()

◆ reduce_termsepaFull()