ConnectivityCons Class Reference

Class for representing connectivity constraints This class uses cutting planes to make disconnected segments infeasible. More...

#include <connectivity_cons.h>

Inheritance diagram for ConnectivityCons:

Public Member Functions
	ConnectivityCons (SCIP *scip, Graph &g_, std::vector< Graph::vertex_descriptor > &master_nodes_, Graph::vertex_descriptor master_node_, std::vector< SCIP_VAR * > &superpixel_vars_)
	Constructor for the connectivity constraints class. More...
virtual	SCIP_DECL_CONSTRANS (scip_trans)
	Transforms constraint data into data belonging to the transformed problem.
	SCIP_DECL_CONSSEPALP (scip_sepalp)
	Separation method of constraint handler for LP solution.
	SCIP_DECL_CONSSEPASOL (scip_sepasol)
	Separation method of constraint handler for arbitrary primal solution.
virtual	SCIP_DECL_CONSENFOLP (scip_enfolp)
	Constraint enforcing method of constraint handler for LP solutions.
virtual	SCIP_DECL_CONSENFOPS (scip_enfops)
	Constraint enforcing method of constraint handler for pseudo solutions.
virtual	SCIP_DECL_CONSCHECK (scip_check)
	Feasibility check method of constraint handler for primal solutions.
virtual	SCIP_DECL_CONSLOCK (scip_lock)
	Variable rounding lock method of constraint handler.

Private Member Functions
size_t	findComponents (SCIP *scip, SCIP_SOL *sol, Graph &subgraph, std::vector< int > &component)
	Finds all connected components in a subgraph. More...
SCIP_RETCODE	sepaConnectivity (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_RESULT *result)
	Adds cutting plane, if possible. More...

Private Attributes
Graph &	g
std::vector< Graph::vertex_descriptor > &	master_nodes
Graph::vertex_descriptor	master_node
std::vector< SCIP_VAR * > &	superpixel_vars

Detailed Description

Class for representing connectivity constraints This class uses cutting planes to make disconnected segments infeasible.

Whenever one of the methods scip_enfolp, scip_enfops, scip_check is called, the connected components of the subgraph containing all superpixels \(s\in\mathcal{S}\) for which \(x_s = 1\) are calculated. In scip_enfolp, a cutting plane is added if the current solution is infeasible.

Constructor & Destructor Documentation

ConnectivityCons::ConnectivityCons	(	SCIP *	scip,
		Graph &	g_,
		std::vector< Graph::vertex_descriptor > &	master_nodes_,
		Graph::vertex_descriptor	master_node_,
		std::vector< SCIP_VAR * > &	superpixel_vars_
	)

Constructor for the connectivity constraints class.

Parameters

scip	pricer SCIP instance
g_	the graph of superpixels
master_nodes_	master nodes of all segements
master_node_	master node of the current segement
superpixel_vars_	vector of variables \(x_s\) for each superpixel \(s\in\mathcal{S}\)

Member Function Documentation

size_t ConnectivityCons::findComponents ( SCIP *  scip, SCIP_SOL *  sol, Graph &  subgraph, std::vector< int > &  component  )

private

Finds all connected components in a subgraph.

Returns

the number of connected components

Parameters

scip	pricer SCIP instance
sol	current primal solution or NULL
subgraph	subgraph with all superpixels for which \(x_s = 1\)
component	component[s] will be the index of the connected component the superpixel s belongs to

SCIP_RETCODE ConnectivityCons::sepaConnectivity ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, SCIP_SOL *  sol, SCIP_RESULT *  result  )

private

Adds cutting plane, if possible.

If the current solution is infeasible, a cutting plane of the following form is added for every superpixel \(s\) in a component \(C\) that is not connected to the master node \(t\):

\[\sum_{s'\in\delta(C)}x_{s'} \geq x_s\]

---

The documentation for this class was generated from the following files:

• /home/rschuetz/uni/2017-SS/Fortgeschrittenenpraktikum_Optimierung/src/connectivity_cons.h
• /home/rschuetz/uni/2017-SS/Fortgeschrittenenpraktikum_Optimierung/src/connectivity_cons.cpp