Scippy

SCIP

Solving Constraint Integer Programs

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_RealSCIProwprepGetCoefs (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.

◆ 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.

◆ 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.

◆ 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.

◆ 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.

◆ 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.

◆ 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.

◆ M_SQRT2

#define M_SQRT2   sqrt(2.0)

Definition at line 59 of file misc_rowprep.c.

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
scipSCIP data structure
rowpreprowprep
varvariable 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
scipSCIP data structure
rowpreprowprep 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
scipSCIP data structure
rowpreprowprep to be improve
solsolution that we try to cut off, or NULL for LP solution
maxcoefrangemaximal 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
scipSCIP data structure
rowpreprowprep to be improve
violviolation of cut in sol (input and output)
minviolminimal 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
scipSCIP data structure
rowpreprowprep to be improve
violviolation of cut in sol (input and output)
minviolminimal 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
scipSCIP data structure
rowpreprowprep to be improve
violNULL 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
scipSCIP data structure
rowpreprowprep to be improve
violNULL 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().