Detailed Description

Separator for Steiner tree problem contraints beyond flow-balance-directed-cut constraints.

Author: Daniel Rehfeldt

This file includes some special separator routines beyond the flow-balance directed cut formulation constraints.

Definition in file sepaspecial.c.

#include <assert.h>
#include <string.h>
#include "sepaspecial.h"
#include "probdata_stp.h"
#include "portab.h"
#include "stpvector.h"
#include "prop_stp.h"
#include "scip/cons_linear.h"

Go to the source code of this file.

Data Structures
struct	pseudoancestor_cliques

struct	prize_collecting_implications

struct	vertex_terminal_implications

Macros
#define	PCIMPLICATIONS_ALLOC_FACTOR 4

Functions
static SCIP_Real	get_inflow (const GRAPH g, const SCIP_Real xval, int vert)

static SCIP_RETCODE	pacliquesBuildMap (SCIP scip, const GRAPH g, PACLIQUES *pacliques)

SCIP_RETCODE	sepaspecial_pacliquesInit (SCIP scip, const GRAPH g, PACLIQUES **pacliques)

void	sepaspecial_pacliquesFree (SCIP scip, PACLIQUES *pacliques)

SCIP_RETCODE	sepaspecial_pacliquesSeparate (SCIP scip, SCIP_CONSHDLR conshdlr, PACLIQUES pacliques, int maxcuts, int ncuts)

SCIP_RETCODE	sepaspecial_pcimplicationsInit (SCIP scip, const GRAPH g, PCIMPLICATION **pcimplications)

void	sepaspecial_pcimplicationsFree (SCIP scip, PCIMPLICATION *pcimplications)

SCIP_RETCODE	sepaspecial_pcimplicationsSeparate (SCIP scip, SCIP_CONSHDLR conshdlr, PCIMPLICATION pcimplications, int maxcuts, int ncuts)

int	sepaspecial_pcimplicationsGetNstarts (const PCIMPLICATION *pcimp)

const int *	sepaspecial_pcimplicationsGetStarts (const PCIMPLICATION *pcimp)

const int *	sepaspecial_pcimplicationsGetVerts (const PCIMPLICATION *pcimp)

SCIP_RETCODE	sepaspecial_vtimplicationsInit (SCIP scip, const GRAPH g, VTIMPLICATION **vtimplications)

void	sepaspecial_vtimplicationsFree (SCIP scip, VTIMPLICATION *vtimplications)

SCIP_RETCODE	sepaspecial_vtimplicationsSeparate (SCIP scip, SCIP_CONSHDLR conshdlr, VTIMPLICATION vtimplications, int maxcuts, int ncuts)

Macro Definition Documentation

◆ PCIMPLICATIONS_ALLOC_FACTOR

#define PCIMPLICATIONS_ALLOC_FACTOR 4

Definition at line 38 of file sepaspecial.c.

Referenced by sepaspecial_pcimplicationsInit().

Function Documentation

◆ get_inflow()

static SCIP_Real get_inflow	(	const GRAPH *	g,
		const SCIP_Real *	xval,
		int	vert
	)

inlinestatic

returns incoming flow for given node

Parameters

g	graph data structure
xval	edge values
vert	the vertex

Definition at line 76 of file sepaspecial.c.

References GRAPH::ieat, and GRAPH::inpbeg.

Referenced by sepaspecial_pcimplicationsSeparate(), and sepaspecial_vtimplicationsSeparate().

◆ pacliquesBuildMap()

static SCIP_RETCODE pacliquesBuildMap	(	SCIP *	scip,
		const GRAPH *	g,
		PACLIQUES *	pacliques
	)

static

initializes pseudo-ancestor CSR like map from edges to ancestors

Parameters

scip	SCIP data structure
g	graph data structure
pacliques	clique data

Definition at line 94 of file sepaspecial.c.

References pseudoancestor_cliques::ancestors_lpweights, BMScopyMemoryArray, graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_get_nEdges(), pseudoancestor_cliques::halfedges_ancestors, pseudoancestor_cliques::halfedges_starts, pseudoancestor_cliques::halfnedges, pseudoancestor_cliques::nancestors, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by sepaspecial_pacliquesInit().

◆ sepaspecial_pacliquesInit()

SCIP_RETCODE sepaspecial_pacliquesInit	(	SCIP *	scip,
		const GRAPH *	g,
		PACLIQUES **	pacliques
	)

initializes pseudo-ancestor cliques

Parameters

scip	SCIP data structure
g	graph data structure
pacliques	clique data

Definition at line 165 of file sepaspecial.c.

References pseudoancestor_cliques::ancestors_lpweights, graph_get_nEdges(), graph_getNpseudoAncestors(), pseudoancestor_cliques::halfedges_ancestors, pseudoancestor_cliques::halfedges_starts, pseudoancestor_cliques::halfnedges, pseudoancestor_cliques::nancestors, pseudoancestor_cliques::nfails, NULL, pacliquesBuildMap(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and SCIPallocMemoryArray.

Referenced by SCIP_DECL_CONSSEPALP().

◆ sepaspecial_pacliquesFree()

void sepaspecial_pacliquesFree	(	SCIP *	scip,
		PACLIQUES **	pacliques
	)

frees

Parameters

scip	SCIP data structure
pacliques	clique data

Definition at line 207 of file sepaspecial.c.

References SCIPfreeMemoryArray, and SCIPfreeMemoryArrayNull.

Referenced by SCIP_DECL_CONSEXITSOL().

◆ sepaspecial_pacliquesSeparate()

SCIP_RETCODE sepaspecial_pacliquesSeparate	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		PACLIQUES *	pacliques,
		int	maxcuts,
		int *	ncuts
	)

separates

Parameters

scip	SCIP data structure
conshdlr	constraint handler
pacliques	clique data
maxcuts	maximal number of cuts
ncuts	pointer to store number of cuts

Definition at line 222 of file sepaspecial.c.

References pseudoancestor_cliques::ancestors_lpweights, FALSE, graph_get_nEdges(), GT, pseudoancestor_cliques::halfedges_ancestors, pseudoancestor_cliques::halfedges_starts, pseudoancestor_cliques::nancestors, pseudoancestor_cliques::nfails, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisCutEfficacious(), SCIPisFeasGT(), SCIPprobdataGetGraph2(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPreleaseRow(), and TRUE.

Referenced by SCIP_DECL_CONSSEPALP().

◆ sepaspecial_pcimplicationsInit()

SCIP_RETCODE sepaspecial_pcimplicationsInit	(	SCIP *	scip,
		const GRAPH *	g,
		PCIMPLICATION **	pcimplications
	)

initializes (R)PC implications

Parameters

scip	SCIP data structure
g	graph data structure
pcimplications	implication data

Definition at line 371 of file sepaspecial.c.

References GRAPH::cost, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_nProperPotentialTerms(), graph_pc_termIsNonLeafTerm(), graph_pc_termMarkProper(), graph_sdWalksConnected(), Is_term, nnodes, NULL, GRAPH::path_heap, GRAPH::path_state, PCIMPLICATIONS_ALLOC_FACTOR, prize_collecting_implications::pcimplnppterms, prize_collecting_implications::pcimplstart, prize_collecting_implications::pcimplverts, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemory, SCIPallocMemoryArray, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIP_DECL_CONSSEPALP().

◆ sepaspecial_pcimplicationsFree()

void sepaspecial_pcimplicationsFree	(	SCIP *	scip,
		PCIMPLICATION **	pcimplications
	)

frees (R)PC implications

Parameters

scip	SCIP data structure
pcimplications	implication data

Definition at line 485 of file sepaspecial.c.

References SCIPfreeMemoryArray, and SCIPfreeMemoryArrayNull.

Referenced by SCIP_DECL_CONSEXITSOL().

◆ sepaspecial_pcimplicationsSeparate()

SCIP_RETCODE sepaspecial_pcimplicationsSeparate	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		PCIMPLICATION *	pcimplications,
		int	maxcuts,
		int *	ncuts
	)

separates PCSPG/MWCS implications

Parameters

scip	SCIP data structure
conshdlr	constraint handler
pcimplications	implications
maxcuts	maximal number of cuts
ncuts	pointer to store number of cuts

Definition at line 498 of file sepaspecial.c.

References EAT_LAST, GRAPH::extended, FALSE, get_inflow(), graph_pc_getRoot2PtermEdge(), graph_pc_getTwinTerm(), graph_pc_nNonFixedTerms(), graph_pc_nProperPotentialTerms(), GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, GRAPH::knots, maxflow(), nnodes, NULL, prize_collecting_implications::pcimplnppterms, prize_collecting_implications::pcimplstart, prize_collecting_implications::pcimplverts, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPdebugMessage, SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisCutEfficacious(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPprobdataGetGraph2(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPreleaseRow(), GRAPH::term, and TRUE.

Referenced by SCIP_DECL_CONSSEPALP().

◆ sepaspecial_pcimplicationsGetNstarts()

int sepaspecial_pcimplicationsGetNstarts ( const PCIMPLICATION * pcimp )

return number of proper potential terminals

Parameters

pcimp implications

Definition at line 636 of file sepaspecial.c.

References prize_collecting_implications::pcimplnppterms.

Referenced by SCIPStpGetPcImplNstarts().

◆ sepaspecial_pcimplicationsGetStarts()

const int* sepaspecial_pcimplicationsGetStarts ( const PCIMPLICATION * pcimp )

return CSR like starts

Parameters

pcimp implications

Definition at line 647 of file sepaspecial.c.

References prize_collecting_implications::pcimplstart.

Referenced by SCIPStpGetPcImplStarts().

◆ sepaspecial_pcimplicationsGetVerts()

const int* sepaspecial_pcimplicationsGetVerts ( const PCIMPLICATION * pcimp )

return CSR like vertices

Parameters

pcimp implications

Definition at line 658 of file sepaspecial.c.

References prize_collecting_implications::pcimplverts.

Referenced by SCIPStpGetPcImplVerts().

◆ sepaspecial_vtimplicationsInit()

SCIP_RETCODE sepaspecial_vtimplicationsInit	(	SCIP *	scip,
		const GRAPH *	g,
		VTIMPLICATION **	vtimplications
	)

initializes implications

Parameters

scip	SCIP data structure
g	graph data structure
vtimplications	implication data

Definition at line 669 of file sepaspecial.c.

References BLOCKED, GRAPH::cost, EAT_LAST, FARAWAY, flipedge, GE, graph_get_nNodes(), graph_typeIsSpgLike(), GRAPH::head, Is_term, LT, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemory, StpVecPushBack, and GRAPH::term.

Referenced by SCIP_DECL_CONSSEPALP().

◆ sepaspecial_vtimplicationsFree()

void sepaspecial_vtimplicationsFree	(	SCIP *	scip,
		VTIMPLICATION **	vtimplications
	)

frees implications

Parameters

scip	SCIP data structure
vtimplications	implication data

Definition at line 730 of file sepaspecial.c.

References SCIPfreeMemoryArray, and StpVecFree.

Referenced by SCIP_DECL_CONSEXITSOL().

◆ sepaspecial_vtimplicationsSeparate()

SCIP_RETCODE sepaspecial_vtimplicationsSeparate	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		VTIMPLICATION *	vtimplications,
		int	maxcuts,
		int *	ncuts
	)

separates implications

Parameters

scip	SCIP data structure
conshdlr	constraint handler
vtimplications	implication data
maxcuts	maximal number of cuts
ncuts	pointer to store number of cuts

Definition at line 743 of file sepaspecial.c.

References EAT_LAST, FALSE, flipedge, get_inflow(), graph_edge_isInRange(), GRAPH::ieat, GRAPH::inpbeg, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPdebugMessage, SCIPflushRowExtensions(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisFeasLT(), SCIPprobdataGetGraph2(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPreleaseRow(), StpVecGetSize, GRAPH::tail, and TRUE.

Referenced by SCIP_DECL_CONSSEPALP().

SCIP

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ PCIMPLICATIONS_ALLOC_FACTOR

Function Documentation

◆ get_inflow()

◆ pacliquesBuildMap()

◆ sepaspecial_pacliquesInit()

◆ sepaspecial_pacliquesFree()

◆ sepaspecial_pacliquesSeparate()

◆ sepaspecial_pcimplicationsInit()

◆ sepaspecial_pcimplicationsFree()

◆ sepaspecial_pcimplicationsSeparate()

◆ sepaspecial_pcimplicationsGetNstarts()

◆ sepaspecial_pcimplicationsGetStarts()

◆ sepaspecial_pcimplicationsGetVerts()

◆ sepaspecial_vtimplicationsInit()

◆ sepaspecial_vtimplicationsFree()

◆ sepaspecial_vtimplicationsSeparate()