Scippy

SCIP

Solving Constraint Integer Programs

sepa_gomory.c File Reference

Detailed Description

Gomory MIR Cuts.

Author
Tobias Achterberg
Stefan Heinz
Domenico Salvagnin
Marc Pfetsch

Definition in file sepa_gomory.c.

#include "blockmemshell/memory.h"
#include "scip/cuts.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_sepa.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sepa.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/sepa_gomory.h"
#include <string.h>

Go to the source code of this file.

Macros

#define SEPA_NAME   "gomory"
 
#define SEPA_DESC   "Gomory MIR cuts separator"
 
#define SEPA_PRIORITY   -1000
 
#define SEPA_FREQ   10
 
#define SEPA_MAXBOUNDDIST   1.0
 
#define SEPA_USESSUBSCIP   FALSE
 
#define SEPA_DELAY   FALSE
 
#define DEFAULT_MAXROUNDS   5
 
#define DEFAULT_MAXROUNDSROOT   10
 
#define DEFAULT_MAXSEPACUTS   50
 
#define DEFAULT_MAXSEPACUTSROOT   200
 
#define DEFAULT_MAXRANK   -1
 
#define DEFAULT_MAXRANKINTEGRAL   -1
 
#define DEFAULT_DYNAMICCUTS   TRUE
 
#define DEFAULT_AWAY   0.01
 
#define DEFAULT_MAKEINTEGRAL   FALSE
 
#define DEFAULT_FORCECUTS   TRUE
 
#define DEFAULT_SEPARATEROWS   TRUE
 
#define DEFAULT_DELAYEDCUTS   FALSE
 
#define DEFAULT_SIDETYPEBASIS   TRUE
 
#define DEFAULT_RANDSEED   53
 
#define BOUNDSWITCH   0.9999
 
#define POSTPROCESS   TRUE
 
#define USEVBDS   TRUE
 
#define FIXINTEGRALRHS   FALSE
 
#define MAKECONTINTEGRAL   FALSE
 
#define MAXAGGRLEN(nvars)   (0.1*(nvars)+1000)
 

Functions

static SCIP_RETCODE evaluateCutNumerics (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW *cut, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool *useful)
 
static SCIP_DECL_SEPACOPY (sepaCopyGomory)
 
static SCIP_DECL_SEPAFREE (sepaFreeGomory)
 
static SCIP_DECL_SEPAINIT (sepaInitGomory)
 
static SCIP_DECL_SEPAEXIT (sepaExitGomory)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpGomory)
 
SCIP_RETCODE SCIPincludeSepaGomory (SCIP *scip)
 

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME   "gomory"

Max y Subject to c1: -x + y <= 1 c2: 2x + 3y <= 12 c3: 3x + 2y <= 12 Bounds 0 <= x 0 <= y General x y END

Definition at line 73 of file sepa_gomory.c.

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

◆ SEPA_DESC

#define SEPA_DESC   "Gomory MIR cuts separator"

Definition at line 74 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   -1000

Definition at line 75 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ SEPA_FREQ

#define SEPA_FREQ   10

Definition at line 76 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 77 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 78 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ SEPA_DELAY

#define SEPA_DELAY   FALSE

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

Definition at line 79 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS   5

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

Definition at line 81 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT   10

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

Definition at line 82 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_MAXSEPACUTS

#define DEFAULT_MAXSEPACUTS   50

maximal number of gomory cuts separated per separation round

Definition at line 83 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_MAXSEPACUTSROOT

#define DEFAULT_MAXSEPACUTSROOT   200

maximal number of gomory cuts separated per separation round in root node

Definition at line 84 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_MAXRANK

#define DEFAULT_MAXRANK   -1

maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited)

Definition at line 85 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_MAXRANKINTEGRAL

#define DEFAULT_MAXRANKINTEGRAL   -1

maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited)

Definition at line 86 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_DYNAMICCUTS

#define DEFAULT_DYNAMICCUTS   TRUE

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

Definition at line 87 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_AWAY

#define DEFAULT_AWAY   0.01

minimal integrality violation of a basis variable in order to try Gomory cut

Definition at line 88 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_MAKEINTEGRAL

#define DEFAULT_MAKEINTEGRAL   FALSE

try to scale all cuts to integral coefficients

Definition at line 89 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_FORCECUTS

#define DEFAULT_FORCECUTS   TRUE

if conversion to integral coefficients failed still consider the cut

Definition at line 90 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_SEPARATEROWS

#define DEFAULT_SEPARATEROWS   TRUE

separate rows with integral slack

Definition at line 91 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_DELAYEDCUTS

#define DEFAULT_DELAYEDCUTS   FALSE

should cuts be added to the delayed cut pool?

Definition at line 92 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_SIDETYPEBASIS

#define DEFAULT_SIDETYPEBASIS   TRUE

choose side types of row (lhs/rhs) based on basis information?

Definition at line 93 of file sepa_gomory.c.

Referenced by SCIPincludeSepaGomory().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   53

initial random seed

Definition at line 94 of file sepa_gomory.c.

Referenced by SCIP_DECL_SEPAINIT().

◆ BOUNDSWITCH

#define BOUNDSWITCH   0.9999

threshold for bound switching - see SCIPcalcMIR()

Definition at line 96 of file sepa_gomory.c.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ POSTPROCESS

#define POSTPROCESS   TRUE

apply postprocessing after MIR calculation - see SCIPcalcMIR()

Definition at line 97 of file sepa_gomory.c.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ USEVBDS

#define USEVBDS   TRUE

use variable bounds - see SCIPcalcMIR()

Definition at line 98 of file sepa_gomory.c.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ FIXINTEGRALRHS

#define FIXINTEGRALRHS   FALSE

try to generate an integral rhs - see SCIPcalcMIR()

Definition at line 99 of file sepa_gomory.c.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ MAKECONTINTEGRAL

#define MAKECONTINTEGRAL   FALSE

convert continuous variable to integral variables in SCIPmakeRowIntegral()

Definition at line 100 of file sepa_gomory.c.

Referenced by evaluateCutNumerics().

◆ MAXAGGRLEN

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

maximal length of base inequality

Definition at line 102 of file sepa_gomory.c.

Referenced by SCIP_DECL_SEPAEXECLP().

Function Documentation

◆ evaluateCutNumerics()

static SCIP_RETCODE evaluateCutNumerics ( SCIP scip,
SCIP_SEPADATA sepadata,
SCIP_ROW cut,
SCIP_Longint  maxdnom,
SCIP_Real  maxscale,
SCIP_Bool useful 
)
static

returns TRUE if the cut can be taken, otherwise FALSE if there some numerical evidences

Parameters
scipSCIP data structure
sepadatadata of the separator
cutcut to check
maxdnommaximal denominator to use for scaling
maxscalemaximal scaling factor
usefulpointer to store if the cut is useful

Definition at line 128 of file sepa_gomory.c.

References FALSE, MAKECONTINTEGRAL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPepsilon(), SCIPgetRowNumIntCols(), SCIPisInfinity(), SCIPmakeRowIntegral(), SCIProwGetNNonz(), SCIProwGetRank(), SCIProwGetRhs(), SCIPsumepsilon(), and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyGomory  )
static

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

Definition at line 177 of file sepa_gomory.c.

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

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeGomory  )
static

destructor of separator to free user data (called when SCIP is exiting) ! [SnippetSepaFreeGomory]

Definition at line 192 of file sepa_gomory.c.

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

◆ SCIP_DECL_SEPAINIT()

static SCIP_DECL_SEPAINIT ( sepaInitGomory  )
static

! [SnippetSepaFreeGomory] initialization method of separator (called after problem was transformed)

Definition at line 212 of file sepa_gomory.c.

References DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), and TRUE.

◆ SCIP_DECL_SEPAEXIT()

static SCIP_DECL_SEPAEXIT ( sepaExitGomory  )
static

deinitialization method of separator (called before transformed problem is freed)

Definition at line 227 of file sepa_gomory.c.

References NULL, SCIP_OKAY, SCIPfreeRandom(), and SCIPsepaGetData().

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpGomory  )
static

LP solution separation method of separator

Definition at line 242 of file sepa_gomory.c.

References BOUNDSWITCH, evaluateCutNumerics(), FALSE, FIXINTEGRALRHS, MAXAGGRLEN, MIN, NULL, POSTPROCESS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_VARTYPE_CONTINUOUS, SCIPaddDelayedPoolCut(), SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPaggrRowSumRows(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPcalcMIR(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPfeasFrac(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetCutEfficacy(), SCIPgetDepth(), SCIPgetLPBasisInd(), SCIPgetLPBInvRow(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetMaxDepth(), SCIPgetNCutsFound(), SCIPgetNLPBranchCands(), SCIPgetNLPs(), SCIPgetRowActivity(), SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetVarsData(), SCIPinfinity(), SCIPisCutNew(), SCIPisEfficacious(), SCIPisFeasNegative(), SCIPisInfinity(), SCIPisLPSolBasic(), SCIPisStopped(), SCIPrandomGetReal(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNorm(), SCIProwGetRhs(), SCIProwIsIntegral(), SCIProwIsModifiable(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SCIPsepaWasLPDelayed(), SCIPsnprintf(), SCIPsortDownRealInt(), SCIPvarGetName(), SCIPvarGetType(), SEPA_NAME, TRUE, and USEVBDS.