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 possibilities 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 taken 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 process 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 "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/cuts.h"
#include "scip/pub_cons.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_sepa.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sepa.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include "scip/scipdefplugins.h"
#include "scip/sepa_cgmip.h"
#include <string.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_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	DEFAULT_GENPRIMALSOLS FALSE

#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	POSTPROCESS TRUE

#define	MINFRAC 0.0009

#define	MAXFRAC 0.9991

#define	FIXINTEGRALRHS FALSE

#define	MAKECONTINTEGRAL FALSE

#define	MAXWEIGHTRANGE 1e+05

#define	AWAY 0.005

#define	SEPARATEROWS TRUE

#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_Bool usefrac, 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_Real cutcoefs, SCIP_Real varsolvals, char normtype, int cutinds, 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 origscip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, CGMIP_MIPDATA mipdata)

static SCIP_RETCODE	subscipSetParams (SCIP_SEPADATA sepadata, CGMIP_MIPDATA mipdata)

static SCIP_RETCODE	createCGMIPprimalsols (SCIP scip, SCIP_SEPADATA sepadata, CGMIP_MIPDATA *mipdata)

static SCIP_RETCODE	solveSubscip (SCIP origscip, 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, int cutinds, 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_AGGRROW aggrrow, SCIP_Real cutcoefs, int cutinds, 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_AGGRROW aggrrow, SCIP_Real cutcoefs, int cutinds, 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"

Definition at line 97 of file sepa_cgmip.c.

Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAFREE(), and SCIPincludeSepaCGMIP().

◆ SEPA_DESC

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

Definition at line 98 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY -1000

Definition at line 99 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ SEPA_FREQ

#define SEPA_FREQ -1

Definition at line 100 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 0.0

Definition at line 101 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 102 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 103 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 105 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 106 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 107 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 108 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 109 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_MEMORYLIMIT

#define DEFAULT_MEMORYLIMIT 1e20

memory limit for sub-MIP

Definition at line 110 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 111 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 112 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 113 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_ONLYACTIVEROWS

#define DEFAULT_ONLYACTIVEROWS FALSE

Use only active rows to generate cuts?

Definition at line 114 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 115 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 116 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 117 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 118 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 119 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 120 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 121 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 122 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 123 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 124 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 125 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_OBJWEIGHT

#define DEFAULT_OBJWEIGHT 1e-03

objective weight for artificial variables

Definition at line 126 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_OBJWEIGHTSIZE

#define DEFAULT_OBJWEIGHTSIZE TRUE

Weight each row by its size?

Definition at line 127 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 128 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_USECMIR

#define DEFAULT_USECMIR TRUE

Use CMIR-generator (otherwise add cut directly)?

Definition at line 129 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_USESTRONGCG

#define DEFAULT_USESTRONGCG FALSE

Use strong CG-function to strengthen cut?

Definition at line 130 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 131 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 132 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 133 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 134 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 135 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 136 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 137 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 138 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 139 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 140 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 141 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 101

start random seed for random number generation

Definition at line 142 of file sepa_cgmip.c.

Referenced by SCIP_DECL_SEPAINIT().

◆ DEFAULT_GENPRIMALSOLS

#define DEFAULT_GENPRIMALSOLS FALSE

Try to generate primal solutions from Gomory cuts?

Definition at line 143 of file sepa_cgmip.c.

Referenced by SCIPincludeSepaCGMIP().

◆ NROWSTOOSMALL

#define NROWSTOOSMALL 5

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

Definition at line 146 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 147 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 149 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 150 of file sepa_cgmip.c.

Referenced by createSubscip().

◆ STALLNODELIMIT

#define STALLNODELIMIT 1000LL

number of stalling nodes if earlyterm is true

Definition at line 151 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 152 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 153 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 154 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 155 of file sepa_cgmip.c.

Referenced by computeObjWeightSize().

◆ BOUNDSWITCH

#define BOUNDSWITCH 0.9999

Definition at line 158 of file sepa_cgmip.c.

Referenced by createCGCutCMIR(), and createCGCutStrongCG().

◆ USEVBDS

#define USEVBDS TRUE

Definition at line 159 of file sepa_cgmip.c.

Referenced by createCGCutCMIR(), and createCGCutStrongCG().

◆ POSTPROCESS

#define POSTPROCESS TRUE

Definition at line 160 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 161 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 162 of file sepa_cgmip.c.

Referenced by createCGCutCMIR(), and createCGCutStrongCG().

◆ FIXINTEGRALRHS

#define FIXINTEGRALRHS FALSE

Definition at line 163 of file sepa_cgmip.c.

Referenced by createCGCutCMIR().

◆ MAKECONTINTEGRAL

#define MAKECONTINTEGRAL FALSE

Definition at line 164 of file sepa_cgmip.c.

Referenced by createCGCutCMIR(), and createCGCutStrongCG().

◆ MAXWEIGHTRANGE

#define MAXWEIGHTRANGE 1e+05

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

Definition at line 165 of file sepa_cgmip.c.

Referenced by computeCut().

◆ AWAY

#define AWAY 0.005

minimal fractionality of a basic variable in order to try GMI cut

Definition at line 166 of file sepa_cgmip.c.

Referenced by createCGMIPprimalsols().

◆ SEPARATEROWS

#define SEPARATEROWS TRUE

Separate rows with integral slack?

Definition at line 167 of file sepa_cgmip.c.

◆ MAXAGGRLEN

#define MAXAGGRLEN ( nvars ) nvars

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

Definition at line 169 of file sepa_cgmip.c.

Referenced by createCGCutCMIR(), and createCGCutStrongCG().

◆ CONSHDLR_NAME

#define CONSHDLR_NAME "violatedCuts"

Definition at line 272 of file sepa_cgmip.c.

Referenced by SCIPincludeConshdlrViolatedCut().

◆ CONSHDLR_DESC

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

Definition at line 273 of file sepa_cgmip.c.

Referenced by SCIPincludeConshdlrViolatedCut().

Typedef Documentation

◆ CGMIP_COLTYPE

typedef enum CGMIP_ColType CGMIP_COLTYPE

Definition at line 226 of file sepa_cgmip.c.

◆ CGMIP_MIPDATA

typedef struct CGMIP_MIPData CGMIP_MIPDATA

Definition at line 264 of file sepa_cgmip.c.

Enumeration Type Documentation

◆ CGMIP_ColType

enum 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 218 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_Bool	usefrac,
		SCIP_Real *	cutcoefs,
		SCIP_Real *	cutrhs,
		SCIP_Bool *	localrowsused,
		SCIP_Bool *	localboundsused,
		int *	cutrank,
		SCIP_Bool *	success
	)

static

Computes cut from the given multipliers

When computing the cut, we take the fractional part of the multipliers. This is known to produce stronger cuts in the pure integer case, since the cut is the sum of the one using fractional parts and integer multiples of the original constraints. However, if there are continuous variables, the resulting cut might not be valid. This is checked and returned.

Moreover, 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 violation may be different as well, because the necessary changes in the lhs/rhs are not used here anymore.

Parameters

scip	original scip
sepa	separator
mipdata	data for sub-MIP
sepadata	separator data
sol	current solution for sub-MIP
usefrac	use fractional value of multipliers
cutcoefs	coefficients of the cut
cutrhs	rhs of the cut
localrowsused	pointer to store whether local rows were used in summation
localboundsused	pointer to store whether local bounds were used in summation
cutrank	pointer to store the cut rank
success	whether we produced a valid cut

Definition at line 2710 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

scip	SCIP data structure
mipdata	data of separating sub-MIP
sol	solution to be checked
violated	pointer to store if the cut is violated

Definition at line 300 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(), SCIPvarGetObj(), and TRUE.

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 499 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 516 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 543 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 557 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 583 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

scip	SCIP data structure
mipdata	data of separating sub-MIP

Definition at line 592 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_Real *	cutcoefs,
		SCIP_Real *	varsolvals,
		char	normtype,
		int *	cutinds,
		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

scip	SCIP data structure
nvars	number of problem variables
cutcoefs	dense coefficient vector
varsolvals	dense variable LP solution vector
normtype	type of norm to use for efficacy norm calculation
cutinds	array to store variables of sparse cut vector
cutvals	array to store coefficients of sparse cut vector
cutlen	pointer to store number of nonzero entries in cut
cutact	pointer to store activity of cut
cutnorm	pointer to store norm of cut vector

Definition at line 628 of file sepa_cgmip.c.

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

Referenced by createCGCutDirect().

◆ 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

scip	SCIP data structure
sepadata	separator data
mipdata	data for sub-MIP
col	column that should be complemented
offset	offset by which column should be shifted
sigma	scaling factor
lhs	array of lhs of rows
rhs	array rhs of rows
lb	pointer to lb of column
ub	pointer to ub of column
primsol	pointer to solution value

Definition at line 768 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

rowsize	size of current row
minrowsize	maximal size of rows
maxrowsize	minimal size of rows

Definition at line 879 of file sepa_cgmip.c.

References a, OBJWEIGHTRANGE, and SCIP_Real.

Referenced by createSubscip().

◆ createSubscip()

static SCIP_RETCODE createSubscip	(	SCIP *	origscip,
		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 & (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

origscip	SCIP data structure
sepa	separator
sepadata	separator data
mipdata	data for sub-MIP

Definition at line 1037 of file sepa_cgmip.c.

References BETAEPSILONVALUE, colAtLb, colAtUb, colContinuous, colConverted, colPresent, computeObjWeightSize(), EPSILONVALUE, FALSE, MINEFFICACY, NULL, r, 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
	)

static

sets parameters for subscip

Parameters

sepadata	separator data
mipdata	data for sub-MIP

Definition at line 2032 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().

◆ createCGMIPprimalsols()

static SCIP_RETCODE createCGMIPprimalsols	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		CGMIP_MIPDATA *	mipdata
	)

static

try to convert fractional gomory cuts to primal solutions of CG-MIP

Parameters

scip	original SCIP data structure
sepadata	separator data
mipdata	data for sub-MIP

Definition at line 2161 of file sepa_cgmip.c.

References AWAY, BMSclearMemoryArray, colPresent, fabs(), FALSE, NULL, r, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPcreateSol(), SCIPdebugMsg, SCIPfeasFrac(), SCIPfloor(), SCIPfrac(), SCIPfreeBufferArray, SCIPgetLPBasisInd(), SCIPgetLPBInvRow(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetRowLPActivity(), SCIPgetVarsData(), SCIPgetVarSol(), SCIPisEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIProwGetBasisStatus(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsIntegral(), SCIProwIsModifiable(), SCIPsetSolVal(), SCIPtrySolFree(), SCIPvarGetType(), and TRUE.

Referenced by solveSubscip().

◆ solveSubscip()

static SCIP_RETCODE solveSubscip	(	SCIP *	origscip,
		SCIP_SEPADATA *	sepadata,
		CGMIP_MIPDATA *	mipdata,
		SCIP_Bool *	success
	)

static

solve subscip

Parameters

origscip	SCIP data structure
sepadata	separator data
mipdata	data for sub-MIP
success	if setting was successful -> stop

Definition at line 2410 of file sepa_cgmip.c.

References createCGMIPprimalsols(), FALSE, MAX, NULL, SCIP_CALL, SCIP_ERROR, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_USERINTERRUPT, SCIPcheckCopyLimits(), SCIPdebugMsg, SCIPerrorMessage, SCIPgetDualbound(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNLPIterations(), SCIPgetNNodes(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPgetStatus(), SCIPisInfinity(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsolve(), SCIPtransformProb(), SCIPwarningMessage(), STALLNODELIMIT, and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ createCGCutDirect()

static SCIP_RETCODE createCGCutDirect	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		CGMIP_MIPDATA *	mipdata,
		SCIP_SOL *	sol,
		SCIP_Real *	cutcoefs,
		int *	cutinds,
		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

scip	SCIP data structure
sepa	separator
sepadata	separator data
mipdata	data for sub-MIP
sol	solution of sub-MIP
cutcoefs	cut coefficients
cutinds	problem indices of variables appearing in cut
cutvals	values of variables in cut
varsolvals	solution value of variables
weights	weights to compute cmir cut
nprevrows	number of previously generated rows
prevrows	previously generated rows
cutoff	whether a cutoff has been detected
ngen	number of generated cuts

Definition at line 3221 of file sepa_cgmip.c.

References colContinuous, colConverted, colPresent, computeCut(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcolGetVar(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), 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_AGGRROW *	aggrrow,
		SCIP_Real *	cutcoefs,
		int *	cutinds,
		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

scip	SCIP data structure
sepa	separator
sepadata	separator data
mipdata	data for sub-MIP
sol	solution of sub-MIP
aggrrow	aggregation row to use for creating MIR cut
cutcoefs	cut coefficients
cutinds	problem indices of variables appearing in cut
cutvals	values of variables in cut
varsolvals	solution value of variables
weights	weights to compute cmir cut
boundsfortrans	bounds for cmir function of NULL
boundtypesfortrans	type of bounds for cmir function or NULL
nprevrows	number of previously generated rows
prevrows	previously generated rows
cutoff	whether a cutoff has been detected
ngen	number of generated cuts

Definition at line 3444 of file sepa_cgmip.c.

References BOUNDSWITCH, colContinuous, colConverted, FALSE, FIXINTEGRALRHS, MAKECONTINTEGRAL, MAXAGGRLEN, MAXFRAC, MINFRAC, NULL, POSTPROCESS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPaggrRowSumRows(), SCIPcacheRowExtensions(), SCIPcalcMIR(), SCIPcolGetLPPos(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPepsilon(), SCIPflushRowExtensions(), SCIPfrac(), SCIPgetCutEfficacy(), SCIPgetLPRowsData(), SCIPgetNLPs(), SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisGE(), SCIPisSumPositive(), SCIPmakeRowIntegral(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetNorm(), SCIProwGetParallelism(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPsnprintf(), SCIPsumepsilon(), SCIPvarGetCol(), SCIPvarGetStatus(), SCIPvarIsIntegral(), 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_AGGRROW *	aggrrow,
		SCIP_Real *	cutcoefs,
		int *	cutinds,
		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

scip	SCIP data structure
sepa	separator
sepadata	separator data
mipdata	data for sub-MIP
sol	solution of sub-MIP
aggrrow	aggregation row to use for creating MIR cut
cutcoefs	cut coefficients
cutinds	problem indices of variables appearing in cut
cutvals	values of variables in cut
varsolvals	solution value of variables
weights	weights to compute cmir cut
nprevrows	number of previously generated rows
prevrows	previously generated rows
cutoff	whether a cutoff has been detected
ngen	number of generated cuts

Definition at line 3734 of file sepa_cgmip.c.

References BOUNDSWITCH, FALSE, MAKECONTINTEGRAL, MAXAGGRLEN, MAXFRAC, MINFRAC, NULL, POSTPROCESS, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPaggrRowSumRows(), SCIPcacheRowExtensions(), SCIPcalcStrongCG(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPepsilon(), SCIPflushRowExtensions(), SCIPfrac(), SCIPgetCutEfficacy(), SCIPgetLPRowsData(), SCIPgetNLPs(), SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisGE(), SCIPmakeRowIntegral(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetNorm(), SCIProwGetParallelism(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPsnprintf(), SCIPsumepsilon(), 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

scip	SCIP data structure
sepa	separator
sepadata	separator data
mipdata	data for sub-MIP
cutoff	whether a cutoff has been detected
ngen	number of generated cuts

Definition at line 3965 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, SCIPaggrRowCreate(), SCIPaggrRowFree(), 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

scip	SCIP data structure
sepa	separator data
mipdata	data for sub-MIP

Definition at line 4119 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 4210 of file sepa_cgmip.c.

References DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), and TRUE.

◆ SCIP_DECL_SEPAEXIT()

static SCIP_DECL_SEPAEXIT ( sepaExitCGMIP )

static

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

Definition at line 4225 of file sepa_cgmip.c.

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

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyCGMIP )

static

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

Definition at line 4239 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 4254 of file sepa_cgmip.c.

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

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpCGMIP )

static

LP solution separation method of separator

Definition at line 4276 of file sepa_cgmip.c.

References CONSHDLRFULLNORM, createCGCuts(), createSubscip(), FALSE, freeSubscip(), NCOLSTOOSMALL, NROWSTOOSMALL, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_VERBLEVEL_NORMAL, SCIPallocBlockMemory, SCIPdebugMsg, SCIPfreeBlockMemory, SCIPgetCharParam(), SCIPgetDepth(), SCIPgetFirstLPTime(), SCIPgetLPSolstat(), SCIPgetNContVars(), SCIPgetNLPBranchCands(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPisStopped(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SCIPsetBoolParam(), SCIPverbMessage(), SEPA_NAME, SCIP_Sepa::sepadata, solveSubscip(), subscipSetParams(), and TRUE.

SCIP

Detailed Description

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ DEFAULT_MAXROUNDS

◆ DEFAULT_MAXROUNDSROOT

◆ DEFAULT_MAXDEPTH

◆ DEFAULT_DECISIONTREE

◆ DEFAULT_TIMELIMIT

◆ DEFAULT_MEMORYLIMIT

◆ DEFAULT_CUTCOEFBND

◆ DEFAULT_MINNODELIMIT

◆ DEFAULT_MAXNODELIMIT

◆ DEFAULT_ONLYACTIVEROWS

◆ DEFAULT_MAXROWAGE

◆ DEFAULT_ONLYRANKONE

◆ DEFAULT_ONLYINTVARS

◆ DEFAULT_CONTCONVERT

◆ DEFAULT_CONTCONVFRAC

◆ DEFAULT_CONTCONVMIN

◆ DEFAULT_INTCONVERT

◆ DEFAULT_INTCONVFRAC

◆ DEFAULT_INTCONVMIN

◆ DEFAULT_SKIPMULTBOUNDS

◆ DEFAULT_OBJLONE

◆ DEFAULT_OBJWEIGHT

◆ DEFAULT_OBJWEIGHTSIZE

◆ DEFAULT_DYNAMICCUTS

◆ DEFAULT_USECMIR

◆ DEFAULT_USESTRONGCG

◆ DEFAULT_CMIROWNBOUNDS

◆ DEFAULT_USECUTPOOL

◆ DEFAULT_PRIMALSEPARATION

◆ DEFAULT_EARLYTERM

◆ DEFAULT_ADDVIOLATIONCONS

◆ DEFAULT_ADDVIOLCONSHDLR

◆ DEFAULT_CONSHDLRUSENORM

◆ DEFAULT_USEOBJUB

◆ DEFAULT_USEOBJLB

◆ DEFAULT_SUBSCIPFAST

◆ DEFAULT_OUTPUT

◆ DEFAULT_RANDSEED

◆ DEFAULT_GENPRIMALSOLS

◆ NROWSTOOSMALL

◆ NCOLSTOOSMALL

◆ EPSILONVALUE

◆ BETAEPSILONVALUE

◆ STALLNODELIMIT

◆ CONSHDLRFULLNORM

◆ MINEFFICACY

◆ MAXNSOLS

◆ OBJWEIGHTRANGE

◆ BOUNDSWITCH

◆ USEVBDS

◆ POSTPROCESS

◆ MINFRAC

◆ MAXFRAC

◆ FIXINTEGRALRHS

◆ MAKECONTINTEGRAL

◆ MAXWEIGHTRANGE

◆ AWAY

◆ SEPARATEROWS

◆ MAXAGGRLEN

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

Typedef Documentation

◆ CGMIP_COLTYPE

◆ CGMIP_MIPDATA

Enumeration Type Documentation

◆ CGMIP_ColType