Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

dual inference presolver

Author
Dieter Weninger
Patrick Gemander

This presolver does bound strengthening on continuous variables (columns) for getting bounds on dual variables y. The bounds of the dual variables are then used to fix primal variables or change the side of constraints. For ranged rows one needs to decide which side (rhs or lhs) determines the equality.

We distinguish two cases concerning complementary slackness: i) reduced cost fixing: c_j - sup_y(y^T A_{.j}) > 0 => x_j = l_j c_j - inf_y(y^T A_{.j}) < 0 => x_j = u_j ii) positive dual lower bound: y_i > 0 => A_{i.}x = b_i

Further information on this presolving approach are given in Achterberg et al. "Presolve reductions in mixed integer programming" and for a two-column extension in Chen et al. "Two-row and two-column mixed-integer presolve using hasing-based pairing methods".

Definition in file presol_dualinfer.c.

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "scip/scipdefplugins.h"
#include "scip/pub_matrix.h"
#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/presol_dualinfer.h"
#include "scip/pub_cons.h"
#include "scip/pub_message.h"
#include "scip/pub_presol.h"
#include "scip/pub_var.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_presol.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_var.h"

Go to the source code of this file.

Data Structures

struct  ColPair
 

Macros

#define PRESOL_NAME   "dualinfer"
 
#define PRESOL_DESC   "exploit dual information for fixings and side changes"
 
#define PRESOL_PRIORITY   (-3000)
 
#define PRESOL_MAXROUNDS   0
 
#define PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
 
#define DEFAULT_TWOCOLUMN_COMBINE   TRUE
 
#define DEFAULT_MAXLOOPS_DUALBNDSTR   12
 
#define DEFAULT_MAXCONSIDEREDNONZEROS   100
 
#define DEFAULT_MAXRETRIEVEFAILS   1000
 
#define DEFAULT_MAXCOMBINEFAILS   1000
 
#define DEFAULT_MAXHASHFAC   10
 
#define DEFAULT_MAXPAIRFAC   1
 
#define DEFAULT_MAXROWSUPPORT   3
 

Typedefs

typedef enum Fixingdirection FIXINGDIRECTION
 
typedef enum SideChange SIDECHANGE
 
typedef struct ColPair COLPAIR
 

Enumerations

enum  Fixingdirection {
  FIXATLB = -1,
  NOFIX = 0,
  FIXATUB = 1,
  FIXATLB = -1,
  NOFIX = 0,
  FIXATUB = 1,
  FIXATLB = -1,
  NOFIX = 0,
  FIXATUB = 1,
  FIXATLB = -1,
  NOFIX = 0,
  FIXATUB = 1
}
 
enum  SideChange {
  RHSTOLHS = -1,
  NOCHANGE = 0,
  LHSTORHS = 1
}
 
enum  signum {
  UP,
  DN,
  POS,
  NEG
}
 

Functions

static void * encodeColPair (COLPAIR *colpair)
 
static int hashIndexPair (int idx1, int idx2)
 
static SCIP_RETCODE addEntry (SCIP *scip, int *pos, int *listsize, int **hashlist, int **colidxlist, int hash, int colidx)
 
static void findNextBlock (const int *list, int len, int *start, int *end)
 
static SCIP_RETCODE combineCols (SCIP *scip, int *row1idxptr, int *row2idxptr, SCIP_Real *row1valptr, SCIP_Real *row2valptr, SCIP_Real b1, SCIP_Real b2, int row1len, int row2len, int ncols, SCIP_Bool swaprow1, SCIP_Bool swaprow2, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Bool *success)
 
static void getMinMaxActivityResiduals (SCIP *scip, SCIP_MATRIX *matrix, int withoutcol, int row, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *isminsettoinfinity, SCIP_Bool *ismaxsettoinfinity)
 
static void getVarBoundsOfRow (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Real *rowub, SCIP_Bool *ubfound, SCIP_Real *rowlb, SCIP_Bool *lbfound)
 
static void getImpliedBounds (SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Bool *ubimplied, SCIP_Bool *lbimplied)
 
static SCIP_Real getMinColActWithoutRow (SCIP *scip, SCIP_MATRIX *matrix, int col, int withoutrow, SCIP_Real *lbdual, SCIP_Real *ubdual)
 
static void calcMinColActResidual (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbdual, SCIP_Real *ubdual, const SCIP_Real *mincolact, const int *mincolactinf, SCIP_Real *mincolresact)
 
static void calcMinColActivity (SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual, SCIP_Real *ubdual, SCIP_Real *mincolact, int *mincolactinf)
 
static void calcMaxColActivity (SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual, SCIP_Real *ubdual, SCIP_Real *maxcolact, int *maxcolactinf)
 
static void infinityCountUpdate (SCIP *scip, SCIP_MATRIX *matrix, int row, SCIP_Real *lbdual, SCIP_Real *ubdual, const SCIP_Bool *isubimplied, SCIP_Real *mincolact, int *mincolactinf, SCIP_Bool ubinfchange, SCIP_Bool lbinfchange)
 
static void updateDualBounds (SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real objval, SCIP_Real val, int row, SCIP_Real mincolresact, SCIP_Real *lbdual, SCIP_Real *ubdual, int *boundchanges, SCIP_Bool *ubinfchange, SCIP_Bool *lbinfchange)
 
static SCIP_RETCODE dualBoundStrengthening (SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, FIXINGDIRECTION *varstofix, int *npossiblefixings, SIDECHANGE *sidestochange, int *npossiblesidechanges)
 
static SCIP_DECL_PRESOLCOPY (presolCopyDualinfer)
 
static SCIP_DECL_PRESOLFREE (presolFreeDualinfer)
 
static SCIP_DECL_PRESOLEXEC (presolExecDualinfer)
 
SCIP_RETCODE SCIPincludePresolDualinfer (SCIP *scip)
 

Macro Definition Documentation

◆ PRESOL_NAME

#define PRESOL_NAME   "dualinfer"

Definition at line 70 of file presol_dualinfer.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolDualinfer().

◆ PRESOL_DESC

#define PRESOL_DESC   "exploit dual information for fixings and side changes"

Definition at line 71 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ PRESOL_PRIORITY

#define PRESOL_PRIORITY   (-3000)

priority of the presolver (>= 0: before, < 0: after constraint handlers)

Definition at line 72 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ PRESOL_MAXROUNDS

#define PRESOL_MAXROUNDS   0

maximal number of presolving rounds the presolver participates in (-1: no limit)

Definition at line 73 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ PRESOL_TIMING

#define PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */

Definition at line 74 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ DEFAULT_TWOCOLUMN_COMBINE

#define DEFAULT_TWOCOLUMN_COMBINE   TRUE

should two column convex combination be used per default

Definition at line 76 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ DEFAULT_MAXLOOPS_DUALBNDSTR

#define DEFAULT_MAXLOOPS_DUALBNDSTR   12

default maximal number of loops for dual bound strengthening

Definition at line 77 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ DEFAULT_MAXCONSIDEREDNONZEROS

#define DEFAULT_MAXCONSIDEREDNONZEROS   100

default maximal number of considered non-zeros within one row

Definition at line 78 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ DEFAULT_MAXRETRIEVEFAILS

#define DEFAULT_MAXRETRIEVEFAILS   1000

default maximal number of consecutive useless hashtable retrieves

Definition at line 79 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ DEFAULT_MAXCOMBINEFAILS

#define DEFAULT_MAXCOMBINEFAILS   1000

default maximal number of consecutive useless row combines

Definition at line 80 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ DEFAULT_MAXHASHFAC

#define DEFAULT_MAXHASHFAC   10

default maximal number of hashlist entries as multiple of number of rows in the problem

Definition at line 81 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ DEFAULT_MAXPAIRFAC

#define DEFAULT_MAXPAIRFAC   1

default maximal number of processed row pairs as multiple of the number of rows in the problem

Definition at line 82 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ DEFAULT_MAXROWSUPPORT

#define DEFAULT_MAXROWSUPPORT   3

default maximal number of non-zeros in one row for turning an inequality into an equality

Definition at line 83 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

Typedef Documentation

◆ FIXINGDIRECTION

Definition at line 110 of file presol_dualinfer.c.

◆ SIDECHANGE

typedef enum SideChange SIDECHANGE

Definition at line 119 of file presol_dualinfer.c.

◆ COLPAIR

typedef struct ColPair COLPAIR

Definition at line 135 of file presol_dualinfer.c.

Enumeration Type Documentation

◆ Fixingdirection

type of variable fixing direction

Enumerator
FIXATLB 

fix variable at lower bound

NOFIX 

do not fix variable

FIXATUB 

fix variable at upper bound

FIXATLB 

fix variable at lower bound

NOFIX 

do not fix variable

FIXATUB 

fix variable at upper bound

FIXATLB 
NOFIX 

fix variable at its lower bound

FIXATUB 

no fixing

FIXATLB 

fix variable at lower bound

NOFIX 

do not fix variable

FIXATUB 

fix variable at upper bound

Definition at line 104 of file presol_dualinfer.c.

◆ SideChange

enum SideChange

type of constraint side change

Enumerator
RHSTOLHS 
NOCHANGE 

set rhs to value of lhs

LHSTORHS 

no side change

Definition at line 113 of file presol_dualinfer.c.

◆ signum

enum signum

Signum for convex-combined variable coefficients \((\lambda * A_{ri} + (1 - \lambda) * A_{si})\) UP - Coefficient changes from negative to positive for increasing lambda DN - Coefficient changes from positive to negative for increasing lambda POS - Coefficient is positive for all lambda in (0,1) NEG - Coefficient is negative for all lambda in (0,1)

Enumerator
UP 
DN 
POS 
NEG 

Definition at line 127 of file presol_dualinfer.c.

Function Documentation

◆ encodeColPair()

static void* encodeColPair ( COLPAIR colpair)
static

encode contents of a colpair as void* pointer

Parameters
colpairpointer to colpair

Definition at line 144 of file presol_dualinfer.c.

References a, b, ColPair::col1idx, and ColPair::col2idx.

Referenced by dualBoundStrengthening().

◆ hashIndexPair()

static int hashIndexPair ( int  idx1,
int  idx2 
)
static

compute single positive int hashvalue for two ints

Parameters
idx1first integer index
idx2second integer index

Definition at line 162 of file presol_dualinfer.c.

References SCIPhashTwo.

Referenced by dualBoundStrengthening().

◆ addEntry()

static SCIP_RETCODE addEntry ( SCIP scip,
int *  pos,
int *  listsize,
int **  hashlist,
int **  colidxlist,
int  hash,
int  colidx 
)
static

add hash/rowidx pair to hashlist/rowidxlist

Parameters
scipSCIP datastructure
posposition of last entry added
listsizesize of hashlist and rowidxlist
hashlistblock memory array containing hashes
colidxlistblock memory array containing column indices
hashhash to be inserted
colidxcolumn index to be inserted

Definition at line 173 of file presol_dualinfer.c.

References SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.

Referenced by dualBoundStrengthening().

◆ findNextBlock()

static void findNextBlock ( const int *  list,
int  len,
int *  start,
int *  end 
)
static

Within a sorted list, get next block with same value E.g. for [h1, h1, h1, h2, h2, h2, h2, h3,...] and end = 0 returns start = 0, end = 3 and on a second call with end = 3 on the same list returns start = 3, end = 7.

Parameters
listlist of integers
lenlength of list
startvariable to contain start index of found block
endvariable to contain end index of found block

Definition at line 205 of file presol_dualinfer.c.

Referenced by dualBoundStrengthening().

◆ combineCols()

static SCIP_RETCODE combineCols ( SCIP scip,
int *  row1idxptr,
int *  row2idxptr,
SCIP_Real row1valptr,
SCIP_Real row2valptr,
SCIP_Real  b1,
SCIP_Real  b2,
int  row1len,
int  row2len,
int  ncols,
SCIP_Bool  swaprow1,
SCIP_Bool  swaprow2,
SCIP_Real lbs,
SCIP_Real ubs,
SCIP_Bool success 
)
static

The algorithm described in Belotti P. "Bound reduction using pairs of linear inequalities" tries to derive upper and lower bounds for all variables via convex combinations of linear inequalities We apply Belotti's algorithm to pairs of columns of continuous variables.

Parameters
scipSCIP datastructure
row1idxptrindices specifying bound positions in lbs and ubs for first row
row2idxptrindices specifying bound positions in lbs und ubs for second row
row1valptrfirst row coefficients
row2valptrsecond row coefficients
b1rhs of first row
b2rhs of second row
row1lenlength of first row (e.g. row1idxptr and row1valptr)
row2lenlength of second row (e.g. row2idxptr and row2valptr)
ncolslength of bound arrays lbs and ubs
swaprow1should the sense of the first row be swapped to <= ?
swaprow2should the sense of the second row be swapped to <= ?
lbslower bound array
ubsupper bound array
successwe return (success || found better bounds")

Definition at line 227 of file presol_dualinfer.c.

References DN, FALSE, MAX, NEG, POS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPsortIntReal(), SCIPsortRealInt(), TRUE, and UP.

Referenced by dualBoundStrengthening().

◆ getMinMaxActivityResiduals()

static void getMinMaxActivityResiduals ( SCIP scip,
SCIP_MATRIX matrix,
int  withoutcol,
int  row,
SCIP_Real lbs,
SCIP_Real ubs,
SCIP_Real minresactivity,
SCIP_Real maxresactivity,
SCIP_Bool isminsettoinfinity,
SCIP_Bool ismaxsettoinfinity 
)
static

get minimal and maximal residual activities without one specific column

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
withoutcolexclude this column index
rowrow index
lbslower bounds
ubsupper bounds
minresactivityminimum residual activity of this row
maxresactivitymaximum residual activity of this row
isminsettoinfinityflag indicating if minresactiviy is set to infinity
ismaxsettoinfinityflag indicating if maxresactiviy is set to infinity

Definition at line 719 of file presol_dualinfer.c.

References FALSE, NULL, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), and TRUE.

Referenced by getVarBoundsOfRow().

◆ getVarBoundsOfRow()

static void getVarBoundsOfRow ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
int  row,
SCIP_Real  val,
SCIP_Real lbs,
SCIP_Real ubs,
SCIP_Real rowub,
SCIP_Bool ubfound,
SCIP_Real rowlb,
SCIP_Bool lbfound 
)
static

calculate the upper and lower bound of one variable from one row

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn index of variable
rowrow index
valcoefficient of this column in this row
lbslower bounds
ubsupper bounds
rowubupper bound of row
ubfoundflag indicating that an upper bound was calculated
rowlblower bound of row
lbfoundflag indicating that a lower bound was caluclated

Definition at line 814 of file presol_dualinfer.c.

References FALSE, getMinMaxActivityResiduals(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), and TRUE.

Referenced by getImpliedBounds().

◆ getImpliedBounds()

static void getImpliedBounds ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
SCIP_Real lbs,
SCIP_Real ubs,
SCIP_Bool ubimplied,
SCIP_Bool lbimplied 
)
static

detect implied variable bounds

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn index for implied free test
lbslower bounds
ubsupper bounds
ubimpliedflag indicating an implied upper bound
lbimpliedflag indicating an implied lower bound

Definition at line 885 of file presol_dualinfer.c.

References FALSE, getVarBoundsOfRow(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), and TRUE.

Referenced by dualBoundStrengthening().

◆ getMinColActWithoutRow()

static SCIP_Real getMinColActWithoutRow ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
int  withoutrow,
SCIP_Real lbdual,
SCIP_Real ubdual 
)
static

calculate minimal column activity from one variable without one row

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn index
withoutrowexclude this row index
lbduallower bounds of dual variables
ubdualupper bounds of dual variables

Definition at line 947 of file presol_dualinfer.c.

References NULL, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), and SCIPmatrixGetColValPtr().

Referenced by calcMinColActResidual().

◆ calcMinColActResidual()

static void calcMinColActResidual ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
int  row,
SCIP_Real  val,
SCIP_Real lbdual,
SCIP_Real ubdual,
const SCIP_Real mincolact,
const int *  mincolactinf,
SCIP_Real mincolresact 
)
static

In the primal the residual activity of a constraint w.r.t. a variable is the activity of the constraint without the variable. This function does the same but in the dual. It computes the residual activity of column 'col' w.r.t. variable 'row'

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn index
rowrow index
valmatrix coefficient
lbduallower bounds of the dual variables
ubdualupper bounds of the dual variables
mincolactminimal column activities
mincolactinfnumber of infinite contributions to minimal column activity
mincolresactminimal residual column activity

Definition at line 1003 of file presol_dualinfer.c.

References getMinColActWithoutRow(), NULL, SCIPinfinity(), and SCIPisInfinity().

Referenced by dualBoundStrengthening().

◆ calcMinColActivity()

static void calcMinColActivity ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
SCIP_Real lbdual,
SCIP_Real ubdual,
SCIP_Real mincolact,
int *  mincolactinf 
)
static

calculate minimal column activity of one column

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn for activity calculations
lbduallower bounds of dual variables
ubdualupper bounds of dual variables
mincolactminimal column activities
mincolactinfnumber of -inf contributions to minimal column activity

Definition at line 1066 of file presol_dualinfer.c.

References NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), and SCIPmatrixGetColValPtr().

Referenced by dualBoundStrengthening(), and infinityCountUpdate().

◆ calcMaxColActivity()

static void calcMaxColActivity ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
SCIP_Real lbdual,
SCIP_Real ubdual,
SCIP_Real maxcolact,
int *  maxcolactinf 
)
static

calculate maximal column activity of one column

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn for activity calculations
lbduallower bounds of dual variables
ubdualupper bounds of dual variables
maxcolactminimal column activities
maxcolactinfnumber of -inf contributions to minimal column activity

Definition at line 1126 of file presol_dualinfer.c.

References NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), and SCIPmatrixGetColValPtr().

Referenced by dualBoundStrengthening().

◆ infinityCountUpdate()

static void infinityCountUpdate ( SCIP scip,
SCIP_MATRIX matrix,
int  row,
SCIP_Real lbdual,
SCIP_Real ubdual,
const SCIP_Bool isubimplied,
SCIP_Real mincolact,
int *  mincolactinf,
SCIP_Bool  ubinfchange,
SCIP_Bool  lbinfchange 
)
static

update minimal/maximal column activity infinity counters

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
rowrow index
lbduallower bounds of dual variables
ubdualupper bounds of dual variables
isubimpliedflags indicating of the upper bound is implied
mincolactminimal column activities
mincolactinfnumber of infinity contributions to minimal column activity
ubinfchangeflag indicating if the upper bound has changed from infinity to a finite value
lbinfchangeflag indicating if the lower bound has changed from -infinity to a finite value

Definition at line 1187 of file presol_dualinfer.c.

References calcMinColActivity(), determineBestBounds(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OBJSENSE_MAXIMIZE, SCIP_OBJSENSE_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIP_STATUS_OPTIMAL, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcheckSolOrig(), SCIPchgVarObj(), SCIPcreate(), SCIPcreateConsBasicLinear(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPfree(), SCIPfreeBufferArray, SCIPfreeTransform(), SCIPgetBestSol(), SCIPgetSolOrigObj(), SCIPgetStatus(), SCIPincludeDefaultPlugins(), SCIPinfinity(), SCIPisGT(), SCIPisLT(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetObjsense(), SCIPsnprintf(), SCIPsolve(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), SCIPwriteOrigProblem(), solveLP(), and TRUE.

Referenced by dualBoundStrengthening().

◆ updateDualBounds()

static void updateDualBounds ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_Real  objval,
SCIP_Real  val,
int  row,
SCIP_Real  mincolresact,
SCIP_Real lbdual,
SCIP_Real ubdual,
int *  boundchanges,
SCIP_Bool ubinfchange,
SCIP_Bool lbinfchange 
)
static

update bounds of the dual variables

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
objvalobjective function value
valmatrix coefficient
rowrow index
mincolresactminimal column residual activity
lbdualdual lower bounds
ubdualdual upper bounds
boundchangescounter for the number of bound changes
ubinfchangeflag indicating an upper bound change from infinite to finite
lbinfchangeflag indicating a lower bound change from infinite to finite

Definition at line 1483 of file presol_dualinfer.c.

References FALSE, NULL, SCIP_Real, SCIPisInfinity(), SCIPisLE(), and TRUE.

Referenced by dualBoundStrengthening().

◆ dualBoundStrengthening()

static SCIP_RETCODE dualBoundStrengthening ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_PRESOLDATA presoldata,
FIXINGDIRECTION varstofix,
int *  npossiblefixings,
SIDECHANGE sidestochange,
int *  npossiblesidechanges 
)
static

dual bound strengthening

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
presoldatapresolver data structure
varstofixarray holding information for later upper/lower bound fixing
npossiblefixingsnumber of possible fixings
sidestochangearray holding if this is an implied equality
npossiblesidechangesnumber of possible equality changes

Definition at line 1552 of file presol_dualinfer.c.

References addEntry(), calcMaxColActivity(), calcMinColActivity(), calcMinColActResidual(), ColPair::col1idx, ColPair::col2idx, combineCols(), encodeColPair(), FALSE, findNextBlock(), FIXATLB, FIXATUB, getImpliedBounds(), hashIndexPair(), infinityCountUpdate(), LHSTORHS, MAX, NOCHANGE, NOFIX, NULL, RHSTOLHS, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPhashsetCreate(), SCIPhashsetExists(), SCIPhashsetFree(), SCIPhashsetInsert(), SCIPinfinity(), SCIPisEQ(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPisPositive(), SCIPmatrixDownlockConflict(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPmatrixUplockConflict(), SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and updateDualBounds().

Referenced by SCIP_DECL_PRESOLEXEC().

◆ SCIP_DECL_PRESOLCOPY()

static SCIP_DECL_PRESOLCOPY ( presolCopyDualinfer  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 2153 of file presol_dualinfer.c.

References NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolDualinfer(), and SCIPpresolGetName().

◆ SCIP_DECL_PRESOLFREE()

static SCIP_DECL_PRESOLFREE ( presolFreeDualinfer  )
static

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

Definition at line 2167 of file presol_dualinfer.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().

◆ SCIP_DECL_PRESOLEXEC()