Detailed Description

heuristic solver for pricing problems that solves independent set problems with cliquer

Author: Henri Lotze; Christian Puchert

#include <assert.h>
#include "solver_cliquer.h"
#include "scip/cons_linear.h"
#include "scip/cons_varbound.h"
#include "pub_solver.h"
#include "pricer_gcg.h"
#include "relax_gcg.h"
#include "pub_gcgcol.h"
#include "pub_gcgvar.h"
#include "cliquer/cliquer.h"

Go to the source code of this file.

Data Structures
struct	GCG_SolverData

Macros
#define	SOLVER_NAME "cliquer"

#define	SOLVER_DESC "heuristic solver for pricing problems that solves independent set problems with cliquer"

#define	SOLVER_PRIORITY 150

#define	SOLVER_HEURENABLED TRUE

#define	SOLVER_EXACTENABLED FALSE

#define	DEFAULT_DENSITY 0.00

#define	solverInitsolCliquer NULL

#define	solverExitsolCliquer NULL

#define	solverInitCliquer NULL

#define	solverExitCliquer NULL

#define	solverUpdateCliquer NULL

#define	solverSolveCliquer NULL

Functions
static SCIP_Bool	isVarLinked (SCIP_VAR *linkedvars, int nlinkedvars, SCIP_VAR var)

static SCIP_Bool	areVarsLinkedRec (int *linkmatrix, int vindex1, int vindex2, int vartrace, int traceindex, SCIP_VAR **linkedvars, int nlinkedvars)

static SCIP_Bool	areVarsLinked (SCIP scip, int linkmatrix, SCIP_VAR var1, SCIP_VAR var2, SCIP_VAR *linkedvars, int nlinkedvars)

static void	updateVarLinks (SCIP scip, int linkmatrix, SCIP_VAR var1, SCIP_VAR var2, SCIP_VAR linkedvars, int nlinkedvars)

static int	getNodeIndex (SCIP_VAR var, SCIP_VAR *indsetvars, int indexcount)

static int	getLinkedNodeIndex (SCIP scip, SCIP_VAR var, SCIP_VAR indsetvars, int indexcount, int linkmatrix, SCIP_VAR **linkedvars, int nlinkedvars)

static int	addVarToGraph (SCIP scip, graph_t g, SCIP_VAR consvar, int indexcount, SCIP_Real scalingfactor, SCIP_VAR indsetvars, int linkmatrix, SCIP_VAR **linkedvars, int nlinkedvars)

static void	setLinkedSolvals (SCIP scip, SCIP_Real solvals, int linkmatrix, SCIP_VAR linkedvars, int nlinkedvars, SCIP_VAR *var, SCIP_Real val)

static SCIP_Bool	areObjectivesIntegral (SCIP *scip)

static SCIP_Real	scaleRelativeToMax (SCIP *scip)

static SCIP_RETCODE	solveCliquer (SCIP_Bool exactly, SCIP scip, SCIP pricingprob, GCG_SOLVERDATA solver, int probnr, SCIP_Real lowerbound, GCG_PRICINGSTATUS *status)

static	GCG_DECL_SOLVERFREE (solverFreeCliquer)

static	GCG_DECL_SOLVERSOLVEHEUR (solverSolveHeurCliquer)

SCIP_RETCODE	GCGincludeSolverCliquer (SCIP *scip)

Macro Definition Documentation

◆ SOLVER_NAME

#define SOLVER_NAME "cliquer"

Definition at line 50 of file solver_cliquer.c.

◆ SOLVER_DESC

#define SOLVER_DESC "heuristic solver for pricing problems that solves independent set problems with cliquer"

Definition at line 51 of file solver_cliquer.c.

◆ SOLVER_PRIORITY

#define SOLVER_PRIORITY 150

Definition at line 52 of file solver_cliquer.c.

◆ SOLVER_HEURENABLED

#define SOLVER_HEURENABLED TRUE

indicates whether the solver should be enabled

Definition at line 54 of file solver_cliquer.c.

◆ SOLVER_EXACTENABLED

#define SOLVER_EXACTENABLED FALSE

indicates whether the solver should be enabled

Definition at line 55 of file solver_cliquer.c.

◆ DEFAULT_DENSITY

#define DEFAULT_DENSITY 0.00

Definition at line 57 of file solver_cliquer.c.

◆ solverInitsolCliquer

#define solverInitsolCliquer NULL

Definition at line 1152 of file solver_cliquer.c.

◆ solverExitsolCliquer

#define solverExitsolCliquer NULL

Definition at line 1153 of file solver_cliquer.c.

◆ solverInitCliquer

#define solverInitCliquer NULL

Definition at line 1154 of file solver_cliquer.c.

◆ solverExitCliquer

#define solverExitCliquer NULL

Definition at line 1155 of file solver_cliquer.c.

◆ solverUpdateCliquer

#define solverUpdateCliquer NULL

Definition at line 1156 of file solver_cliquer.c.

◆ solverSolveCliquer

#define solverSolveCliquer NULL

Definition at line 1157 of file solver_cliquer.c.

Function Documentation

◆ isVarLinked()

static SCIP_Bool isVarLinked	(	SCIP_VAR **	linkedvars,
		int	nlinkedvars,
		SCIP_VAR *	var
	)

static

Returns whether the given var is linked in some way with other variables

Parameters

linkedvars	Array of variables that are linked by eq-constraints
nlinkedvars	Index of linkedvars array
var	Variable whose membership in the linkedvars array is to be checked

Definition at line 71 of file solver_cliquer.c.

Referenced by addVarToGraph(), and getLinkedNodeIndex().

◆ areVarsLinkedRec()

static SCIP_Bool areVarsLinkedRec	(	int **	linkmatrix,
		int	vindex1,
		int	vindex2,
		int *	vartrace,
		int	traceindex,
		SCIP_VAR **	linkedvars,
		int	nlinkedvars
	)

static

Returns whether 2 variables are linked, either simply or in a transitive way in respect to a given linkmatrix matrix. Use of the wrapper function areVarsLinked(..) is recommended

Parameters

linkmatrix	Matrix indicating which variables are linked by a node
vindex1	Problem index of the first variable in the pair that is to be checked
vindex2	Problem index of the second variable in the pair that is to be checked
vartrace	Array to keep track of which nodes have already been visited during recursion
traceindex	Index to keep track of the number of visited nodes during recursion
linkedvars	Array of variables that are linked by eq-constraints
nlinkedvars	Index of linkedvars array

Definition at line 95 of file solver_cliquer.c.

Referenced by areVarsLinked().

◆ areVarsLinked()

static SCIP_Bool areVarsLinked	(	SCIP *	scip,
		int **	linkmatrix,
		SCIP_VAR *	var1,
		SCIP_VAR *	var2,
		SCIP_VAR **	linkedvars,
		int	nlinkedvars
	)

static

Wrapper function for areVarsLinkedRec, mallocs and cleans up the necessary memory and passes through the result

Parameters

scip	The problem instance
linkmatrix	Matrix indicating which variables are linked by a node
var1	The first variable in the pair that is to be checked
var2	The second variable in the pair that is to be checked
linkedvars	Array of variables that are linked by eq-constraints
nlinkedvars	Index of linkedvars array

Definition at line 143 of file solver_cliquer.c.

References areVarsLinkedRec().

Referenced by getLinkedNodeIndex(), setLinkedSolvals(), and updateVarLinks().

◆ updateVarLinks()

static void updateVarLinks	(	SCIP *	scip,
		int **	linkmatrix,
		SCIP_VAR *	var1,
		SCIP_VAR *	var2,
		SCIP_VAR **	linkedvars,
		int *	nlinkedvars
	)

static

Update transitivity in the linkmatrix matrix between 2 variables that are to be linked and all linked variables

Parameters

scip	The Problem instance
linkmatrix	Matrix indicating which variables are linked by a node
var1	The first variable in the pair that is to be checked
var2	The second variable in the pair that is to be checked
linkedvars	Array of variables that are linked by eq-constraints
nlinkedvars	Index of linkedvars array

Definition at line 184 of file solver_cliquer.c.

References areVarsLinked().

Referenced by solveCliquer().

◆ getNodeIndex()

static int getNodeIndex	(	SCIP_VAR *	var,
		SCIP_VAR **	indsetvars,
		int	indexcount
	)

static

Get the node index of a given variable in the bijection if mapped, else return -1

Parameters

var	Variable for which the node index is to be determined
indsetvars	Array of variables that are mapped to a node of the graph
indexcount	Number of variables that are mapped in the graph

Definition at line 250 of file solver_cliquer.c.

Referenced by addVarToGraph(), and getLinkedNodeIndex().

◆ getLinkedNodeIndex()

static int getLinkedNodeIndex	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_VAR **	indsetvars,
		int	indexcount,
		int **	linkmatrix,
		SCIP_VAR **	linkedvars,
		int	nlinkedvars
	)

static

Returns the node index of a given variable in the bijection or that of a linked variable, if any.

Parameters

scip	The problem instance
var	Variable for which the node index is to be determined
indsetvars	Array of variables that are mapped to a node of the graph
indexcount	Number of variables that are mapped in the graph
linkmatrix	Matrix indicating which variables are linked by a node
linkedvars	Array of variables that are linked by eq-constraints
nlinkedvars	Index of linkedvars array

Definition at line 268 of file solver_cliquer.c.

References areVarsLinked(), getNodeIndex(), and isVarLinked().

Referenced by addVarToGraph(), and solveCliquer().

◆ addVarToGraph()

static int addVarToGraph	(	SCIP *	scip,
		graph_t *	g,
		SCIP_VAR *	consvar,
		int *	indexcount,
		SCIP_Real	scalingfactor,
		SCIP_VAR **	indsetvars,
		int **	linkmatrix,
		SCIP_VAR **	linkedvars,
		int	nlinkedvars
	)

static

Add a variable to the bijection graph g and indsetvars array. Returns the index of the corresponding node in the graph.

Parameters

scip	The problem instance
g	Graph into which to insert the new variable as a node
consvar	The variable that is to be assigned a node in the graph
indexcount	Pointer to Index of the next unassigned node in the graph
scalingfactor	Factor for scaling the weight of newly mapped nodes
indsetvars	Array that keeps track of variables that are part of the graph
linkmatrix	Matrix indicating which variables are linked by a node
linkedvars	Array of variables that are linked by eq-constraints
nlinkedvars	Index of linkedvars array

Definition at line 308 of file solver_cliquer.c.

References getLinkedNodeIndex(), getNodeIndex(), and isVarLinked().

Referenced by solveCliquer().

◆ setLinkedSolvals()

static void setLinkedSolvals	(	SCIP *	scip,
		SCIP_Real *	solvals,
		int **	linkmatrix,
		SCIP_VAR **	linkedvars,
		int	nlinkedvars,
		SCIP_VAR *	var,
		SCIP_Real	val
	)

static

Set the solvals of a variable and of all its linked variables, if any

Parameters

scip	The problem instance
solvals	Array holding the current solution values of all variables of the problem
linkmatrix	Matrix indicating which variables are linked by a node
linkedvars	Array of variables that are linked by eq-constraints
nlinkedvars	Index of linkedvars array
var	Var that may be linked that itself should be set to the value val
val	Value to which all linked vars are supposed to be set to

Definition at line 349 of file solver_cliquer.c.

References areVarsLinked().

Referenced by solveCliquer().

◆ areObjectivesIntegral()

static SCIP_Bool areObjectivesIntegral ( SCIP * scip )

static

Check if the objective coefficients of the variables are already Integral

Parameters

scip	The problem instance

Definition at line 377 of file solver_cliquer.c.

Referenced by solveCliquer().

◆ scaleRelativeToMax()

static SCIP_Real scaleRelativeToMax ( SCIP * scip )

static

Scale the objective coefficients of the variables maximally s.t. they become integral and the sum of values does not exceed INT_MAX

Parameters

scip	The problem instance

Definition at line 402 of file solver_cliquer.c.

Referenced by solveCliquer().

◆ solveCliquer()

static SCIP_RETCODE solveCliquer	(	SCIP_Bool	exactly,
		SCIP *	scip,
		SCIP *	pricingprob,
		GCG_SOLVERDATA *	solver,
		int	probnr,
		SCIP_Real *	lowerbound,
		GCG_PRICINGSTATUS *	status
	)

static

Solve the pricing problem as an independent set problem, in an approximate way.

Parameters

exactly	should the pricing problem be solved to optimality or heuristically?
scip	master problem SCIP data structure
pricingprob	pricing problem SCIP data structure
solver	solver data structure
probnr	problem number
lowerbound	pointer to store lower bound
status	pointer to store pricing problem status

Definition at line 462 of file solver_cliquer.c.

References addVarToGraph(), areObjectivesIntegral(), GCG_SolverData::density, GCG_PRICINGSTATUS_NOTAPPLICABLE, GCG_PRICINGSTATUS_UNKNOWN, GCGcreateGcgCol(), GCGpricerAddCol(), getLinkedNodeIndex(), scaleRelativeToMax(), setLinkedSolvals(), and updateVarLinks().

Referenced by GCG_DECL_SOLVERSOLVEHEUR().

◆ GCG_DECL_SOLVERFREE()

static GCG_DECL_SOLVERFREE ( solverFreeCliquer )

static

destructor of pricing solver to free user data (called when SCIP is exiting)

Definition at line 1135 of file solver_cliquer.c.

References GCGsolverGetData(), and GCGsolverSetData().

◆ GCG_DECL_SOLVERSOLVEHEUR()

static GCG_DECL_SOLVERSOLVEHEUR ( solverSolveHeurCliquer )

static

heuristic solving method of independent set solver

Definition at line 1161 of file solver_cliquer.c.

References GCGsolverGetData(), and solveCliquer().

◆ GCGincludeSolverCliquer()

SCIP_RETCODE GCGincludeSolverCliquer ( SCIP * scip )

creates the cliquer solver for pricing problems and includes it in GCG

Parameters

scip	SCIP data structure

Definition at line 1175 of file solver_cliquer.c.

References DEFAULT_DENSITY, GCG_SolverData::density, GCGmasterGetOrigprob(), GCGpricerIncludeSolver(), SOLVER_DESC, SOLVER_EXACTENABLED, SOLVER_HEURENABLED, SOLVER_NAME, SOLVER_PRIORITY, solverExitCliquer, solverExitsolCliquer, solverInitCliquer, solverInitsolCliquer, solverSolveCliquer, and solverUpdateCliquer.

Referenced by GCGincludeMasterPlugins().

GCG

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ SOLVER_NAME

◆ SOLVER_DESC

◆ SOLVER_PRIORITY

◆ SOLVER_HEURENABLED

◆ SOLVER_EXACTENABLED

◆ DEFAULT_DENSITY

◆ solverInitsolCliquer

◆ solverExitsolCliquer

◆ solverInitCliquer

◆ solverExitCliquer

◆ solverUpdateCliquer

◆ solverSolveCliquer

Function Documentation

◆ isVarLinked()

◆ areVarsLinkedRec()

◆ areVarsLinked()

◆ updateVarLinks()

◆ getNodeIndex()

◆ getLinkedNodeIndex()

◆ addVarToGraph()

◆ setLinkedSolvals()

◆ areObjectivesIntegral()

◆ scaleRelativeToMax()

◆ solveCliquer()

◆ GCG_DECL_SOLVERFREE()

◆ GCG_DECL_SOLVERSOLVEHEUR()

◆ GCGincludeSolverCliquer()