Scippy

SCIP

Solving Constraint Integer Programs

cons_stpcomponents.c File Reference

Detailed Description

Component constraint handler for Steiner problems.

Author
Daniel Rehfeldt

This file checks for biconnected components and solves them separately.

Definition in file cons_stpcomponents.c.

#include <assert.h>
#include <string.h>
#include "cons_stpcomponents.h"
#include "scip/scip.h"
#include "bidecomposition.h"
#include "prop_stp.h"
#include "substpsolver.h"
#include "graph.h"
#include "solstp.h"

Go to the source code of this file.

Data Structures

struct  sub_solution
 

Macros

#define consEnfolpStpcomponents   NULL
 
#define consEnfopsStpcomponents   NULL
 
#define consCheckStpcomponents   NULL
 
Constraint handler properties
#define CONSHDLR_NAME   "stpcomponents"
 
#define CONSHDLR_DESC   "steiner tree components constraint handler"
 
#define CONSHDLR_SEPAPRIORITY   -1
 
#define CONSHDLR_ENFOPRIORITY   -1
 
#define CONSHDLR_CHECKPRIORITY   -1
 
#define CONSHDLR_SEPAFREQ   -1
 
#define CONSHDLR_PROPFREQ   0
 
#define CONSHDLR_EAGERFREQ   -1
 
#define CONSHDLR_DELAYSEPA   FALSE
 
#define CONSHDLR_DELAYPROP   FALSE
 
#define CONSHDLR_NEEDSCONS   FALSE
 
#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
#define DECOMP_MAXCOMPRATIO   0.95
 
#define DECOMP_MINNNODES   10
 

Typedefs

typedef struct sub_solution SUBSOL
 

Functions

static SCIP_RETCODE subsolGet (SUBSTP *substp, SUBSOL *subcomp)
 
static SCIP_RETCODE subsolFixOrgEdges (SCIP *scip, const SUBINOUT *subinout, SUBSOL *subsol)
 
static SCIP_RETCODE subsolInit (SCIP *scip, const SUBSTP *substp, SUBSOL **subsolution)
 
static void subsolFree (SCIP *subscip, SUBSOL **subsolution)
 
static SCIP_RETCODE subcompFixOrgEdges (SCIP *scip, const SUBINOUT *subinout, SUBSTP *substp)
 
static SCIP_Bool decomposeIsPromising (const GRAPH *g, const BIDECOMP *bidecomp)
 
static SCIP_RETCODE decomposeGetSubgraph (SCIP *scip, const BIDECOMP *bidecomp, int compindex, GRAPH *orggraph, GRAPH **subgraph)
 
static SCIP_RETCODE decomposeSolveSub (SCIP *scip, const BIDECOMP *bidecomp, int compindex, GRAPH *orggraph, SCIP_Bool *success)
 
static SCIP_RETCODE decomposeExec (SCIP *scip, BIDECOMP *bidecomp, CUTNODES *cutnodes, GRAPH *orggraph, SCIP_Bool *success)
 
static SCIP_RETCODE initDecompose (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, GRAPH *orggraph, SCIP_Bool *isPromsing)
 
static void freeDecompose (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
 
static SCIP_RETCODE divideAndConquer (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_Bool *success)
 
static SCIP_DECL_CONSHDLRCOPY (conshdlrCopyStpcomponents)
 
static SCIP_DECL_CONSFREE (consFreeStpcomponents)
 
static SCIP_DECL_CONSINITSOL (consInitsolStpcomponents)
 
static SCIP_DECL_CONSEXITSOL (consExitsolStpcomponents)
 
static SCIP_DECL_CONSDELETE (consDeleteStpcomponents)
 
static SCIP_DECL_CONSTRANS (consTransStpcomponents)
 
static SCIP_DECL_CONSINITLP (consInitlpStpcomponents)
 
static SCIP_DECL_CONSPROP (consPropStpcomponents)
 
static SCIP_DECL_CONSLOCK (consLockStpcomponents)
 
SCIP_RETCODE SCIPStpcomponentsSetUp (SCIP *scip, GRAPH *graph)
 
SCIP_Bool SCIPStpcomponentsAllowsDecomposition (SCIP *scip)
 
SCIP_RETCODE SCIPincludeConshdlrStpcomponents (SCIP *scip)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

#define CONSHDLR_NAME   "stpcomponents"

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "steiner tree components constraint handler"

Definition at line 45 of file cons_stpcomponents.c.

Referenced by SCIPincludeConshdlrStpcomponents().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   -1

priority of the constraint handler for separation

Definition at line 46 of file cons_stpcomponents.c.

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   -1

priority of the constraint handler for constraint enforcing

Definition at line 47 of file cons_stpcomponents.c.

Referenced by SCIPincludeConshdlrStpcomponents().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -1

priority of the constraint handler for checking feasibility

Definition at line 48 of file cons_stpcomponents.c.

Referenced by SCIPincludeConshdlrStpcomponents().

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ   -1

frequency for separating cuts; zero means to separate only in the root node

Definition at line 49 of file cons_stpcomponents.c.

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   0

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 50 of file cons_stpcomponents.c.

Referenced by SCIPincludeConshdlrStpcomponents().

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ   -1

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 51 of file cons_stpcomponents.c.

Referenced by SCIPincludeConshdlrStpcomponents().

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 54 of file cons_stpcomponents.c.

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 55 of file cons_stpcomponents.c.

Referenced by SCIPincludeConshdlrStpcomponents().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   FALSE

should the constraint handler be skipped, if no constraints are available?

Definition at line 56 of file cons_stpcomponents.c.

Referenced by SCIPincludeConshdlrStpcomponents().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 59 of file cons_stpcomponents.c.

Referenced by SCIPincludeConshdlrStpcomponents().

◆ DECOMP_MAXCOMPRATIO

#define DECOMP_MAXCOMPRATIO   0.95

Definition at line 60 of file cons_stpcomponents.c.

Referenced by decomposeIsPromising().

◆ DECOMP_MINNNODES

#define DECOMP_MINNNODES   10

Definition at line 61 of file cons_stpcomponents.c.

Referenced by decomposeIsPromising().

◆ consEnfolpStpcomponents

#define consEnfolpStpcomponents   NULL

Definition at line 650 of file cons_stpcomponents.c.

Referenced by SCIPincludeConshdlrStpcomponents().

◆ consEnfopsStpcomponents

#define consEnfopsStpcomponents   NULL

Definition at line 651 of file cons_stpcomponents.c.

Referenced by SCIPincludeConshdlrStpcomponents().

◆ consCheckStpcomponents

#define consCheckStpcomponents   NULL

Definition at line 652 of file cons_stpcomponents.c.

Referenced by SCIPincludeConshdlrStpcomponents().

Typedef Documentation

◆ SUBSOL

typedef struct sub_solution SUBSOL

sub-solution

Function Documentation

◆ subsolGet()

static SCIP_RETCODE subsolGet ( SUBSTP substp,
SUBSOL subcomp 
)
static

gets optimal sub-problem solution

Parameters
substpsub-problem data structure
subcompcomponent

Definition at line 104 of file cons_stpcomponents.c.

References SCIP_CALL, SCIP_OKAY, sub_solution::subedgesSol, subsolFixOrgEdges(), and substpsolver_getSolution().

Referenced by subcompFixOrgEdges().

◆ subsolFixOrgEdges()

static SCIP_RETCODE subsolFixOrgEdges ( SCIP scip,
const SUBINOUT subinout,
SUBSOL subsol 
)
static

◆ subsolInit()

static SCIP_RETCODE subsolInit ( SCIP scip,
const SUBSTP substp,
SUBSOL **  subsolution 
)
static

initializes

Parameters
scipsub-SCIP data structure
substpsub problem
subsolutionto initialize

Definition at line 166 of file cons_stpcomponents.c.

References sub_solution::nsubedges, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, sub_solution::subedgesSol, subsol, subsolFree(), and substpsolver_getNsubedges().

Referenced by subcompFixOrgEdges(), and subsolFixOrgEdges().

◆ subsolFree()

static void subsolFree ( SCIP subscip,
SUBSOL **  subsolution 
)
static

exits

Parameters
subscipsub-SCIP data structure
subsolutionto initialize

Definition at line 190 of file cons_stpcomponents.c.

References SCIPfreeMemory, SCIPfreeMemoryArray, subcompFixOrgEdges(), sub_solution::subedgesSol, and subsol.

Referenced by subcompFixOrgEdges(), and subsolInit().

◆ subcompFixOrgEdges()

static SCIP_RETCODE subcompFixOrgEdges ( SCIP scip,
const SUBINOUT subinout,
SUBSTP substp 
)
static

fixes original edges with sub-solution

Parameters
scipSCIP data structure
subinoutsub-problem insertion/extraction data structure
substpsub-problem data structure

Definition at line 208 of file cons_stpcomponents.c.

References decomposeIsPromising(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, subsolFixOrgEdges(), subsolFree(), subsolGet(), and subsolInit().

Referenced by decomposeSolveSub(), and subsolFree().

◆ decomposeIsPromising()

static SCIP_Bool decomposeIsPromising ( const GRAPH g,
const BIDECOMP bidecomp 
)
static

is promising?

Parameters
ggraph data structure
bidecompbidecomposition data structure

Definition at line 229 of file cons_stpcomponents.c.

References bidecomposition_getMaxcompNodeRatio(), DECOMP_MAXCOMPRATIO, DECOMP_MINNNODES, decomposeGetSubgraph(), FALSE, GT, GRAPH::knots, and SCIP_Real.

Referenced by divideAndConquer(), initDecompose(), and subcompFixOrgEdges().

◆ decomposeGetSubgraph()

static SCIP_RETCODE decomposeGetSubgraph ( SCIP scip,
const BIDECOMP bidecomp,
int  compindex,
GRAPH orggraph,
GRAPH **  subgraph 
)
static

gets subgraph

Parameters
scipSCIP data structure
bidecompall-components storage
compindexcomponent index
orggraphgraph data structure
subgraphsubgraph

Definition at line 252 of file cons_stpcomponents.c.

References bidecomposition_getMarkedSubRoot(), bidecomposition_markSub(), decomposeSolveSub(), graph_knot_isInRange(), graph_knot_printInfo(), graph_subgraphExtract(), graph_valid(), Is_term, GRAPH::knots, GRAPH::mark, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, GRAPH::source, biconnected_component_decomposition::subinout, and GRAPH::term.

Referenced by decomposeIsPromising(), and decomposeSolveSub().

◆ decomposeSolveSub()

static SCIP_RETCODE decomposeSolveSub ( SCIP scip,
const BIDECOMP bidecomp,
int  compindex,
GRAPH orggraph,
SCIP_Bool success 
)
static

◆ decomposeExec()

static SCIP_RETCODE decomposeExec ( SCIP scip,
BIDECOMP bidecomp,
CUTNODES cutnodes,
GRAPH orggraph,
SCIP_Bool success 
)
static

tries to decompose and solve

Parameters
scipSCIP data structure
bidecompbidecomposition data structure
cutnodescut nodes data structure
orggraphgraph to decompose
successdecomposed?

Definition at line 352 of file cons_stpcomponents.c.

References bidecomposition_initSubInOut(), decomposeSolveSub(), FALSE, graph_subinoutActivateEdgeMap(), graph_subinoutActivateNewHistory(), graph_valid(), initDecompose(), biconnected_component_decomposition::nbicomps, SCIP_CALL, SCIP_OKAY, biconnected_component_decomposition::subinout, and TRUE.

Referenced by decomposeSolveSub(), and divideAndConquer().

◆ initDecompose()

static SCIP_RETCODE initDecompose ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
GRAPH orggraph,
SCIP_Bool isPromsing 
)
static

initializes for conshdlrdata

Parameters
scipSCIP data structure
conshdlrdatacosntraint handler data
orggraphgraph to decompose
isPromsingpromising decomposition?

Definition at line 390 of file cons_stpcomponents.c.

References cut_nodes::biconn_ncomps, bidecomposition_cutnodesCompute(), bidecomposition_cutnodesInit(), bidecomposition_init(), bidecomposition_isPossible(), decomposeIsPromising(), FALSE, freeDecompose(), graph_mark(), graph_typeIsSpgLike(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and GRAPH::terms.

Referenced by decomposeExec(), and SCIPStpcomponentsSetUp().

◆ freeDecompose()

static void freeDecompose ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata 
)
static

tries to decompose and solve

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data

Definition at line 440 of file cons_stpcomponents.c.

References bidecomposition_cutnodesFree(), bidecomposition_free(), and divideAndConquer().

Referenced by initDecompose(), SCIP_DECL_CONSEXITSOL(), and SCIPStpcomponentsSetUp().

◆ divideAndConquer()

static SCIP_RETCODE divideAndConquer ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_Bool success 
)
static

decomposes and solves

Parameters
scipSCIP data structure
conshdlrdataconstraints handler data
successdecomposed?

Definition at line 460 of file cons_stpcomponents.c.

References decomposeExec(), decomposeIsPromising(), FALSE, graph_mark(), graph_typeIsSpgLike(), SCIP_CALL, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIPprobdataGetGraph2(), and GRAPH::terms.

Referenced by freeDecompose(), and SCIP_DECL_CONSPROP().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyStpcomponents  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 490 of file cons_stpcomponents.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrStpcomponents(), and TRUE.

Referenced by divideAndConquer().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeStpcomponents  )
static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 506 of file cons_stpcomponents.c.

References CONSHDLR_NAME, NULL, SCIP_DECL_CONSINITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconshdlrSetData(), and SCIPfreeMemory.

Referenced by SCIP_DECL_CONSHDLRCOPY().

◆ SCIP_DECL_CONSINITSOL()

static SCIP_DECL_CONSINITSOL ( consInitsolStpcomponents  )
static

solving process initialization method of constraint handler (called when branch and bound process is about to begin)

Definition at line 527 of file cons_stpcomponents.c.

References SCIP_DECL_CONSEXITSOL(), and SCIP_OKAY.

Referenced by SCIP_DECL_CONSFREE().

◆ SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolStpcomponents  )
static

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteStpcomponents  )
static

frees specific constraint data

Definition at line 549 of file cons_stpcomponents.c.

References CONSHDLR_NAME, NULL, SCIP_DECL_CONSTRANS(), SCIP_OKAY, SCIPconshdlrGetName(), and SCIPfreeBlockMemory.

Referenced by SCIP_DECL_CONSEXITSOL().

◆ SCIP_DECL_CONSTRANS()

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpStpcomponents  )
static

LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)

Definition at line 594 of file cons_stpcomponents.c.

References SCIP_DECL_CONSPROP(), and SCIP_OKAY.

Referenced by SCIP_DECL_CONSTRANS().

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropStpcomponents  )
static

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockStpcomponents  )
static

variable rounding lock method of constraint handler

Definition at line 644 of file cons_stpcomponents.c.

References SCIP_OKAY.

Referenced by SCIP_DECL_CONSPROP().

◆ SCIPStpcomponentsSetUp()

SCIP_RETCODE SCIPStpcomponentsSetUp ( SCIP scip,
GRAPH graph 
)

sets the data for bidecomposition up

Parameters
scipSCIP data structure
graphgraph data

Definition at line 660 of file cons_stpcomponents.c.

References FALSE, freeDecompose(), initDecompose(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPfindConshdlr(), and SCIPStpcomponentsAllowsDecomposition().

Referenced by SCIPprobdataCreateFromGraph().

◆ SCIPStpcomponentsAllowsDecomposition()

SCIP_Bool SCIPStpcomponentsAllowsDecomposition ( SCIP scip)

is a promising bidecomposition available?

Parameters
scipSCIP data structure

Definition at line 689 of file cons_stpcomponents.c.

References NULL, SCIPconshdlrGetData(), SCIPfindConshdlr(), and SCIPincludeConshdlrStpcomponents().

Referenced by SCIPprobdataCreateFromGraph(), and SCIPStpcomponentsSetUp().

◆ SCIPincludeConshdlrStpcomponents()