SCIP

Solving Constraint Integer Programs

sepa_gmi.c File Reference

Detailed Description

Gomory Mixed-Integer Cuts.

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)

◆ 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 GMI 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 GMI 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 GMI 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 GMI 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().

◆ DEFAULT_AWAY

 #define DEFAULT_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().

◆ DEFAULT_MIN_VIOLATION

 #define DEFAULT_MIN_VIOLATION   0.00

minimal violation to accept cut - default

Definition at line 86 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ DEFAULT_EPS_COEFF

 #define DEFAULT_EPS_COEFF   1e-11

tolerance for zeroing out small coefficients - default

Definition at line 87 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ DEFAULT_EPS_RELAX_ABS

 #define DEFAULT_EPS_RELAX_ABS   1e-11

absolute cut rhs relaxation - default

Definition at line 88 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ DEFAULT_EPS_RELAX_REL

 #define DEFAULT_EPS_RELAX_REL   1e-13

relative cut rhs relaxation - default

Definition at line 89 of file sepa_gmi.c.

Referenced by SCIPincludeSepaGMI().

◆ DEFAULT_MAX_DYN

 #define DEFAULT_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().

◆ DEFAULT_MAX_SUPP_ABS

 #define DEFAULT_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().

◆ DEFAULT_MAX_SUPP_REL

 #define DEFAULT_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().

◆ 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, and Nannicini for more information. Returns TRUE if cut is accepted, FALSE if it is discarded.

Parameters
 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

Definition at line 126 of file sepa_gmi.c.

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, and Nannicini for more information. Returns TRUE if cut is accepted, FALSE if it is discarded.

Parameters
 scip pointer to the SCIP environment sepadata pointer to separator data ncols number of columns in the LP cols columns of the LP cutcoefs cut in sparse format cutind cut indices in sparse format cutnz number of nonzero elements in the cut in sparse format cutrhs rhs of the cut cutact pointer to store activity 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, 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
 scip pointer to the SCIP environment sepadata pointer to separator data ncols number of columns in the LP nrows number of rows in the LP cols columns of the LP rows rows of the LP binvrow row of the basis inverse binvarow row of the simplex tableau rowrhs rhs of the tableau row, i.e., corresponding element in the LP solution cutcoefs array for cut elements in sparse format - must be of size ncols cutind array for indices of nonzero cut coefficients - must be of size ncols cutnz pointer to store number of nonzero elements in the cut cutrhs pointer to store cut rhs cutact pointer to store cut activity at the current LP optimum - only meaningful if returns TRUE workcoefs working array of size ncols, allocated by caller for efficiency

Definition at line 267 of file sepa_gmi.c.

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 527 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 541 of file sepa_gmi.c.

◆ SCIP_DECL_SEPAEXECLP()

 static SCIP_DECL_SEPAEXECLP ( sepaExeclpGMI )
static

◆ SCIPincludeSepaGMI()

 SCIP_RETCODE SCIPincludeSepaGMI ( SCIP * scip )

creates the GMI MIR cut separator and includes it in SCIP

Parameters
 scip SCIP data structure

Definition at line 817 of file sepa_gmi.c.

Referenced by runSCIP(), and SCIP_DECL_SEPACOPY().