Detailed Description

Gomory MIR Cuts.

Author: Tobias Achterberg; Stefan Heinz; Domenico Salvagnin; Marc Pfetsch; Leona Gottwald

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/scip_var.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 "separator for Gomory mixed-integer and strong CG cuts from LP tableau rows"

#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_TRYSTRONGCG TRUE

#define	DEFAULT_GENBOTHGOMSCG 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_RETCODE	addCut (SCIP scip, SCIP_SEPADATA sepadata, SCIP_VAR *vars, int c, SCIP_Longint maxdnom, SCIP_Real maxscale, int cutnnz, int cutinds, SCIP_Real cutcoefs, SCIP_Real cutefficacy, SCIP_Real cutrhs, SCIP_Bool cutislocal, int cutrank, SCIP_Bool strongcg, SCIP_Bool cutoff, int *naddedcuts)

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)

static	SCIP_DECL_SEPAEXECLP (sepaExeclpDummy)

static	SCIP_DECL_SEPAEXECSOL (sepaExecsolDummy)

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 85 of file sepa_gomory.c.

◆ SEPA_DESC

#define SEPA_DESC "separator for Gomory mixed-integer and strong CG cuts from LP tableau rows"

Definition at line 86 of file sepa_gomory.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY -1000

Definition at line 87 of file sepa_gomory.c.

◆ SEPA_FREQ

#define SEPA_FREQ 10

Definition at line 88 of file sepa_gomory.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 1.0

Definition at line 89 of file sepa_gomory.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 90 of file sepa_gomory.c.

◆ SEPA_DELAY

#define SEPA_DELAY FALSE

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

Definition at line 91 of file sepa_gomory.c.

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS 5

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

Definition at line 93 of file sepa_gomory.c.

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT 10

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

Definition at line 94 of file sepa_gomory.c.

◆ DEFAULT_MAXSEPACUTS

#define DEFAULT_MAXSEPACUTS 50

maximal number of gomory cuts separated per separation round

Definition at line 95 of file sepa_gomory.c.

◆ DEFAULT_MAXSEPACUTSROOT

#define DEFAULT_MAXSEPACUTSROOT 200

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

Definition at line 96 of file sepa_gomory.c.

◆ 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 97 of file sepa_gomory.c.

◆ DEFAULT_MAXRANKINTEGRAL

#define DEFAULT_MAXRANKINTEGRAL -1

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

Definition at line 98 of file sepa_gomory.c.

◆ DEFAULT_DYNAMICCUTS

#define DEFAULT_DYNAMICCUTS TRUE

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

Definition at line 99 of file sepa_gomory.c.

◆ DEFAULT_AWAY

#define DEFAULT_AWAY 0.01

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

Definition at line 100 of file sepa_gomory.c.

◆ DEFAULT_MAKEINTEGRAL

#define DEFAULT_MAKEINTEGRAL FALSE

try to scale all cuts to integral coefficients

Definition at line 101 of file sepa_gomory.c.

◆ DEFAULT_FORCECUTS

#define DEFAULT_FORCECUTS TRUE

if conversion to integral coefficients failed still consider the cut

Definition at line 102 of file sepa_gomory.c.

◆ DEFAULT_SEPARATEROWS

#define DEFAULT_SEPARATEROWS TRUE

separate rows with integral slack

Definition at line 103 of file sepa_gomory.c.

◆ DEFAULT_DELAYEDCUTS

#define DEFAULT_DELAYEDCUTS FALSE

should cuts be added to the delayed cut pool?

Definition at line 104 of file sepa_gomory.c.

◆ DEFAULT_SIDETYPEBASIS

#define DEFAULT_SIDETYPEBASIS TRUE

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

Definition at line 105 of file sepa_gomory.c.

◆ DEFAULT_TRYSTRONGCG

#define DEFAULT_TRYSTRONGCG TRUE

try to generate strengthened Chvatal-Gomory cuts?

Definition at line 106 of file sepa_gomory.c.

◆ DEFAULT_GENBOTHGOMSCG

#define DEFAULT_GENBOTHGOMSCG TRUE

should both Gomory and strong CG cuts be generated (otherwise take best)

Definition at line 107 of file sepa_gomory.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 53

initial random seed

Definition at line 108 of file sepa_gomory.c.

◆ BOUNDSWITCH

#define BOUNDSWITCH 0.9999

threshold for bound switching - see SCIPcalcMIR()

Definition at line 110 of file sepa_gomory.c.

◆ POSTPROCESS

#define POSTPROCESS TRUE

apply postprocessing after MIR calculation - see SCIPcalcMIR()

Definition at line 111 of file sepa_gomory.c.

◆ USEVBDS

#define USEVBDS TRUE

use variable bounds - see SCIPcalcMIR()

Definition at line 112 of file sepa_gomory.c.

◆ FIXINTEGRALRHS

#define FIXINTEGRALRHS FALSE

try to generate an integral rhs - see SCIPcalcMIR()

Definition at line 113 of file sepa_gomory.c.

◆ MAKECONTINTEGRAL

#define MAKECONTINTEGRAL FALSE

convert continuous variable to integral variables in SCIPmakeRowIntegral()

Definition at line 114 of file sepa_gomory.c.

◆ MAXAGGRLEN

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

maximal length of base inequality

Definition at line 116 of file sepa_gomory.c.

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

scip	SCIP data structure
sepadata	data of the separator
cut	cut to check
maxdnom	maximal denominator to use for scaling
maxscale	maximal scaling factor
useful	pointer to store if the cut is useful

Definition at line 146 of file sepa_gomory.c.

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

Referenced by addCut().

◆ addCut()

static SCIP_RETCODE addCut	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_VAR **	vars,
		int	c,
		SCIP_Longint	maxdnom,
		SCIP_Real	maxscale,
		int	cutnnz,
		int *	cutinds,
		SCIP_Real *	cutcoefs,
		SCIP_Real	cutefficacy,
		SCIP_Real	cutrhs,
		SCIP_Bool	cutislocal,
		int	cutrank,
		SCIP_Bool	strongcg,
		SCIP_Bool *	cutoff,
		int *	naddedcuts
	)

static

add cut

Parameters

scip	SCIP instance
sepadata	separator data
vars	array of variables
c	index of basic variable (< 0 for slack variables)
maxdnom	maximal denominator to use for scaling
maxscale	maximal scaling factor
cutnnz	number of nonzeros in cut
cutinds	variable indices in cut
cutcoefs	cut cofficients
cutefficacy	cut efficacy
cutrhs	rhs of cut
cutislocal	whether cut is local
cutrank	rank of cut
strongcg	whether the cut arises from the strong-CG procedure
cutoff	pointer to store whether a cutoff appeared
naddedcuts	pointer to store number of added cuts

Definition at line 191 of file sepa_gomory.c.

References evaluateCutNumerics(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddDelayedPoolCut(), SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPgetCutEfficacy(), SCIPgetNLPs(), SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPinfinity(), SCIPisCutNew(), SCIPisEfficacious(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetNorm(), SCIProwGetRhs(), SCIPsnprintf(), 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 339 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 354 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 374 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 389 of file sepa_gomory.c.

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

◆ SCIP_DECL_SEPAEXECLP() [1/2]

static SCIP_DECL_SEPAEXECLP ( sepaExeclpGomory )

static

LP solution separation method of separator

Definition at line 404 of file sepa_gomory.c.

References addCut(), BOUNDSWITCH, FALSE, FIXINTEGRALRHS, MAXAGGRLEN, MIN, NULL, POSTPROCESS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_VARTYPE_CONTINUOUS, SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPaggrRowSumRows(), SCIPallocBufferArray, SCIPcalcMIR(), SCIPcalcStrongCG(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPdebugMsg, SCIPfeasFrac(), SCIPfreeBufferArray, SCIPgetLPBasisInd(), SCIPgetLPBInvRow(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetMaxDepth(), SCIPgetNCutsFound(), SCIPgetNLPBranchCands(), SCIPgetRowActivity(), SCIPgetVarsData(), SCIPincVarGMISumScore(), SCIPisEfficacious(), SCIPisLPSolBasic(), SCIPisStopped(), SCIPrandomGetReal(), SCIProwIsIntegral(), SCIProwIsModifiable(), SCIPsepaGetData(), SCIPsepaGetFreq(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SCIPsetVarLastGMIScore(), SCIPsortDownRealInt(), SCIPvarGetType(), SEPA_NAME, TRUE, and USEVBDS.

◆ SCIP_DECL_SEPAEXECLP() [2/2]

static SCIP_DECL_SEPAEXECLP ( sepaExeclpDummy )

static

LP solution separation method of dummy separator

Definition at line 739 of file sepa_gomory.c.

References NULL, SCIP_DIDNOTRUN, and SCIP_OKAY.

◆ SCIP_DECL_SEPAEXECSOL()

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolDummy )

static

arbitrary primal solution separation method of dummy separator

Definition at line 750 of file sepa_gomory.c.

References NULL, SCIP_DIDNOTRUN, and SCIP_OKAY.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ DEFAULT_MAXROUNDS

◆ DEFAULT_MAXROUNDSROOT

◆ DEFAULT_MAXSEPACUTS

◆ DEFAULT_MAXSEPACUTSROOT

◆ DEFAULT_MAXRANK

◆ DEFAULT_MAXRANKINTEGRAL

◆ DEFAULT_DYNAMICCUTS

◆ DEFAULT_AWAY

◆ DEFAULT_MAKEINTEGRAL

◆ DEFAULT_FORCECUTS

◆ DEFAULT_SEPARATEROWS

◆ DEFAULT_DELAYEDCUTS

◆ DEFAULT_SIDETYPEBASIS

◆ DEFAULT_TRYSTRONGCG

◆ DEFAULT_GENBOTHGOMSCG

◆ DEFAULT_RANDSEED

◆ BOUNDSWITCH

◆ POSTPROCESS

◆ USEVBDS

◆ FIXINTEGRALRHS

◆ MAKECONTINTEGRAL

◆ MAXAGGRLEN

Function Documentation

◆ evaluateCutNumerics()

◆ addCut()

◆ SCIP_DECL_SEPACOPY()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAINIT()

◆ SCIP_DECL_SEPAEXIT()

◆ SCIP_DECL_SEPAEXECLP() [1/2]

◆ SCIP_DECL_SEPAEXECLP() [2/2]

◆ SCIP_DECL_SEPAEXECSOL()