Scippy

SCIP

Solving Constraint Integer Programs

sepa_closecuts.c File Reference

Detailed Description

closecuts meta separator

Author
Marc Pfetsch

This separator generates a convex combination of the current LP solution and either the best primal feasible solution or an interior point of the LP relaxation. If the convex combination is proper, the new point is closer to the convex hull of the feasible points. The separator then calls all other separators to separate this point. The idea is that in this way possibly "deeper" cuts are generated. Note, however, that the new point is not a basic solution, i.e., separators relying basis information, e.g., Gomory cuts, will not work.

The other cuts are generated via the sepasol() callbacks in constraints handlers or separators.

This separator stops after a certain number (parameter maxunsuccessful) of unsuccessful calls. It also inhibits the separation of the ordinary LP solution if it already generated enough (parameter sepathreshold) cuts. The convex combination is determined via the parameter sepacombvalue.

In general, this separator makes sense if it is expected that there will be many separation rounds and many cuts will be again deleted, because they are not active after a certain number of rounds. In particular, branch-and-cut algorithms for combinatorial optimization problems form good candidates.

The idea seems to be first proposed in the context of the travelling salesman problem, see

The Traveling Salesman Problem: A Computational Study
David L. Applegate, Robert E. Bixby, Vasek Chvatal & William J. Cook
Princeton University Press 2006
for more details. See also
Acceleration of cutting-plane and column generation algorithms: Applications to network design.
Walid Ben-Ameur, Jose Neto
Networks 49(1): 3-17 (2007).

Definition in file sepa_closecuts.c.

#include <assert.h>
#include <string.h>
#include "scip/sepa_closecuts.h"

Go to the source code of this file.

Macros

#define SEPA_NAME   "closecuts"
 
#define SEPA_DESC   "closecuts meta separator"
 
#define SEPA_PRIORITY   1000000
 
#define SEPA_FREQ   -1
 
#define SEPA_MAXBOUNDDIST   1.0
 
#define SEPA_USESSUBSCIP   FALSE
 
#define SEPA_DELAY   FALSE
 
#define SCIP_DEFAULT_SEPARELINT   TRUE
 
#define SCIP_DEFAULT_SEPACOMBVALUE   0.30
 
#define SCIP_DEFAULT_SEPATHRESHOLD   50
 
#define SCIP_DEFAULT_INCLOBJCUTOFF   FALSE
 
#define SCIP_DEFAULT_RECOMPUTERELINT   FALSE
 
#define SCIP_DEFAULT_MAXUNSUCCESSFUL   0
 
#define SCIP_DEFAULT_MAXLPITERFACTOR   10.0
 
#define SCIP_MIN_LPITERS   100
 

Functions

static SCIP_RETCODE generateCloseCutPoint (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL **point)
 
static SCIP_DECL_SEPACOPY (sepaCopyClosecuts)
 
static SCIP_DECL_SEPAFREE (sepaFreeClosecuts)
 
static SCIP_DECL_SEPAEXITSOL (sepaExitsolClosecuts)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpClosecuts)
 
SCIP_RETCODE SCIPincludeSepaClosecuts (SCIP *scip)
 
SCIP_RETCODE SCIPsetBasePointClosecuts (SCIP *scip, SCIP_SOL *sol)
 

Macro Definition Documentation

#define SEPA_DESC   "closecuts meta separator"

Definition at line 59 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SEPA_PRIORITY   1000000

Definition at line 60 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SEPA_FREQ   -1

Definition at line 61 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 62 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 63 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SEPA_DELAY   FALSE

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

Definition at line 64 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SCIP_DEFAULT_SEPARELINT   TRUE

generate close cuts w.r.t. relative interior point (best solution otherwise)?

Definition at line 68 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SCIP_DEFAULT_SEPACOMBVALUE   0.30

convex combination value for close cuts

Definition at line 69 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SCIP_DEFAULT_SEPATHRESHOLD   50

threshold on number of generated cuts below which the ordinary separation is started

Definition at line 70 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SCIP_DEFAULT_INCLOBJCUTOFF   FALSE

include the objective cutoff when computing the relative interior?

Definition at line 71 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SCIP_DEFAULT_RECOMPUTERELINT   FALSE

recompute relative interior in each separation call?

Definition at line 72 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SCIP_DEFAULT_MAXUNSUCCESSFUL   0

turn off separation in current node after unsuccessful calls (-1 never turn off)

Definition at line 73 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SCIP_DEFAULT_MAXLPITERFACTOR   10.0

factor for maximal LP iterations in relative interior computation compared to node LP iterations

Definition at line 74 of file sepa_closecuts.c.

Referenced by SCIPincludeSepaClosecuts().

#define SCIP_MIN_LPITERS   100

minimum number of allowed LP iterations in relative interior computation

Definition at line 76 of file sepa_closecuts.c.

Referenced by SCIP_DECL_SEPAEXECLP().

Function Documentation

static SCIP_RETCODE generateCloseCutPoint ( SCIP scip,
SCIP_SEPADATA sepadata,
SCIP_SOL **  point 
)
static

generate point for close cut separation

The constructed point is the convex combination of the point stored in set->closesol and the current LP solution. The convexity parameter is set->sepa_closecombvalue. If this parameter is 0, the point coincides with the LP solution.

Parameters
scipSCIP data structure
sepadataseparator data
pointpoint to be generated (or NULL if unsuccessful)

Definition at line 103 of file sepa_closecuts.c.

References MAX, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateSol(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisZero(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), and SCIPvarGetUbLocal().

Referenced by SCIP_DECL_SEPAEXECLP().

static SCIP_DECL_SEPACOPY ( sepaCopyClosecuts  )
static

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

Definition at line 167 of file sepa_closecuts.c.

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

static SCIP_DECL_SEPAFREE ( sepaFreeClosecuts  )
static

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

Definition at line 181 of file sepa_closecuts.c.

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

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolClosecuts  )
static

solving process deinitialization method of separator (called before branch and bound process data is freed)

Definition at line 202 of file sepa_closecuts.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), SCIPsepaGetData(), SCIPsepaGetName(), and SEPA_NAME.

SCIP_RETCODE SCIPsetBasePointClosecuts ( SCIP scip,
SCIP_SOL sol 
)

sets point to be used as base point for computing the point to be separated

The point is only stored if separation of relative interior points is used. The solution is copied.

Parameters
scipSCIP data structure
solbase point solution

Definition at line 462 of file sepa_closecuts.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPcreateSolCopy(), SCIPerrorMessage, SCIPfindSepa(), SCIPfreeSol(), SCIPsepaGetData(), SCIPsepaGetName(), SEPA_NAME, and TRUE.