Detailed Description
Gomory MIR Cuts.
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 "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 84 of file sepa_gomory.c.
Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAFREE(), and SCIPincludeSepaGomory().
◆ SEPA_DESC
#define SEPA_DESC "separator for Gomory mixed-integer and strong CG cuts from LP tableau rows" |
Definition at line 85 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGomory().
◆ SEPA_PRIORITY
#define SEPA_PRIORITY -1000 |
Definition at line 86 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGomory().
◆ SEPA_FREQ
#define SEPA_FREQ 10 |
Definition at line 87 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGomory().
◆ SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 88 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 89 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 90 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 92 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 93 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 94 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 95 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 96 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 97 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 98 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 99 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 100 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 101 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGomory().
◆ DEFAULT_SEPARATEROWS
#define DEFAULT_SEPARATEROWS TRUE |
separate rows with integral slack
Definition at line 102 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 103 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 104 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGomory().
◆ DEFAULT_TRYSTRONGCG
#define DEFAULT_TRYSTRONGCG TRUE |
try to generate strengthened Chvatal-Gomory cuts?
Definition at line 105 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGomory().
◆ DEFAULT_GENBOTHGOMSCG
#define DEFAULT_GENBOTHGOMSCG TRUE |
should both Gomory and strong CG cuts be generated (otherwise take best)
Definition at line 106 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGomory().
◆ DEFAULT_RANDSEED
#define DEFAULT_RANDSEED 53 |
initial random seed
Definition at line 107 of file sepa_gomory.c.
Referenced by SCIP_DECL_SEPAINIT().
◆ BOUNDSWITCH
#define BOUNDSWITCH 0.9999 |
threshold for bound switching - see SCIPcalcMIR()
Definition at line 109 of file sepa_gomory.c.
Referenced by SCIP_DECL_SEPAEXECLP().
◆ POSTPROCESS
#define POSTPROCESS TRUE |
apply postprocessing after MIR calculation - see SCIPcalcMIR()
Definition at line 110 of file sepa_gomory.c.
Referenced by SCIP_DECL_SEPAEXECLP().
◆ USEVBDS
#define USEVBDS TRUE |
use variable bounds - see SCIPcalcMIR()
Definition at line 111 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 112 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 113 of file sepa_gomory.c.
Referenced by evaluateCutNumerics().
◆ MAXAGGRLEN
#define MAXAGGRLEN | ( | nvars | ) | (0.1*(nvars)+1000) |
maximal length of base inequality
Definition at line 115 of file sepa_gomory.c.
Referenced by SCIP_DECL_SEPAEXECLP().
Function Documentation
◆ evaluateCutNumerics()
|
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 145 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 |
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 190 of file sepa_gomory.c.
References evaluateCutNumerics(), FALSE, NULL, SCIP_Bool, SCIP_CALL, 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 |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 338 of file sepa_gomory.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaGomory(), SCIPsepaGetName(), and SEPA_NAME.
◆ SCIP_DECL_SEPAFREE()
|
static |
destructor of separator to free user data (called when SCIP is exiting) ! [SnippetSepaFreeGomory]
Definition at line 353 of file sepa_gomory.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.
◆ SCIP_DECL_SEPAINIT()
|
static |
! [SnippetSepaFreeGomory] initialization method of separator (called after problem was transformed)
Definition at line 373 of file sepa_gomory.c.
References DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), and TRUE.
◆ SCIP_DECL_SEPAEXIT()
|
static |
deinitialization method of separator (called before transformed problem is freed)
Definition at line 388 of file sepa_gomory.c.
References NULL, SCIP_OKAY, SCIPfreeRandom(), and SCIPsepaGetData().
◆ SCIP_DECL_SEPAEXECLP() [1/2]
|
static |
LP solution separation method of separator
Definition at line 403 of file sepa_gomory.c.
References addCut(), BOUNDSWITCH, FALSE, FIXINTEGRALRHS, MAXAGGRLEN, NULL, POSTPROCESS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, 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(), SCIPisLPSolBasic(), SCIPisStopped(), SCIPrandomGetReal(), SCIProwIsIntegral(), SCIProwIsModifiable(), SCIPsepaGetData(), SCIPsepaGetFreq(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SCIPsortDownRealInt(), SCIPvarGetType(), SEPA_NAME, TRUE, and USEVBDS.
◆ SCIP_DECL_SEPAEXECLP() [2/2]
|
static |
LP solution separation method of dummy separator
Definition at line 698 of file sepa_gomory.c.
References NULL, SCIP_DIDNOTRUN, and SCIP_OKAY.
◆ SCIP_DECL_SEPAEXECSOL()
|
static |
arbitrary primal solution separation method of dummy separator
Definition at line 709 of file sepa_gomory.c.
References NULL, SCIP_DIDNOTRUN, and SCIP_OKAY.