Detailed Description

default Benders' decomposition plugin

Author: Stephen J. Maher

The default Benders' decomposition plugin is provided to simplify the interaction the Benders' decomposition framework within SCIP. This plugin is included in the SCIP package by default. Using the default Benders' decomposition plugin, a problem can be solved by Benders' decomposition by calling

SCIPcreateBendersDefault(master problem, array of subproblems, number of subproblems)

where "master problem" is a SCIP instance of the master problem, "array of subproblems" is an array of SCIP instances that are the Benders' decomposition subproblems and "number of subproblems" is an integer indicating the number of subproblems for this decomposition.

A key feature of the default Benders' decomposition plugin is the automatic generation of the variable mapping between the variables of the master problem and the subproblems.

In the traditional application of Benders' decomposition, master problem variables are fixed to a solution value and modify the RHS of the second stage constraints. The implementation within SCIP requires that a variable is created in the subproblem for every master problem variable that appears in the subproblem constraints. This variable MUST have the same name as the corresponding variable in the master problem. This name is used to automatically generate the mapping between the master problem and the corresponding subproblem variables.

Definition in file benders_default.c.

#include "scip/benders_default.h"
#include "scip/bendersdefcuts.h"
#include "scip/pub_benders.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_var.h"
#include "scip/scip.h"

Go to the source code of this file.

Macros
#define	BENDERS_NAME "default"

#define	BENDERS_DESC "default implementation of Benders' decomposition"

#define	BENDERS_PRIORITY 0

#define	BENDERS_CUTLP TRUE

#define	BENDERS_CUTPSEUDO TRUE

#define	BENDERS_CUTRELAX TRUE

#define	BENDERS_SHAREAUXVARS FALSE

Functions
static SCIP_RETCODE	createBendersData (SCIP scip, SCIP subproblems, SCIP_BENDERSDATA *bendersdata, int nsubproblems)

static SCIP_RETCODE	createVariableMappings (SCIP scip, SCIP_BENDERS benders)

static	SCIP_DECL_BENDERSCOPY (bendersCopyDefault)

static	SCIP_DECL_BENDERSFREE (bendersFreeDefault)

static	SCIP_DECL_BENDERSINIT (bendersInitDefault)

static	SCIP_DECL_BENDERSEXIT (bendersExitDefault)

static	SCIP_DECL_BENDERSGETVAR (bendersGetvarDefault)

static	SCIP_DECL_BENDERSCREATESUB (bendersCreatesubDefault)

SCIP_RETCODE	SCIPcreateBendersDefault (SCIP scip, SCIP *subproblems, int nsubproblems)

SCIP_RETCODE	SCIPincludeBendersDefault (SCIP *scip)

Macro Definition Documentation

◆ BENDERS_NAME

#define BENDERS_NAME "default"

Definition at line 61 of file benders_default.c.

◆ BENDERS_DESC

#define BENDERS_DESC "default implementation of Benders' decomposition"

Definition at line 62 of file benders_default.c.

◆ BENDERS_PRIORITY

#define BENDERS_PRIORITY 0

Definition at line 63 of file benders_default.c.

◆ BENDERS_CUTLP

#define BENDERS_CUTLP TRUE

should Benders' cut be generated for LP solutions

Definition at line 64 of file benders_default.c.

◆ BENDERS_CUTPSEUDO

#define BENDERS_CUTPSEUDO TRUE

should Benders' cut be generated for pseudo solutions

Definition at line 65 of file benders_default.c.

◆ BENDERS_CUTRELAX

#define BENDERS_CUTRELAX TRUE

should Benders' cut be generated for relaxation solutions

Definition at line 66 of file benders_default.c.

◆ BENDERS_SHAREAUXVARS

#define BENDERS_SHAREAUXVARS FALSE

should this Benders' share the highest priority Benders' aux vars

Definition at line 67 of file benders_default.c.

Function Documentation

◆ createBendersData()

static SCIP_RETCODE createBendersData	(	SCIP *	scip,
		SCIP **	subproblems,
		SCIP_BENDERSDATA **	bendersdata,
		int	nsubproblems
	)

static

creates the Benders' decomposition data

Parameters

scip	SCIP data structure
subproblems	the Benders' decomposition subproblems
bendersdata	the Benders' decomposition data
nsubproblems	the number of subproblems in the Benders' decomposition

Definition at line 97 of file benders_default.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, and TRUE.

Referenced by SCIPcreateBendersDefault().

◆ createVariableMappings()

static SCIP_RETCODE createVariableMappings	(	SCIP *	scip,
		SCIP_BENDERS *	benders
	)

static

Creates the variable mappings between the master problem and the corresponding variable in the subproblem.

TODO: add the functionality to allow the user to provide an array of hashmaps for mapping between the master problem variables and the corresponding subproblem variables. TODO: check for uniqueness of names in this function.

Parameters

scip	SCIP data structure
benders	the Benders' decomposition structure

Definition at line 130 of file benders_default.c.

References NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPbendersGetData(), SCIPblkmem(), SCIPcaptureVar(), SCIPfindVar(), SCIPgetNVars(), SCIPgetSubscipDepth(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapInsert(), SCIPhashmapInsertInt(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarGetOrigvarSum(), and TRUE.

Referenced by SCIP_DECL_BENDERSINIT().

◆ SCIP_DECL_BENDERSCOPY()

static SCIP_DECL_BENDERSCOPY ( bendersCopyDefault )

static

copy method for Benders' decomposition plugins (called when SCIP copies plugins)

Definition at line 232 of file benders_default.c.

References BENDERS_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPbendersGetData(), SCIPbendersIsActive(), SCIPcopyOrig(), SCIPcreate(), SCIPcreateBendersDefault(), SCIPfindBenders(), SCIPfreeBufferArray, SCIPincludeBendersDefault(), and TRUE.

◆ SCIP_DECL_BENDERSFREE()

static SCIP_DECL_BENDERSFREE ( bendersFreeDefault )

static

destructor of Benders' decomposition to free user data (called when SCIP is exiting) ! [SnippetBendersFreeDefault]

Definition at line 303 of file benders_default.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPbendersGetData(), SCIPfree(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

◆ SCIP_DECL_BENDERSINIT()

static SCIP_DECL_BENDERSINIT ( bendersInitDefault )

static

! [SnippetBendersFreeDefault] initialization method of Benders' decomposition (called after problem was transformed)

Definition at line 342 of file benders_default.c.

References createVariableMappings(), NULL, SCIP_CALL, and SCIP_OKAY.

◆ SCIP_DECL_BENDERSEXIT()

static SCIP_DECL_BENDERSEXIT ( bendersExitDefault )

static

deinitialization method of Benders' decomposition (called before transformed problem is freed and the Benders' decomposition is active)

Definition at line 357 of file benders_default.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPbendersGetData(), SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPreleaseVar().

◆ SCIP_DECL_BENDERSGETVAR()

static SCIP_DECL_BENDERSGETVAR ( bendersGetvarDefault )

static

mapping method between the master problem variables and the subproblem variables of Benders' decomposition ! [SnippetBendersGetvarDefault]

Definition at line 396 of file benders_default.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbendersGetData(), SCIPhashmapGetImage(), SCIPhashmapGetImageInt(), and SCIPvarGetOrigvarSum().

◆ SCIP_DECL_BENDERSCREATESUB()

static SCIP_DECL_BENDERSCREATESUB ( bendersCreatesubDefault )

static

! [SnippetBendersGetvarDefault] the method for creating the Benders' decomposition subproblem. This method is called during the initialisation stage (after the master problem was transformed)

This method must create the SCIP instance for the subproblem and add the required variables and constraints. In addition, the settings required for the solving the problem must be set here. However, some settings will be overridden by the standard solving method included in the Benders' decomposition framework. If a special solving method is desired, the user can implement the bendersSolvesubDefault callback.

Definition at line 455 of file benders_default.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBendersSubproblem(), and SCIPbendersGetData().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ BENDERS_NAME

◆ BENDERS_DESC

◆ BENDERS_PRIORITY

◆ BENDERS_CUTLP

◆ BENDERS_CUTPSEUDO

◆ BENDERS_CUTRELAX

◆ BENDERS_SHAREAUXVARS

Function Documentation

◆ createBendersData()

◆ createVariableMappings()

◆ SCIP_DECL_BENDERSCOPY()

◆ SCIP_DECL_BENDERSFREE()

◆ SCIP_DECL_BENDERSINIT()

◆ SCIP_DECL_BENDERSEXIT()

◆ SCIP_DECL_BENDERSGETVAR()

◆ SCIP_DECL_BENDERSCREATESUB()