Detailed Description

benders relaxator

Author: Stephen J. Maher

This relaxator is provided to apply Benders' decomposition to a supplied decomposition structure. The relaxator is invoked if the user supplies a decomposition structure and sets the parameter "decomposition/applybenders" to TRUE. In addition, it is recommended that the parameter "decomposition/benderslabels" is set to TRUE to ensure that the block labelling of the variables and constraints is correct for applying Benders' decomposition.

Given a decomposition structure, the relaxator will create a number of SCIP instances: one for the master problem and one for each subproblems. These SCIP instances are supplied to the default Benders' decomposition plugin to trigger the execution of the Benders' decomposition algorithm. The original SCIP instance will execute presolving and start the solving process. When the root node starts solving, this relaxator will be called first. The Benders' decomposition algorithm attempts to solve the problem to optimality. At the completion of the Benders' decomposition algorithm, the best found primal and dual bounds are returned to the original SCIP instance. The solution from the decomposed problem is mapped back to the original instance variables.

By default, the original SCIP instance will terminate with an optimal solution or infeasible status (if found or proven by the Benders' decomposition algorithm, resp.), or a status indicating a time, gap, or bound limit, or a "user interrupt". To prevent the original SCIP instance to continue solving if the Benders' decomposition algorithm fails to solve the problem, the user interrupt is also triggered if the Benders' decomposition algorithm stopped due to a node, restart, or solution limit, or when transferring the solution to the original SCIP instance fails. To continue solving the original SCIP instance after the conclusion of the Benders' decomposition algorithm, parameter "relaxing/benders/continueorig" can be set to TRUE.

The working limits from the original SCIP instance are copied across to the master problem SCIP instance. However, if the user desires to have a different node limit for the master problem, for example if they wish to use Benders' decomposition as a start heuristic, then this can be set with the parameter "relaxing/benders/nodelimit".

If the Benders' decomposition relaxator is used, then statistics for both the original SCIP instance and the master problem SCIP instance are displayed when the statistics are requested by via the SCIP shell dialog.

Definition in file relax_benders.c.

#include <assert.h>
#include "scip/scip.h"
#include "scip/benders_default.h"
#include "scip/pub_benders.h"
#include "scip/pub_relax.h"
#include "scip/relax_benders.h"
#include "scip/type_benders.h"
#include "scip/type_message.h"
#include "scip/type_relax.h"
#include "scip/type_retcode.h"
#include "scip/type_stat.h"

Go to the source code of this file.

Macros
#define	RELAX_NAME "benders"

#define	RELAX_DESC "applies default Benders' decomposition and solves the problem"

#define	RELAX_PRIORITY 1

#define	RELAX_FREQ 0

#define	DEFAULT_CONTORIG FALSE

#define	DEFAULT_NODELIMIT -1LL

#define	relaxCopyBenders NULL

#define	relaxInitBenders NULL

#define	relaxExitBenders NULL

#define	relaxExitsolBenders NULL

Functions
static SCIP_RETCODE	addVariableToBendersProblem (SCIP scip, SCIP targetscip, SCIP_HASHMAP varmap, SCIP_VAR sourcevar)

static SCIP_RETCODE	addConstraintToBendersProblem (SCIP scip, SCIP targetscip, SCIP_HASHMAP varmap, SCIP_CONS sourcecons)

static SCIP_RETCODE	applyDecomposition (SCIP scip, SCIP_RELAX relax, SCIP_DECOMP *decomp)

static SCIP_RETCODE	addInitialSolution (SCIP scip, SCIP_RELAXDATA relaxdata)

static SCIP_Bool	masterSolutionExists (SCIP scip, SCIP_RELAX relax)

static SCIP_RETCODE	solveBendersSubproblems (SCIP scip, SCIP_RELAX relax, SCIP_Bool *infeasible)

static SCIP_RETCODE	getNlpSolution (SCIP scip, SCIP_SOL *nlpsol)

static SCIP_RETCODE	setSolutionValues (SCIP scip, SCIP_RELAX relax, SCIP_SOL *sol)

static SCIP_RETCODE	freeBendersSubproblems (SCIP scip, SCIP_RELAX relax)

static SCIP_RETCODE	createOriginalSolution (SCIP scip, SCIP_RELAX relax, SCIP_Bool *infeasible)

static SCIP_RETCODE	freeDecomposition (SCIP scip, SCIP_RELAX relax)

static	SCIP_DECL_RELAXFREE (relaxFreeBenders)

static	SCIP_DECL_RELAXINITSOL (relaxInitsolBenders)

static	SCIP_DECL_RELAXEXEC (relaxExecBenders)

SCIP_RETCODE	SCIPincludeRelaxBenders (SCIP *scip)

SCIP *	SCIPgetMasterProblemRelaxBenders (SCIP *scip)

Macro Definition Documentation

◆ RELAX_NAME

#define RELAX_NAME "benders"

Definition at line 74 of file relax_benders.c.

◆ RELAX_DESC

#define RELAX_DESC "applies default Benders' decomposition and solves the problem"

Definition at line 75 of file relax_benders.c.

◆ RELAX_PRIORITY

#define RELAX_PRIORITY 1

Definition at line 76 of file relax_benders.c.

◆ RELAX_FREQ

#define RELAX_FREQ 0

Definition at line 77 of file relax_benders.c.

◆ DEFAULT_CONTORIG

#define DEFAULT_CONTORIG FALSE

continue solving the original SCIP instance if optimal solution is not found

Definition at line 79 of file relax_benders.c.

◆ DEFAULT_NODELIMIT

#define DEFAULT_NODELIMIT -1LL

node limit for the Benders' decomposition solve, -1 indicates original SCIP limit is used.

Definition at line 80 of file relax_benders.c.

◆ relaxCopyBenders

#define relaxCopyBenders NULL

Definition at line 776 of file relax_benders.c.

◆ relaxInitBenders

#define relaxInitBenders NULL

Definition at line 777 of file relax_benders.c.

◆ relaxExitBenders

#define relaxExitBenders NULL

Definition at line 778 of file relax_benders.c.

◆ relaxExitsolBenders

#define relaxExitsolBenders NULL

Definition at line 779 of file relax_benders.c.

Function Documentation

◆ addVariableToBendersProblem()

static SCIP_RETCODE addVariableToBendersProblem	(	SCIP *	scip,
		SCIP *	targetscip,
		SCIP_HASHMAP *	varmap,
		SCIP_VAR *	sourcevar
	)

static

adding variables from the original problem to the respective decomposed problem

Parameters

scip	the SCIP data structure
targetscip	the SCIP instance that the constraint will be copied into
varmap	the variable hash map mapping the source variables to the target variables
sourcevar	the variable to add to the problem

Definition at line 109 of file relax_benders.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPaddVar(), SCIPcreateVarImpl(), SCIPhashmapExists(), SCIPhashmapInsert(), SCIPreleaseVar(), SCIPvarGetImplType(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsInitial(), and SCIPvarIsRemovable().

Referenced by addConstraintToBendersProblem().

◆ addConstraintToBendersProblem()

static SCIP_RETCODE addConstraintToBendersProblem	(	SCIP *	scip,
		SCIP *	targetscip,
		SCIP_HASHMAP *	varmap,
		SCIP_CONS *	sourcecons
	)

static

Parameters

scip	the original SCIP instance
targetscip	the SCIP instance that the constraint will be copied into
varmap	the variable hash map mapping the source variables to the target variables
sourcecons	the constraint that being added to the subproblem

Definition at line 150 of file relax_benders.c.

References addVariableToBendersProblem(), NULL, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsMarkedPropagate(), SCIPconsIsModifiable(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPdebugMessage, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetConsCopy(), SCIPgetConsNVars(), SCIPgetConsVars(), SCIPreleaseCons(), and TRUE.

Referenced by applyDecomposition().

◆ applyDecomposition()

static SCIP_RETCODE applyDecomposition	(	SCIP *	scip,
		SCIP_RELAX *	relax,
		SCIP_DECOMP *	decomp
	)

static

Applies a Benders' decomposition to the problem based upon the decomposition selected from the storage

Parameters

scip	the original SCIP instance
relax	the relaxator
decomp	the decomposition to apply to the problem

Definition at line 218 of file relax_benders.c.

References addConstraintToBendersProblem(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PARAMSETTING_OFF, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPblkmem(), SCIPcopyParamSettings(), SCIPcopyPlugins(), SCIPcreate(), SCIPcreateBendersDefault(), SCIPcreateProbBasic(), SCIPdebugMessage, SCIPdecompGetConsLabels(), SCIPdecompGetNBlocks(), SCIPdecompGetVarsLabels(), SCIPfreeBufferArray, SCIPgetConss(), SCIPgetNConss(), SCIPgetProbName(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPincludeBendersDefault(), SCIPrelaxGetData(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetPresolving(), SCIPsnprintf(), and TRUE.

Referenced by SCIP_DECL_RELAXINITSOL().

◆ addInitialSolution()

static SCIP_RETCODE addInitialSolution	(	SCIP *	scip,
		SCIP_RELAXDATA *	relaxdata
	)

static

copies the best solution from the original SCIP instance and adds it to the master problem of the decomposed problem

Parameters

scip	the SCIP instance
relaxdata	the relaxator data

Definition at line 359 of file relax_benders.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcreateSol(), SCIPdecompGetVarsLabels(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPhashmapGetImage(), SCIPsetSolVal(), SCIPtrySolFree(), and TRUE.

Referenced by SCIP_DECL_RELAXEXEC().

◆ masterSolutionExists()

static SCIP_Bool masterSolutionExists	(	SCIP *	scip,
		SCIP_RELAX *	relax
	)

static

returns whether a solution exists for the master problem

Parameters

scip	the SCIP data structure
relax	the relaxator

Definition at line 425 of file relax_benders.c.

References NULL, SCIPgetBestSol(), and SCIPrelaxGetData().

Referenced by createOriginalSolution().

◆ solveBendersSubproblems()

static SCIP_RETCODE solveBendersSubproblems	(	SCIP *	scip,
		SCIP_RELAX *	relax,
		SCIP_Bool *	infeasible
	)

static

solves the Benders' decomposition subproblems using the best solution from the master problem

Parameters

scip	the SCIP data structure
relax	the relaxator
infeasible	indicates whether the best solution is infeasible

Definition at line 446 of file relax_benders.c.

References NULL, SCIP_BENDERSENFOTYPE_CHECK, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_PROBLEM, SCIPbendersGetNSubproblems(), SCIPbendersSubproblem(), SCIPfindBenders(), SCIPgetBestSol(), SCIPgetNActiveBenders(), SCIPgetStage(), SCIPrelaxGetData(), SCIPsetupBendersSubproblem(), SCIPsolveBendersSubproblem(), and TRUE.

Referenced by createOriginalSolution().

◆ getNlpSolution()

static SCIP_RETCODE getNlpSolution	(	SCIP *	scip,
		SCIP_SOL **	nlpsol
	)

static

constructs the NLP solution and returns it

Parameters

scip	the SCIP instance for which an NLP must be constructed
nlpsol	the NLP solution that will be created

Definition at line 499 of file relax_benders.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateNLPSol(), SCIPgetNNlpis(), and SCIPisNLPConstructed().

Referenced by setSolutionValues().

◆ setSolutionValues()

static SCIP_RETCODE setSolutionValues	(	SCIP *	scip,
		SCIP_RELAX *	relax,
		SCIP_SOL *	sol
	)

static

using the stored mappings for the variables, the solution values from the master and subproblems are used to set the solution values in the original SCIP solution

Parameters