Scippy

SCIP

Solving Constraint Integer Programs

sepa_cgmip.c File Reference

Detailed Description

Chvatal-Gomory cuts computed via a sub-MIP.

Author
Marc Pfetsch

Separate Chvátal-Gomory cuts using a sub-MIP. The approach is based on the following papers.

M. Fischetti and A. Lodi
Optimizing over the first Chvátal closure,
in: M. Jünger and V. Kaibel (eds.) Integer Programming and Combinatorial Optimization IPCO 2005,
LNCS 3509, pp. 12-22. Springer, Berlin Heidelberg New York (2005)

M. Fischetti and A. Lodi
Optimizing over the first Chvátal closure,
Mathematical Programming 110, 3-20 (2007)

P. Bonami, G. Cornuéjols, S. Dash, M. Fischetti, and A. Lodi
Projected Chvátal-Gomory cuts for mixed integer linear programs,
Mathematical Programming 113, No. 2 (2008)

There are several versions to generate the final cut:

  • The CMIR-routines of SCIP can be used (if usecmir is true). One can determine which bound is used in the rounding operation (if cmirownbounds is true) or let SCIP choose the best. This version is generally numerically the most stable.
  • If usestrongcg is true, we try to generate Strong-CG cuts (as done in sepa_strongcg.c).
  • One can directly generate the CG-cut as computed (if usecmir and usestrongcg are false). The cut is not take from the solution of the MIP, but is recomputed, and some care (but not as much as in the first version) has been taken to create a valid cut.

The computation time of the separation MIP is limited as follows:

  • There is a node limit (parameters minnodelimit and maxnodelimit).
  • There is a time limit (parameter timelimit).
  • If paramter earlyterm is true, the separation is run until the first cut that is violated is found. (Note that these cuts are not necessarily added to the LP, because here also the norm of the cuts are taken into account - which cannot easily be included into the separation subscip.) Then the solution is continued for a certain number of nodes.
Warning
This separator should be used carefully - it may require a long separation time.

Definition in file sepa_cgmip.c.

#include <assert.h>
#include <string.h>
#include "scip/sepa_cgmip.h"
#include "scip/scipdefplugins.h"
#include "scip/cons_linear.h"
#include "scip/pub_misc.h"
#include "scip/pub_lp.h"

Go to the source code of this file.

Macros

#define SEPA_NAME   "cgmip"
 
#define SEPA_DESC   "Chvatal-Gomory cuts via MIPs separator"
 
#define SEPA_PRIORITY   -1000
 
#define SEPA_FREQ   -1
 
#define SEPA_MAXBOUNDDIST   0.0
 
#define SEPA_USESSUBSCIP   TRUE
 
#define SEPA_DELAY   FALSE
 
#define DEFAULT_MAXROUNDS   5
 
#define DEFAULT_MAXROUNDSROOT   50
 
#define DEFAULT_MAXDEPTH   -1
 
#define DEFAULT_DECISIONTREE   FALSE
 
#define DEFAULT_TIMELIMIT   1e20
 
#define DEFAULT_MEMORYLIMIT   1e20
 
#define DEFAULT_CUTCOEFBND   1000.0
 
#define DEFAULT_MINNODELIMIT   500LL
 
#define DEFAULT_MAXNODELIMIT   5000LL
 
#define DEFAULT_ONLYACTIVEROWS   FALSE
 
#define DEFAULT_MAXROWAGE   -1
 
#define DEFAULT_ONLYRANKONE   FALSE
 
#define DEFAULT_ONLYINTVARS   FALSE
 
#define DEFAULT_ALLOWLOCAL   FALSE
 
#define DEFAULT_CONTCONVERT   FALSE
 
#define DEFAULT_CONTCONVFRAC   0.1
 
#define DEFAULT_CONTCONVMIN   100
 
#define DEFAULT_INTCONVERT   FALSE
 
#define DEFAULT_INTCONVFRAC   0.1
 
#define DEFAULT_INTCONVMIN   100
 
#define DEFAULT_SKIPMULTBOUNDS   TRUE
 
#define DEFAULT_OBJLONE   FALSE
 
#define DEFAULT_OBJWEIGHT   1e-03
 
#define DEFAULT_OBJWEIGHTSIZE   TRUE
 
#define DEFAULT_DYNAMICCUTS   TRUE
 
#define DEFAULT_USECMIR   TRUE
 
#define DEFAULT_USESTRONGCG   FALSE
 
#define DEFAULT_CMIROWNBOUNDS   FALSE
 
#define DEFAULT_USECUTPOOL   TRUE
 
#define DEFAULT_PRIMALSEPARATION   TRUE
 
#define DEFAULT_EARLYTERM   TRUE
 
#define DEFAULT_ADDVIOLATIONCONS   FALSE
 
#define DEFAULT_ADDVIOLCONSHDLR   FALSE
 
#define DEFAULT_CONSHDLRUSENORM   TRUE
 
#define DEFAULT_USEOBJUB   FALSE
 
#define DEFAULT_USEOBJLB   FALSE
 
#define DEFAULT_SUBSCIPFAST   TRUE
 
#define DEFAULT_OUTPUT   FALSE
 
#define DEFAULT_RANDSEED   101
 
#define NROWSTOOSMALL   5
 
#define NCOLSTOOSMALL   5
 
#define EPSILONVALUE   1e-03
 
#define BETAEPSILONVALUE   1e-02
 
#define STALLNODELIMIT   1000LL
 
#define CONSHDLRFULLNORM   FALSE
 
#define MINEFFICACY   0.05
 
#define MAXNSOLS   1000
 
#define OBJWEIGHTRANGE   0.01
 
#define BOUNDSWITCH   0.9999
 
#define USEVBDS   TRUE
 
#define MINFRAC   0.0009 /* to allow a deviation of the same size as EPSILONVALUE */
 
#define MAXFRAC   0.9991 /* to allow a deviation of the same size as EPSILONVALUE */
 
#define FIXINTEGRALRHS   FALSE
 
#define MAKECONTINTEGRAL   FALSE
 
#define MAXWEIGHTRANGE   1e+05
 
#define MAXAGGRLEN(nvars)   nvars
 
#define CONSHDLR_NAME   "violatedCuts"
 
#define CONSHDLR_DESC   "only allow solutions corresponding to violated cuts"
 

Typedefs

typedef enum CGMIP_ColType CGMIP_COLTYPE
 
typedef struct CGMIP_MIPData CGMIP_MIPDATA
 

Enumerations

enum  CGMIP_ColType {
  colPresent = 0,
  colContinuous = 1,
  colConverted = 2,
  colAtUb = 3,
  colAtLb = 4
}
 

Functions

static SCIP_RETCODE computeCut (SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, SCIP_Bool *localrowsused, SCIP_Bool *localboundsused, int *cutrank, SCIP_Bool *success)
 
static SCIP_RETCODE solCutIsViolated (SCIP *scip, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Bool *violated)
 
static SCIP_DECL_CONSFREE (consFreeViolatedCuts)
 
static SCIP_DECL_CONSENFOLP (consEnfolpViolatedCuts)
 
static SCIP_DECL_CONSENFOPS (consEnfopsViolatedCuts)
 
static SCIP_DECL_CONSCHECK (consCheckViolatedCuts)
 
static SCIP_DECL_CONSLOCK (consLockViolatedCuts)
 
static SCIP_RETCODE SCIPincludeConshdlrViolatedCut (SCIP *scip, CGMIP_MIPDATA *mipdata)
 
static SCIP_RETCODE storeCutInArrays (SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, char normtype, SCIP_VAR **cutvars, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact, SCIP_Real *cutnorm)
 
static SCIP_RETCODE transformColumn (SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_COL *col, SCIP_Real offset, SCIP_Real sigma, SCIP_Real *lhs, SCIP_Real *rhs, SCIP_Real *lb, SCIP_Real *ub, SCIP_Real *primsol)
 
static SCIP_Real computeObjWeightSize (int rowsize, int minrowsize, int maxrowsize)
 
static SCIP_RETCODE createSubscip (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata)
 
static SCIP_RETCODE subscipSetParams (SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *success)
 
static SCIP_RETCODE solveSubscip (SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *success)
 
static SCIP_RETCODE createCGCutDirect (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_VAR **cutvars, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
 
static SCIP_RETCODE createCGCutCMIR (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_VAR **cutvars, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
 
static SCIP_RETCODE createCGCutStrongCG (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_VAR **cutvars, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
 
static SCIP_RETCODE createCGCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *cutoff, unsigned int *ngen)
 
static SCIP_RETCODE freeSubscip (SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata)
 
static SCIP_DECL_SEPAINIT (sepaInitCGMIP)
 
static SCIP_DECL_SEPAEXIT (sepaExitCGMIP)
 
static SCIP_DECL_SEPACOPY (sepaCopyCGMIP)
 
static SCIP_DECL_SEPAFREE (sepaFreeCGMIP)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpCGMIP)
 
SCIP_RETCODE SCIPincludeSepaCGMIP (SCIP *scip)
 

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME   "cgmip"

◆ SEPA_DESC

#define SEPA_DESC   "Chvatal-Gomory cuts via MIPs separator"

Definition at line 74 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   -1000

Definition at line 75 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ SEPA_FREQ

#define SEPA_FREQ   -1

Definition at line 76 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   0.0

Definition at line 77 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   TRUE

does the separator use a secondary SCIP instance?

Definition at line 78 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ SEPA_DELAY

#define SEPA_DELAY   FALSE

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

Definition at line 79 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS   5

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

Definition at line 81 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT   50

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

Definition at line 82 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_MAXDEPTH

#define DEFAULT_MAXDEPTH   -1

maximal depth at which the separator is applied

Definition at line 83 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_DECISIONTREE

#define DEFAULT_DECISIONTREE   FALSE

Use decision tree to turn separation on/off?

Definition at line 84 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_TIMELIMIT

#define DEFAULT_TIMELIMIT   1e20

time limit for sub-MIP (set to infinity in order to be deterministic)

Definition at line 85 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_MEMORYLIMIT

#define DEFAULT_MEMORYLIMIT   1e20

memory limit for sub-MIP

Definition at line 86 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_CUTCOEFBND

#define DEFAULT_CUTCOEFBND   1000.0

bounds on the values of the coefficients in the CG-cut

Definition at line 87 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_MINNODELIMIT

#define DEFAULT_MINNODELIMIT   500LL

minimum number of nodes considered for sub-MIP (-1: unlimited)

Definition at line 88 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_MAXNODELIMIT

#define DEFAULT_MAXNODELIMIT   5000LL

maximum number of nodes considered for sub-MIP (-1: unlimited)

Definition at line 89 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_ONLYACTIVEROWS

#define DEFAULT_ONLYACTIVEROWS   FALSE

Use only active rows to generate cuts?

Definition at line 90 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_MAXROWAGE

#define DEFAULT_MAXROWAGE   -1

maximal age of rows to consider if onlyactiverows is false

Definition at line 91 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_ONLYRANKONE

#define DEFAULT_ONLYRANKONE   FALSE

Separate rank 1 inequalities w.r.t. CG-MIP separator?

Definition at line 92 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_ONLYINTVARS

#define DEFAULT_ONLYINTVARS   FALSE

Generate cuts for problems with only integer variables?

Definition at line 93 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_ALLOWLOCAL

#define DEFAULT_ALLOWLOCAL   FALSE

Allow to generate local cuts?

Definition at line 94 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_CONTCONVERT

#define DEFAULT_CONTCONVERT   FALSE

Convert some integral variables to be continuous to reduce the size of the sub-MIP?

Definition at line 95 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_CONTCONVFRAC

#define DEFAULT_CONTCONVFRAC   0.1

fraction of integral variables converted to be continuous (if contconvert)

Definition at line 96 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_CONTCONVMIN

#define DEFAULT_CONTCONVMIN   100

minimum number of integral variables before some are converted to be continuous

Definition at line 97 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_INTCONVERT

#define DEFAULT_INTCONVERT   FALSE

Convert some integral variables attaining fractional values to have integral value?

Definition at line 98 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_INTCONVFRAC

#define DEFAULT_INTCONVFRAC   0.1

fraction of fractional integral variables converted to have integral value (if intconvert)

Definition at line 99 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_INTCONVMIN

#define DEFAULT_INTCONVMIN   100

minimum number of integral variables before some are converted to have integral value

Definition at line 100 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_SKIPMULTBOUNDS

#define DEFAULT_SKIPMULTBOUNDS   TRUE

Skip the upper bounds on the multipliers in the sub-MIP?

Definition at line 101 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_OBJLONE

#define DEFAULT_OBJLONE   FALSE

Should the objective of the sub-MIP only minimize the l1-norm of the multipliers?

Definition at line 102 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_OBJWEIGHT

#define DEFAULT_OBJWEIGHT   1e-03

objective weight for artificial variables

Definition at line 103 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_OBJWEIGHTSIZE

#define DEFAULT_OBJWEIGHTSIZE   TRUE

Weight each row by its size?

Definition at line 104 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_DYNAMICCUTS

#define DEFAULT_DYNAMICCUTS   TRUE

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

Definition at line 105 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_USECMIR

#define DEFAULT_USECMIR   TRUE

Use CMIR-generator (otherwise add cut directly)?

Definition at line 106 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_USESTRONGCG

#define DEFAULT_USESTRONGCG   FALSE

Use strong CG-function to strengthen cut?

Definition at line 107 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_CMIROWNBOUNDS

#define DEFAULT_CMIROWNBOUNDS   FALSE

Tell CMIR-generator which bounds to used in rounding?

Definition at line 108 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_USECUTPOOL

#define DEFAULT_USECUTPOOL   TRUE

Use cutpool to store CG-cuts even if the are not efficient?

Definition at line 109 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_PRIMALSEPARATION

#define DEFAULT_PRIMALSEPARATION   TRUE

Only separate cuts that are tight for the best feasible solution?

Definition at line 110 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_EARLYTERM

#define DEFAULT_EARLYTERM   TRUE

Terminate separation if a violated (but possibly sub-optimal) cut has been found?

Definition at line 111 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_ADDVIOLATIONCONS

#define DEFAULT_ADDVIOLATIONCONS   FALSE

Add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?

Definition at line 112 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_ADDVIOLCONSHDLR

#define DEFAULT_ADDVIOLCONSHDLR   FALSE

Add constraint handler to filter out violated cuts?

Definition at line 113 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_CONSHDLRUSENORM

#define DEFAULT_CONSHDLRUSENORM   TRUE

Should the violation constraint handler use the norm of a cut to check for feasibility?

Definition at line 114 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_USEOBJUB

#define DEFAULT_USEOBJUB   FALSE

Use upper bound on objective function (via primal solution)?

Definition at line 115 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_USEOBJLB

#define DEFAULT_USEOBJLB   FALSE

Use lower bound on objective function (via lower bound)?

Definition at line 116 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_SUBSCIPFAST

#define DEFAULT_SUBSCIPFAST   TRUE

Should the settings for the sub-MIP be optimized for speed?

Definition at line 117 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_OUTPUT

#define DEFAULT_OUTPUT   FALSE

Should information about the sub-MIP and cuts be displayed?

Definition at line 118 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   101

start random seed for random number generation

Definition at line 119 of file sepa_cgmip.c.

Referenced by SCIP_DECL_SEPAINIT().

◆ NROWSTOOSMALL

#define NROWSTOOSMALL   5

only separate if the number of rows is larger than this number

Definition at line 121 of file sepa_cgmip.c.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ NCOLSTOOSMALL

#define NCOLSTOOSMALL   5

only separate if the number of columns is larger than this number

Definition at line 122 of file sepa_cgmip.c.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ EPSILONVALUE

#define EPSILONVALUE   1e-03

epsilon value needed to model strict-inequalities

Definition at line 124 of file sepa_cgmip.c.

Referenced by createSubscip().

◆ BETAEPSILONVALUE

#define BETAEPSILONVALUE   1e-02

epsilon value for fracbeta - is larger than EPSILONVALUE for numerical stability

Definition at line 125 of file sepa_cgmip.c.

Referenced by createSubscip().

◆ STALLNODELIMIT

#define STALLNODELIMIT   1000LL

number of stalling nodes if earlyterm is true

Definition at line 126 of file sepa_cgmip.c.

Referenced by solveSubscip().

◆ CONSHDLRFULLNORM

#define CONSHDLRFULLNORM   FALSE

compute real cut and compute norm for this (if addviolconshdlr and conshdlrusenorm are true)

Definition at line 127 of file sepa_cgmip.c.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ MINEFFICACY

#define MINEFFICACY   0.05

minimum efficacy of a cut - compare set.c

Definition at line 128 of file sepa_cgmip.c.

Referenced by createSubscip(), and subscipSetParams().

◆ MAXNSOLS

#define MAXNSOLS   1000

maximal number of solutions stored in sub-SCIP

Definition at line 129 of file sepa_cgmip.c.

Referenced by subscipSetParams().

◆ OBJWEIGHTRANGE

#define OBJWEIGHTRANGE   0.01

maximal range of scaling of objective w.r.t. size of rows

Definition at line 130 of file sepa_cgmip.c.

Referenced by computeObjWeightSize().

◆ BOUNDSWITCH

#define BOUNDSWITCH   0.9999

Definition at line 133 of file sepa_cgmip.c.

Referenced by createCGCutCMIR(), and createCGCutStrongCG().

◆ USEVBDS

#define USEVBDS   TRUE

Definition at line 134 of file sepa_cgmip.c.

Referenced by createCGCutCMIR(), and createCGCutStrongCG().

◆ MINFRAC

#define MINFRAC   0.0009 /* to allow a deviation of the same size as EPSILONVALUE */

Definition at line 135 of file sepa_cgmip.c.

Referenced by createCGCutCMIR(), and createCGCutStrongCG().

◆ MAXFRAC

#define MAXFRAC   0.9991 /* to allow a deviation of the same size as EPSILONVALUE */

Definition at line 136 of file sepa_cgmip.c.

Referenced by createCGCutCMIR(), and createCGCutStrongCG().

◆ FIXINTEGRALRHS

#define FIXINTEGRALRHS   FALSE

Definition at line 137 of file sepa_cgmip.c.

Referenced by createCGCutCMIR().

◆ MAKECONTINTEGRAL

#define MAKECONTINTEGRAL   FALSE

Definition at line 138 of file sepa_cgmip.c.

Referenced by addCut(), createCGCutCMIR(), and createCGCutStrongCG().

◆ MAXWEIGHTRANGE

#define MAXWEIGHTRANGE   1e+05

maximal valid range max(|weights|)/min(|weights|) of row weights

Definition at line 139 of file sepa_cgmip.c.

Referenced by computeCut(), createCGCutCMIR(), and createCGCutStrongCG().

◆ MAXAGGRLEN

#define MAXAGGRLEN (   nvars)    nvars

currently very large to allow any generation; an alternative would be (0.1*(nvars)+1000)

Definition at line 141 of file sepa_cgmip.c.

Referenced by createCGCutCMIR(), and createCGCutStrongCG().

◆ CONSHDLR_NAME

#define CONSHDLR_NAME   "violatedCuts"

Definition at line 240 of file sepa_cgmip.c.

Referenced by SCIPincludeConshdlrViolatedCut().

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "only allow solutions corresponding to violated cuts"

Definition at line 241 of file sepa_cgmip.c.

Referenced by SCIPincludeConshdlrViolatedCut().

Typedef Documentation

◆ CGMIP_COLTYPE

Definition at line 197 of file sepa_cgmip.c.

◆ CGMIP_MIPDATA

typedef struct CGMIP_MIPData CGMIP_MIPDATA

Definition at line 232 of file sepa_cgmip.c.

Enumeration Type Documentation

◆ CGMIP_ColType

what happens for columns in the LP

Enumerator
colPresent 

column is present in the separating MIP

colContinuous 

column corresponds to a continuous variable

colConverted 

column is converted to be continuous

colAtUb 

variable corresponding to column was at it's upper bound and was complemented

colAtLb 

variable corresponding to column was at it's lower bound (possibly complemented)

Definition at line 189 of file sepa_cgmip.c.

Function Documentation

◆ computeCut()

static SCIP_RETCODE computeCut ( SCIP scip,
SCIP_SEPA sepa,
CGMIP_MIPDATA mipdata,
SCIP_SEPADATA sepadata,
SCIP_SOL sol,
SCIP_Real cutcoefs,
SCIP_Real cutrhs,
SCIP_Bool localrowsused,
SCIP_Bool localboundsused,
int *  cutrank,
SCIP_Bool success 
)
static

Computes cut from the given multipliers

Note that the cut computed here in general will not be the same as the one computed with the sub-MIP, because of numerical differences. Here, we only combine rows whose corresponding multiplier is positive w.r.t. the feasibility tolerance. In the sub-MIP, however, the rows are combined in any case. This makes a difference, if the coefficients in the matrix are large and hence yield a value that is larger than the tolerance.

Because of the transformations we have the following:

If variable \(x_j\) was complemented, we have \(x'_j = u_j - x_j\). If in the transformed system the lower bound is used, its corresponding multiplier is \(y^T A'_j - \lfloor y^T A'_j \rfloor\), which corresponds to

\[ y^T A'_j - \lfloor y^T A'_j \rfloor = - y^T A_j - \lfloor - y^T A_j \rfloor = - y^T A_j + \lceil y^T A_j \rceil \]

in the original system.

If such a variable was at its upper bound before the transformation, it is at its lower bound afterwards. Hence, its contribution to the cut is 0.

Note that if the original LP-solution does not satisfy some of the rows with equality the violation of the cut might be smaller than what is computed with the reduced sub-MIP.

Furthermore, note that if continuous variables have been shifted, the computed violated may be different as well, because the necessary changes in the lhs/rhs are not used here anymore.

Parameters
sciporiginal scip
sepaseparator
mipdatadata for sub-MIP
sepadataseparator data
solcurrent solution for sub-MIP
cutcoefscoefficients of the cut
cutrhsrhs of the cut
localrowsusedpointer to store whether local rows were used in summation
localboundsusedpointer to store whether local bounds were used in summation
cutrankpointer to store the cut rank
successwhether we produced a valid cut

Definition at line 2366 of file sepa_cgmip.c.

References BMSclearMemoryArray, colContinuous, colConverted, colPresent, FALSE, MAXWEIGHTRANGE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetObj(), SCIPcolGetUb(), SCIPcolGetVar(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfrac(), SCIPgetLowerbound(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetSolVal(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisIntegral(), SCIPisNegative(), SCIPisObjIntegral(), SCIPisSumPositive(), SCIPisSumZero(), SCIPisZero(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetOriginSepa(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsIntegral(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and TRUE.

Referenced by createCGCutDirect(), and solCutIsViolated().

◆ solCutIsViolated()

static SCIP_RETCODE solCutIsViolated ( SCIP scip,
CGMIP_MIPDATA mipdata,
SCIP_SOL sol,
SCIP_Bool violated 
)
static

check whether cut corresponding to solution is violated

Parameters
scipSCIP data structure
mipdatadata of separating sub-MIP
solsolution to be checked
violatedpointer to store if the cut is violated

Definition at line 268 of file sepa_cgmip.c.

References computeCut(), FALSE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfoMessage(), SCIPisEfficacious(), SCIPisZero(), SCIPvarGetLPSol(), and SCIPvarGetObj().

Referenced by SCIP_DECL_CONSCHECK(), and SCIP_DECL_CONSENFOLP().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeViolatedCuts  )
static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 461 of file sepa_cgmip.c.

References NULL, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpViolatedCuts  )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 478 of file sepa_cgmip.c.

References NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), SCIPgetNLPBranchCands(), and solCutIsViolated().

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsViolatedCuts  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 505 of file sepa_cgmip.c.

References NULL, SCIP_FEASIBLE, and SCIP_OKAY.

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckViolatedCuts  )
static

feasibility check method of constraint handler for integral solutions

Definition at line 519 of file sepa_cgmip.c.

References NULL, SCIP_Bool, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), and solCutIsViolated().

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockViolatedCuts  )
static

variable rounding lock method of constraint handler

Definition at line 545 of file sepa_cgmip.c.

References SCIP_OKAY.

◆ SCIPincludeConshdlrViolatedCut()

static SCIP_RETCODE SCIPincludeConshdlrViolatedCut ( SCIP scip,
CGMIP_MIPDATA mipdata 
)
static

creates the violated CG-cut constraint handler and includes it in SCIP

Parameters
scipSCIP data structure
mipdatadata of separating sub-MIP

Definition at line 554 of file sepa_cgmip.c.

References CONSHDLR_DESC, CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPincludeConshdlrBasic(), and SCIPsetConshdlrFree().

Referenced by createSubscip().

◆ storeCutInArrays()

static SCIP_RETCODE storeCutInArrays ( SCIP scip,
int  nvars,
SCIP_VAR **  vars,
SCIP_Real cutcoefs,
SCIP_Real varsolvals,
char  normtype,
SCIP_VAR **  cutvars,
SCIP_Real cutvals,
int *  cutlen,
SCIP_Real cutact,
SCIP_Real cutnorm 
)
static

stores nonzero elements of dense coefficient vector as sparse vector and calculates activity and norm

copied from sepa_gomory.c

Parameters
scipSCIP data structure
nvarsnumber of problem variables
varsproblem variables
cutcoefsdense coefficient vector
varsolvalsdense variable LP solution vector
normtypetype of norm to use for efficacy norm calculation
cutvarsarray to store variables of sparse cut vector
cutvalsarray to store coefficients of sparse cut vector
cutlenpointer to store number of nonzero entries in cut
cutactpointer to store activity of cut
cutnormpointer to store norm of cut vector

Definition at line 590 of file sepa_cgmip.c.

References NULL, REALABS, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, and SCIPisZero().

Referenced by createCGCutCMIR(), createCGCutDirect(), and createCGCutStrongCG().

◆ transformColumn()

static SCIP_RETCODE transformColumn ( SCIP scip,
SCIP_SEPADATA sepadata,
CGMIP_MIPDATA mipdata,
SCIP_COL col,
SCIP_Real  offset,
SCIP_Real  sigma,
SCIP_Real lhs,
SCIP_Real rhs,
SCIP_Real lb,
SCIP_Real ub,
SCIP_Real primsol 
)
static

Compute lhs/rhs for transformed column

Consider a variable \(x_j\) and some row of the original system:

\[ \gamma \leq a^T x \leq \delta, \quad \ell_j \leq x_j \leq u_j. \]

We perform the transformation

\[ x_i' = \left\{ \begin{array}{ll} s + \frac{1}{\sigma}\, x_j & \mbox{if }i = j\\ x_i & \mbox{otherwise}, \end{array} \right. \]

where \(s\) is the offset value and \(\sigma\) is a scaling factor. The new system is

\[ \gamma + \sigma\, a_j\,s \leq \sum_{i \neq j} a_i\, x_i' + \sigma a_j\, x_j' \leq \delta + \sigma\, a_j\, s \]

with bounds

\[ \frac{1}{\sigma} \ell_j + s \leq x_j' \leq \frac{1}{\sigma} u_j + s, \qquad \mbox{ if }\sigma > 0 \]

and

\[ \frac{1}{\sigma} u_j + s \leq x_j' \leq \frac{1}{\sigma} \ell_j + s, \qquad \mbox{ if }\sigma < 0. \]

This can be used as follows:

  • If \(x_j \geq \ell_j\) has a (nonzero) lower bound, one can use \(s = -\ell_j\), \(\sigma = 1\), and obtain \(\gamma - a_j\,\ell_j \leq a^T x' \leq \delta - a_j\,\ell_j\), \(0 \leq x_j' \leq u_j - \ell_j\).
  • If \(x_j \leq u_j\) has a (nonzero) upper bound, one can use \(s = u_j\), \(\sigma = -1\), and obtain \(\gamma - a_j\,u_j \leq \sum_{i \neq j} a_i\, x_i' - a_j\, x_j' \leq \delta - a_j\, u_j\), \(0 \leq x_j' \leq u_j - \ell_j\).
Parameters
scipSCIP data structure
sepadataseparator data
mipdatadata for sub-MIP
colcolumn that should be complemented
offsetoffset by which column should be shifted
sigmascaling factor
lhsarray of lhs of rows
rhsarray rhs of rows
lbpointer to lb of column
ubpointer to ub of column
primsolpointer to solution value

Definition at line 731 of file sepa_cgmip.c.

References NULL, SCIP_OKAY, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetObj(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPcolGetVar(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisNegative(), SCIPisZero(), SCIProwGetLPPos(), SCIProwIsLocal(), SCIProwIsModifiable(), and SCIPvarGetObj().

Referenced by createSubscip().

◆ computeObjWeightSize()

static SCIP_Real computeObjWeightSize ( int  rowsize,
int  minrowsize,
int  maxrowsize 
)
static

compute objective coefficient for rows that are weighted by size

The objective is computed by multiplying a default value by

\[ 1 - (r_{\mbox{max}} - r) \frac{1 - a}{r_{\mbox{max}} - r_{\mbox{min}}}, \]

where \(r\) is the size of the current row, \(a \in [0,1]\) is a parameter, and \(r_{\mbox{max}}\) and \(r_{\mbox{min}}\) are the maximal and minimal size of a row, respectively.

Thus, if \(r = r_{\mbox{max}}\), we get 1 and if \(r = r_{\mbox{min}}\), we get \(a\).

Parameters
rowsizesize of current row
minrowsizemaximal size of rows
maxrowsizeminimal size of rows

Definition at line 842 of file sepa_cgmip.c.

References OBJWEIGHTRANGE, and SCIP_Real.

Referenced by createSubscip().

◆ createSubscip()

static SCIP_RETCODE createSubscip ( SCIP scip,
SCIP_SEPA sepa,
SCIP_SEPADATA sepadata,
CGMIP_MIPDATA mipdata 
)
static

Creates a subscip representing the separating MIP.

Let the constraints of the original MIP be of the following form:

\[ \begin{array}{l@{\;}ll} a \leq A x + & C r & \leq b\\ \ell \leq x & & \leq u\\ c \leq & r & \leq d\\ x \in Z^n. \end{array} \]

Here, some of the bounds may have value \(\infty\) or \(-\infty\). Written in \(\leq\)-form this becomes:

\[ \begin{array}{r@{\;}l} \tilde{A} x + \tilde{C} r & \leq \tilde{b}\\ -x & \leq -\ell\\ x & \leq u\\ -r & \leq -c\\ r & \leq d\\ x \in Z^n, \end{array} \]

where we use

\[ \tilde{A} = \left[ \begin{array}{r} -A \\ A \end{array} \right], \quad \tilde{C} = \left[ \begin{array}{r} - C\\ C \end{array} \right] \qquad\mbox{ and }\qquad \tilde{b} = \left[ \begin{array}{r} -a\\ b \end{array} \right]. \]

For the moment we assume that \(c = 0\), i.e., the lower bounds on the continuous variables are 0. To obtain a Chvátal-Gomory cut we have to find nonnegative multipliers \(y\), \(\underline{z}\), and \(\overline{z}\) such that

\[ y^T \tilde{A} - \underline{z}^T + \overline{z}^T \in Z \qquad\mbox{ and }\qquad y^T \tilde{C} \geq 0. \]

Note that we use zero multipliers for the bounds on the continuous variables \(r\). Moreover, if some bounds are infinity, the corresponding multipliers are assumed to be 0. From these conditions, we obtain

\[ (y^T \tilde{A} - \underline{z}^T + \overline{z}^T)\, x + y^T \tilde{C} \, r \leq y^T \tilde{b} - \underline{z}^T \ell + \overline{z}^T u. \]

Because \(r \geq 0\), we can ignore the term \(y^T \tilde{C} \, r \geq 0\) and obtain the following cut:

\[ (y^T \tilde{A} - \underline{z}^T + \overline{z}^T )\, x \leq \lfloor y^T \tilde{b} - \underline{z}^T \ell + \overline{z}^T u \rfloor. \]

Assume that \(\ell = 0\) for the meantime. Then the cut can be written as:

\[ \lfloor y^T \tilde{A} + \overline{z}^T \rfloor \, x \leq \lfloor y^T \tilde{b} + \overline{z}^T u \rfloor. \]

Following Fischetti and Lodi [2005], let \((x^*,r^*)\) be a fractional solution of the above original system. The separating MIP created below is

\[ \begin{array}{rlr@{\;}l} \max & \multicolumn{2}{@{}l}{(x^*)^T \alpha - \beta - w^T y} &\\ & f = & \tilde{A}^T y + \overline{z} - \alpha & \\ & \tilde{f} = & \tilde{b}^T y + u^T \overline{z} - \beta &\\ & & \tilde{C}^T y & \geq 0\\ & & 0 \leq f & \leq 1 - \epsilon \\ & & 0 \leq \tilde{f} & \leq 1 - \epsilon\\ & & 0 \leq y, \overline{z} & \leq 1 - \epsilon.\\ & & \alpha \in Z^m, \beta & \in Z. \end{array} \]

Here, \(w\) is a weight vector; it's idea is to make the sum over all components of \(y\) as small as possible, in order to generate sparse cuts.

We perform the following additional computations:

  • If the lower bounds on \(x_i\) or \(r_j\) are finite, we shift the variable to have a zero lower bound, i.e., we replace it by \(x_i - \ell_i\) (or \(r_j - u_j\)). This is helpful in several ways: As seen above, the resulting inequalities/formulations simplify. Moreover, it allows to drop a variable if \(x^*_i = 0\), see the next comment. If the lower bounds are not finite, but the upper bounds are finite, we can complement the variable. If the variables are free, the above formulation changes as follows: For free continuous variables, we require \(\tilde{C}^T y = 0\). For a free integer variable \(x_j\) (which rarely occurs in practice), we require \(f_j = 0\), i.e., we force that \((\tilde{A}^T y + \overline{z})_j = \alpha_j\).
  • If \(x^*_j = 0 = \ell_j\) (after the above preprocessing), we drop variable \(\alpha_j\) from the formulation. Let \((\alpha^*, \beta^*, y^*, \overline{z}^*)\) be an optimal solution to the separating MIP. Then we can compute \(\alpha_j = \lfloor(\tilde{A}_j^T y^* + \overline{z}^*)\rfloor\).
  • If \(x^*_i = u_i\), we complement the variable and drop it from the formulation, since the lower bound is 0 afterwards.
  • If a variable has been shifted or complemented, we have to recompute \(\beta\) with the original lhs/rhs.
  • If a continuous variable \(r_j\) is free, we have to force equality for the corresponding components in \(y^T \tilde{C} \, r \geq 0\).
  • If an integer variable \(x_i\) is free, we are not allowed to round the cut down. In this case, the combintation of rows and bounds has to be integral. We force this by requiring that \(f_i = 0\).
  • If contconvert is true some integral variables are randomly treated as if they were continuous. This has the effect that in the resulting cut the corresponding coefficient has value 0. This makes the cuts more sparse. Moreover, the separation problems should become easier.
  • If required, i.e., parameter primalseparation is true, we force a primal separation step. For this we require that the cut is tight at the currently best solution. To get reliable solutions we relax equality by EPSILONVALUE.
  • If required (via parameters useobjub or useobjlb), we add a row corresponding to the objective function with respect to the current lower and upper bounds.
Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
mipdatadata for sub-MIP

Definition at line 1000 of file sepa_cgmip.c.

References BETAEPSILONVALUE, colAtLb, colAtUb, colContinuous, colConverted, colPresent, computeObjWeightSize(), EPSILONVALUE, FALSE, MINEFFICACY, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OBJSENSE_MAXIMIZE, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_INTEGER, SCIPaddCons(), SCIPaddVar(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcolGetLb(), SCIPcolGetNLPNonz(), SCIPcolGetObj(), SCIPcolGetPrimsol(), SCIPcolGetRows(), SCIPcolGetUb(), SCIPcolGetVals(), SCIPcolGetVar(), SCIPcolIsIntegral(), SCIPcreate(), SCIPcreateConsLinear(), SCIPcreateProb(), SCIPcreateVar(), SCIPdebugMsg, SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetLowerbound(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNObjVars(), SCIPgetProbName(), SCIPgetRowLPActivity(), SCIPgetSolVal(), SCIPgetUpperbound(), SCIPgetVarSol(), SCIPincludeConshdlrViolatedCut(), SCIPincludeDefaultPlugins(), SCIPinfinity(), SCIPinfoMessage(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPisObjIntegral(), SCIPisZero(), SCIPrandomGetReal(), SCIPreleaseCons(), SCIProwGetAge(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetOriginSepa(), SCIProwGetRhs(), SCIProwIsIntegral(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPsetObjsense(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPwriteOrigProblem(), transformColumn(), and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ subscipSetParams()

static SCIP_RETCODE subscipSetParams ( SCIP_SEPADATA sepadata,
CGMIP_MIPDATA mipdata,
SCIP_Bool success 
)
static

sets parameters for subscip

Parameters
sepadataseparator data
mipdatadata for sub-MIP
successif setting was successful -> stop solution otherwise

Definition at line 1995 of file sepa_cgmip.c.

References FALSE, MAXNSOLS, MINEFFICACY, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMEMPHASIS_FEASIBILITY, SCIP_PARAMSETTING_FAST, SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetEmphasis(), SCIPsetIntParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetRealParam(), SCIPsetSeparating(), SCIPsetSubscipsOff(), and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ solveSubscip()

◆ createCGCutDirect()

static SCIP_RETCODE createCGCutDirect ( SCIP scip,
SCIP_SEPA sepa,
SCIP_SEPADATA sepadata,
CGMIP_MIPDATA mipdata,
SCIP_SOL sol,
SCIP_Real cutcoefs,
SCIP_VAR **  cutvars,
SCIP_Real cutvals,
SCIP_Real varsolvals,
SCIP_Real weights,
int *  nprevrows,
SCIP_ROW **  prevrows,
SCIP_Bool cutoff,
unsigned int *  ngen 
)
static

Create CG-cut directly from solution of sub-MIP

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
mipdatadata for sub-MIP
solsolution of sub-MIP
cutcoefscut coefficients
cutvarsvariables appearing in cut
cutvalsvalues of variables in cut
varsolvalssolution value of variables
weightsweights to compute cmir cut
nprevrowsnumber of previously generated rows
prevrowspreviously generated rows
cutoffwhether a cutoff has been detected
ngennumber of generated cuts

Definition at line 2859 of file sepa_cgmip.c.

References colContinuous, colConverted, colPresent, computeCut(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCut(), SCIPaddPoolCut(), SCIPaddVarsToRow(), SCIPcolGetVar(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPgetCutEfficacy(), SCIPgetLPColsData(), SCIPgetNLPs(), SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfinity(), SCIPisEfficacious(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisGE(), SCIPisPositive(), SCIPprintRow(), SCIPprintSol(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetNorm(), SCIProwGetParallelism(), SCIProwGetRhs(), SCIPsnprintf(), SCIPvarGetObj(), SCIPvarGetProbindex(), storeCutInArrays(), and TRUE.

Referenced by createCGCuts().

◆ createCGCutCMIR()

static SCIP_RETCODE createCGCutCMIR ( SCIP scip,
SCIP_SEPA sepa,
SCIP_SEPADATA sepadata,
CGMIP_MIPDATA mipdata,
SCIP_SOL sol,
SCIP_Real cutcoefs,
SCIP_VAR **  cutvars,
SCIP_Real cutvals,
SCIP_Real varsolvals,
SCIP_Real weights,
int *  boundsfortrans,
SCIP_BOUNDTYPE boundtypesfortrans,
int *  nprevrows,
SCIP_ROW **  prevrows,
SCIP_Bool cutoff,
unsigned int *  ngen 
)
static

create CG-cut via CMIR-function

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
mipdatadata for sub-MIP
solsolution of sub-MIP
cutcoefscut coefficients
cutvarsvariables appearing in cut
cutvalsvalues of variables in cut
varsolvalssolution value of variables
weightsweights to compute cmir cut
boundsfortransbounds for cmir function of NULL
boundtypesfortranstype of bounds for cmir function or NULL
nprevrowsnumber of previously generated rows
prevrowspreviously generated rows
cutoffwhether a cutoff has been detected
ngennumber of generated cuts

Definition at line 3068 of file sepa_cgmip.c.

References BOUNDSWITCH, colContinuous, colConverted, FALSE, FIXINTEGRALRHS, MAKECONTINTEGRAL, MAXAGGRLEN, MAXFRAC, MAXWEIGHTRANGE, MINFRAC, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPaddCut(), SCIPaddPoolCut(), SCIPaddVarsToRow(), SCIPcalcMIR(), SCIPcolGetLPPos(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPepsilon(), SCIPfrac(), SCIPgetCutEfficacy(), SCIPgetLPRowsData(), SCIPgetNLPs(), SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisGE(), SCIPisPositive(), SCIPisSumPositive(), SCIPmakeRowIntegral(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetNorm(), SCIProwGetParallelism(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPsnprintf(), SCIPsumepsilon(), SCIPvarGetCol(), SCIPvarGetStatus(), SCIPvarIsIntegral(), storeCutInArrays(), and USEVBDS.

Referenced by createCGCuts().

◆ createCGCutStrongCG()

static SCIP_RETCODE createCGCutStrongCG ( SCIP scip,
SCIP_SEPA sepa,
SCIP_SEPADATA sepadata,
CGMIP_MIPDATA mipdata,
SCIP_SOL sol,
SCIP_Real cutcoefs,
SCIP_VAR **  cutvars,
SCIP_Real cutvals,
SCIP_Real varsolvals,
SCIP_Real weights,
int *  nprevrows,
SCIP_ROW **  prevrows,
SCIP_Bool cutoff,
unsigned int *  ngen 
)
static

create CG-cut via strong-CG-function

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
mipdatadata for sub-MIP
solsolution of sub-MIP
cutcoefscut coefficients
cutvarsvariables appearing in cut
cutvalsvalues of variables in cut
varsolvalssolution value of variables
weightsweights to compute cmir cut
nprevrowsnumber of previously generated rows
prevrowspreviously generated rows
cutoffwhether a cutoff has been detected
ngennumber of generated cuts

Definition at line 3357 of file sepa_cgmip.c.

References BOUNDSWITCH, FALSE, MAKECONTINTEGRAL, MAXAGGRLEN, MAXFRAC, MAXWEIGHTRANGE, MINFRAC, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCut(), SCIPaddPoolCut(), SCIPaddVarsToRow(), SCIPcalcStrongCG(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPepsilon(), SCIPfrac(), SCIPgetCutEfficacy(), SCIPgetLPRowsData(), SCIPgetNLPs(), SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisGE(), SCIPisPositive(), SCIPmakeRowIntegral(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetNorm(), SCIProwGetParallelism(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPsnprintf(), SCIPsumepsilon(), storeCutInArrays(), and USEVBDS.

Referenced by createCGCuts().

◆ createCGCuts()

static SCIP_RETCODE createCGCuts ( SCIP scip,
SCIP_SEPA sepa,
SCIP_SEPADATA sepadata,
CGMIP_MIPDATA mipdata,
SCIP_Bool cutoff,
unsigned int *  ngen 
)
static

Create CG-cuts from solutions of sub-MIP

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
mipdatadata for sub-MIP
cutoffwhether a cutoff has been detected
ngennumber of generated cuts

Definition at line 3588 of file sepa_cgmip.c.

References createCGCutCMIR(), createCGCutDirect(), createCGCutStrongCG(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVED, SCIP_STAGE_SOLVING, SCIP_VARSTATUS_COLUMN, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetNLPRows(), SCIPgetNSols(), SCIPgetSols(), SCIPgetStage(), SCIPgetVarsData(), SCIPreleaseRow(), SCIPvarGetLPSol(), and SCIPvarGetStatus().

Referenced by SCIP_DECL_SEPAEXECLP().

◆ freeSubscip()

static SCIP_RETCODE freeSubscip ( SCIP scip,
SCIP_SEPA sepa,
CGMIP_MIPDATA mipdata 
)
static

frees "subscip" data

Parameters
scipSCIP data structure
sepaseparator data
mipdatadata for sub-MIP

Definition at line 3731 of file sepa_cgmip.c.

References colPresent, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfree(), SCIPfreeBlockMemoryArray, SCIPreleaseVar(), and SCIPsepaGetData().

Referenced by SCIP_DECL_SEPAEXECLP().

◆ SCIP_DECL_SEPAINIT()

static SCIP_DECL_SEPAINIT ( sepaInitCGMIP  )
static

initialization method of separator (called after problem was transformed)

Definition at line 3820 of file sepa_cgmip.c.

References DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPinitializeRandomSeed(), SCIPrandomCreate(), and SCIPsepaGetData().

◆ SCIP_DECL_SEPAEXIT()

static SCIP_DECL_SEPAEXIT ( sepaExitCGMIP  )
static

deinitialization method of separator (called before transformed problem is freed)

Definition at line 3835 of file sepa_cgmip.c.

References NULL, SCIP_OKAY, SCIPrandomFree(), and SCIPsepaGetData().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyCGMIP  )
static

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

Definition at line 3849 of file sepa_cgmip.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaCGMIP(), SCIPsepaGetName(), and SEPA_NAME.

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeCGMIP  )
static

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

Definition at line 3864 of file sepa_cgmip.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.

◆ SCIP_DECL_SEPAEXECLP()