Scippy

SCIP

Solving Constraint Integer Programs

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"

◆ BENDERS_DESC

#define BENDERS_DESC   "default implementation of Benders' decomposition"

Definition at line 53 of file benders_default.c.

Referenced by SCIPincludeBendersDefault().

◆ BENDERS_PRIORITY

#define BENDERS_PRIORITY   0

Definition at line 54 of file benders_default.c.

Referenced by SCIPincludeBendersDefault().

◆ BENDERS_CUTLP

#define BENDERS_CUTLP   TRUE

should Benders' cut be generated for LP solutions

Definition at line 55 of file benders_default.c.

Referenced by SCIPincludeBendersDefault().

◆ BENDERS_CUTPSEUDO

#define BENDERS_CUTPSEUDO   TRUE

should Benders' cut be generated for pseudo solutions

Definition at line 56 of file benders_default.c.

Referenced by SCIPincludeBendersDefault().

◆ BENDERS_CUTRELAX

#define BENDERS_CUTRELAX   TRUE

should Benders' cut be generated for relaxation solutions

Definition at line 57 of file benders_default.c.

Referenced by SCIPincludeBendersDefault().

◆ BENDERS_SHAREAUXVARS

#define BENDERS_SHAREAUXVARS   FALSE

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

Definition at line 58 of file benders_default.c.

Referenced by SCIPincludeBendersDefault().

Function Documentation

◆ createBendersData()

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

creates the Benders' decomposition data

Parameters
scipSCIP data structure
subproblemsthe Benders' decomposition subproblems
bendersdatathe Benders' decomposition data
nsubproblemsthe number of subproblems in the Benders' decomposition

Definition at line 88 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
scipSCIP data structure
bendersthe Benders' decomposition structure

Definition at line 121 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

◆ 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 294 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 333 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 348 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 387 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 446 of file benders_default.c.

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