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_NAME "closecuts"

Definition at line 58 of file sepa_closecuts.c.

Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXITSOL(), SCIP_DECL_SEPAFREE(), SCIPincludeSepaClosecuts(), and SCIPsetBasePointClosecuts().

#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