Detailed Description

flower-inequality separator

Author: Matthias Walter

Definition in file sepa_flower.c.

#include "scip/sepa_flower.h"
#include "scip/cons_and.h"
#include "scip/cons_nonlinear.h"
#include "scip/struct_scip.h"
#include "scip/struct_set.h"
#include "scip/set.h"
#include "scip/hypergraph.h"

Go to the source code of this file.

Macros
#define	SEPA_NAME "flower"

#define	SEPA_DESC "flower cut separator"

#define	SEPA_PRIORITY 100000

#define	SEPA_FREQ 1

#define	SEPA_MAXBOUNDDIST 1.0

#define	SEPA_USESSUBSCIP FALSE

#define	SEPA_DELAY FALSE

#define	DEFAULT_MIN_OVERLAPS 1

#define	DEFAULT_SCAN_AND TRUE

#define	DEFAULT_SCAN_PRODUCT FALSE

#define	DEFAULT_MAX_STANDARD 0

#define	DEFAULT_MAX_ONEFLOWER 10000000

#define	DEFAULT_MAX_TWOFLOWER 10000000

#define	DEFAULT_DELAY_STANDARD FALSE

#define	DEFAULT_MAX_USELESS_ONEFLOWER 1

#define	DEFAULT_MAX_USELESS_TWOFLOWER 1

Functions
static SCIP_RETCODE	constructHypergraph (SCIP scip, SCIP_SEPADATA sepadata)
	constructs the hypergraph from transformed problem More...

static SCIP_RETCODE	prepareSeparation (SCIP scip, SCIP_SEPA sepa, SCIP_SOL *sol)

static SCIP_RETCODE	addCut (SCIP scip, SCIP_SOL sol, SCIP_ROW row, int pnumseparated, SCIP_RESULT presult, SCIP_Bool padded)
	add a generated cut row to the cut pool (for the root node) or as a row (otherwise) More...

static SCIP_RETCODE	separateStandard (SCIP scip, SCIP_SEPA sepa, SCIP_SOL sol, int maxnsepa, SCIP_RESULT presult)
	separate missing inequalities from the standard relaxation More...

static SCIP_RETCODE	separateOneFlower (SCIP scip, SCIP_SEPA sepa, SCIP_SOL sol, int maxnsepa, SCIP_RESULT presult)

static SCIP_RETCODE	separateTwoFlower (SCIP scip, SCIP_SEPA sepa, SCIP_SOL sol, int maxnsepa, SCIP_RESULT presult)

static SCIP_RETCODE	separate (SCIP scip, SCIP_SEPA sepa, SCIP_SOL sol, SCIP_RESULT result)
	Main separation function. More...

static	SCIP_DECL_SEPACOPY (sepaCopyFlower)

static	SCIP_DECL_SEPAFREE (sepaFreeFlower)

static	SCIP_DECL_SEPAINIT (sepaInitFlower)

static	SCIP_DECL_SEPAEXITSOL (sepaExitsolFlower)

static	SCIP_DECL_SEPAEXECLP (sepaExeclpFlower)

static	SCIP_DECL_SEPAEXECSOL (sepaExecsolFlower)

SCIP_RETCODE	SCIPincludeSepaFlower (SCIP *scip)

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME "flower"

Definition at line 42 of file sepa_flower.c.

◆ SEPA_DESC

#define SEPA_DESC "flower cut separator"

Definition at line 43 of file sepa_flower.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY 100000

Definition at line 44 of file sepa_flower.c.

◆ SEPA_FREQ

#define SEPA_FREQ 1

Definition at line 45 of file sepa_flower.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 1.0

Definition at line 46 of file sepa_flower.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 47 of file sepa_flower.c.

◆ SEPA_DELAY

#define SEPA_DELAY FALSE

should separation method be delayed if other separators found cuts?

Definition at line 48 of file sepa_flower.c.

◆ DEFAULT_MIN_OVERLAPS

#define DEFAULT_MIN_OVERLAPS 1

Definition at line 50 of file sepa_flower.c.

◆ DEFAULT_SCAN_AND

#define DEFAULT_SCAN_AND TRUE

Definition at line 51 of file sepa_flower.c.

◆ DEFAULT_SCAN_PRODUCT

#define DEFAULT_SCAN_PRODUCT FALSE

Definition at line 52 of file sepa_flower.c.

◆ DEFAULT_MAX_STANDARD

#define DEFAULT_MAX_STANDARD 0

Definition at line 53 of file sepa_flower.c.

◆ DEFAULT_MAX_ONEFLOWER

#define DEFAULT_MAX_ONEFLOWER 10000000

Definition at line 54 of file sepa_flower.c.

◆ DEFAULT_MAX_TWOFLOWER

#define DEFAULT_MAX_TWOFLOWER 10000000

Definition at line 55 of file sepa_flower.c.

◆ DEFAULT_DELAY_STANDARD

#define DEFAULT_DELAY_STANDARD FALSE

Definition at line 56 of file sepa_flower.c.

◆ DEFAULT_MAX_USELESS_ONEFLOWER

#define DEFAULT_MAX_USELESS_ONEFLOWER 1

Number of useless separation rounds after which we stop separating.

Definition at line 57 of file sepa_flower.c.

◆ DEFAULT_MAX_USELESS_TWOFLOWER

#define DEFAULT_MAX_USELESS_TWOFLOWER 1

Number of useless separation rounds after which we stop separating.

Definition at line 58 of file sepa_flower.c.

Function Documentation

◆ constructHypergraph()

static SCIP_RETCODE constructHypergraph	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata
	)

static

constructs the hypergraph from transformed problem

Parameters

scip	SCIP data structure.
sepadata	Sepadata.

Definition at line 135 of file sepa_flower.c.

References FALSE, NULL, SCIP_CALL, SCIP_ERROR, SCIP_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateClock(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPexpriterSetStagesDFS(), SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPfreeClock(), SCIPfreeExpriter(), SCIPgetClockTime(), SCIPgetCoefExprProduct(), SCIPgetExprAuxVarNonlinear(), SCIPgetExprNonlinear(), SCIPgetMessagehdlr(), SCIPgetNVars(), SCIPgetNVarsAnd(), SCIPgetResultantAnd(), SCIPgetVarsAnd(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPhypergraphAddEdge(), SCIPhypergraphAddVertex(), SCIPhypergraphComputeOverlaps(), SCIPhypergraphComputeOverlapsEdges(), SCIPhypergraphComputeVerticesEdges(), SCIPhypergraphCreate(), SCIPhypergraphGetNEdges(), SCIPhypergraphGetNOverlaps(), SCIPhypergraphGetNVertices(), SCIPhypergraphIsValid(), SCIPisExprProduct(), SCIPisLT(), SCIPmessagePrintInfo(), SCIPreallocBlockMemoryArray, SCIPstartClock(), and SCIPvarGetLbGlobal().

Referenced by separate().

◆ prepareSeparation()

static SCIP_RETCODE prepareSeparation	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol
	)

static

Parameters

scip	SCIP data structure.
sepa	Separator.
sol	Solution to be separated.

Definition at line 340 of file sepa_flower.c.

References MAX, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateClock(), SCIPdebugMsg, SCIPfeastol(), SCIPfreeClock(), SCIPgetClockTime(), SCIPgetLPObjval(), SCIPgetSolVal(), SCIPhypergraphEdgeData(), SCIPhypergraphEdgeSize(), SCIPhypergraphEdgesOverlapsBeyond(), SCIPhypergraphEdgesOverlapsFirst(), SCIPhypergraphEdgesOverlapsGetAtIndex(), SCIPhypergraphEdgeVertices(), SCIPhypergraphGetNEdges(), SCIPhypergraphGetNOverlaps(), SCIPhypergraphGetNVertices(), SCIPhypergraphOverlapData(), SCIPhypergraphOverlapSize(), SCIPhypergraphOverlapVertices(), SCIPhypergraphVertexData(), SCIPisGE(), SCIPsepaGetData(), SCIPsolGetOrigObj(), SCIPstartClock(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by separate().

◆ addCut()

static SCIP_RETCODE addCut	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_ROW *	row,
		int *	pnumseparated,
		SCIP_RESULT *	presult,
		SCIP_Bool *	padded
	)

static

add a generated cut row to the cut pool (for the root node) or as a row (otherwise)

Parameters

scip	SCIP datastructure.
sol	Solution.
row	Cutting plane.
pnumseparated	Pointer to store number of separated cuts.
presult	Pointer to store result.
padded	Pointer for storing whether it was added.

Definition at line 471 of file sepa_flower.c.

References FALSE, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_SEPARATED, SCIPaddPoolCut(), SCIPaddRow(), SCIPgetDepth(), SCIPisCutEfficacious(), and TRUE.

Referenced by separateOneFlower(), separateStandard(), and separateTwoFlower().

◆ separateStandard()

static SCIP_RETCODE separateStandard	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol,
		int	maxnsepa,
		SCIP_RESULT *	presult
	)

static

separate missing inequalities from the standard relaxation

Parameters

scip	SCIP datastructure.
sepa	Separator.
sol	Solution to be separated.
maxnsepa	Maximum number of separated inequalities.
presult	Pointer to store result.

Definition at line 514 of file sepa_flower.c.

References addCut(), FALSE, NULL, SCIP_CALL, SCIP_CUTOFF, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarsToRow(), SCIPcreateClock(), SCIPcreateEmptyRowSepa(), SCIPdebugMessage, SCIPfreeClock(), SCIPgetClockTime(), SCIPgetDepth(), SCIPhypergraphEdgeData(), SCIPhypergraphEdgeSize(), SCIPhypergraphEdgeVertices(), SCIPhypergraphGetNEdges(), SCIPhypergraphVertexData(), SCIPinfinity(), SCIPisEfficacious(), SCIPreleaseRow(), SCIPsepaGetData(), SCIPsnprintf(), SCIPstartClock(), and TRUE.

Referenced by separate().

◆ separateOneFlower()

static SCIP_RETCODE separateOneFlower	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol,
		int	maxnsepa,
		SCIP_RESULT *	presult
	)

static

Parameters

scip	SCIP data structure.
sepa	Separator.
sol	Solution to be separated.
maxnsepa	Maximum number of separated inequalities.
presult	Pointer to store result.

Definition at line 721 of file sepa_flower.c.

References addCut(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateClock(), SCIPcreateRowSepa(), SCIPdebugMessage, SCIPflushRowExtensions(), SCIPfreeClock(), SCIPgetClockTime(), SCIPgetDepth(), SCIPhypergraphEdgeData(), SCIPhypergraphEdgeSize(), SCIPhypergraphEdgesOverlapsBeyond(), SCIPhypergraphEdgesOverlapsFirst(), SCIPhypergraphEdgesOverlapsGetAtIndex(), SCIPhypergraphEdgeVertices(), SCIPhypergraphGetNEdges(), SCIPhypergraphOverlapData(), SCIPhypergraphOverlapSize(), SCIPhypergraphOverlapVertices(), SCIPhypergraphVertexData(), SCIPinfinity(), SCIPisEfficacious(), SCIPreleaseRow(), SCIPsepaGetData(), SCIPsnprintf(), SCIPstartClock(), and TRUE.

Referenced by separate().

◆ separateTwoFlower()

static SCIP_RETCODE separateTwoFlower	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol,
		int	maxnsepa,
		SCIP_RESULT *	presult
	)

static

Parameters

scip	SCIP datastructure.
sepa	Separator.
sol	Solution to be separated.
maxnsepa	Maximum number of separated inequalities.
presult	Pointer to store result.

Definition at line 1033 of file sepa_flower.c.

References addCut(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateClock(), SCIPcreateRowSepa(), SCIPdebugMessage, SCIPflushRowExtensions(), SCIPfreeClock(), SCIPgetClockTime(), SCIPgetDepth(), SCIPhypergraphEdgeData(), SCIPhypergraphEdgeSize(), SCIPhypergraphEdgesOverlapsBeyond(), SCIPhypergraphEdgesOverlapsFirst(), SCIPhypergraphEdgesOverlapsGetAtIndex(), SCIPhypergraphEdgeVertices(), SCIPhypergraphGetNEdges(), SCIPhypergraphOverlapData(), SCIPhypergraphOverlapsDisjoint(), SCIPhypergraphOverlapSize(), SCIPhypergraphOverlapVertices(), SCIPhypergraphVertexData(), SCIPinfinity(), SCIPisEfficacious(), SCIPreleaseRow(), SCIPsepaGetData(), SCIPsnprintf(), SCIPstartClock(), and TRUE.

Referenced by separate().

◆ separate()

static SCIP_RETCODE separate	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol,
		SCIP_RESULT *	result
	)

static

Main separation function.

Parameters

scip	SCIP data structure.
sepa	Separator.
sol	Solution to be separated (or `NULL` for the LP solution).
result	Pointer for storing the result.

Definition at line 1219 of file sepa_flower.c.

References constructHypergraph(), NULL, prepareSeparation(), SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SEPARATED, SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetNRuns(), SCIPgetSubscipDepth(), SCIPhypergraphFree(), SCIPhypergraphGetNOverlaps(), SCIPsepaGetData(), separateOneFlower(), separateStandard(), and separateTwoFlower().

Referenced by copyConsPseudoboolean(), createAndAddAndCons(), createAndAddLinearCons(), createBinaryConstraint(), createCipFormulation(), createCons(), createConsCumulative(), createConsSetppc(), createConsXorIntvar(), createIndicatorConstraint(), createNormalizedKnapsack(), createNormalizedLogicor(), createNormalizedSetppc(), extractGates(), getConstraint(), orbisackUpgrade(), priceAndCutLoop(), readConstraints(), readConstraintsRational(), readIndicators(), readObjective(), readQMatrix(), readRows(), readRowsExact(), readSOS(), readSos(), readSOScons(), SCIP_DECL_CONFLICTEXEC(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSPARSE(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXECSOL(), SCIPconsCopy(), SCIPconsCreate(), SCIPconsParse(), SCIPconsSetSeparated(), SCIPcopyConsExactLinear(), SCIPcopyConsLinear(), SCIPcreateCons(), SCIPcreateConsAnd(), SCIPcreateConsBounddisjunction(), SCIPcreateConsBounddisjunctionRedundant(), SCIPcreateConsCumulative(), SCIPcreateConsExactLinear(), SCIPcreateConsIndicator(), SCIPcreateConsIndicatorGeneric(), SCIPcreateConsIndicatorGenericLinCons(), SCIPcreateConsIndicatorGenericLinConsPure(), SCIPcreateConsIndicatorLinCons(), SCIPcreateConsIndicatorLinConsPure(), SCIPcreateConsKnapsack(), SCIPcreateConsLinear(), SCIPcreateConsLinking(), SCIPcreateConsLogicor(), SCIPcreateConsLOP(), SCIPcreateConsNonlinear(), SCIPcreateConsOptcumulative(), SCIPcreateConsOr(), SCIPcreateConsOrbisack(), SCIPcreateConsOrbitope(), SCIPcreateConsOrbitopeFull(), SCIPcreateConsOrbitopePP(), SCIPcreateConsPseudoboolean(), SCIPcreateConsPseudobooleanWithConss(), SCIPcreateConsQuadraticNonlinear(), SCIPcreateConsSetcover(), SCIPcreateConsSetpack(), SCIPcreateConsSetpart(), SCIPcreateConsSOS1(), SCIPcreateConsSOS2(), tsp::SCIPcreateConsSubtour(), SCIPcreateConsSuperindicator(), SCIPcreateConsSymresack(), SCIPcreateConsVarbound(), SCIPcreateConsXor(), SCIPcreateSymbreakCons(), SCIPgetConsCopy(), SCIPparseCons(), and SCIPsetConsSeparated().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyFlower )

static

copy method for separator plugins (called when SCIP copies plugins)

Definition at line 1336 of file sepa_flower.c.

References NULL, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_STRINGEQ, SCIPincludeSepaFlower(), SCIPsepaGetName(), and SEPA_NAME.

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeFlower )

static

Destructor of separator to free user data (called when SCIP is exiting).

Definition at line 1351 of file sepa_flower.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), and SCIPsepaSetData().

◆ SCIP_DECL_SEPAINIT()

static SCIP_DECL_SEPAINIT ( sepaInitFlower )

static

Initialization method of separator (called after problem was transformed).

Definition at line 1368 of file sepa_flower.c.

References SCIP_OKAY, and SCIPsepaGetData().

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolFlower )

static

solving process deinitialization method of separator (called before branch and bound process data is freed)

Definition at line 1383 of file sepa_flower.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPgetSubscipDepth(), SCIPhypergraphFree(), and SCIPsepaGetData().

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpFlower )

static

LP solution separation method of separator.

Definition at line 1403 of file sepa_flower.c.

References NULL, SCIP_CALL, SCIP_OKAY, and separate().

◆ SCIP_DECL_SEPAEXECSOL()

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolFlower )

static

arbitrary primal solution separation method of separator

Definition at line 1413 of file sepa_flower.c.

References SCIP_CALL, SCIP_OKAY, and separate().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ DEFAULT_MIN_OVERLAPS

◆ DEFAULT_SCAN_AND

◆ DEFAULT_SCAN_PRODUCT

◆ DEFAULT_MAX_STANDARD

◆ DEFAULT_MAX_ONEFLOWER

◆ DEFAULT_MAX_TWOFLOWER

◆ DEFAULT_DELAY_STANDARD

◆ DEFAULT_MAX_USELESS_ONEFLOWER

◆ DEFAULT_MAX_USELESS_TWOFLOWER

Function Documentation

◆ constructHypergraph()

◆ prepareSeparation()

◆ addCut()

◆ separateStandard()

◆ separateOneFlower()

◆ separateTwoFlower()

◆ separate()

◆ SCIP_DECL_SEPACOPY()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAINIT()

◆ SCIP_DECL_SEPAEXITSOL()

◆ SCIP_DECL_SEPAEXECLP()

◆ SCIP_DECL_SEPAEXECSOL()