Scippy

SCIP

Solving Constraint Integer Programs

benders.h File Reference

Detailed Description

internal methods for Benders' decomposition

Author
Stephen J. Maher

Definition in file benders.h.

#include "blockmemshell/memory.h"
#include "scip/def.h"
#include "scip/type_benders.h"
#include "scip/type_benderscut.h"
#include "scip/type_message.h"
#include "scip/type_misc.h"
#include "scip/type_result.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"
#include "scip/type_set.h"
#include "scip/type_sol.h"
#include "scip/type_stat.h"
#include "scip/type_var.h"

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPbendersCopyInclude (SCIP_BENDERS *benders, SCIP_SET *sourceset, SCIP_SET *targetset, SCIP_HASHMAP *varmap, SCIP_Bool *valid)
 
SCIP_RETCODE SCIPbendersCreate (SCIP_BENDERS **benders, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, SCIP_Bool cutlp, SCIP_Bool cutpseudo, SCIP_Bool cutrelax, SCIP_Bool shareauxvars, SCIP_DECL_BENDERSCOPY((*benderscopy)), SCIP_DECL_BENDERSFREE((*bendersfree)), SCIP_DECL_BENDERSINIT((*bendersinit)), SCIP_DECL_BENDERSEXIT((*bendersexit)), SCIP_DECL_BENDERSINITPRE((*bendersinitpre)), SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)), SCIP_DECL_BENDERSINITSOL((*bendersinitsol)), SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)), SCIP_DECL_BENDERSGETVAR((*bendersgetvar)), SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)), SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)), SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)), SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)), SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)), SCIP_DECL_BENDERSFREESUB((*bendersfreesub)), SCIP_BENDERSDATA *bendersdata)
 
SCIP_RETCODE SCIPbendersFree (SCIP_BENDERS **benders, SCIP_SET *set)
 
SCIP_RETCODE SCIPbendersInit (SCIP_BENDERS *benders, SCIP_SET *set)
 
SCIP_RETCODE SCIPbendersExit (SCIP_BENDERS *benders, SCIP_SET *set)
 
SCIP_RETCODE SCIPbendersInitpre (SCIP_BENDERS *benders, SCIP_SET *set, SCIP_STAT *stat)
 
SCIP_RETCODE SCIPbendersExitpre (SCIP_BENDERS *benders, SCIP_SET *set, SCIP_STAT *stat)
 
SCIP_RETCODE SCIPbendersInitsol (SCIP_BENDERS *benders, SCIP_SET *set)
 
SCIP_RETCODE SCIPbendersExitsol (SCIP_BENDERS *benders, SCIP_SET *set)
 
SCIP_RETCODE SCIPbendersActivate (SCIP_BENDERS *benders, SCIP_SET *set, int nsubproblems)
 
void SCIPbendersDeactivate (SCIP_BENDERS *benders, SCIP_SET *set)
 
void SCIPbendersEnableOrDisableClocks (SCIP_BENDERS *benders, SCIP_Bool enable)
 
SCIP_RETCODE SCIPbendersExec (SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool *infeasible, SCIP_Bool *auxviol, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
 
SCIP_RETCODE SCIPbendersExecSubproblemSolve (SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnum, SCIP_BENDERSSOLVELOOP solveloop, SCIP_Bool enhancement, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_BENDERSENFOTYPE type)
 
SCIP_RETCODE SCIPbendersSetupSubproblem (SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnum)
 
SCIP_RETCODE SCIPbendersSolveSubproblem (SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber, SCIP_Bool *infeasible, SCIP_BENDERSENFOTYPE type, SCIP_Bool solvecip, SCIP_Real *objective)
 
SCIP_RETCODE SCIPbendersFreeSubproblem (SCIP_BENDERS *benders, SCIP_SET *set, int probnumber)
 
SCIP_RETCODE SCIPbendersCheckSubproblemOptimality (SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber, SCIP_Bool *optimal)
 
SCIP_Real SCIPbendersGetAuxiliaryVarVal (SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber)
 
SCIP_RETCODE SCIPbendersComputeSubproblemLowerbound (SCIP_BENDERS *benders, SCIP_SET *set, int probnumber, SCIP_Real *lowerbound, SCIP_Bool *infeasible)
 
SCIP_RETCODE SCIPbendersMergeSubproblemIntoMaster (SCIP_BENDERS *benders, SCIP_SET *set, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, int probnumber)
 
void SCIPbendersSetPriority (SCIP_BENDERS *benders, SCIP_SET *set, int priority)
 
void SCIPbendersSetCopy (SCIP_BENDERS *benders, SCIP_DECL_BENDERSCOPY((*benderscopy)))
 
void SCIPbendersSetFree (SCIP_BENDERS *benders, SCIP_DECL_BENDERSFREE((*bendersfree)))
 
void SCIPbendersSetInit (SCIP_BENDERS *benders, SCIP_DECL_BENDERSINIT((*bendersinit)))
 
void SCIPbendersSetExit (SCIP_BENDERS *benders, SCIP_DECL_BENDERSEXIT((*bendersexit)))
 
void SCIPbendersSetInitpre (SCIP_BENDERS *benders, SCIP_DECL_BENDERSINITPRE((*bendersinitpre)))
 
void SCIPbendersSetExitpre (SCIP_BENDERS *benders, SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)))
 
void SCIPbendersSetInitsol (SCIP_BENDERS *benders, SCIP_DECL_BENDERSINITSOL((*bendersinitsol)))
 
void SCIPbendersSetExitsol (SCIP_BENDERS *benders, SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)))
 
void SCIPbendersSetPresubsolve (SCIP_BENDERS *benders, SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)))
 
void SCIPbendersSetSolvesubconvex (SCIP_BENDERS *benders, SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)))
 
void SCIPbendersSetSolvesub (SCIP_BENDERS *benders, SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)))
 
void SCIPbendersSetPostsolve (SCIP_BENDERS *benders, SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)))
 
void SCIPbendersSetFreesub (SCIP_BENDERS *benders, SCIP_DECL_BENDERSFREESUB((*bendersfreesub)))
 
SCIP_RETCODE SCIPbendersGetVar (SCIP_BENDERS *benders, SCIP_SET *set, SCIP_VAR *var, SCIP_VAR **mappedvar, int probnumber)
 
SCIP_RETCODE SCIPbendersAddSubproblem (SCIP_BENDERS *benders, SCIP *subproblem)
 
void SCIPbendersRemoveSubproblems (SCIP_BENDERS *benders)
 
void SCIPbendersSetSubproblemIsSetup (SCIP_BENDERS *benders, int probnumber, SCIP_Bool issetup)
 
SCIP_Bool SCIPbendersSubproblemIsSetup (SCIP_BENDERS *benders, int probnumber)
 
void SCIPbendersSetSubproblemEnabled (SCIP_BENDERS *benders, int probnumber, SCIP_Bool enabled)
 
SCIP_RETCODE SCIPbendersChgMastervarsToCont (SCIP_BENDERS *benders, SCIP_SET *set, int probnumber)
 
SCIP_RETCODE SCIPbendersSetMastervarsCont (SCIP_BENDERS *benders, int probnumber, SCIP_Bool arecont)
 
SCIP_Bool SCIPbendersGetMastervarsCont (SCIP_BENDERS *benders, int probnumber)
 
SCIP_RETCODE SCIPbendersIncludeBenderscut (SCIP_BENDERS *benders, SCIP_SET *set, SCIP_BENDERSCUT *benderscut)
 
void SCIPbendersSetBenderscutsSorted (SCIP_BENDERS *benders, SCIP_Bool sorted)
 
void SCIPbendersSortBenderscuts (SCIP_BENDERS *benders)
 
void SCIPbendersSortBenderscutsName (SCIP_BENDERS *benders)
 

Function Documentation

◆ SCIPbendersCopyInclude()

SCIP_RETCODE SCIPbendersCopyInclude ( SCIP_BENDERS benders,
SCIP_SET sourceset,
SCIP_SET targetset,
SCIP_HASHMAP varmap,
SCIP_Bool valid 
)

copies the given Benders' decomposition to a new scip

copies the given Benders' decomposition to a new SCIP

Parameters
bendersBenders' decomposition
sourcesetSCIP_SET of SCIP to copy from
targetsetSCIP_SET of SCIP to copy to
varmapa hashmap to store the mapping of source variables corresponding target variables; must not be NULL
validwas the copying process valid?

Definition at line 777 of file benders.c.

References SCIP_Set::benders_copybenders, SCIP_Benders::benderscuts, createMasterVarMapping(), FALSE, SCIP_Benders::lnscheck, SCIP_Benders::nbenderscuts, NULL, SCIP_Set::scip, SCIP_CALL, SCIP_OKAY, SCIPbenderscutCopyInclude(), SCIPbendersGetName(), SCIPbendersIsActive(), SCIPbendersSortBenderscuts(), SCIPsetDebugMsg, SCIPsetFindBenders(), and TRUE.

Referenced by SCIPcopyBenders().

◆ SCIPbendersCreate()

SCIP_RETCODE SCIPbendersCreate ( SCIP_BENDERS **  benders,
SCIP_SET set,
SCIP_MESSAGEHDLR messagehdlr,
BMS_BLKMEM blkmem,
const char *  name,
const char *  desc,
int  priority,
SCIP_Bool  cutlp,
SCIP_Bool  cutpseudo,
SCIP_Bool  cutrelax,
SCIP_Bool  shareauxvars,
SCIP_DECL_BENDERSCOPY((*benderscopy))  ,
SCIP_DECL_BENDERSFREE((*bendersfree))  ,
SCIP_DECL_BENDERSINIT((*bendersinit))  ,
SCIP_DECL_BENDERSEXIT((*bendersexit))  ,
SCIP_DECL_BENDERSINITPRE((*bendersinitpre))  ,
SCIP_DECL_BENDERSEXITPRE((*bendersexitpre))  ,
SCIP_DECL_BENDERSINITSOL((*bendersinitsol))  ,
SCIP_DECL_BENDERSEXITSOL((*bendersexitsol))  ,
SCIP_DECL_BENDERSGETVAR((*bendersgetvar))  ,
SCIP_DECL_BENDERSCREATESUB((*benderscreatesub))  ,
SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve))  ,
SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex))  ,
SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub))  ,
SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve))  ,
SCIP_DECL_BENDERSFREESUB((*bendersfreesub))  ,
SCIP_BENDERSDATA bendersdata 
)

creates a Benders' decomposition

creates a Benders' decomposition structure

To use the Benders' decomposition for solving a problem, it first has to be activated with a call to SCIPactivateBenders().

Parameters
benderspointer to Benders' decomposition data structure
setglobal SCIP settings
messagehdlrmessage handler
blkmemblock memory for parameter settings
namename of Benders' decomposition
descdescription of Benders' decomposition
prioritypriority of the Benders' decomposition
cutlpshould Benders' cuts be generated for LP solutions
cutpseudoshould Benders' cuts be generated for pseudo solutions
cutrelaxshould Benders' cuts be generated for relaxation solutions
shareauxvarsshould this Benders' use the highest priority Benders aux vars
bendersdataBenders' decomposition data

Definition at line 969 of file benders.c.

References doBendersCreate(), NULL, SCIP_CALL_FINALLY, SCIP_OKAY, and SCIPbendersFree().

Referenced by SCIPincludeBenders(), and SCIPincludeBendersBasic().

◆ SCIPbendersFree()

SCIP_RETCODE SCIPbendersFree ( SCIP_BENDERS **  benders,
SCIP_SET set 
)

calls destructor and frees memory of Benders' decomposition

Parameters
benderspointer to Benders' decomposition data structure
setglobal SCIP settings

Definition at line 1048 of file benders.c.

References BMSfreeMemory, BMSfreeMemoryArray, BMSfreeMemoryArrayNull, NULL, releaseVarMappingHashmapVars(), SCIP_CALL, SCIP_OKAY, SCIPbenderscutFree(), SCIPclockFree(), and SCIPhashmapFree().

Referenced by SCIPbendersCreate().

◆ SCIPbendersInit()

◆ SCIPbendersExit()

◆ SCIPbendersInitpre()

SCIP_RETCODE SCIPbendersInitpre ( SCIP_BENDERS benders,
SCIP_SET set,
SCIP_STAT stat 
)

informs the Benders' decomposition that the presolving process is being started

Parameters
bendersBenders' decomposition
setglobal SCIP settings
statdynamic problem statistics

Definition at line 1664 of file benders.c.

References addAuxiliaryVariablesToMaster(), assignAuxiliaryVariables(), checkSubproblemIndependence(), SCIP_Benders::iscopy, NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Benders::setuptime.

Referenced by SCIPsetExitPlugins().

◆ SCIPbendersExitpre()

SCIP_RETCODE SCIPbendersExitpre ( SCIP_BENDERS benders,
SCIP_SET set,
SCIP_STAT stat 
)

informs the Benders' decomposition that the presolving process has completed

Parameters
bendersBenders' decomposition
setglobal SCIP settings
statdynamic problem statistics

Definition at line 1708 of file benders.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Benders::setuptime.

Referenced by SCIPsetExitPlugins().

◆ SCIPbendersInitsol()

SCIP_RETCODE SCIPbendersInitsol ( SCIP_BENDERS benders,
SCIP_SET set 
)

informs Benders' decomposition that the branch and bound process is being started

Parameters
bendersBenders' decomposition
setglobal SCIP settings

Definition at line 1734 of file benders.c.

References SCIP_Benders::benderscuts, SCIP_Benders::nbenderscuts, NULL, SCIP_CALL, SCIP_OKAY, SCIPbenderscutInitsol(), SCIPbendersSortBenderscuts(), SCIPclockStart(), SCIPclockStop(), and SCIP_Benders::setuptime.

Referenced by SCIPsetInitprePlugins().

◆ SCIPbendersExitsol()

SCIP_RETCODE SCIPbendersExitsol ( SCIP_BENDERS benders,
SCIP_SET set 
)

informs Benders' decomposition that the branch and bound process data is being freed

Parameters
bendersBenders' decomposition
setglobal SCIP settings

Definition at line 1767 of file benders.c.

References SCIP_Benders::benderscuts, FALSE, SCIP_Benders::nbenderscuts, NULL, SCIP_CALL, SCIP_OKAY, SCIPbenderscutExitsol(), SCIPbendersFreeSubproblem(), SCIPbendersGetNSubproblems(), SCIPbendersSetSubproblemIsIndependent(), SCIPbendersSortBenderscuts(), SCIPbendersSubproblemIsIndependent(), SCIPclockStart(), SCIPclockStop(), and SCIP_Benders::setuptime.

Referenced by SCIPsetInitsolPlugins().

◆ SCIPbendersActivate()

◆ SCIPbendersDeactivate()

void SCIPbendersDeactivate ( SCIP_BENDERS benders,
SCIP_SET set 
)

◆ SCIPbendersEnableOrDisableClocks()

void SCIPbendersEnableOrDisableClocks ( SCIP_BENDERS benders,
SCIP_Bool  enable 
)

enables or disables all clocks of Benders' decomposition depending on the value of the flag

enables or disables all clocks of the Benders' decomposition, depending on the value of the flag

Parameters
bendersthe Benders' decomposition for which all clocks should be enabled or disabled
enableshould the clocks of the Benders' decomposition be enabled?

Definition at line 4297 of file benders.c.

References SCIP_Benders::bendersclock, NULL, SCIPclockEnableOrDisable(), and SCIP_Benders::setuptime.

◆ SCIPbendersExec()

SCIP_RETCODE SCIPbendersExec ( SCIP_BENDERS benders,
SCIP_SET set,
SCIP_SOL sol,
SCIP_RESULT result,
SCIP_Bool infeasible,
SCIP_Bool auxviol,
SCIP_BENDERSENFOTYPE  type,
SCIP_Bool  checkint 
)

solves the subproblem using the current master problem solution.

The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint == FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e. checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check solution feasibility.

Solves the subproblem using the current master problem solution.

The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint == FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e. checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check solution feasibility.

TODO: consider allowing the possibility to pass solution information back from the subproblems instead of the scip instance. This would allow the use of different solvers for the subproblems, more importantly allowing the use of an LP solver for LP subproblems.

Parameters
bendersBenders' decomposition
setglobal SCIP settings
solprimal CIP solution
resultresult of the pricing process
infeasibleis the master problem infeasible with respect to the Benders' cuts?
auxviolset to TRUE only if the solution is feasible but the aux vars are violated
typethe type of solution being enforced
checkintshould the integer solution be checked by the subproblems

Definition at line 2498 of file benders.c.

References BENDERS_MAXPSEUDOSOLS, SCIP_Benders::bendersclock, FALSE, SCIP_Benders::firstchecked, generateBendersCuts(), SCIP_Benders::iscopy, SCIP_Benders::lastchecked, SCIP_Benders::lnscheck, SCIP_Benders::lnsmaxdepth, SCIP_Benders::name, SCIP_Benders::ncalls, SCIP_Benders::npseudosols, NULL, resetSubproblemObjectiveValue(), SCIP_BENDERSENFOTYPE_CHECK, SCIP_BENDERSENFOTYPE_LP, SCIP_BENDERSENFOTYPE_PSEUDO, SCIP_BENDERSSOLVELOOP_USERCIP, SCIP_BENDERSSOLVELOOP_USERCONVEX, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_ERROR, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_INVALIDRESULT, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIP_SEPARATED, SCIP_SOLVELP, SCIP_STAGE_TRANSFORMED, SCIP_VERBLEVEL_HIGH, SCIPallocClearBlockMemoryArray, SCIPbendersFreeSubproblem(), SCIPbendersGetName(), SCIPbendersGetNConvexSubproblems(), SCIPbendersGetNSubproblems(), SCIPbendersOnlyCheckConvexRelax(), SCIPbendersSubproblem(), SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPgetDepth(), SCIPgetLPSolstat(), SCIPgetObjsense(), SCIPgetPrimalbound(), SCIPgetSolOrigObj(), SCIPgetStage(), SCIPinProbing(), SCIPsetDebugMsg, SCIPsetIsFeasLE(), SCIPverbMessage(), solveBendersSubproblems(), SCIP_Benders::sourcescip, subproblemIsActive(), TRUE, updateAuxiliaryVarLowerbound(), and SCIP_Benders::updateauxvarbound.

Referenced by SCIPsolveBendersSubproblems().

◆ SCIPbendersExecSubproblemSolve()

SCIP_RETCODE SCIPbendersExecSubproblemSolve ( SCIP_BENDERS benders,
SCIP_SET set,
SCIP_SOL sol,
int  probnumber,
SCIP_BENDERSSOLVELOOP  solveloop,
SCIP_Bool  enhancement,
SCIP_Bool solved,
SCIP_Bool infeasible,
SCIP_BENDERSENFOTYPE  type 
)

Executes the subproblem solving process.

executes the subproblem solving process

Parameters
bendersBenders' decomposition
setglobal SCIP settings
solprimal CIP solution
probnumberthe subproblem number
solveloopthe solve loop iteration. The first iter is for LP, the second for IP
enhancementis the solve performed as part of and enhancement?
solvedflag to indicate whether the subproblem was solved
infeasiblereturns whether the current subproblem is infeasible
typethe enforcement type calling this function

Definition at line 2940 of file benders.c.

References executeUserDefinedSolvesub(), FALSE, NULL, SCIP_BENDERSSOLVELOOP_CIP, SCIP_BENDERSSOLVELOOP_CONVEX, SCIP_BENDERSSOLVELOOP_USERCIP, SCIP_BENDERSSOLVELOOP_USERCONVEX, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_LPSOLSTAT_ERROR, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_NOTSOLVED, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_TIMELIMIT, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_USERINTERRUPT, SCIP_UNBOUNDED, SCIP_VERBLEVEL_FULL, SCIPABORT, SCIPbendersGetAuxiliaryVarVal(), SCIPbendersSetSubproblemObjval(), SCIPbendersSetupSubproblem(), SCIPbendersSolveSubproblemCIP(), SCIPbendersSolveSubproblemLP(), SCIPbendersSubproblem(), SCIPbendersSubproblemIsConvex(), SCIPbendersSubproblemIsSetup(), SCIPerrorMessage, SCIPgetBestSol(), SCIPgetLPSolstat(), SCIPgetObjsense(), SCIPgetSolOrigObj(), SCIPgetStatus(), SCIPsetDebugMsg, SCIPsetInfinity(), SCIPverbMessage(), TRUE, and updateEventhdlrUpperbound().

Referenced by solveBendersSubproblems().

◆ SCIPbendersSetupSubproblem()

SCIP_RETCODE SCIPbendersSetupSubproblem ( SCIP_BENDERS benders,
SCIP_SET set,
SCIP_SOL sol,
int  probnumber 
)

◆ SCIPbendersSolveSubproblem()

SCIP_RETCODE SCIPbendersSolveSubproblem ( SCIP_BENDERS benders,
SCIP_SET set,
SCIP_SOL sol,
int  probnumber,
SCIP_Bool infeasible,
SCIP_BENDERSENFOTYPE  type,
SCIP_Bool  solvecip,
SCIP_Real objective 
)

Solve a Benders' decomposition subproblems. This will either call the user defined method or the generic solving methods. If the generic method is called, then the subproblem must be set up before calling this method.

Parameters
bendersBenders' decomposition
setglobal SCIP settings
solprimal CIP solution, can be NULL
probnumberthe subproblem number
infeasiblereturns whether the current subproblem is infeasible
typethe enforcement type calling this function
solvecipdirectly solve the CIP subproblem
objectivethe objective function value of the subproblem, can be NULL

Definition at line 3214 of file benders.c.

References executeUserDefinedSolvesub(), initialiseSubproblem(), NULL, SCIP_BENDERSSOLVELOOP_USERCIP, SCIP_BENDERSSOLVELOOP_USERCONVEX, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPbendersGetNSubproblems(), SCIPbendersSolveSubproblemCIP(), SCIPbendersSolveSubproblemLP(), SCIPbendersSubproblem(), SCIPbendersSubproblemIsConvex(), SCIPbendersSubproblemIsIndependent(), SCIPbendersSubproblemIsSetup(), SCIPerrorMessage, SCIPgetBestSol(), SCIPgetObjsense(), SCIPgetSolOrigObj(), SCIPinfinity(), SCIPinProbing(), SCIPstartProbing(), and TRUE.

Referenced by SCIPsolveBendersSubproblem().

◆ SCIPbendersFreeSubproblem()

SCIP_RETCODE SCIPbendersFreeSubproblem ( SCIP_BENDERS benders,
SCIP_SET set,
int  probnumber 
)

◆ SCIPbendersCheckSubproblemOptimality()

SCIP_RETCODE SCIPbendersCheckSubproblemOptimality ( SCIP_BENDERS benders,
SCIP_SET set,
SCIP_SOL sol,
int  probnumber,
SCIP_Bool optimal 
)

compares the subproblem objective value with the auxiliary variable value for optimality

Parameters
bendersthe benders' decomposition structure
setglobal SCIP settings
solprimal CIP solution
probnumberthe subproblem number
optimalflag to indicate whether the current subproblem is optimal for the master

Definition at line 3652 of file benders.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbendersGetAuxiliaryVarVal(), SCIPbendersGetSubproblemObjval(), SCIPrelDiff(), SCIPsetDebugMsg, SCIPsetGetRealParam(), and TRUE.

Referenced by SCIPcheckBendersSubproblemOptimality(), and solveBendersSubproblems().

◆ SCIPbendersGetAuxiliaryVarVal()

SCIP_Real SCIPbendersGetAuxiliaryVarVal ( SCIP_BENDERS benders,
SCIP_SET set,
SCIP_SOL sol,
int  probnumber 
)

returns the value of the auxiliary variable value in a master problem solution

Parameters
bendersthe benders' decomposition structure
setglobal SCIP settings
solprimal CIP solution
probnumberthe subproblem number

Definition at line 3684 of file benders.c.

References NULL, SCIPbendersGetAuxiliaryVar(), and SCIPgetSolVal().

Referenced by SCIPbendersCheckSubproblemOptimality(), SCIPbendersExecSubproblemSolve(), SCIPgetBendersAuxiliaryVarVal(), and solveBendersSubproblems().

◆ SCIPbendersComputeSubproblemLowerbound()

SCIP_RETCODE SCIPbendersComputeSubproblemLowerbound ( SCIP_BENDERS benders,
SCIP_SET set,
int  probnumber,
SCIP_Real lowerbound,
SCIP_Bool infeasible 
)

◆ SCIPbendersMergeSubproblemIntoMaster()

SCIP_RETCODE SCIPbendersMergeSubproblemIntoMaster ( SCIP_BENDERS benders,
SCIP_SET set,
SCIP_HASHMAP varmap,
SCIP_HASHMAP consmap,
int  probnumber 
)

merges a subproblem into the master problem. This process just adds a copy of the subproblem variables and constraints to the master problem, but keeps the subproblem stored in the Benders' decomposition data structure. The reason for keeping the subproblem available is for when it is queried for solutions after the problem is solved.

Once the subproblem is merged into the master problem, then the subproblem is flagged as disabled. This means that it will not be solved in the subsequent subproblem solving loops.

The associated auxiliary variables are kept in the master problem. The objective function of the merged subproblem is added as an underestimator constraint.

Merges a subproblem into the master problem. This process just adds a copy of the subproblem variables and constraints to the master problem, but keeps the subproblem stored in the Benders' decomposition data structure. The reason for keeping the subproblem available is for when it is queried for solutions after the problem is solved.

Once the subproblem is merged into the master problem, then the subproblem is flagged as disabled. This means that it will not be solved in the subsequent subproblem solving loops.

The associated auxiliary variables are kept in the master problem. The objective function of the merged subproblem is added as an underestimator constraint.

Parameters
bendersBenders' decomposition
setglobal SCIP settings
varmapa hashmap to store the mapping of subproblem variables corresponding to the newly created master variables, or NULL
consmapa hashmap to store the mapping of subproblem constraints to the corresponding newly created constraints, or NULL
probnumberthe number of the subproblem that will be merged into the master problem

Definition at line 3818 of file benders.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPbendersFreeSubproblem(), SCIPbendersGetAuxiliaryVar(), SCIPbendersSetSubproblemEnabled(), SCIPbendersSubproblem(), SCIPblkmem(), SCIPconsGetHdlr(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPcreateConsBasicLinear(), SCIPcreateVarBasic(), SCIPgetBendersMasterVar(), SCIPgetConsCopy(), SCIPgetConss(), SCIPgetNConss(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetConsRemovable(), SCIPsetInfinity(), SCIPsnprintf(), SCIPvarGetLbOriginal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetOrigvarSum(), SCIPvarGetType(), SCIPvarGetUbOriginal(), SCIPverbMessage(), and TRUE.

Referenced by SCIPmergeBendersSubproblemIntoMaster().

◆ SCIPbendersSetPriority()

void SCIPbendersSetPriority ( SCIP_BENDERS benders,
SCIP_SET set,
int  priority 
)

sets priority of Benders' decomposition

Parameters
bendersBenders' decomposition
setglobal SCIP settings
prioritynew priority of the Benders' decomposition

Definition at line 4221 of file benders.c.

References FALSE, NULL, and SCIP_Benders::priority.

Referenced by SCIPsetBendersPriority().

◆ SCIPbendersSetCopy()

void SCIPbendersSetCopy ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSCOPY((*benderscopy))   
)

sets copy callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4048 of file benders.c.

References NULL.

Referenced by SCIPsetBendersCopy().

◆ SCIPbendersSetFree()

void SCIPbendersSetFree ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSFREE((*bendersfree))   
)

sets destructor callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4059 of file benders.c.

References NULL.

Referenced by SCIPsetBendersFree().

◆ SCIPbendersSetInit()

void SCIPbendersSetInit ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSINIT((*bendersinit))   
)

sets initialization callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4070 of file benders.c.

References NULL.

Referenced by SCIPsetBendersInit().

◆ SCIPbendersSetExit()

void SCIPbendersSetExit ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSEXIT((*bendersexit))   
)

sets deinitialization callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4081 of file benders.c.

References NULL.

Referenced by SCIPsetBendersExit().

◆ SCIPbendersSetInitpre()

void SCIPbendersSetInitpre ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSINITPRE((*bendersinitpre))   
)

sets presolving initialization callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4092 of file benders.c.

References NULL.

Referenced by SCIPsetBendersInitpre().

◆ SCIPbendersSetExitpre()

void SCIPbendersSetExitpre ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSEXITPRE((*bendersexitpre))   
)

sets presolving deinitialization callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4103 of file benders.c.

References NULL.

Referenced by SCIPsetBendersExitpre().

◆ SCIPbendersSetInitsol()

void SCIPbendersSetInitsol ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSINITSOL((*bendersinitsol))   
)

sets solving process initialization callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4114 of file benders.c.

References NULL.

Referenced by SCIPsetBendersInitsol().

◆ SCIPbendersSetExitsol()

void SCIPbendersSetExitsol ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSEXITSOL((*bendersexitsol))   
)

sets solving process deinitialization callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4125 of file benders.c.

References NULL.

Referenced by SCIPsetBendersExitsol().

◆ SCIPbendersSetPresubsolve()

void SCIPbendersSetPresubsolve ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve))   
)

sets the pre subproblem solve callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4136 of file benders.c.

References NULL.

Referenced by SCIPsetBendersPresubsolve().

◆ SCIPbendersSetSolvesubconvex()

void SCIPbendersSetSolvesubconvex ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex))   
)

sets convex solve callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4147 of file benders.c.

References NULL.

Referenced by SCIPsetBendersSolveAndFreesub().

◆ SCIPbendersSetSolvesub()

void SCIPbendersSetSolvesub ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub))   
)

sets solve callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4158 of file benders.c.

References NULL.

Referenced by SCIPsetBendersSolveAndFreesub().

◆ SCIPbendersSetPostsolve()

void SCIPbendersSetPostsolve ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve))   
)

sets post-solve callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4169 of file benders.c.

References NULL.

Referenced by SCIPsetBendersPostsolve().

◆ SCIPbendersSetFreesub()

void SCIPbendersSetFreesub ( SCIP_BENDERS benders,
SCIP_DECL_BENDERSFREESUB((*bendersfreesub))   
)

sets free subproblem callback of Benders' decomposition

Parameters
bendersBenders' decomposition

Definition at line 4180 of file benders.c.

References NULL.

Referenced by SCIPsetBendersSolveAndFreesub().

◆ SCIPbendersGetVar()

SCIP_RETCODE SCIPbendersGetVar ( SCIP_BENDERS benders,
SCIP_SET set,
SCIP_VAR var,
SCIP_VAR **  mappedvar,
int  probnumber 
)

Returns the corresponding master or subproblem variable for the given variable. This provides a call back for the variable mapping between the master and subproblems.

Parameters
bendersBenders' decomposition
setglobal SCIP settings
varthe variable for which the corresponding variable is desired
mappedvarthe variable that is mapped to var
probnumberthe problem number for the desired variable, -1 for the master problem

Definition at line 4001 of file benders.c.

References AUXILIARYVAR_NAME, NULL, SCIP_CALL, SCIP_OKAY, and SCIPvarGetName().

Referenced by createSubproblems(), SCIPbendersChgMastervarsToCont(), SCIPbendersSetupSubproblem(), SCIPgetBendersMasterVar(), and SCIPgetBendersSubproblemVar().

◆ SCIPbendersAddSubproblem()

SCIP_RETCODE SCIPbendersAddSubproblem ( SCIP_BENDERS benders,
SCIP subproblem 
)

adds a subproblem to the Benders' decomposition data

Parameters
bendersBenders' decomposition
subproblemsubproblem to be added to the data storage

Definition at line 4359 of file benders.c.

References SCIP_Benders::naddedsubprobs, SCIP_Benders::nsubproblems, NULL, SCIP_OKAY, and SCIP_Benders::subproblems.

Referenced by SCIPaddBendersSubproblem().

◆ SCIPbendersRemoveSubproblems()

void SCIPbendersRemoveSubproblems ( SCIP_BENDERS benders)

removes the subproblems from the Benders' decomposition data

Parameters
bendersBenders' decomposition

Definition at line 4377 of file benders.c.

References BMSclearMemoryArray, SCIP_Benders::naddedsubprobs, NULL, and SCIP_Benders::subproblems.

◆ SCIPbendersSetSubproblemIsSetup()

void SCIPbendersSetSubproblemIsSetup ( SCIP_BENDERS benders,
int  probnumber,
SCIP_Bool  issetup 
)

sets the subproblem setup flag

Parameters
bendersBenders' decomposition
probnumberthe subproblem number
issetupflag to indicate whether the subproblem has been setup

Definition at line 4561 of file benders.c.

References NULL, SCIPbendersGetNSubproblems(), and SCIP_Benders::subprobsetup.

Referenced by SCIPbendersFreeSubproblem(), and SCIPbendersSetupSubproblem().

◆ SCIPbendersSubproblemIsSetup()

SCIP_Bool SCIPbendersSubproblemIsSetup ( SCIP_BENDERS benders,
int  probnumber 
)

returns the subproblem setup flag

Parameters
bendersBenders' decomposition
probnumberthe subproblem number

Definition at line 4574 of file benders.c.

References NULL, SCIPbendersGetNSubproblems(), and SCIP_Benders::subprobsetup.

Referenced by SCIPbendersExecSubproblemSolve(), SCIPbendersSolveSubproblem(), and SCIPbendersSolveSubproblemLP().

◆ SCIPbendersSetSubproblemEnabled()

void SCIPbendersSetSubproblemEnabled ( SCIP_BENDERS benders,
int  probnumber,
SCIP_Bool  enabled 
)

Sets whether the subproblem is enabled or disabled. A subproblem is disabled if it has been merged into the master problem.

Parameters
bendersBenders' decomposition
probnumberthe subproblem number
enabledflag to indicate whether the subproblem is enabled

Definition at line 4640 of file benders.c.

References SCIP_Benders::nactivesubprobs, NULL, SCIP_Bool, SCIPbendersGetNSubproblems(), SCIP_Benders::subprobenabled, and subproblemIsActive().

Referenced by SCIPbendersMergeSubproblemIntoMaster().

◆ SCIPbendersChgMastervarsToCont()

SCIP_RETCODE SCIPbendersChgMastervarsToCont ( SCIP_BENDERS benders,
SCIP_SET set,
int  probnumber 
)

changes all of the master problem variables in the given subproblem to continuous

changes all of the master problem variables in the given subproblem to continuous.

Parameters
bendersBenders' decomposition
setglobal SCIP settings
probnumberthe subproblem number

Definition at line 4491 of file benders.c.

References initialiseLPSubproblem(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPbendersGetMastervarsCont(), SCIPbendersGetNSubproblems(), SCIPbendersGetVar(), SCIPbendersSetMastervarsCont(), SCIPbendersSetSubproblemIsConvex(), SCIPbendersSubproblem(), SCIPchgVarType(), SCIPgetVarsData(), SCIPvarGetType(), and TRUE.

Referenced by SCIPbendersSetupSubproblem().

◆ SCIPbendersSetMastervarsCont()

SCIP_RETCODE SCIPbendersSetMastervarsCont ( SCIP_BENDERS benders,
int  probnumber,
SCIP_Bool  arecont 
)

sets a flag to indicate whether the master variables are all set to continuous

Parameters
bendersBenders' decomposition
probnumberthe subproblem number
arecontflag to indicate whether the master problem variables are continuous

Definition at line 4678 of file benders.c.

References FALSE, SCIP_Benders::mastervarscont, NULL, SCIP_CALL, SCIP_OKAY, SCIPbendersGetNSubproblems(), SCIPbendersSetSubproblemIsConvex(), SCIPbendersSubproblem(), SCIPendProbing(), and SCIPinProbing().

Referenced by SCIPbendersChgMastervarsToCont().

◆ SCIPbendersGetMastervarsCont()

SCIP_Bool SCIPbendersGetMastervarsCont ( SCIP_BENDERS benders,
int  probnumber 
)

returns whether the master variables are all set to continuous

Parameters
bendersBenders' decomposition
probnumberthe subproblem number

Definition at line 4705 of file benders.c.

References SCIP_Benders::mastervarscont, NULL, and SCIPbendersGetNSubproblems().

Referenced by SCIPbendersChgMastervarsToCont().

◆ SCIPbendersIncludeBenderscut()

SCIP_RETCODE SCIPbendersIncludeBenderscut ( SCIP_BENDERS benders,
SCIP_SET set,
SCIP_BENDERSCUT benderscut 
)

inserts a Benders' cut algorithm plugin into the Benders' cuts plugin list

inserts a Benders' cut into the Benders' cuts list

Parameters
bendersBenders' decomposition structure
setglobal SCIP settings
benderscutBenders' cut

Definition at line 4772 of file benders.c.

References SCIP_Benders::benderscuts, SCIP_Benders::benderscutssize, SCIP_Benders::benderscutssorted, BMSreallocMemoryArray, FALSE, SCIP_Benders::nbenderscuts, NULL, SCIP_ALLOC, SCIP_OKAY, and SCIPsetCalcMemGrowSize().

Referenced by SCIPincludeBenderscut(), and SCIPincludeBenderscutBasic().

◆ SCIPbendersSetBenderscutsSorted()

void SCIPbendersSetBenderscutsSorted ( SCIP_BENDERS benders,
SCIP_Bool  sorted 
)

sets the Benders' cuts sorted flags in the Benders' decomposition

sets the sorted flags in the Benders' decomposition

Parameters
bendersBenders' decomposition structure
sortedthe value to set the sorted flag to

Definition at line 4760 of file benders.c.

References SCIP_Benders::benderscutsnamessorted, SCIP_Benders::benderscutssorted, and NULL.

Referenced by SCIPsetBenderscutPriority().

◆ SCIPbendersSortBenderscuts()

void SCIPbendersSortBenderscuts ( SCIP_BENDERS benders)

sorts Benders' decomposition cuts by priorities

Parameters
bendersBenders' decomposition

Definition at line 4861 of file benders.c.

References SCIP_Benders::benderscuts, SCIP_Benders::benderscutsnamessorted, SCIP_Benders::benderscutssorted, FALSE, SCIP_Benders::nbenderscuts, NULL, SCIPsortPtr(), and TRUE.

Referenced by SCIPbendersCopyInclude(), SCIPbendersExit(), SCIPbendersExitsol(), SCIPbendersInit(), and SCIPbendersInitsol().

◆ SCIPbendersSortBenderscutsName()

void SCIPbendersSortBenderscutsName ( SCIP_BENDERS benders)

sorts Benders' decomposition cuts by name

Parameters
bendersBenders' decomposition

Definition at line 4876 of file benders.c.

References SCIP_Benders::benderscuts, SCIP_Benders::benderscutsnamessorted, SCIP_Benders::benderscutssorted, FALSE, SCIP_Benders::nbenderscuts, NULL, SCIPsortPtr(), and TRUE.