Scippy

SCIP

Solving Constraint Integer Programs

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.h.

#include "scip/scip.h"
#include "graph.h"

Go to the source code of this file.

Typedefs
typedef struct pseudoancestor_cliques	PACLIQUES

typedef struct prize_collecting_implications	PCIMPLICATION

typedef struct vertex_terminal_implications	VTIMPLICATION

Functions
SCIP_RETCODE	sepaspecial_pacliquesInit (SCIP , const GRAPH , PACLIQUES **)

void	sepaspecial_pacliquesFree (SCIP , PACLIQUES *)

SCIP_RETCODE	sepaspecial_pacliquesSeparate (SCIP , SCIP_CONSHDLR , PACLIQUES , int, int )

int	sepaspecial_pcimplicationsGetNstarts (const PCIMPLICATION *)

const int *	sepaspecial_pcimplicationsGetStarts (const PCIMPLICATION *)

const int *	sepaspecial_pcimplicationsGetVerts (const PCIMPLICATION *)

SCIP_RETCODE	sepaspecial_pcimplicationsInit (SCIP , const GRAPH , PCIMPLICATION **)

void	sepaspecial_pcimplicationsFree (SCIP , PCIMPLICATION *)

SCIP_RETCODE	sepaspecial_pcimplicationsSeparate (SCIP , SCIP_CONSHDLR , PCIMPLICATION , int, int )

SCIP_RETCODE	sepaspecial_vtimplicationsInit (SCIP , const GRAPH , VTIMPLICATION **)

void	sepaspecial_vtimplicationsFree (SCIP , VTIMPLICATION *)

SCIP_RETCODE	sepaspecial_vtimplicationsSeparate (SCIP , SCIP_CONSHDLR , VTIMPLICATION , int, int )

Typedef Documentation

◆ PACLIQUES

typedef struct pseudoancestor_cliques PACLIQUES

cuts for pseudo ancestor cliques

Definition at line 42 of file sepaspecial.h.

◆ PCIMPLICATION

typedef struct prize_collecting_implications PCIMPLICATION

cuts for implications between potential terminals

Definition at line 45 of file sepaspecial.h.

◆ VTIMPLICATION

typedef struct vertex_terminal_implications VTIMPLICATION

cuts for implications between non-terminals and terminals

Definition at line 48 of file sepaspecial.h.

Function Documentation

◆ 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_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_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_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().