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/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) |
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) |
#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.
#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.
#define SEPA_PRIORITY -1000 |
Definition at line 87 of file sepa_gomory.c.
#define SEPA_FREQ 10 |
Definition at line 88 of file sepa_gomory.c.
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 89 of file sepa_gomory.c.
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 90 of file sepa_gomory.c.
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 91 of file sepa_gomory.c.
#define DEFAULT_MAXROUNDS 5 |
maximal number of gomory separation rounds per node (-1: unlimited)
Definition at line 93 of file sepa_gomory.c.
#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.
#define DEFAULT_MAXSEPACUTS 50 |
maximal number of gomory cuts separated per separation round
Definition at line 95 of file sepa_gomory.c.
#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.
#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.
#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.
#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.
#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.
Referenced by SCIPincludeSepaGMI(), SCIPincludeSepaGomory(), and SCIPincludeSepaLagromory().
#define DEFAULT_MAKEINTEGRAL FALSE |
try to scale all cuts to integral coefficients
Definition at line 101 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGomory(), and SCIPincludeSepaLagromory().
#define DEFAULT_FORCECUTS TRUE |
if conversion to integral coefficients failed still consider the cut
Definition at line 102 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGomory(), and SCIPincludeSepaLagromory().
#define DEFAULT_SEPARATEROWS TRUE |
separate rows with integral slack
Definition at line 103 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGMI(), SCIPincludeSepaGomory(), and SCIPincludeSepaLagromory().
#define DEFAULT_DELAYEDCUTS FALSE |
should cuts be added to the delayed cut pool?
Definition at line 104 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGomory(), and SCIPincludeSepaLagromory().
#define DEFAULT_SIDETYPEBASIS TRUE |
choose side types of row (lhs/rhs) based on basis information?
Definition at line 105 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGomory(), and SCIPincludeSepaLagromory().
#define DEFAULT_TRYSTRONGCG TRUE |
try to generate strengthened Chvatal-Gomory cuts?
Definition at line 106 of file sepa_gomory.c.
Referenced by SCIPincludeSepaGomory().
#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.
Referenced by SCIPincludeSepaGomory().
#define DEFAULT_RANDSEED 53 |
initial random seed
Definition at line 108 of file sepa_gomory.c.
#define BOUNDSWITCH 0.9999 |
threshold for bound switching - see SCIPcalcMIR()
Definition at line 110 of file sepa_gomory.c.
#define POSTPROCESS TRUE |
apply postprocessing after MIR calculation - see SCIPcalcMIR()
Definition at line 111 of file sepa_gomory.c.
#define USEVBDS TRUE |
use variable bounds - see SCIPcalcMIR()
Definition at line 112 of file sepa_gomory.c.
#define FIXINTEGRALRHS FALSE |
try to generate an integral rhs - see SCIPcalcMIR()
Definition at line 113 of file sepa_gomory.c.
#define MAKECONTINTEGRAL FALSE |
convert continuous variable to integral variables in SCIPmakeRowIntegral()
Definition at line 114 of file sepa_gomory.c.
#define MAXAGGRLEN | ( | nvars | ) |
maximal length of base inequality
Definition at line 116 of file sepa_gomory.c.
|
static |
returns TRUE if the cut can be taken, otherwise FALSE if there some numerical evidences
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 assert(), FALSE, MAKECONTINTEGRAL, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPepsilon(), SCIPgetRowNumIntCols(), SCIPisInfinity(), SCIPmakeRowIntegral(), SCIProwGetNNonz(), SCIProwGetRank(), SCIProwGetRhs(), SCIPsumepsilon(), sepadata, and TRUE.
Referenced by addCut().
|
static |
add cut
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 assert(), c, cutoff, evaluateCutNumerics(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, 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(), sepadata, TRUE, and vars.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 339 of file sepa_gomory.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaGomory(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
destructor of separator to free user data (called when SCIP is exiting) ! [SnippetSepaFreeGomory]
Definition at line 354 of file sepa_gomory.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), SEPA_NAME, and sepadata.
|
static |
! [SnippetSepaFreeGomory] initialization method of separator (called after problem was transformed)
Definition at line 374 of file sepa_gomory.c.
References assert(), DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), sepadata, and TRUE.
|
static |
deinitialization method of separator (called before transformed problem is freed)
Definition at line 389 of file sepa_gomory.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeRandom(), SCIPsepaGetData(), and sepadata.
|
static |
LP solution separation method of separator
Definition at line 404 of file sepa_gomory.c.
References addCut(), assert(), BOUNDSWITCH, c, cutoff, depth, FALSE, FIXINTEGRALRHS, frac, i, MAXAGGRLEN, maxdepth, MIN, ncalls, NULL, nvars, POSTPROCESS, result, 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, sepadata, TRUE, USEVBDS, var, and vars.
|
static |
LP solution separation method of dummy separator
Definition at line 739 of file sepa_gomory.c.
References assert(), NULL, result, SCIP_DIDNOTRUN, and SCIP_OKAY.
|
static |
arbitrary primal solution separation method of dummy separator
Definition at line 750 of file sepa_gomory.c.
References assert(), NULL, result, SCIP_DIDNOTRUN, and SCIP_OKAY.