SCIP Doxygen Documentation
Loading...
Searching...
No Matches
sepa_flower.c File Reference
Implementation files (.c files) » SCIP Default Plugins » Default Separators

Detailed Description

flower-inequality separator

Author
Matthias Walter

Definition in file sepa_flower.c.

#include <assert.h>
#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
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)
static SCIP_RETCODE separateStandard (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, int maxnsepa, SCIP_RESULT *presult)
 separate missing inequalities from the standard relaxation
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.
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 44 of file sepa_flower.c.

◆ SEPA_DESC

#define SEPA_DESC   "flower cut separator"

Definition at line 45 of file sepa_flower.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   100000

Definition at line 46 of file sepa_flower.c.

◆ SEPA_FREQ

#define SEPA_FREQ   1

Definition at line 47 of file sepa_flower.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 48 of file sepa_flower.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 49 of file sepa_flower.c.

◆ SEPA_DELAY

#define SEPA_DELAY   FALSE

should separation method be delayed if other separators found cuts?

Definition at line 50 of file sepa_flower.c.

◆ DEFAULT_MIN_OVERLAPS

#define DEFAULT_MIN_OVERLAPS   1

Definition at line 52 of file sepa_flower.c.

Referenced by SCIPincludeSepaFlower().

◆ DEFAULT_SCAN_AND

#define DEFAULT_SCAN_AND   TRUE

Definition at line 53 of file sepa_flower.c.

Referenced by SCIPincludeSepaFlower().

◆ DEFAULT_SCAN_PRODUCT

#define DEFAULT_SCAN_PRODUCT   FALSE

Definition at line 54 of file sepa_flower.c.

Referenced by SCIPincludeSepaFlower().

◆ DEFAULT_MAX_STANDARD

#define DEFAULT_MAX_STANDARD   0

Definition at line 55 of file sepa_flower.c.

Referenced by SCIPincludeSepaFlower().

◆ DEFAULT_MAX_ONEFLOWER

#define DEFAULT_MAX_ONEFLOWER   10000000

Definition at line 56 of file sepa_flower.c.

Referenced by SCIPincludeSepaFlower().

◆ DEFAULT_MAX_TWOFLOWER

#define DEFAULT_MAX_TWOFLOWER   10000000

Definition at line 57 of file sepa_flower.c.

Referenced by SCIPincludeSepaFlower().

◆ DEFAULT_DELAY_STANDARD

#define DEFAULT_DELAY_STANDARD   FALSE

Definition at line 58 of file sepa_flower.c.

Referenced by SCIPincludeSepaFlower().

◆ DEFAULT_MAX_USELESS_ONEFLOWER

#define DEFAULT_MAX_USELESS_ONEFLOWER   1

Number of useless separation rounds after which we stop separating.

Definition at line 59 of file sepa_flower.c.

Referenced by SCIPincludeSepaFlower().

◆ DEFAULT_MAX_USELESS_TWOFLOWER

#define DEFAULT_MAX_USELESS_TWOFLOWER   1

Number of useless separation rounds after which we stop separating.

Definition at line 60 of file sepa_flower.c.

Referenced by SCIPincludeSepaFlower().

Function Documentation

◆ constructHypergraph()

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

constructs the hypergraph from transformed problem

Parameters
scipSCIP data structure.
sepadataSepadata.

Definition at line 137 of file sepa_flower.c.

References assert(), c, FALSE, i, NULL, nvars, 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(), SCIPvarGetLbGlobal(), sepadata, and vars.

Referenced by separate().

◆ prepareSeparation()

SCIP_RETCODE prepareSeparation ( SCIP * scip,
SCIP_SEPA * sepa,
SCIP_SOL * sol )
static
Parameters
scipSCIP data structure.
sepaSeparator.
solSolution to be separated.

Definition at line 342 of file sepa_flower.c.

References assert(), i, 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(), SCIPvarGetUbLocal(), sepadata, and sol.

Referenced by separate().

◆ addCut()

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
scipSCIP datastructure.
solSolution.
rowCutting plane.
pnumseparatedPointer to store number of separated cuts.
presultPointer to store result.
paddedPointer for storing whether it was added.

Definition at line 473 of file sepa_flower.c.

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

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

◆ separateStandard()

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
scipSCIP datastructure.
sepaSeparator.
solSolution to be separated.
maxnsepaMaximum number of separated inequalities.
presultPointer to store result.

Definition at line 516 of file sepa_flower.c.

References addCut(), assert(), FALSE, i, 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(), sepadata, sol, TRUE, and vars.

Referenced by separate().

◆ separateOneFlower()

SCIP_RETCODE separateOneFlower ( SCIP * scip,
SCIP_SEPA * sepa,
SCIP_SOL * sol,
int maxnsepa,
SCIP_RESULT * presult )
static
Parameters
scipSCIP data structure.
sepaSeparator.
solSolution to be separated.
maxnsepaMaximum number of separated inequalities.
presultPointer to store result.

Definition at line 723 of file sepa_flower.c.

References addCut(), assert(), FALSE, i, 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(), sepadata, sol, and TRUE.

Referenced by separate().

◆ separateTwoFlower()

SCIP_RETCODE separateTwoFlower ( SCIP * scip,
SCIP_SEPA * sepa,
SCIP_SOL * sol,
int maxnsepa,
SCIP_RESULT * presult )
static
Parameters
scipSCIP datastructure.
sepaSeparator.
solSolution to be separated.
maxnsepaMaximum number of separated inequalities.
presultPointer to store result.

Definition at line 1035 of file sepa_flower.c.

References addCut(), assert(), FALSE, i, 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(), sepadata, sol, and TRUE.

Referenced by separate().

◆ separate()

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

Main separation function.

Parameters
scipSCIP data structure.
sepaSeparator.
solSolution to be separated (or NULL for the LP solution).
resultPointer for storing the result.

Definition at line 1221 of file sepa_flower.c.

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

Referenced by copyConsPseudoboolean(), createAndAddAndCons(), createAndAddLinearCons(), createBinaryConstraint(), createCipFormulation(), createCons(), createConsCumulative(), createConsSetppc(), createConsXorIntvar(), createIndicatorConstraint(), createNormalizedKnapsack(), createNormalizedLogicor(), createNormalizedSetppc(), extractGates(), getConstraint(), orbisackUpgrade(), priceAndCutLoop(), readConstraints(), readConstraints(), readConstraints(), readConstraintsRational(), readIndicators(), readObjective(), readQMatrix(), readRows(), readRowsExact(), readSOS(), readSos(), readSOScons(), SCIP_DECL_CONFLICTEXEC(), SCIP_DECL_CONFLICTEXEC(), SCIP_DECL_CONFLICTEXEC(), SCIP_DECL_CONFLICTEXEC(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPARSE(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXECSOL(), SCIPconsCopy(), SCIPconsCreate(), SCIPconsParse(), SCIPconsSetSeparated(), SCIPcopyConsExactLinear(), SCIPcopyConsLinear(), SCIPcreateCons(), SCIPcreateConsAnd(), SCIPcreateConsBounddisjunction(), SCIPcreateConsBounddisjunctionRedundant(), SCIPcreateConsCardinality(), 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()

SCIP_DECL_SEPACOPY ( sepaCopyFlower )
static

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

Definition at line 1338 of file sepa_flower.c.

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

◆ SCIP_DECL_SEPAFREE()

SCIP_DECL_SEPAFREE ( sepaFreeFlower )
static

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

Definition at line 1352 of file sepa_flower.c.

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

◆ SCIP_DECL_SEPAINIT()

SCIP_DECL_SEPAINIT ( sepaInitFlower )
static

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

Definition at line 1369 of file sepa_flower.c.

References assert(), SCIP_OKAY, SCIPsepaGetData(), and sepadata.

◆ SCIP_DECL_SEPAEXITSOL()

SCIP_DECL_SEPAEXITSOL ( sepaExitsolFlower )
static

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

Definition at line 1384 of file sepa_flower.c.

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

◆ SCIP_DECL_SEPAEXECLP()

SCIP_DECL_SEPAEXECLP ( sepaExeclpFlower )
static

LP solution separation method of separator.

Definition at line 1404 of file sepa_flower.c.

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

◆ SCIP_DECL_SEPAEXECSOL()

SCIP_DECL_SEPAEXECSOL ( sepaExecsolFlower )
static

arbitrary primal solution separation method of separator

Definition at line 1414 of file sepa_flower.c.

References result, SCIP_CALL, SCIP_OKAY, separate(), and sol.