misc_rowprep.c File Reference

Detailed Description

linear inequalities in preparation

Author

Stefan Vigerske

Benjamin Mueller

Felipe Serrano

Definition in file misc_rowprep.c.

#include "scip/pub_misc_rowprep.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_var.h"
#include "scip/pub_message.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_sepa.h"
#include "scip/scip_sol.h"
#include "scip/scip_tree.h"
#include "scip/struct_misc.h"
#include "scip/struct_scip.h"
#include "scip/set.h"

Go to the source code of this file.

Macros
#define	ROWPREP_SCALEUP_VIOLNONZERO   (10.0*SCIPepsilon(scip))
#define	ROWPREP_SCALEUP_MINVIOLFACTOR   2.0
#define	ROWPREP_SCALEUP_MAXMINCOEF   (1.0 / SCIPfeastol(scip))
#define	ROWPREP_SCALEUP_MAXMAXCOEF   SCIPgetHugeValue(scip)
#define	ROWPREP_SCALEUP_MAXSIDE   SCIPgetHugeValue(scip)
#define	ROWPREP_SCALEDOWN_MINMAXCOEF   (1.0 / SCIPfeastol(scip))
#define	ROWPREP_SCALEDOWN_MINCOEF   SCIPfeastol(scip)
#define	M_SQRT2   sqrt(2.0)

Functions
static SCIP_RETCODE	rowprepRecordModifiedVar (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var)
static SCIP_RETCODE	rowprepCleanupSortTerms (SCIP *scip, SCIP_ROWPREP *rowprep)
static SCIP_RETCODE	rowprepCleanupImproveCoefrange (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefrange)
static void	rowprepCleanupScaleup (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real *viol, SCIP_Real minviol)
static void	rowprepCleanupScaledown (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real *viol, SCIP_Real minviol)
static SCIP_RETCODE	rowprepCleanupIntegralCoefs (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real *viol)
static void	rowprepCleanupSide (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real *viol)
SCIP_RETCODE	SCIPcreateRowprep (SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
void	SCIPfreeRowprep (SCIP *scip, SCIP_ROWPREP **rowprep)
SCIP_RETCODE	SCIPcopyRowprep (SCIP *scip, SCIP_ROWPREP **target, SCIP_ROWPREP *source)
int	SCIProwprepGetNVars (SCIP_ROWPREP *rowprep)
SCIP_VAR **	SCIProwprepGetVars (SCIP_ROWPREP *rowprep)
SCIP_Real *	SCIProwprepGetCoefs (SCIP_ROWPREP *rowprep)
SCIP_Real	SCIProwprepGetSide (SCIP_ROWPREP *rowprep)
SCIP_SIDETYPE	SCIProwprepGetSidetype (SCIP_ROWPREP *rowprep)
SCIP_Bool	SCIProwprepIsLocal (SCIP_ROWPREP *rowprep)
char *	SCIProwprepGetName (SCIP_ROWPREP *rowprep)
int	SCIProwprepGetNModifiedVars (SCIP_ROWPREP *rowprep)
SCIP_VAR **	SCIProwprepGetModifiedVars (SCIP_ROWPREP *rowprep)
void	SCIProwprepReset (SCIP_ROWPREP *rowprep)
void	SCIProwprepSetCoef (SCIP_ROWPREP *rowprep, int idx, SCIP_Real newcoef)
void	SCIProwprepAddSide (SCIP_ROWPREP *rowprep, SCIP_Real side)
void	SCIProwprepAddConstant (SCIP_ROWPREP *rowprep, SCIP_Real constant)
void	SCIProwprepSetSidetype (SCIP_ROWPREP *rowprep, SCIP_SIDETYPE sidetype)
void	SCIProwprepSetLocal (SCIP_ROWPREP *rowprep, SCIP_Bool islocal)
void	SCIProwprepRecordModifications (SCIP_ROWPREP *rowprep)
void	SCIPprintRowprep (SCIP *scip, SCIP_ROWPREP *rowprep, FILE *file)
void	SCIPprintRowprepSol (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, FILE *file)
SCIP_RETCODE	SCIPensureRowprepSize (SCIP *scip, SCIP_ROWPREP *rowprep, int size)
SCIP_RETCODE	SCIPaddRowprepTerm (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
SCIP_RETCODE	SCIPaddRowprepTerms (SCIP *scip, SCIP_ROWPREP *rowprep, int nvars, SCIP_VAR **vars, SCIP_Real *coefs)
SCIP_Real	SCIPgetRowprepViolation (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Bool *reliable)
SCIP_Bool	SCIPisRowprepViolationReliable (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol)
void	SCIPmergeRowprepTerms (SCIP *scip, SCIP_ROWPREP *rowprep)
SCIP_RETCODE	SCIPcleanupRowprep (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real minviol, SCIP_Real *viol, SCIP_Bool *success)
SCIP_RETCODE	SCIPcleanupRowprep2 (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefbound, SCIP_Bool *success)
SCIP_Real	SCIPscaleupRowprep (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real minscaleup, SCIP_Bool *success)
int	SCIPscaleRowprep (SCIP_ROWPREP *rowprep, SCIP_Real factor)
SCIP_RETCODE	SCIPgetRowprepRowConshdlr (SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE	SCIPgetRowprepRowCons (SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONS *cons)
SCIP_RETCODE	SCIPgetRowprepRowSepa (SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_SEPA *sepa)

Macro Definition Documentation

ROWPREP_SCALEUP_VIOLNONZERO

#define ROWPREP_SCALEUP_VIOLNONZERO   (10.0*SCIPepsilon(scip))

minimal violation for considering up-scaling of rowprep (we want to avoid upscaling very small violations)

Definition at line 50 of file misc_rowprep.c.

Referenced by rowprepCleanupScaleup().

ROWPREP_SCALEUP_MINVIOLFACTOR

#define ROWPREP_SCALEUP_MINVIOLFACTOR   2.0

scale up will target a violation of ~MINVIOLFACTOR*minviol, where minviol is given by caller

Definition at line 51 of file misc_rowprep.c.

Referenced by rowprepCleanupScaledown(), and rowprepCleanupScaleup().

ROWPREP_SCALEUP_MAXMINCOEF

#define ROWPREP_SCALEUP_MAXMINCOEF   (1.0 / SCIPfeastol(scip))

scale up only if min. coef is below this number (before scaling)

Definition at line 52 of file misc_rowprep.c.

Referenced by rowprepCleanupScaleup().

ROWPREP_SCALEUP_MAXMAXCOEF

#define ROWPREP_SCALEUP_MAXMAXCOEF   SCIPgetHugeValue(scip)

scale up only if max. coef will not exceed this number by scaling

Definition at line 53 of file misc_rowprep.c.

Referenced by rowprepCleanupScaleup().

ROWPREP_SCALEUP_MAXSIDE

#define ROWPREP_SCALEUP_MAXSIDE   SCIPgetHugeValue(scip)

scale up only if side will not exceed this number by scaling

Definition at line 54 of file misc_rowprep.c.

Referenced by rowprepCleanupIntegralCoefs(), and rowprepCleanupScaleup().

ROWPREP_SCALEDOWN_MINMAXCOEF

#define ROWPREP_SCALEDOWN_MINMAXCOEF   (1.0 / SCIPfeastol(scip))

scale down if max. coef is at least this number (before scaling)

Definition at line 55 of file misc_rowprep.c.

Referenced by rowprepCleanupScaledown().

ROWPREP_SCALEDOWN_MINCOEF

#define ROWPREP_SCALEDOWN_MINCOEF   SCIPfeastol(scip)

scale down only if min. coef does not drop below this number by scaling

Definition at line 56 of file misc_rowprep.c.

Referenced by rowprepCleanupScaledown().

M_SQRT2

#define M_SQRT2   sqrt(2.0)

Definition at line 59 of file misc_rowprep.c.

Referenced by SCIPcalcCumulativeDistribution(), SCIPnormalCDF(), and SCIPscaleupRowprep().

Function Documentation

rowprepRecordModifiedVar()

static SCIP_RETCODE rowprepRecordModifiedVar ( SCIP *  scip, SCIP_ROWPREP *  rowprep, SCIP_VAR *  var  )

static

adds a variable to the rowprep->modifiedvars array, if recording of modification has been enabled and the variable is not fixed

Parameters

scip	SCIP data structure
rowprep	rowprep
var	variable to add

Definition at line 64 of file misc_rowprep.c.

References SCIP_RowPrep::modifiedvars, SCIP_RowPrep::modifiedvarssize, SCIP_RowPrep::nmodifiedvars, SCIP_RowPrep::recordmodifications, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPdebugMsg, SCIPisRelEQ(), SCIPreallocBlockMemoryArray, SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by rowprepCleanupImproveCoefrange(), and rowprepCleanupIntegralCoefs().

rowprepCleanupSortTerms()

static SCIP_RETCODE rowprepCleanupSortTerms ( SCIP *  scip, SCIP_ROWPREP *  rowprep  )

static

sort terms by absolute value of coefficients, from largest to smallest

Parameters

scip	SCIP data structure
rowprep	rowprep to be sorted

Definition at line 99 of file misc_rowprep.c.

References SCIP_RowPrep::coefs, NULL, SCIP_RowPrep::nvars, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownRealRealPtr(), and SCIP_RowPrep::vars.

Referenced by SCIPcleanupRowprep(), and SCIPcleanupRowprep2().

rowprepCleanupImproveCoefrange()

static SCIP_RETCODE rowprepCleanupImproveCoefrange ( SCIP *  scip, SCIP_ROWPREP *  rowprep, SCIP_SOL *  sol, SCIP_Real  maxcoefrange  )

static

try to improve coef range by aggregating row with variable bounds

Assumes terms have been sorted by rowprepCleanupSortTerms().

Parameters

scip	SCIP data structure
rowprep	rowprep to be improve
sol	solution that we try to cut off, or NULL for LP solution
maxcoefrange	maximal allowed coefficients range

Definition at line 158 of file misc_rowprep.c.

References SCIP_RowPrep::coefs, SCIP_RowPrep::local, MAX, MIN, SCIP_RowPrep::nvars, REALABS, rowprepRecordModifiedVar(), SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPdebugMsg, SCIPgetSolVal(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIProwprepAddConstant(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIP_RowPrep::sidetype, and SCIP_RowPrep::vars.

Referenced by SCIPcleanupRowprep(), and SCIPcleanupRowprep2().

rowprepCleanupScaleup()

static void rowprepCleanupScaleup ( SCIP *  scip, SCIP_ROWPREP *  rowprep, SCIP_Real *  viol, SCIP_Real  minviol  )

static

scales up rowprep if it seems useful

Parameters

scip	SCIP data structure
rowprep	rowprep to be improve
viol	violation of cut in sol (input and output)
minviol	minimal violation we try to achieve

Definition at line 326 of file misc_rowprep.c.

References SCIP_RowPrep::coefs, NULL, SCIP_RowPrep::nvars, REALABS, ROWPREP_SCALEUP_MAXMAXCOEF, ROWPREP_SCALEUP_MAXMINCOEF, ROWPREP_SCALEUP_MAXSIDE, ROWPREP_SCALEUP_MINVIOLFACTOR, ROWPREP_SCALEUP_VIOLNONZERO, SCIP_Real, SCIPisInfinity(), SCIPscaleRowprep(), and SCIP_RowPrep::side.

Referenced by SCIPcleanupRowprep().

rowprepCleanupScaledown()

static void rowprepCleanupScaledown ( SCIP *  scip, SCIP_ROWPREP *  rowprep, SCIP_Real *  viol, SCIP_Real  minviol  )

static

scales down rowprep if it improves coefs and keeps rowprep violated

Parameters

scip	SCIP data structure
rowprep	rowprep to be improve
viol	violation of cut in sol (input and output)
minviol	minimal violation we try to keep

Definition at line 376 of file misc_rowprep.c.

References SCIP_RowPrep::coefs, SCIP_RowPrep::nvars, REALABS, ROWPREP_SCALEDOWN_MINCOEF, ROWPREP_SCALEDOWN_MINMAXCOEF, ROWPREP_SCALEUP_MINVIOLFACTOR, SCIP_Real, SCIPisInfinity(), and SCIPscaleRowprep().

Referenced by SCIPcleanupRowprep().

rowprepCleanupIntegralCoefs()

static SCIP_RETCODE rowprepCleanupIntegralCoefs ( SCIP *  scip, SCIP_ROWPREP *  rowprep, SCIP_Real *  viol  )

static

rounds almost integral coefs to integrals, thereby trying to relax the cut

Parameters

scip	SCIP data structure
rowprep	rowprep to be improve
viol	NULL or violation of cut in sol (input), set to SCIP_INVALID if some coef changed

Definition at line 421 of file misc_rowprep.c.

References SCIP_RowPrep::coefs, SCIP_RowPrep::local, NULL, SCIP_RowPrep::nvars, REALABS, ROWPREP_SCALEUP_MAXSIDE, rowprepRecordModifiedVar(), SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_RIGHT, SCIPdebugMsg, SCIPisEQ(), SCIPisInfinity(), SCIPisZero(), SCIPround(), SCIProwprepAddConstant(), SCIPscaleRowprep(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIP_RowPrep::side, SCIP_RowPrep::sidetype, and SCIP_RowPrep::vars.

Referenced by SCIPcleanupRowprep(), and SCIPcleanupRowprep2().

rowprepCleanupSide()

static void rowprepCleanupSide ( SCIP *  scip, SCIP_ROWPREP *  rowprep, SCIP_Real *  viol  )

static

relaxes almost zero side

Parameters

scip	SCIP data structure
rowprep	rowprep to be improve
viol	NULL or violation of cut in sol (input), set to SCIP_INVALID if some coef changed

Definition at line 514 of file misc_rowprep.c.

References SCIP_RowPrep::modifiedside, NULL, SCIP_RowPrep::recordmodifications, SCIP_INVALID, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPepsilon(), SCIPisZero(), SCIP_RowPrep::side, SCIP_RowPrep::sidetype, and TRUE.

Referenced by SCIPcleanupRowprep(), and SCIPcleanupRowprep2().