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 "scip/pub_message.h"
#include "scip/pub_sepa.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.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_timing.h"
#include "scip/scip_tree.h"
#include "scip/sepa_closecuts.h"
#include <string.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

SEPA_NAME

#define SEPA_NAME   "closecuts"

Definition at line 85 of file sepa_closecuts.c.

SEPA_DESC

#define SEPA_DESC   "closecuts meta separator"

Definition at line 86 of file sepa_closecuts.c.

SEPA_PRIORITY

#define SEPA_PRIORITY   1000000

Definition at line 87 of file sepa_closecuts.c.

SEPA_FREQ

#define SEPA_FREQ   -1

Definition at line 88 of file sepa_closecuts.c.

SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 89 of file sepa_closecuts.c.

SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 90 of file sepa_closecuts.c.

SEPA_DELAY

#define SEPA_DELAY   FALSE

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

Definition at line 91 of file sepa_closecuts.c.

SCIP_DEFAULT_SEPARELINT

#define SCIP_DEFAULT_SEPARELINT   TRUE

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

Definition at line 95 of file sepa_closecuts.c.

SCIP_DEFAULT_SEPACOMBVALUE

#define SCIP_DEFAULT_SEPACOMBVALUE   0.30

convex combination value for close cuts

Definition at line 96 of file sepa_closecuts.c.

SCIP_DEFAULT_SEPATHRESHOLD

#define SCIP_DEFAULT_SEPATHRESHOLD   50

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

Definition at line 97 of file sepa_closecuts.c.

SCIP_DEFAULT_INCLOBJCUTOFF

#define SCIP_DEFAULT_INCLOBJCUTOFF   FALSE

include the objective cutoff when computing the relative interior?

Definition at line 98 of file sepa_closecuts.c.

SCIP_DEFAULT_RECOMPUTERELINT

#define SCIP_DEFAULT_RECOMPUTERELINT   FALSE

recompute relative interior in each separation call?

Definition at line 99 of file sepa_closecuts.c.

SCIP_DEFAULT_MAXUNSUCCESSFUL

#define SCIP_DEFAULT_MAXUNSUCCESSFUL   0

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

Definition at line 100 of file sepa_closecuts.c.

SCIP_DEFAULT_MAXLPITERFACTOR

#define SCIP_DEFAULT_MAXLPITERFACTOR   10.0

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

Definition at line 101 of file sepa_closecuts.c.

SCIP_MIN_LPITERS

#define SCIP_MIN_LPITERS   100

minimum number of allowed LP iterations in relative interior computation

Definition at line 103 of file sepa_closecuts.c.

Function Documentation

generateCloseCutPoint()

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

scip	SCIP data structure
sepadata	separator data
point	point to be generated (or NULL if unsuccessful)

Definition at line 130 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().

SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyClosecuts  )

static

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

Definition at line 194 of file sepa_closecuts.c.

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

SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeClosecuts  )

static

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

Definition at line 208 of file sepa_closecuts.c.

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

SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolClosecuts  )

static

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

Definition at line 229 of file sepa_closecuts.c.

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

SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpClosecuts  )

static

LP solution separation method of separator

Definition at line 253 of file sepa_closecuts.c.

References FALSE, generateCloseCutPoint(), MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MIN_LPITERS, SCIP_NEWROUND, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_VERBLEVEL_MINIMAL, SCIPcomputeLPRelIntPoint(), SCIPdebugMsg, SCIPfreeSol(), SCIPgetBestSol(), SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPSolstat(), SCIPgetNCuts(), SCIPgetNLPBranchCands(), SCIPgetNLPIterations(), SCIPgetNRootLPIterations(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPisStopped(), SCIPnodeGetNumber(), SCIPremoveInefficaciousCuts(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPseparateSol(), SCIPverbMessage(), SEPA_NAME, and TRUE.