Detailed Description

run Benders algorithm

Author: Marc Pfetsch

Run Benders algorithm using an oracle for solving the subproblems and solving the master problem to optimality.

Definition in file benders.h.

#include <scip/scip.h>

Macros
#define	BENDERS_CUTORACLE(x) SCIP_RETCODE x (SCIP* masterscip, int nmastervars, SCIP_VAR** mastervars, SCIP_Real* mastersolution, BENDERS_DATA* data, SCIP_Real timelimit, SCIP_Longint ntotalcuts, int* ncuts, BENDERS_STATUS* status)

Typedefs
typedef enum BENDERS_Status	BENDERS_STATUS

typedef struct BENDERS_Data	BENDERS_DATA

Enumerations
enum	BENDERS_Status { BENDERS_STATUS_UNKNOWN = 0, BENDERS_STATUS_ADDEDCUT = 1, BENDERS_STATUS_SUCESS = 2, BENDERS_STATUS_TIMELIMIT = 3, BENDERS_STATUS_USERINTERRUPT = 4, BENDERS_STATUS_ERROR = 5 }

Functions
SCIP_RETCODE	runBenders (SCIP masterscip, BENDERS_CUTORACLE((Oracle)), BENDERS_DATA data, SCIP_Real timelimit, SCIP_Real memlimit, int dispfreq, SCIP_Bool usereopt, SCIP_Bool solvemasterapprox, SCIP_Longint masterstallnodes, SCIP_Real mastergaplimit, SCIP_VERBLEVEL verblevel, SCIP_STATUS status)

Macro Definition Documentation

◆ BENDERS_CUTORACLE

#define BENDERS_CUTORACLE ( x ) SCIP_RETCODE x (SCIP* masterscip, int nmastervars, SCIP_VAR** mastervars, SCIP_Real* mastersolution, BENDERS_DATA* data, SCIP_Real timelimit, SCIP_Longint ntotalcuts, int* ncuts, BENDERS_STATUS* status)

user callback method for a Benders subproblem oracle input:

masterscip: SCIP pointer of Benders master problem
nmastervars: number of variables in master problem
mastervars: variables in master problem
mastersolution: solution of Benders master problem
data: user data for oracle
timelimit: time limit for subproblem
ntotalcuts: total number of cuts output:
ncuts: number of cuts added
status: status

The oracle should take the given solution and possibly add a Benders Cut to the master problem.

Definition at line 61 of file benders.h.

Typedef Documentation

◆ BENDERS_STATUS

typedef enum BENDERS_Status BENDERS_STATUS

Definition at line 42 of file benders.h.

◆ BENDERS_DATA

typedef struct BENDERS_Data BENDERS_DATA

user defined data to pass to the oracle

Definition at line 44 of file benders.h.

Enumeration Type Documentation

◆ BENDERS_Status

enum BENDERS_Status

Benders subproblem oracle solving status

Enumerator
BENDERS_STATUS_UNKNOWN	the solving status is not yet known
BENDERS_STATUS_ADDEDCUT	a Benders cut has been added
BENDERS_STATUS_SUCESS	the solution is optimal, no further Benders cut has to be generated
BENDERS_STATUS_TIMELIMIT	the time limit has been reached
BENDERS_STATUS_USERINTERRUPT	the user has interrupted the solution of the subproblem
BENDERS_STATUS_ERROR	an error occured during the solution of the subproblem

Definition at line 33 of file benders.h.

Function Documentation

◆ runBenders()

SCIP_RETCODE runBenders	(	SCIP *	masterscip,
		BENDERS_CUTORACLE((*Oracle))	,
		BENDERS_DATA *	data,
		SCIP_Real	timelimit,
		SCIP_Real	memlimit,
		int	dispfreq,
		SCIP_Bool	usereopt,
		SCIP_Bool	solvemasterapprox,
		SCIP_Longint	masterstallnodes,
		SCIP_Real	mastergaplimit,
		SCIP_VERBLEVEL	verblevel,
		SCIP_STATUS *	status
	)

run Benders algorithm using an oracle for the subproblems

Parameters

masterscip	master SCIP instance
data	user data for oracle
timelimit	time limit read from arguments
memlimit	memory limit read from arguments
dispfreq	display frequency
usereopt	Use reoptimization?
solvemasterapprox	Solve master problem approximately?
masterstallnodes	stall nodes for master problem if solvemasterapprox is true
mastergaplimit	gap limit for master problem if solvemasterapprox is true
verblevel	verbosity level for output
status	status of optimization

Definition at line 198 of file benders.c.

References BENDERS_STATUS_ADDEDCUT, BENDERS_STATUS_SUCESS, BENDERS_STATUS_TIMELIMIT, BENDERS_STATUS_UNKNOWN, BENDERS_STATUS_USERINTERRUPT, FALSE, MAX, MAXITERATIONS, NULL, printLongStatistics(), printShortStatistics(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_OPTIMAL, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, SCIP_VERBLEVEL_NORMAL, SCIPallocClearBlockMemoryArray, SCIPcreateClock(), SCIPdebugMessage, SCIPdispInt(), SCIPdispLongint(), SCIPdispTime(), SCIPenableReoptimization(), SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPfreeClock(), SCIPfreeTransform(), SCIPgetBestSol(), SCIPgetClockTime(), SCIPgetDualbound(), SCIPgetGap(), SCIPgetMessagehdlr(), SCIPgetNIntVars(), SCIPgetNOrigConss(), SCIPgetNOrigVars(), SCIPgetNTotalNodes(), SCIPgetOrigVarsData(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetStatus(), SCIPinfinity(), SCIPinfoMessage(), SCIPisInfinity(), SCIPisIntegral(), SCIPmessageFPrintInfo(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsolve(), SCIPstartClock(), SCIPstopClock(), and TRUE.

Referenced by solveClassification(), and solveMinIISC().

SCIP