Scippy

SCIP

Solving Constraint Integer Programs

sepa_gmi.c File Reference

Detailed Description

Gomory Mixed-Integer Cuts.

Author
Giacomo Nannicini
Marc Pfetsch

This file implements a Gomory Mixed-Integer (GMI) cuts generator that reads cuts from the simplex tableau, applying the textbook formula:

\[ \sum_{j \in J_I : f_j \leq f_0} f_j x_j + \sum_{j \in J_I : f_j > f_0} f_0 \frac{1-f_j}{1 - f_0} x_j + \sum_{j \in J_C : a_j \geq 0} a_j x_j - \sum_{j \in J_C : a_j < 0} f_0 \frac{a_j}{1-f_0} x_j \geq f_0. \]

Here, \(J_I\) and \(J_C \subseteq \{1, \ldots, n\}\) are the indices of integer and continuous non basic variables, respectively. The tableaux row is given by \(a_j\) and its right hand side is \(a_0\). The values \(f_j\) for \(j = 0, \ldots, n\) denote the fractional values of the tableaux row and rhs, i.e., \(f_j = a_j - \lfloor a_j \rfloor\).

Here is a brief description of the simplex tableau that we can expect from the SCIP LP interfaces:

  • Nonbasic columns can be at lower or upper bound, or they can be nonbasic at zero if they are free. Nonbasic columns at the upper bound must be flipped. Nonbasic free variables at zero are currently untested in the cut generator, but they should be handled properly anyway.
  • Nonbasic rows can be at lower or upper bound, depending on whether the lower or upper bound of the row is attained. SCIP always adds slack/surplus variables with a coefficient of +1: the slack variable is nonnegative in case of a <= constraint, it is nonpositive in case of a >= or ranged constraint. Therefore, slack variables corresponding to >= or ranged constraints must be flipped if the row is at its lower bound. (Ranged constraints at the upper bound do not have to - * be flipped because the variable is nonpositive.)

Generated cuts are modified and their numerical properties are checked before being added to the LP relaxation. Default parameters for cut modification and checking procedures are taken from the paper

G. Cornuejols, F. Margot, and G. Nannicini:
On the safety of Gomory cut generators.
Mathematical Programming Computation 5, No. 4 (2013), pp. 345-395.

In addition to the routines described in the paper above, here we additionally check the support of the cutting plane.

Definition in file sepa_gmi.c.

#include <assert.h>
#include <string.h>
#include "scip/pub_misc.h"
#include "sepa_gmi.h"

Go to the source code of this file.

Macros

#define SEPA_NAME   "gmi"
 
#define SEPA_DESC   "Gomory Mixed-Integer cuts separator"
 
#define SEPA_PRIORITY   -1000
 
#define SEPA_FREQ   0
 
#define SEPA_MAXBOUNDDIST   0.0
 
#define SEPA_USESSUBSCIP   FALSE
 
#define SEPA_DELAY   FALSE
 
#define DEFAULT_MAXROUNDS   5
 
#define DEFAULT_MAXROUNDSROOT   30
 
#define DEFAULT_MAXSEPACUTS   -1
 
#define DEFAULT_MAXSEPACUTSROOT   -1
 
#define DEFAULT_DYNAMICCUTS   TRUE
 
#define DEFAULT_SEPARATEROWS   TRUE
 
#define AWAY   0.005
 
#define MIN_VIOLATION   0.00
 
#define EPS_COEFF   1e-11
 
#define EPS_RELAX_ABS   1e-11
 
#define EPS_RELAX_REL   1e-13
 
#define MAX_DYN   1.0e+6
 
#define MAX_SUPP_ABS   1000
 
#define MAX_SUPP_REL   0.1
 

Functions

static SCIP_Bool modifyAndPackCut (SCIP *scip, SCIP_SEPADATA *sepadata, int ncols, SCIP_COL **cols, SCIP_Real *densecoefs, SCIP_Real *sparsecoefs, int *cutind, int *cutnz, SCIP_Real *cutrhs)
 
static SCIP_Bool checkNumerics (SCIP *scip, SCIP_SEPADATA *sepadata, int ncols, SCIP_COL **cols, SCIP_Real *cutcoefs, int *cutind, int *cutnz, SCIP_Real *cutrhs, SCIP_Real *cutact)
 
static SCIP_Bool getGMIFromRow (SCIP *scip, SCIP_SEPADATA *sepadata, int ncols, int nrows, SCIP_COL **cols, SCIP_ROW **rows, SCIP_Real *binvrow, SCIP_Real *binvarow, SCIP_Real rowrhs, SCIP_Real *cutcoefs, int *cutind, int *cutnz, SCIP_Real *cutrhs, SCIP_Real *cutact, SCIP_Real *workcoefs)
 
static SCIP_DECL_SEPACOPY (sepaCopyGMI)
 
static SCIP_DECL_SEPAFREE (sepaFreeGMI)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpGMI)
 
SCIP_RETCODE SCIPincludeSepaGMI (SCIP *scip)
 

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME   "gmi"

◆ SEPA_DESC

#define SEPA_DESC   "Gomory Mixed-Integer cuts separator"

Definition at line 71 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   -1000

Definition at line 72 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ SEPA_FREQ

#define SEPA_FREQ   0

Definition at line 73 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   0.0

Definition at line 74 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 75 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ SEPA_DELAY

#define SEPA_DELAY   FALSE

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

Definition at line 76 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS   5

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

Definition at line 78 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT   30

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

Definition at line 79 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ DEFAULT_MAXSEPACUTS

#define DEFAULT_MAXSEPACUTS   -1

maximal number of gomory cuts separated per separation round

Definition at line 80 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ DEFAULT_MAXSEPACUTSROOT

#define DEFAULT_MAXSEPACUTSROOT   -1

maximal number of gomory cuts separated per separation round in root node

Definition at line 81 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ DEFAULT_DYNAMICCUTS

#define DEFAULT_DYNAMICCUTS   TRUE

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

Definition at line 82 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ DEFAULT_SEPARATEROWS

#define DEFAULT_SEPARATEROWS   TRUE

separate rows with integral slack?

Definition at line 83 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ AWAY

#define AWAY   0.005

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

Definition at line 85 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ MIN_VIOLATION

#define MIN_VIOLATION   0.00

minimal violation to accept cut - default

Definition at line 86 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ EPS_COEFF

#define EPS_COEFF   1e-11

tolerance for zeroing out small coefficients - default

Definition at line 87 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ EPS_RELAX_ABS

#define EPS_RELAX_ABS   1e-11

absolute cut rhs relaxation - default

Definition at line 88 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ EPS_RELAX_REL

#define EPS_RELAX_REL   1e-13

relative cut rhs relaxation - default

Definition at line 89 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ MAX_DYN

#define MAX_DYN   1.0e+6

maximal valid range max(|weights|)/min(|weights|) of cut coefficients - default

Definition at line 90 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ MAX_SUPP_ABS

#define MAX_SUPP_ABS   1000

maximum cut support - absolute value in the formula - default

Definition at line 91 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ MAX_SUPP_REL

#define MAX_SUPP_REL   0.1

maximum cut support - relative value in the formula - default

Definition at line 92 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

Function Documentation

◆ modifyAndPackCut()

static SCIP_Bool modifyAndPackCut ( SCIP scip,
SCIP_SEPADATA sepadata,
int  ncols,
SCIP_COL **  cols,
SCIP_Real densecoefs,
SCIP_Real sparsecoefs,
int *  cutind,
int *  cutnz,
SCIP_Real cutrhs 
)
static

Modify the cut to make it numerically safer, and packs it from dense format to sparse format.

See paper "On the safety of Gomory cut generators" by Cornuejols, Margot, Nannicini for more information. Returns TRUE if cut is accepted, FALSE if it is discarded.

Parameters
scippointer to the SCIP environment
sepadatapointer to separator data
ncolsnumber of columns in the LP
colscolumns of the LP
densecoefscut in dense format on input
sparsecoefscut coefficients in sparse format on output
cutindcut indices in sparse format on output
cutnznumber of nonzero elements in the cut in sparse format on output
cutrhsrhs of the cut

Definition at line 126 of file sepa_gmi.c.

References EPSZ, FALSE, NULL, REALABS, SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetUb(), SCIPisInfinity(), SCIPisZero(), and TRUE.

Referenced by getGMIFromRow().

◆ checkNumerics()

static SCIP_Bool checkNumerics ( SCIP scip,
SCIP_SEPADATA sepadata,
int  ncols,
SCIP_COL **  cols,
SCIP_Real cutcoefs,
int *  cutind,
int *  cutnz,
SCIP_Real cutrhs,
SCIP_Real cutact 
)
static

Check the numerical properties of the cut.

See paper "On the safety of Gomory cut generators" by Cornuejols, Margot, Nannicini for more information. Returns TRUE if cut is accepted, FALSE if it is discarded.

Parameters
scippointer to the SCIP environment
sepadatapointer to separator data
ncolsnumber of columns in the LP
colscolumns of the LP
cutcoefscut in sparse format
cutindcut indices in sparse format
cutnznumber of nonzero elements in the cut in sparse format
cutrhsrhs of the cut
cutactactivity of the cut at the current LP optimum will go here on output

Definition at line 203 of file sepa_gmi.c.

References FALSE, MAX, MIN, NULL, REALABS, SCIP_Real, SCIP_REAL_MAX, SCIPcolGetPrimsol(), SCIPdebugMsg, and TRUE.

Referenced by getGMIFromRow().

◆ getGMIFromRow()

static SCIP_Bool getGMIFromRow ( SCIP scip,
SCIP_SEPADATA sepadata,
int  ncols,
int  nrows,
SCIP_COL **  cols,
SCIP_ROW **  rows,
SCIP_Real binvrow,
SCIP_Real binvarow,
SCIP_Real  rowrhs,
SCIP_Real cutcoefs,
int *  cutind,
int *  cutnz,
SCIP_Real cutrhs,
SCIP_Real cutact,
SCIP_Real workcoefs 
)
static

Method to obtain a GMI in the space of the original variables from a row of the simplex tableau.

Returns TRUE if cut is successfully created, FALSE if no cut was generated or if it should be discarded. If the function returns FALSE, the contents of cutcoefs, cutind, cutnz, cutrhs, cutact may be garbage.

Parameters
scippointer to the SCIP environment
sepadatapointer to separator data
ncolsnumber of columns in the LP
nrowsnumber of rows in the LP
colscolumns of the LP
rowsrows of the LP
binvrowrow of the basis inverse
binvarowrow of the simplex tableau
rowrhsrhs of the tableau row, i.e. corresponding element in the LP solution
cutcoefscut elements in sparse format will go here - must be of size ncols
cutindindices of nonzero cut coefficients will go here - must be of size ncols
cutnznumber of nonzero elements in the cuts will go here
cutrhscut rhs will go here
cutactcut activity at the current LP optimum will go here - only meaningful if returns TRUE
workcoefsworking array of size ncols, allocated by caller for efficiency

Definition at line 269 of file sepa_gmi.c.

References BMSclearMemoryArray, checkNumerics(), FALSE, modifyAndPackCut(), NULL, SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_Bool, SCIP_Real, SCIPcolGetBasisStatus(), SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetUb(), SCIPcolIsIntegral(), SCIPdebugMsg, SCIPfeasFrac(), SCIPfrac(), SCIPgetRowLPActivity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisLE(), SCIPisZero(), SCIProwGetBasisStatus(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsIntegral(), and SCIProwIsModifiable().

Referenced by SCIP_DECL_SEPAEXECLP().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyGMI  )
static

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

Definition at line 529 of file sepa_gmi.c.

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

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeGMI  )
static

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

Definition at line 543 of file sepa_gmi.c.

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

◆ SCIP_DECL_SEPAEXECLP()

◆ SCIPincludeSepaGMI()