Scippy

SCIP

Solving Constraint Integer Programs

sepa_aggregation.c File Reference

Detailed Description

flow cover and complemented mixed integer rounding cuts separator (Marchand's version)

Author
Robert Lion Gottwald
Kati Wolter
Tobias Achterberg

For an overview see:

Marchand, H., & Wolsey, L. A. (2001).
Aggregation and mixed integer rounding to solve MIPs.
Operations research, 49(3), 363-371.

Some remarks:

  • In general, continuous variables are less prefered than integer variables, since their cut coefficient is worse.
  • We seek for aggregations that project out continuous variables that are far away from their bound, since if it is at its bound then it doesn't contribute to the violation
  • These aggregations are also useful for the flowcover separation, so after building an aggregation we try to generate a MIR cut and a flowcover cut.
  • We only keep the best cut.

Definition in file sepa_aggregation.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_sepa.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include "scip/sepa_aggregation.h"
#include <string.h>

Go to the source code of this file.

Data Structures

struct  AggregationData
 

Macros

#define SEPA_NAME   "aggregation"
 
#define SEPA_DESC   "aggregation heuristic for complemented mixed integer rounding cuts and flowcover cuts"
 
#define SEPA_PRIORITY   -3000
 
#define SEPA_FREQ   10
 
#define SEPA_MAXBOUNDDIST   1.0
 
#define SEPA_USESSUBSCIP   FALSE
 
#define SEPA_DELAY   FALSE
 
#define DEFAULT_MAXROUNDS   -1
 
#define DEFAULT_MAXROUNDSROOT   -1
 
#define DEFAULT_MAXTRIES   200
 
#define DEFAULT_MAXTRIESROOT   -1
 
#define DEFAULT_MAXFAILS   20
 
#define DEFAULT_MAXFAILSROOT   100
 
#define DEFAULT_MAXAGGRS   3
 
#define DEFAULT_MAXAGGRSROOT   6
 
#define DEFAULT_MAXSEPACUTS   100
 
#define DEFAULT_MAXSEPACUTSROOT   500
 
#define DEFAULT_MAXSLACK   0.0
 
#define DEFAULT_MAXSLACKROOT   0.1
 
#define DEFAULT_DENSITYSCORE   1e-4
 
#define DEFAULT_SLACKSCORE   1e-3
 
#define DEFAULT_MAXAGGDENSITY   0.20
 
#define DEFAULT_MAXROWDENSITY   0.05
 
#define DEFAULT_DENSITYOFFSET   100
 
#define DEFAULT_MAXROWFAC   1e+4
 
#define DEFAULT_MAXTESTDELTA   -1
 
#define DEFAULT_AGGRTOL   1e-2
 
#define DEFAULT_TRYNEGSCALING   TRUE
 
#define DEFAULT_FIXINTEGRALRHS   TRUE
 
#define DEFAULT_DYNAMICCUTS   TRUE
 
#define BOUNDSWITCH   0.5
 
#define POSTPROCESS   TRUE
 
#define USEVBDS   TRUE
 
#define MINFRAC   0.05
 
#define MAXFRAC   0.999
 
#define MAKECONTINTEGRAL   FALSE
 
#define IMPLINTSARECONT
 

Typedefs

typedef struct AggregationData AGGREGATIONDATA
 

Functions

static SCIP_RETCODE addCut (SCIP *scip, SCIP_SOL *sol, SCIP_SEPA *sepa, SCIP_Bool makeintegral, SCIP_Real *cutcoefs, int *cutinds, int cutnnz, SCIP_Real cutrhs, SCIP_Real cutefficacy, SCIP_Bool cutislocal, SCIP_Bool cutremovable, int cutrank, const char *cutclassname, SCIP_Bool *cutoff, int *ncuts, SCIP_ROW **thecut)
 
static SCIP_RETCODE setupAggregationData (SCIP *scip, SCIP_SOL *sol, SCIP_Bool allowlocal, AGGREGATIONDATA *aggrdata)
 
static void destroyAggregationData (SCIP *scip, AGGREGATIONDATA *aggrdata)
 
static SCIP_Bool getRowAggregationCandidates (AGGREGATIONDATA *aggrdata, int probvaridx, SCIP_ROW ***rows, SCIP_Real **rowvarcoefs, int *nrows, int *ngoodrows)
 
static SCIP_Real aggrdataGetBoundDist (AGGREGATIONDATA *aggrdata, int probvaridx)
 
static SCIP_RETCODE aggregateNextRow (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *rowlhsscores, SCIP_Real *rowrhsscores, AGGREGATIONDATA *aggrdata, SCIP_AGGRROW *aggrrow, int *naggrs, SCIP_Bool *success)
 
static SCIP_RETCODE aggregation (SCIP *scip, AGGREGATIONDATA *aggrdata, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_Real *rowlhsscores, SCIP_Real *rowrhsscores, int startrow, int maxaggrs, SCIP_Bool *wastried, SCIP_Bool *cutoff, int *cutinds, SCIP_Real *cutcoefs, SCIP_Bool negate, int *ncuts)
 
static SCIP_Real getRowFracActivity (SCIP_ROW *row, SCIP_Real *fractionalities)
 
static SCIP_RETCODE separateCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_RESULT *result)
 
static SCIP_DECL_SEPACOPY (sepaCopyAggregation)
 
static SCIP_DECL_SEPAFREE (sepaFreeAggregation)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpAggregation)
 
static SCIP_DECL_SEPAEXECSOL (sepaExecsolAggregation)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpDummy)
 
static SCIP_DECL_SEPAEXECSOL (sepaExecsolDummy)
 
SCIP_RETCODE SCIPincludeSepaAggregation (SCIP *scip)
 

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME   "aggregation"

Definition at line 66 of file sepa_aggregation.c.

Referenced by separateCuts().

◆ SEPA_DESC

#define SEPA_DESC   "aggregation heuristic for complemented mixed integer rounding cuts and flowcover cuts"

Definition at line 67 of file sepa_aggregation.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   -3000

Definition at line 68 of file sepa_aggregation.c.

◆ SEPA_FREQ

#define SEPA_FREQ   10

Definition at line 69 of file sepa_aggregation.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 70 of file sepa_aggregation.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 71 of file sepa_aggregation.c.

◆ SEPA_DELAY

#define SEPA_DELAY   FALSE

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

Definition at line 72 of file sepa_aggregation.c.

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS   -1

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

Definition at line 74 of file sepa_aggregation.c.

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT   -1

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

Definition at line 75 of file sepa_aggregation.c.

◆ DEFAULT_MAXTRIES

#define DEFAULT_MAXTRIES   200

maximal number of rows to start aggregation with per separation round (-1: unlimited)

Definition at line 76 of file sepa_aggregation.c.

◆ DEFAULT_MAXTRIESROOT

#define DEFAULT_MAXTRIESROOT   -1

maximal number of rows to start aggregation with per round in the root node (-1: unlimited)

Definition at line 79 of file sepa_aggregation.c.

◆ DEFAULT_MAXFAILS

#define DEFAULT_MAXFAILS   20

maximal number of consecutive unsuccessful aggregation tries (-1: unlimited)

Definition at line 82 of file sepa_aggregation.c.

◆ DEFAULT_MAXFAILSROOT

#define DEFAULT_MAXFAILSROOT   100

maximal number of consecutive unsuccessful aggregation tries in the root node (-1: unlimited)

Definition at line 83 of file sepa_aggregation.c.

◆ DEFAULT_MAXAGGRS

#define DEFAULT_MAXAGGRS   3

maximal number of aggregations for each row per separation round

Definition at line 86 of file sepa_aggregation.c.

◆ DEFAULT_MAXAGGRSROOT

#define DEFAULT_MAXAGGRSROOT   6

maximal number of aggregations for each row per round in the root node

Definition at line 87 of file sepa_aggregation.c.

◆ DEFAULT_MAXSEPACUTS

#define DEFAULT_MAXSEPACUTS   100

maximal number of cmir cuts separated per separation round

Definition at line 88 of file sepa_aggregation.c.

◆ DEFAULT_MAXSEPACUTSROOT

#define DEFAULT_MAXSEPACUTSROOT   500

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

Definition at line 89 of file sepa_aggregation.c.

◆ DEFAULT_MAXSLACK

#define DEFAULT_MAXSLACK   0.0

maximal slack of rows to be used in aggregation

Definition at line 90 of file sepa_aggregation.c.

◆ DEFAULT_MAXSLACKROOT

#define DEFAULT_MAXSLACKROOT   0.1

maximal slack of rows to be used in aggregation in the root node

Definition at line 91 of file sepa_aggregation.c.

◆ DEFAULT_DENSITYSCORE

#define DEFAULT_DENSITYSCORE   1e-4

weight of row density in the aggregation scoring of the rows

Definition at line 92 of file sepa_aggregation.c.

◆ DEFAULT_SLACKSCORE

#define DEFAULT_SLACKSCORE   1e-3

weight of slack in the aggregation scoring of the rows

Definition at line 93 of file sepa_aggregation.c.

◆ DEFAULT_MAXAGGDENSITY

#define DEFAULT_MAXAGGDENSITY   0.20

maximal density of aggregated row

Definition at line 94 of file sepa_aggregation.c.

◆ DEFAULT_MAXROWDENSITY

#define DEFAULT_MAXROWDENSITY   0.05

maximal density of row to be used in aggregation

Definition at line 95 of file sepa_aggregation.c.

◆ DEFAULT_DENSITYOFFSET

#define DEFAULT_DENSITYOFFSET   100

additional number of variables allowed in row on top of density

Definition at line 96 of file sepa_aggregation.c.

◆ DEFAULT_MAXROWFAC

#define DEFAULT_MAXROWFAC   1e+4

maximal row aggregation factor

Definition at line 97 of file sepa_aggregation.c.

◆ DEFAULT_MAXTESTDELTA

#define DEFAULT_MAXTESTDELTA   -1

maximal number of different deltas to try (-1: unlimited)

Definition at line 98 of file sepa_aggregation.c.

◆ DEFAULT_AGGRTOL

#define DEFAULT_AGGRTOL   1e-2

aggregation heuristic: we try to delete continuous variables from the current aggregation, whose distance to its tightest bound is >= L - DEFAULT_AGGRTOL, where L is the largest of the distances between a continuous variable's value and its tightest bound in the current aggregation

Definition at line 99 of file sepa_aggregation.c.

◆ DEFAULT_TRYNEGSCALING

#define DEFAULT_TRYNEGSCALING   TRUE

should negative values also be tested in scaling?

Definition at line 106 of file sepa_aggregation.c.

◆ DEFAULT_FIXINTEGRALRHS

#define DEFAULT_FIXINTEGRALRHS   TRUE

should an additional variable be complemented if f0 = 0?

Definition at line 107 of file sepa_aggregation.c.

◆ DEFAULT_DYNAMICCUTS

#define DEFAULT_DYNAMICCUTS   TRUE

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

Definition at line 108 of file sepa_aggregation.c.

◆ BOUNDSWITCH

#define BOUNDSWITCH   0.5

Definition at line 110 of file sepa_aggregation.c.

Referenced by aggregation().

◆ POSTPROCESS

#define POSTPROCESS   TRUE

Definition at line 111 of file sepa_aggregation.c.

Referenced by aggregation().

◆ USEVBDS

#define USEVBDS   TRUE

Definition at line 112 of file sepa_aggregation.c.

Referenced by aggregation().

◆ MINFRAC

#define MINFRAC   0.05

Definition at line 113 of file sepa_aggregation.c.

Referenced by aggregation().

◆ MAXFRAC

#define MAXFRAC   0.999

Definition at line 114 of file sepa_aggregation.c.

Referenced by aggregation().

◆ MAKECONTINTEGRAL

#define MAKECONTINTEGRAL   FALSE

Definition at line 115 of file sepa_aggregation.c.

Referenced by addCut().

◆ IMPLINTSARECONT

#define IMPLINTSARECONT

Definition at line 116 of file sepa_aggregation.c.

Typedef Documentation

◆ AGGREGATIONDATA

data used for aggregation of row

Function Documentation

◆ addCut()

static SCIP_RETCODE addCut ( SCIP scip,
SCIP_SOL sol,
SCIP_SEPA sepa,
SCIP_Bool  makeintegral,
SCIP_Real cutcoefs,
int *  cutinds,
int  cutnnz,
SCIP_Real  cutrhs,
SCIP_Real  cutefficacy,
SCIP_Bool  cutislocal,
SCIP_Bool  cutremovable,
int  cutrank,
const char *  cutclassname,
SCIP_Bool cutoff,
int *  ncuts,
SCIP_ROW **  thecut 
)
static

adds given cut to LP if violated

Parameters
scipSCIP data structure
solthe solution that should be separated, or NULL for LP solution
sepaseparator
makeintegralshould cut be scaled to integral coefficients if possible?
cutcoefscoefficients of active variables in cut
cutindsproblem indices of variables in cut
cutnnznumber of non-zeros in cut
cutrhsright hand side of cut
cutefficacyefficacy of cut
cutislocalis the cut only locally valid?
cutremovableshould the cut be removed from the LP due to aging or cleanup?
cutrankrank of the cut
cutclassnamename of cut class to use for row names
cutoffwhether a cutoff has been detected
ncutspointer to count the number of added cuts
thecutpointer to return cut if it was added

Definition at line 183 of file sepa_aggregation.c.

References FALSE, MAKECONTINTEGRAL, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPdebug, SCIPdebugMsg, SCIPepsilon(), SCIPflushRowExtensions(), SCIPgetNLPs(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetRowNumIntCols(), SCIPgetVars(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisCutNew(), SCIPisEfficacious(), SCIPisInfinity(), SCIPmakeRowIntegral(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetNNonz(), SCIProwGetRank(), SCIProwGetRhs(), SCIPsnprintf(), SCIPsumepsilon(), and setupAggregationData().

Referenced by aggregation().

◆ setupAggregationData()

◆ destroyAggregationData()

static void destroyAggregationData ( SCIP scip,
AGGREGATIONDATA aggrdata 
)
static

free resources held in aggregation data

Parameters
scipSCIP datastructure
aggrdatapointer to ggregation data

Definition at line 484 of file sepa_aggregation.c.

Referenced by separateCuts(), and setupAggregationData().

◆ getRowAggregationCandidates()

static SCIP_Bool getRowAggregationCandidates ( AGGREGATIONDATA aggrdata,
int  probvaridx,
SCIP_ROW ***  rows,
SCIP_Real **  rowvarcoefs,
int *  nrows,
int *  ngoodrows 
)
static

retrieves the candidate rows for canceling out the given variable, also returns the number of "good" rows which are the rows stored at the first ngoodrows positions. A row is good if its continuous variables are all at their bounds, except maybe the given continuous variable (in probvaridx)

Parameters
aggrdatapointer to ggregation data
probvaridxproblem index of variables to retrieve candidates for
rowspointer to store array to candidate rows
rowvarcoefspointer to store array of coefficients of given variable in the corresponding rows
nrowspointer to return number of rows in returned arrays
ngoodrowspointer to return number of "good" rows in the returned arrays

Definition at line 504 of file sepa_aggregation.c.

References aggrdataGetBoundDist(), AggregationData::aggrrows, AggregationData::aggrrowscoef, AggregationData::aggrrowsstart, AggregationData::bounddistinds, FALSE, AggregationData::nbounddistvars, AggregationData::ngoodaggrrows, SCIP_Real, SCIPsortedvecFindInt(), and TRUE.

Referenced by aggregateNextRow().

◆ aggrdataGetBoundDist()

static SCIP_Real aggrdataGetBoundDist ( AGGREGATIONDATA aggrdata,
int  probvaridx 
)
static

find the bound distance value in the aggregation data struct for the given variable problem index

Parameters
aggrdataSCIP datastructure
probvaridxproblem index of variables to retrieve candidates for

Definition at line 528 of file sepa_aggregation.c.

Referenced by aggregateNextRow(), and getRowAggregationCandidates().

◆ aggregateNextRow()

static SCIP_RETCODE aggregateNextRow ( SCIP scip,
SCIP_SEPADATA sepadata,
SCIP_Real rowlhsscores,
SCIP_Real rowrhsscores,
AGGREGATIONDATA aggrdata,
SCIP_AGGRROW aggrrow,
int *  naggrs,
SCIP_Bool success 
)
static

Aggregates the next row suitable for cancelling out an active continuous variable.

Equality rows that contain no other active continuous variables are preffered and apart from that the scores for the rows are used to determine which row is aggregated next

Parameters
scipSCIP data structure
sepadataseparator data
rowlhsscoresaggregation scores for left hand sides of row
rowrhsscoresaggregation scores for right hand sides of row
aggrdataaggregation data
aggrrowcurrent aggregation row
naggrspointer to increase counter if real aggregation took place
successpointer to return whether another row was added to the aggregation row

Definition at line 547 of file sepa_aggregation.c.

References aggrdataGetBoundDist(), aggregation(), FALSE, getRowAggregationCandidates(), MAX, MIN, AggregationData::nbadvarsinrow, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPaggrRowAddRow(), SCIPaggrRowGetInds(), SCIPaggrRowGetNNz(), SCIPaggrRowGetProbvarValue(), SCIPaggrRowHasRowBeenAdded(), SCIPaggrRowRemoveZeros(), SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPisEQ(), SCIPisFeasZero(), SCIPisGT(), SCIPisInfinity(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), and SCIPsortDownRealInt().

Referenced by aggregation().

◆ aggregation()

static SCIP_RETCODE aggregation ( SCIP scip,
AGGREGATIONDATA aggrdata,
SCIP_SEPA sepa,
SCIP_SOL sol,
SCIP_Bool  allowlocal,
SCIP_Real rowlhsscores,
SCIP_Real rowrhsscores,
int  startrow,
int  maxaggrs,
SCIP_Bool wastried,
SCIP_Bool cutoff,
int *  cutinds,
SCIP_Real cutcoefs,
SCIP_Bool  negate,
int *  ncuts 
)
static

aggregates different single mixed integer constraints by taking linear combinations of the rows of the LP

Parameters
scipSCIP data structure
aggrdatapointer to aggregation data
sepaseparator
solthe solution that should be separated, or NULL for LP solution
allowlocalshould local cuts be allowed
rowlhsscoresaggregation scores for left hand sides of row
rowrhsscoresaggregation scores for right hand sides of row
startrowindex of row to start aggregation
maxaggrsmaximal number of aggregations
wastriedpointer to store whether the given startrow was actually tried
cutoffwhether a cutoff has been detected
cutindsbuffer array to store temporarily cut
cutcoefsbuffer array to store temporarily cut
negateshould the start row be multiplied by -1
ncutspointer to count the number of generated cuts

Definition at line 776 of file sepa_aggregation.c.

References addCut(), aggregateNextRow(), AggregationData::aggrrow, BOUNDSWITCH, FALSE, getRowFracActivity(), MAXFRAC, MINFRAC, NULL, POSTPROCESS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaggrRowAddRow(), SCIPaggrRowClear(), SCIPaggrRowGetNNz(), SCIPaggrRowGetNRows(), SCIPaggrRowGetRowInds(), SCIPcalcFlowCover(), SCIPcutGenerationHeuristicCMIR(), SCIPdebugMsg, SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPgetRowSolActivity(), SCIPinfinity(), SCIPreleaseRow(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetParallelism(), SCIProwGetRhs(), SCIPsepaGetData(), TRUE, and USEVBDS.

Referenced by aggregateNextRow(), and separateCuts().

◆ getRowFracActivity()

static SCIP_Real getRowFracActivity ( SCIP_ROW row,
SCIP_Real fractionalities 
)
static

gives an estimate of how much the activity of this row is affected by fractionality in the current solution

Parameters
rowthe LP row
fractionalitiesarray of fractionalities for each variable

Definition at line 966 of file sepa_aggregation.c.

Referenced by aggregation(), and separateCuts().

◆ separateCuts()

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyAggregation  )
static

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

Definition at line 1370 of file sepa_aggregation.c.

Referenced by separateCuts().

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeAggregation  )
static

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

Definition at line 1384 of file sepa_aggregation.c.

◆ SCIP_DECL_SEPAEXECLP() [1/2]

static SCIP_DECL_SEPAEXECLP ( sepaExeclpAggregation  )
static

LP solution separation method of separator

Definition at line 1401 of file sepa_aggregation.c.

◆ SCIP_DECL_SEPAEXECSOL() [1/2]

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolAggregation  )
static

arbitrary primal solution separation method of separator

Definition at line 1426 of file sepa_aggregation.c.

◆ SCIP_DECL_SEPAEXECLP() [2/2]

static SCIP_DECL_SEPAEXECLP ( sepaExeclpDummy  )
static

LP solution separation method of dummy separator

Definition at line 1439 of file sepa_aggregation.c.

References NULL, and SCIP_DIDNOTRUN.

◆ SCIP_DECL_SEPAEXECSOL() [2/2]

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolDummy  )
static

arbitrary primal solution separation method of dummy separator

Definition at line 1450 of file sepa_aggregation.c.