Scippy

SCIP

Solving Constraint Integer Programs

Macros | Functions
sepa_strongcg.c File Reference

Detailed Description

Strong CG Cuts (Letchford & Lodi)

Author
Kati Wolter
Tobias Achterberg

Definition in file sepa_strongcg.c.

#include <assert.h>
#include <string.h>
#include "scip/sepa_strongcg.h"
#include "scip/pub_misc.h"

Go to the source code of this file.

Macros

#define SEPA_NAME   "strongcg"
 
#define SEPA_DESC   "Strong CG cuts separator (Letchford and Lodi)"
 
#define SEPA_PRIORITY   -2000
 
#define SEPA_FREQ   0
 
#define SEPA_MAXBOUNDDIST   0.0
 
#define SEPA_USESSUBSCIP   FALSE
 
#define SEPA_DELAY   FALSE
 
#define DEFAULT_MAXROUNDS   5
 
#define DEFAULT_MAXROUNDSROOT   20
 
#define DEFAULT_MAXSEPACUTS   50
 
#define DEFAULT_MAXSEPACUTSROOT   500
 
#define DEFAULT_DYNAMICCUTS   TRUE
 
#define DEFAULT_MAXWEIGHTRANGE   1e+04
 
#define MAKECUTINTEGRAL   /* try to scale all cuts to integral coefficients */
 
#define FORCECUTINTEGRAL   /* discard cut if conversion to integral coefficients failed */
 
#define SEPARATEROWS   /* separate rows with integral slack */
 
#define BOUNDSWITCH   0.9999
 
#define USEVBDS   TRUE
 
#define ALLOWLOCAL   TRUE
 
#define MAKECONTINTEGRAL   FALSE
 
#define MINFRAC   0.05
 
#define MAXFRAC   0.95
 
#define MAXAGGRLEN(nvars)    (0.1*(nvars)+1000)
 

Functions

static SCIP_RETCODE storeCutInArrays (SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, char normtype, SCIP_VAR **cutvars, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact, SCIP_Real *cutnorm)
 
static SCIP_DECL_SEPACOPY (sepaCopyStrongcg)
 
static SCIP_DECL_SEPAFREE (sepaFreeStrongcg)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpStrongcg)
 
SCIP_RETCODE SCIPincludeSepaStrongcg (SCIP *scip)
 

Macro Definition Documentation

#define SEPA_NAME   "strongcg"

Definition at line 31 of file sepa_strongcg.c.

Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAFREE(), and SCIPincludeSepaStrongcg().

#define SEPA_DESC   "Strong CG cuts separator (Letchford and Lodi)"

Definition at line 32 of file sepa_strongcg.c.

Referenced by SCIPincludeSepaStrongcg().

#define SEPA_PRIORITY   -2000

Definition at line 33 of file sepa_strongcg.c.

Referenced by SCIPincludeSepaStrongcg().

#define SEPA_FREQ   0

Definition at line 34 of file sepa_strongcg.c.

Referenced by SCIPincludeSepaStrongcg().

#define SEPA_MAXBOUNDDIST   0.0

Definition at line 35 of file sepa_strongcg.c.

Referenced by SCIPincludeSepaStrongcg().

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 36 of file sepa_strongcg.c.

Referenced by SCIPincludeSepaStrongcg().

#define SEPA_DELAY   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 37 of file sepa_strongcg.c.

Referenced by SCIPincludeSepaStrongcg().

#define DEFAULT_MAXROUNDS   5

maximal number of strong CG separation rounds per node (-1: unlimited)

Definition at line 39 of file sepa_strongcg.c.

Referenced by SCIPincludeSepaStrongcg().

#define DEFAULT_MAXROUNDSROOT   20

maximal number of strong CG separation rounds in the root node (-1: unlimited)

Definition at line 40 of file sepa_strongcg.c.

Referenced by SCIPincludeSepaStrongcg().

#define DEFAULT_MAXSEPACUTS   50

maximal number of strong CG cuts separated per separation round

Definition at line 41 of file sepa_strongcg.c.

Referenced by SCIPincludeSepaStrongcg().

#define DEFAULT_MAXSEPACUTSROOT   500

maximal number of strong CG cuts separated per separation round in root node

Definition at line 42 of file sepa_strongcg.c.

Referenced by SCIPincludeSepaStrongcg().

#define DEFAULT_DYNAMICCUTS   TRUE

should generated cuts be removed from the LP if they are no longer tight?

Definition at line 43 of file sepa_strongcg.c.

Referenced by SCIPincludeSepaStrongcg().

#define DEFAULT_MAXWEIGHTRANGE   1e+04

maximal valid range max(|weights|)/min(|weights|) of row weights

Definition at line 44 of file sepa_strongcg.c.

Referenced by SCIPincludeSepaStrongcg().

#define MAKECUTINTEGRAL   /* try to scale all cuts to integral coefficients */

Definition at line 46 of file sepa_strongcg.c.

#define FORCECUTINTEGRAL   /* discard cut if conversion to integral coefficients failed */

Definition at line 48 of file sepa_strongcg.c.

#define SEPARATEROWS   /* separate rows with integral slack */

Definition at line 49 of file sepa_strongcg.c.

#define BOUNDSWITCH   0.9999

Definition at line 51 of file sepa_strongcg.c.

Referenced by SCIP_DECL_SEPAEXECLP().

#define USEVBDS   TRUE

Definition at line 52 of file sepa_strongcg.c.

Referenced by SCIP_DECL_SEPAEXECLP().

#define ALLOWLOCAL   TRUE

Definition at line 53 of file sepa_strongcg.c.

Referenced by SCIP_DECL_SEPAEXECLP().

#define MAKECONTINTEGRAL   FALSE

Definition at line 54 of file sepa_strongcg.c.

Referenced by SCIP_DECL_SEPAEXECLP().

#define MINFRAC   0.05

Definition at line 55 of file sepa_strongcg.c.

Referenced by SCIP_DECL_SEPAEXECLP().

#define MAXFRAC   0.95

Definition at line 56 of file sepa_strongcg.c.

Referenced by SCIP_DECL_SEPAEXECLP().

#define MAXAGGRLEN (   nvars)    (0.1*(nvars)+1000)

maximal length of base inequality

Definition at line 58 of file sepa_strongcg.c.

Referenced by SCIP_DECL_SEPAEXECLP().

Function Documentation

static SCIP_RETCODE storeCutInArrays ( SCIP *  scip,
int  nvars,
SCIP_VAR **  vars,
SCIP_Real *  cutcoefs,
SCIP_Real *  varsolvals,
char  normtype,
SCIP_VAR **  cutvars,
SCIP_Real *  cutvals,
int *  cutlen,
SCIP_Real *  cutact,
SCIP_Real *  cutnorm 
)
static

stores nonzero elements of dense coefficient vector as sparse vector, and calculates activity and norm

Parameters
scipSCIP data structure
nvarsnumber of problem variables
varsproblem variables
cutcoefsdense coefficient vector
varsolvalsdense variable LP solution vector
normtypetype of norm to use for efficacy norm calculation
cutvarsarray to store variables of sparse cut vector
cutvalsarray to store coefficients of sparse cut vector
cutlenpointer to store number of nonzero entries in cut
cutactpointer to store activity of cut
cutnormpointer to store norm of cut vector

Definition at line 80 of file sepa_strongcg.c.

References MAX, NULL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, and SCIPisZero().

Referenced by SCIP_DECL_SEPAEXECLP().

static SCIP_DECL_SEPACOPY ( sepaCopyStrongcg  )
static

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

Definition at line 193 of file sepa_strongcg.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaStrongcg(), SCIPsepaGetName(), and SEPA_NAME.

static SCIP_DECL_SEPAFREE ( sepaFreeStrongcg  )
static

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

Definition at line 207 of file sepa_strongcg.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.

static SCIP_DECL_SEPAEXECLP ( sepaExeclpStrongcg  )
static

LP solution separation method of separator

Definition at line 227 of file sepa_strongcg.c.

References ALLOWLOCAL, BOUNDSWITCH, FALSE, MAKECONTINTEGRAL, MAXAGGRLEN, MAXFRAC, MINFRAC, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_VARSTATUS_COLUMN, SCIP_VARTYPE_CONTINUOUS, SCIPaddCut(), SCIPaddPoolCut(), SCIPaddVarsToRow(), SCIPallocBufferArray, SCIPcalcStrongCG(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPcreateEmptyRowSepa(), SCIPdebugMessage, SCIPepsilon(), SCIPfeasFrac(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetCharParam(), SCIPgetCutEfficacy(), SCIPgetDepth(), SCIPgetLPBasisInd(), SCIPgetLPBInvRow(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetMaxDepth(), SCIPgetNCutsFound(), SCIPgetNLPBranchCands(), SCIPgetNLPs(), SCIPgetRowActivity(), SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetVarsData(), SCIPgetVarSol(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPisFeasGT(), SCIPisLPSolBasic(), SCIPisPositive(), SCIPisStopped(), SCIPmakeRowIntegral(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetName(), SCIProwGetNorm(), SCIProwGetRhs(), SCIProwIsIntegral(), SCIProwIsModifiable(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SCIPsepaWasLPDelayed(), SCIPsnprintf(), SCIPsumepsilon(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarIsIntegral(), SEPA_NAME, storeCutInArrays(), TRUE, and USEVBDS.

SCIP_RETCODE SCIPincludeSepaStrongcg ( SCIP *  scip)

creates the Strong CG cut separator and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 580 of file sepa_strongcg.c.

References DEFAULT_DYNAMICCUTS, DEFAULT_MAXROUNDS, DEFAULT_MAXROUNDSROOT, DEFAULT_MAXSEPACUTS, DEFAULT_MAXSEPACUTSROOT, DEFAULT_MAXWEIGHTRANGE, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPincludeSepaBasic(), SCIPsetSepaCopy(), SCIPsetSepaFree(), SEPA_DELAY, SEPA_DESC, SEPA_FREQ, SEPA_MAXBOUNDDIST, SEPA_NAME, SEPA_PRIORITY, SEPA_USESSUBSCIP, and TRUE.

Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeDefaultPlugins().