Scippy

SCIP

Solving Constraint Integer Programs

benders.h File Reference

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>

Go to the source code of this file.

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 70 of file benders.h.

Typedef Documentation

◆ BENDERS_STATUS

Definition at line 51 of file benders.h.

◆ BENDERS_DATA

typedef struct BENDERS_Data BENDERS_DATA

user defined data to pass to the oracle

Definition at line 53 of file benders.h.

Enumeration Type Documentation

◆ 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 42 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
masterscipmaster SCIP instance
datauser data for oracle
timelimittime limit read from arguments
memlimitmemory limit read from arguments
dispfreqdisplay frequency
usereoptUse reoptimization?
solvemasterapproxSolve master problem approximately?
masterstallnodesstall nodes for master problem if solvemasterapprox is true
mastergaplimitgap limit for master problem if solvemasterapprox is true
verblevelverbosity level for output
statusstatus of optimization

Definition at line 207 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(), SCIPfreeReoptSolve(), 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().