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 the 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	DEFAULT_AWAY 0.005

#define	DEFAULT_MIN_VIOLATION 0.00

#define	DEFAULT_EPS_COEFF 1e-11

#define	DEFAULT_EPS_RELAX_ABS 1e-11

#define	DEFAULT_EPS_RELAX_REL 1e-13

#define	DEFAULT_MAX_DYN 1.0e+6

#define	DEFAULT_MAX_SUPP_ABS 1000

#define	DEFAULT_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"

Definition at line 70 of file sepa_gmi.c.

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

◆ SEPA_DESC

#define SEPA_DESC "Gomory Mixed-Integer cuts separator"

Definition at line 71 of file sepa_gmi.c.

scip	pointer to the SCIP environment
sepadata	pointer to separator data
ncols	number of columns in the LP
cols	columns of the LP
densecoefs	cut in dense format on input
sparsecoefs	cut coefficients in sparse format on output
cutind	cut indices in sparse format on output
cutnz	pointer to store the number of nonzero elements in the cut in sparse format on output
cutrhs	pointer to store the rhs of the cut, initialized to original value, modified

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ DEFAULT_MAXROUNDS

◆ DEFAULT_MAXROUNDSROOT

◆ DEFAULT_MAXSEPACUTS

◆ DEFAULT_MAXSEPACUTSROOT

◆ DEFAULT_DYNAMICCUTS

◆ DEFAULT_SEPARATEROWS

◆ DEFAULT_AWAY

◆ DEFAULT_MIN_VIOLATION

◆ DEFAULT_EPS_COEFF

◆ DEFAULT_EPS_RELAX_ABS

◆ DEFAULT_EPS_RELAX_REL

◆ DEFAULT_MAX_DYN

◆ DEFAULT_MAX_SUPP_ABS

◆ DEFAULT_MAX_SUPP_REL

Function Documentation

◆ modifyAndPackCut()

◆ checkNumerics()

◆ getGMIFromRow()

◆ SCIP_DECL_SEPACOPY()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAEXECLP()

◆ SCIPincludeSepaGMI()