dec_isomorph.cpp File Reference

Detailed Description

detector for pricing problems that can be aggregated (uses bliss)

Author

Martin Bergner

Daniel Peters

Jonas Witt

Michael Bastubbe

Note

requires package to be installed: BLISS, requires flag to be set: BLISS=true

This detector finds subproblems that can be aggregated thus reducing the symmetry of the problem using color preserving automorphisms and bliss.

Definition in file dec_isomorph.cpp.

#include "dec_isomorph.h"
#include "pub_decomp.h"
#include "cons_decomp.h"
#include "scip_misc.h"
#include "gcg.h"
#include "class_partialdecomp.h"
#include "class_detprobdata.h"
#include "scip/clock.h"
#include "bliss/graph.hh"
#include "pub_gcgvar.h"
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include "pub_bliss.h"

Go to the source code of this file.

Data Structures
struct	DEC_DetectorData
struct	struct_hook

Macros
#define	DEC_DETECTORNAME   "isomorph"
#define	DEC_DESC   "detector for pricing problems suitable for aggregation"
#define	DEC_FREQCALLROUND   1
#define	DEC_MAXCALLROUND   0
#define	DEC_MINCALLROUND   0
#define	DEC_FREQCALLROUNDORIGINAL   1
#define	DEC_MAXCALLROUNDORIGINAL   0
#define	DEC_MINCALLROUNDORIGINAL   0
#define	DEC_PRIORITY   100
#define	DEC_DECCHAR   'I'
#define	DEC_ENABLED   FALSE
#define	DEC_ENABLEDFINISHING   FALSE
#define	DEC_ENABLEDPOSTPROCESSING   FALSE
#define	DEC_SKIP   TRUE
#define	DEC_USEFULRECALL   FALSE
#define	DEFAULT_MAXDECOMPSEXACT   6
#define	DEFAULT_MAXDECOMPSEXTEND   4
#define	SET_MULTIPLEFORSIZETRANSF   12500
#define	detectorExitIsomorph   NULL
#define	detectorFinishPartialdecIsomorph   NULL
#define	detectorPostprocessPartialdecIsomorph   NULL

Typedefs
typedef struct struct_hook	AUT_HOOK

Functions
static int	gcd (int a, int b)
static void	fhook (void *user_param, unsigned int N, const unsigned int *aut)
static void	fhookForPartialdecs (void *user_param, unsigned int N, const unsigned int *aut)
static SCIP_RETCODE	allocMemory (SCIP *scip, AUT_COLOR *colorinfo, int nconss, int nvars)
static void	freeMemory (SCIP *scip, AUT_COLOR *colorinfo)
static SCIP_RETCODE	setupArrays (SCIP *scip, AUT_COLOR *colorinfo, SCIP_RESULT *result)
static SCIP_RETCODE	setupArrays (SCIP *scip, AUT_COLOR *colorinfo, SCIP_RESULT *result, gcg::PARTIALDECOMP *partialdec, gcg::DETPROBDATA *detprobdata)
static SCIP_RETCODE	createGraph (SCIP *scip, AUT_COLOR colorinfo, bliss::Graph *graph, SCIP_RESULT *result)
static SCIP_RETCODE	createGraph (SCIP *scip, AUT_COLOR colorinfo, bliss::Graph *graph, SCIP_RESULT *result, gcg::PARTIALDECOMP *partialdec, gcg::DETPROBDATA *detprobdata)
SCIP_RETCODE	createPartialdecFromMasterconss (SCIP *scip, gcg::PARTIALDECOMP **newPartialdec, int *masterconss, int nmasterconss, gcg::PARTIALDECOMP *partialdec, gcg::DETPROBDATA *detprobdata, SCIP_Bool exact)
static	DEC_DECL_FREEDETECTOR (detectorFreeIsomorph)
static	DEC_DECL_INITDETECTOR (detectorInitIsomorph)
int	renumberPermutations (int *permutation, int permsize)
void	collapsePermutation (int *permutation, int permsize)
static std::vector< std::vector< int > >	getAllSubsets (std::vector< int > set)
SCIP_RETCODE	reorderPermutations (SCIP *scip, gcg::DETPROBDATA *detprobdata, int *permutation, int permsize, int nperms)
static SCIP_RETCODE	detectIsomorph (SCIP *scip, PARTIALDEC_DETECTION_DATA *detectiondata, DEC_DETECTORDATA *detectordata, SCIP_RESULT *result, SCIP_Bool onlysign, int maxdecomps)
	DEC_DECL_PROPAGATEPARTIALDEC (detectorPropagatePartialdecIsomorph)
static	DEC_DECL_SETPARAMAGGRESSIVE (setParamAggressiveIsomorph)
static	DEC_DECL_SETPARAMDEFAULT (setParamDefaultIsomorph)
static	DEC_DECL_SETPARAMFAST (setParamFastIsomorph)
SCIP_RETCODE	SCIPincludeDetectorIsomorphism (SCIP *scip)

Macro Definition Documentation

DEC_DETECTORNAME

#define DEC_DETECTORNAME   "isomorph"

name of detector

Definition at line 64 of file dec_isomorph.cpp.

DEC_DESC

#define DEC_DESC   "detector for pricing problems suitable for aggregation"

description of detector

Definition at line 65 of file dec_isomorph.cpp.

DEC_FREQCALLROUND

#define DEC_FREQCALLROUND   1

frequency the detector gets called in detection loop ,ie it is called in round r if and only if minCallRound <= r <= maxCallRound AND (r - minCallRound) mod freqCallRound == 0

Definition at line 66 of file dec_isomorph.cpp.

DEC_MAXCALLROUND

#define DEC_MAXCALLROUND   0

last round the detector gets called

Definition at line 67 of file dec_isomorph.cpp.

DEC_MINCALLROUND

#define DEC_MINCALLROUND   0

first round the detector gets called

Definition at line 68 of file dec_isomorph.cpp.

DEC_FREQCALLROUNDORIGINAL

#define DEC_FREQCALLROUNDORIGINAL   1

frequency the detector gets called in detection loop while detecting the original problem

Definition at line 69 of file dec_isomorph.cpp.

DEC_MAXCALLROUNDORIGINAL

#define DEC_MAXCALLROUNDORIGINAL   0

last round the detector gets called while detecting the original problem

Definition at line 70 of file dec_isomorph.cpp.

DEC_MINCALLROUNDORIGINAL

#define DEC_MINCALLROUNDORIGINAL   0

first round the detector gets called while detecting the original problem

Definition at line 71 of file dec_isomorph.cpp.

DEC_PRIORITY

#define DEC_PRIORITY   100

priority of the constraint handler for separation

Definition at line 72 of file dec_isomorph.cpp.

DEC_DECCHAR

#define DEC_DECCHAR   'I'

display character of detector

Definition at line 73 of file dec_isomorph.cpp.

DEC_ENABLED

#define DEC_ENABLED   FALSE

should the detection be enabled

Definition at line 75 of file dec_isomorph.cpp.

DEC_ENABLEDFINISHING

#define DEC_ENABLEDFINISHING   FALSE

should the finishing be enabled

Definition at line 76 of file dec_isomorph.cpp.

DEC_ENABLEDPOSTPROCESSING

#define DEC_ENABLEDPOSTPROCESSING   FALSE

should the postprocessing be enabled

Definition at line 77 of file dec_isomorph.cpp.

DEC_SKIP

#define DEC_SKIP   TRUE

should the detector be skipped if others found decompositions

Definition at line 78 of file dec_isomorph.cpp.

DEC_USEFULRECALL

#define DEC_USEFULRECALL   FALSE

is it useful to call this detector on a descendant of the propagated partialdec

Definition at line 79 of file dec_isomorph.cpp.

DEFAULT_MAXDECOMPSEXACT

#define DEFAULT_MAXDECOMPSEXACT   6

default maximum number of decompositions

Definition at line 81 of file dec_isomorph.cpp.

DEFAULT_MAXDECOMPSEXTEND

#define DEFAULT_MAXDECOMPSEXTEND   4

default maximum number of decompositions

Definition at line 82 of file dec_isomorph.cpp.

SET_MULTIPLEFORSIZETRANSF

#define SET_MULTIPLEFORSIZETRANSF   12500

Definition at line 84 of file dec_isomorph.cpp.

detectorExitIsomorph

#define detectorExitIsomorph   NULL

Definition at line 1513 of file dec_isomorph.cpp.

detectorFinishPartialdecIsomorph

#define detectorFinishPartialdecIsomorph   NULL

Definition at line 1515 of file dec_isomorph.cpp.

detectorPostprocessPartialdecIsomorph

#define detectorPostprocessPartialdecIsomorph   NULL

Definition at line 1517 of file dec_isomorph.cpp.

Typedef Documentation

AUT_HOOK

typedef struct struct_hook AUT_HOOK

Definition at line 98 of file dec_isomorph.cpp.

Function Documentation

gcd()

static int gcd ( int  a, int  b  )

static

method to calculate the greatest common divisor

Definition at line 171 of file dec_isomorph.cpp.

Referenced by reorderPermutations().

fhook()

static void fhook ( void *  user_param, unsigned int  N, const unsigned int *  aut  )

static

hook function to save the permutation of the graph

Parameters

user_param	data structure to save hashmaps with permutation
N	number of permutations
aut	array of permutations

Definition at line 216 of file dec_isomorph.cpp.

References struct_hook::conssperm, struct_hook::getScip(), and struct_hook::setBool().

fhookForPartialdecs()

static void fhookForPartialdecs ( void *  user_param, unsigned int  N, const unsigned int *  aut  )

static

hook function to save the permutation of the graph

Parameters

user_param	data structure to save hashmaps with permutation
N	number of permutations
aut	array of permutations

Definition at line 258 of file dec_isomorph.cpp.

References struct_hook::conssperm, gcg::DETPROBDATA::getCons(), struct_hook::getDetprobdata(), gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getOpenconss(), struct_hook::getPartialdec(), and struct_hook::setBool().

Referenced by detectIsomorph().

allocMemory()

static SCIP_RETCODE allocMemory ( SCIP *  scip, AUT_COLOR *  colorinfo, int  nconss, int  nvars  )

static

Parameters

scip	SCIP data structure
colorinfo	struct to save intermediate information
nconss	number of constraints
nvars	number of variables

Definition at line 304 of file dec_isomorph.cpp.

Referenced by setupArrays().

freeMemory()

static void freeMemory ( SCIP *  scip, AUT_COLOR *  colorinfo  )

static

destructor for colorinfo

Parameters

scip	SCIP data structure
colorinfo	struct to save intermediate information

Definition at line 320 of file dec_isomorph.cpp.

Referenced by createGraph().

setupArrays() [1/2]

static SCIP_RETCODE setupArrays ( SCIP *  scip, AUT_COLOR *  colorinfo, SCIP_RESULT *  result  )

static

set up a help structure for graph creation

Parameters

scip	SCIP to compare
colorinfo	data structure to save intermediate data
result	result pointer to indicate success or failure

Definition at line 350 of file dec_isomorph.cpp.

References allocMemory(), GCGconsGetNVars(), GCGconsGetVals(), and GCGconsGetVars().

Referenced by detectIsomorph().

setupArrays() [2/2]

static SCIP_RETCODE setupArrays ( SCIP *  scip, AUT_COLOR *  colorinfo, SCIP_RESULT *  result, gcg::PARTIALDECOMP *  partialdec, gcg::DETPROBDATA *  detprobdata  )

static

set up a help structure for graph creation (for partialdecs)

Parameters

scip	SCIP to compare
colorinfo	data structure to save intermediate data
result	result pointer to indicate success or failure
partialdec	partialdec to set up help structure for
detprobdata	detection process information and data

Definition at line 456 of file dec_isomorph.cpp.

References allocMemory(), gcg::DETPROBDATA::getCons(), gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getNVars(), gcg::DETPROBDATA::getNVarsForCons(), gcg::PARTIALDECOMP::getOpenconss(), gcg::DETPROBDATA::getValsForCons(), and gcg::DETPROBDATA::getVar().

createGraph() [1/2]

static SCIP_RETCODE createGraph ( SCIP *  scip, AUT_COLOR  colorinfo, bliss::Graph *  graph, SCIP_RESULT *  result  )

static

create a graph out of an array of scips

Parameters

scip	SCIP to compare
colorinfo	data structure to save intermediate data
graph	graph needed for discovering isomorphism
result	result pointer to indicate success or failure

Definition at line 549 of file dec_isomorph.cpp.

References freeMemory(), GCGconsGetNVars(), GCGconsGetVals(), and GCGconsGetVars().

Referenced by detectIsomorph().

createGraph() [2/2]

static SCIP_RETCODE createGraph ( SCIP *  scip, AUT_COLOR  colorinfo, bliss::Graph *  graph, SCIP_RESULT *  result, gcg::PARTIALDECOMP *  partialdec, gcg::DETPROBDATA *  detprobdata  )

static

create a graph out of an array of scips (for partialdecs)

Parameters

scip	SCIP to compare
colorinfo	data structure to save intermediate data
graph	graph needed for discovering isomorphism
result	result pointer to indicate success or failure
partialdec	partialdec to create graph for
detprobdata	detection process information and data

Definition at line 690 of file dec_isomorph.cpp.

References freeMemory(), gcg::DETPROBDATA::getCons(), gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getNVars(), gcg::DETPROBDATA::getNVarsForCons(), gcg::PARTIALDECOMP::getOpenconss(), gcg::DETPROBDATA::getValsForCons(), gcg::DETPROBDATA::getVar(), and gcg::DETPROBDATA::getVarsForCons().

createPartialdecFromMasterconss()

SCIP_RETCODE createPartialdecFromMasterconss	(	SCIP *	scip,
		gcg::PARTIALDECOMP **	newPartialdec,
		int *	masterconss,
		int	nmasterconss,
		gcg::PARTIALDECOMP *	partialdec,
		gcg::DETPROBDATA *	detprobdata,
		SCIP_Bool	exact
	)

creates a partialdec with provided constraints in the master The function will put the remaining constraints in one or more pricing problems depending on whether the subproblems decompose with no variables in common.

Parameters

scip	SCIP data structure
newPartialdec	partialdec data structure
masterconss	constraints to be put in the master
nmasterconss	number of constraints in the master
partialdec	partialdec to propagate
detprobdata	detection process information and data
exact	does this partialdec stems from exact graph construction ( or was onlysign = TRUE ) was used

Definition at line 830 of file dec_isomorph.cpp.

References gcg::DETPROBDATA::getCons(), gcg::DETPROBDATA::getNConss(), gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getNVars(), gcg::DETPROBDATA::getNVarsForCons(), gcg::PARTIALDECOMP::getOpenconss(), gcg::DETPROBDATA::getVar(), and gcg::DETPROBDATA::getVarsForCons().

Referenced by detectIsomorph().

DEC_DECL_FREEDETECTOR()

static DEC_DECL_FREEDETECTOR ( detectorFreeIsomorph  )

static

destructor of detector to free user data (called when GCG is exiting)

Definition at line 1093 of file dec_isomorph.cpp.

References DEC_DETECTORNAME, DECdetectorGetData(), and DECdetectorGetName().

DEC_DECL_INITDETECTOR()

static DEC_DECL_INITDETECTOR ( detectorInitIsomorph  )

static

detector initialization method (called after problem was transformed)

Definition at line 1112 of file dec_isomorph.cpp.

References DEC_DETECTORNAME, DECdetectorGetData(), DECdetectorGetName(), and DEC_DetectorData::result.

renumberPermutations()

int renumberPermutations	(	int *	permutation,
		int	permsize
	)

renumbers the permutations from 0 to n-1 and returns the number of permutations

Returns

the number of permutations

Parameters

permutation	the permutation
permsize	size of the permutation

Definition at line 1132 of file dec_isomorph.cpp.

Referenced by detectIsomorph().

collapsePermutation()

void collapsePermutation	(	int *	permutation,
		int	permsize
	)

collapses the permutation, if possible

Parameters

permutation	the permutation
permsize	size of the permutation

Definition at line 1165 of file dec_isomorph.cpp.

Referenced by detectIsomorph().

getAllSubsets()

static std::vector< std::vector<int> > getAllSubsets ( std::vector< int >  set )

static

method to enumerate all subsets

Definition at line 1186 of file dec_isomorph.cpp.

Referenced by reorderPermutations().

reorderPermutations()

SCIP_RETCODE reorderPermutations	(	SCIP *	scip,
		gcg::DETPROBDATA *	detprobdata,
		int *	permutation,
		int	permsize,
		int	nperms
	)

reorder such that the best permutation is represented by 0, the second best by 1, etc.

Parameters

scip	SCIP data structure
detprobdata	detection process information and data
permutation	the permutation
permsize	size of the permutation
nperms	number of permutations

Definition at line 1206 of file dec_isomorph.cpp.

References gcd(), GCGconshdlrDecompAddCandidatesNBlocks(), getAllSubsets(), and gcg::DETPROBDATA::isAssignedToOrigProb().

Referenced by detectIsomorph().

detectIsomorph()

static SCIP_RETCODE detectIsomorph ( SCIP *  scip, PARTIALDEC_DETECTION_DATA *  detectiondata, DEC_DETECTORDATA *  detectordata, SCIP_RESULT *  result, SCIP_Bool  onlysign, int  maxdecomps  )

static

detection function of isomorph detector for partialdecs

Parameters

scip	SCIP data structure
detectiondata	detection data
detectordata	detector data structure
result	pointer to store result
onlysign	use only sign of coefficients instead of coefficients?
maxdecomps	maximum number of new decompositions

Definition at line 1329 of file dec_isomorph.cpp.

References gcg::PARTIALDECOMP::addClockTime(), collapsePermutation(), struct_hook::conssperm, createGraph(), createPartialdecFromMasterconss(), Partialdec_Detection_Data::detectiontime, Partialdec_Detection_Data::detprobdata, fhookForPartialdecs(), struct_hook::getBool(), gcg::DETPROBDATA::getCons(), gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getOpenconss(), gcg::PARTIALDECOMP::isEqual(), Partialdec_Detection_Data::newpartialdecs, Partialdec_Detection_Data::nnewpartialdecs, renumberPermutations(), reorderPermutations(), DEC_DetectorData::result, setupArrays(), and Partialdec_Detection_Data::workonpartialdec.

Referenced by DEC_DECL_PROPAGATEPARTIALDEC().

DEC_DECL_PROPAGATEPARTIALDEC()

DEC_DECL_PROPAGATEPARTIALDEC

(

detectorPropagatePartialdecIsomorph

)

Definition at line 1485 of file dec_isomorph.cpp.

References DECdetectorGetData(), detectIsomorph(), gcg::PARTIALDECOMP::getNBlocks(), gcg::PARTIALDECOMP::getNOpenvars(), gcg::PARTIALDECOMP::getNVars(), DEC_DetectorData::maxdecompsexact, and DEC_DetectorData::maxdecompsextend.

DEC_DECL_SETPARAMAGGRESSIVE()

static DEC_DECL_SETPARAMAGGRESSIVE ( setParamAggressiveIsomorph  )

static

Definition at line 1520 of file dec_isomorph.cpp.

References DECdetectorGetName(), DEFAULT_MAXDECOMPSEXACT, DEFAULT_MAXDECOMPSEXTEND, and SET_MULTIPLEFORSIZETRANSF.

DEC_DECL_SETPARAMDEFAULT()

static DEC_DECL_SETPARAMDEFAULT ( setParamDefaultIsomorph  )

static

Definition at line 1586 of file dec_isomorph.cpp.

References DEC_ENABLED, DEC_ENABLEDFINISHING, DECdetectorGetName(), DEFAULT_MAXDECOMPSEXACT, DEFAULT_MAXDECOMPSEXTEND, and SET_MULTIPLEFORSIZETRANSF.

DEC_DECL_SETPARAMFAST()

static DEC_DECL_SETPARAMFAST ( setParamFastIsomorph  )

static

Definition at line 1641 of file dec_isomorph.cpp.

References DECdetectorGetName(), DEFAULT_MAXDECOMPSEXACT, DEFAULT_MAXDECOMPSEXTEND, and SET_MULTIPLEFORSIZETRANSF.

SCIPincludeDetectorIsomorphism()

SCIP_RETCODE SCIPincludeDetectorIsomorphism

(

SCIP *

scip

)

creates the handler for isomorph subproblems and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1693 of file dec_isomorph.cpp.

References DEC_DECCHAR, DEC_DESC, DEC_DETECTORNAME, DEC_ENABLED, DEC_ENABLEDFINISHING, DEC_ENABLEDPOSTPROCESSING, DEC_FREQCALLROUND, DEC_FREQCALLROUNDORIGINAL, DEC_MAXCALLROUND, DEC_MAXCALLROUNDORIGINAL, DEC_MINCALLROUND, DEC_MINCALLROUNDORIGINAL, DEC_PRIORITY, DEC_SKIP, DEC_USEFULRECALL, DECincludeDetector(), DEFAULT_MAXDECOMPSEXACT, DEFAULT_MAXDECOMPSEXTEND, detectorExitIsomorph, detectorFinishPartialdecIsomorph, detectorPostprocessPartialdecIsomorph, DEC_DetectorData::maxdecompsexact, and DEC_DetectorData::maxdecompsextend.

Referenced by SCIPincludeGcgPlugins().