Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

mixing/star inequality separator

Author
Weikun Chen
Marc Pfetsch

This separator generates cuts based on the mixing set

\[ X = \{ (x,y) \in \{0,1\}^{N \cup M} \times \mathbb{R} \, : \, y \geq a_i x_i, \, \textrm{for} \, i \in N, \, y \leq u - a_i x_i, \, \textrm{for} \, i \in M, \, 0 \leq y \leq u \}, \]

where \(0 \leq a_i \leq u\) for all \(i\). This information can be obtained directly from the variable bounds data structure. The separator will generate three classes of cuts.

VLB: Let \(T\) be a subset of \(N\), wlog, \(T = \{1,\ldots,r\}\) with \(a_1 \leq a_2 \leq \ldots \leq a_r\). Let \(a_0 = 0\). The mixing/star VLB cut is of the form \( y \geq \sum_{i=1}^r (a_i - a_{i-1})x_i \).

VUB: Let \(T\) be a subset of \(M\), wlog, \(T = \{1,\ldots,r\}\) with \(a_1 \leq a_2 \leq \ldots \leq a_r\). Let \(a_0 = 0\). The mixing/star VUB cut is of the form \( y \leq u - \sum_{i=1}^r (a_i - a_{i-1})x_i \).

CONFLICT: Consider \(i \in N\) and \(j \in M\) with \(a_i + a_j > u\). The conflict cut is \(x_i + x_j \leq 1\).

A small example is described in the following to see the generated cuts.

\[ Y = \{ (x,y) \in \{0,1\}^{4} \times \mathbb{R} \, : \, y \geq 2x_1, \, y \geq 3x_2, \, y \leq 4 - x_3, \, y \leq 4 - 2 x_4, \, 0 \leq y \leq 4 \}. \]

In this small example, the mixing/star cuts \(y \geq 2x_1 + x_2\) (VLB) and \(y \leq 4 - x_3 - x_4\) (VUB) will be considered to be generated. Besides the mixing cuts, we also consider the conflict cut \(x_1 + x_3 \leq 1\) (CONFLICT).

For an overview see: Atamturk, A., Nemhauser, G.L. and Savelsbergh, M.W.,
The mixed vertex packing problem.
Mathematical Programming, 89(1), 35-53, 2000.

Some remarks:

  • Besides the mixing inequality, we also add the conflict inequality.
  • Currently, the performance is bad on the neos-565672 instance. The reason is that, after adding the separator, SCIP spends a lot of time at the stage of cutting plane generation.
  • We do not consider sparsity of the cuts as we aim to find a most violated cut.
  • Besides the most violated cut we consider, we also add an additional variable to make the cut be the strongest one, even the additional variable does not contribute any to the violation.

Definition in file sepa_mixing.c.

#include "blockmemshell/memory.h"
#include "scip/pub_implics.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_cut.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_sepa.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_var.h"
#include "scip/sepa_mixing.h"
#include "scip/scip_tree.h"
#include <string.h>

Go to the source code of this file.

Macros

#define SEPA_NAME   "mixing"
 
#define SEPA_DESC   "mixing inequality separator"
 
#define DEFAULT_MAXROUNDS   -1
 
#define DEFAULT_MAXROUNDSROOT   -1
 
#define SEPA_PRIORITY   -50
 
#define SEPA_FREQ   10
 
#define SEPA_MAXBOUNDDIST   1.0
 
#define SEPA_USESSUBSCIP   FALSE
 
#define SEPA_DELAY   FALSE
 
#define DEFAULT_USELOCALBOUNDS   FALSE
 
#define DEFAULT_ISCUTSONINTS   FALSE
 
#define DEFAULT_MAXNUNSUCCESSFUL   10
 

Functions

static SCIP_RETCODE addCut (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Real *cutcoefs, int *cutinds, int cutnnz, SCIP_Real cutrhs, SCIP_Bool cutislocal, SCIP_Bool *cutoff, int *ncuts)
 
static SCIP_RETCODE separateCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
 
static SCIP_DECL_SEPACOPY (sepaCopyMixing)
 
static SCIP_DECL_SEPAFREE (sepaFreeMixing)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpMixing)
 
static SCIP_DECL_SEPAEXECSOL (sepaExecSolMixing)
 
SCIP_RETCODE SCIPincludeSepaMixing (SCIP *scip)
 

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME   "mixing"

Definition at line 99 of file sepa_mixing.c.

◆ SEPA_DESC

#define SEPA_DESC   "mixing inequality separator"

Definition at line 100 of file sepa_mixing.c.

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS   -1

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

Definition at line 101 of file sepa_mixing.c.

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT   -1

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

Definition at line 102 of file sepa_mixing.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   -50

Definition at line 103 of file sepa_mixing.c.

◆ SEPA_FREQ

#define SEPA_FREQ   10

Definition at line 104 of file sepa_mixing.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 105 of file sepa_mixing.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 106 of file sepa_mixing.c.

◆ SEPA_DELAY

#define SEPA_DELAY   FALSE

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

Definition at line 107 of file sepa_mixing.c.

◆ DEFAULT_USELOCALBOUNDS

#define DEFAULT_USELOCALBOUNDS   FALSE

should local bounds be used?

Definition at line 109 of file sepa_mixing.c.

◆ DEFAULT_ISCUTSONINTS

#define DEFAULT_ISCUTSONINTS   FALSE

should general/implicit integer variables be used to generate cuts?

Definition at line 110 of file sepa_mixing.c.

◆ DEFAULT_MAXNUNSUCCESSFUL

#define DEFAULT_MAXNUNSUCCESSFUL   10

maximal number of consecutive unsuccessful iterations

Definition at line 111 of file sepa_mixing.c.

Function Documentation

◆ addCut()

static SCIP_RETCODE addCut ( SCIP scip,
SCIP_SEPA sepa,
SCIP_SOL sol,
SCIP_Real cutcoefs,
int *  cutinds,
int  cutnnz,
SCIP_Real  cutrhs,
SCIP_Bool  cutislocal,
SCIP_Bool cutoff,
int *  ncuts 
)
static

adds the given cut

Parameters
scipSCIP data structure
sepaseparator
solthe solution that should be separated, or NULL for LP solution
cutcoefscoefficients of active variables in cut
cutindsproblem indices of variables in cut
cutnnznumber of non-zeros in cut
cutrhsright hand side of cut
cutislocalIs the cut only locally valid?
cutoffpointer to store whether a cutoff has been detected
ncutspointer to update number of cuts added

Definition at line 130 of file sepa_mixing.c.

References FALSE, NULL, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPgetCutEfficacy(), SCIPgetNLPs(), SCIPgetVars(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIPsnprintf(), and TRUE.

Referenced by separateCuts().

◆ separateCuts()

static SCIP_RETCODE separateCuts ( SCIP scip,
SCIP_SEPA sepa,
SCIP_SOL sol,
SCIP_Bool cutoff,
int *  ncuts 
)
static

searches and adds mixing cuts that are violated by the given solution value array

This function implements a separation heuristic that runs in linear time in comparison to the quadratic exact algorithm in Atamturk et al.:

  • Lower and upper bounds are considered separately. Then possible conflict cuts.
  • Variable lower/upper bounds data are collected, i.e., the corresponding binary variables and coefficients.
  • These lists are sorted non-increasingly according to the solution values.
  • Then binary variables are added in turn as long as their coefficients increase in order to make the coefficients nonnegative. This clearly makes the cuts heuristic, since it is order dependent, but also sparser.
  • The procedure stops as soon as it reaches 0 solution values.
  • If the cut is efficious it is added.
Parameters
scipSCIP data structure
sepaseparator
solthe solution that should be separated, or NULL for LP solution
cutoffwhether a cutoff has been detected
ncutspointer to store the number of generated cuts

Definition at line 221 of file sepa_mixing.c.

References addCut(), FALSE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisEfficacious(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPsepaGetData(), SCIPsortDownRealRealIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsBinary(), and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyMixing  )
static

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

Definition at line 721 of file sepa_mixing.c.

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

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeMixing  )
static

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

Definition at line 735 of file sepa_mixing.c.

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

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpMixing  )
static

◆ SCIP_DECL_SEPAEXECSOL()

static SCIP_DECL_SEPAEXECSOL ( sepaExecSolMixing  )
static