Scippy

GCG

Branch-and-Price & Column Generation for Everyone

benders_gcg.c File Reference

Detailed Description

GCG Benders' decomposition algorithm.

Author
Stephen J. Maher

Definition in file benders_gcg.c.

#include <assert.h>
#include <string.h>
#include "benders_gcg.h"
#include "gcg.h"
#include "relax_gcg.h"
#include "scip_misc.h"
#include "pub_gcgvar.h"
#include "scip/cons_linear.h"
#include "scip/pub_var.h"
#include "scip/pub_benders.h"
#include "scip/bendersdefcuts.h"

Go to the source code of this file.

Data Structures

struct  SCIP_BendersData
 

Macros

#define BENDERS_NAME   "gcg"
 
#define BENDERS_DESC   "Benders' decomposition for the Generic Column Generation package"
 
#define BENDERS_PRIORITY   1000
 
#define BENDERS_CUTLP   TRUE
 
#define BENDERS_CUTPSEUDO   TRUE
 
#define BENDERS_CUTRELAX   TRUE
 
#define BENDERS_SHAREAUXVARS   FALSE
 
#define LARGE_VALUE   10000
 

Functions

static SCIP_Real varGetObj (SCIP_VAR *var)
 
static SCIP_RETCODE setSubproblemObjs (SCIP_BENDERS *benders, int probnumber)
 
static SCIP_RETCODE setOriginalProblemPricingValues (SCIP *origprob, SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *origsol, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Bool *success)
 
static SCIP_RETCODE setOriginalProblemMasterValues (SCIP *origprob, SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *origsol, SCIP_VAR **vars, SCIP_Real *vals, int nvars)
 
static SCIP_RETCODE createOriginalProblemSolution (SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_Bool artificial)
 
static SCIP_RETCODE mergeSubproblemIntoMaster (SCIP *masterprob, SCIP_BENDERS *benders, int probnumber)
 
static SCIP_RETCODE mergeSubproblemsIntoMaster (SCIP *masterprob, SCIP_BENDERS *benders, int *mergecands, int npriomergecands, int nmergecands, SCIP_Bool *merged)
 
static SCIP_DECL_BENDERSFREE (bendersFreeGcg)
 
static SCIP_DECL_BENDERSINITPRE (bendersInitpreGcg)
 
static SCIP_DECL_BENDERSEXITSOL (bendersExitsolGcg)
 
static SCIP_DECL_BENDERSGETVAR (bendersGetvarGcg)
 
static SCIP_DECL_BENDERSPOSTSOLVE (bendersPostsolveGcg)
 
static SCIP_DECL_BENDERSCREATESUB (bendersCreatesubGcg)
 
SCIP_RETCODE SCIPincludeBendersGcg (SCIP *scip, SCIP *origprob)
 
SCIP_SOL * SCIPbendersGetRelaxSol (SCIP_BENDERS *benders)
 
SCIP * GCGbendersGetOrigprob (SCIP *masterprob)
 

Macro Definition Documentation

◆ BENDERS_NAME

#define BENDERS_NAME   "gcg"

Definition at line 39 of file benders_gcg.c.

◆ BENDERS_DESC

#define BENDERS_DESC   "Benders' decomposition for the Generic Column Generation package"

Definition at line 40 of file benders_gcg.c.

◆ BENDERS_PRIORITY

#define BENDERS_PRIORITY   1000

Definition at line 41 of file benders_gcg.c.

◆ BENDERS_CUTLP

#define BENDERS_CUTLP   TRUE

should Benders' cut be generated for LP solutions

Definition at line 42 of file benders_gcg.c.

◆ BENDERS_CUTPSEUDO

#define BENDERS_CUTPSEUDO   TRUE

should Benders' cut be generated for pseudo solutions

Definition at line 43 of file benders_gcg.c.

◆ BENDERS_CUTRELAX

#define BENDERS_CUTRELAX   TRUE

should Benders' cut be generated for relaxation solutions

Definition at line 44 of file benders_gcg.c.

◆ BENDERS_SHAREAUXVARS

#define BENDERS_SHAREAUXVARS   FALSE

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

Definition at line 45 of file benders_gcg.c.

◆ LARGE_VALUE

#define LARGE_VALUE   10000

a large value that is used to create an artificial solution

Definition at line 47 of file benders_gcg.c.

Function Documentation

◆ varGetObj()

static SCIP_Real varGetObj ( SCIP_VAR *  var)
static

Definition at line 66 of file benders_gcg.c.

References GCGoriginalVarIsLinking(), and GCGpricingVarGetOrigvars().

Referenced by setSubproblemObjs().

◆ setSubproblemObjs()

static SCIP_RETCODE setSubproblemObjs ( SCIP_BENDERS *  benders,
int  probnumber 
)
static
Parameters
bendersthe benders' decomposition constraint handler
probnumberthe subproblem number

Definition at line 83 of file benders_gcg.c.

References GCGoriginalVarIsLinking(), GCGpricingVarGetOrigvars(), GCGvarGetBlock(), and varGetObj().

Referenced by SCIP_DECL_BENDERSCREATESUB().

◆ setOriginalProblemPricingValues()

static SCIP_RETCODE setOriginalProblemPricingValues ( SCIP *  origprob,
SCIP *  masterprob,
SCIP_BENDERS *  benders,
SCIP_SOL *  origsol,
SCIP_VAR **  vars,
SCIP_Real *  vals,
int  nvars,
SCIP_Bool *  success 
)
static

sets the pricing problem variable values for the original problem using the decomposed problem solution There is a mapping between the original problem and the variables from the pricing problems. This mapping is used to identify the variables of the original problem corresponding to the pricing problem variables.

An artificial solution can be constructed, which is indicated by the vals array provided as NULL. An artifical solution sets the original problem variables corresponding to pricing problems variables to their bounds. An artificial solution is created if branching candidates need to be found. Branching candidates only come from the master problem, so the variable values of the pricing problem variables does not affect the branching variable selection

Parameters
origprobthe SCIP instance of the original problem
masterprobthe Benders' master problem
bendersthe Benders' decomposition structure
origsolthe solution for the original problem
varsthe variables from the decomposed problem
valsthe solution values of the given problem, can be NULL for an artificial solution
nvarsthe number of variables
successwere all values set successfully?

Definition at line 126 of file benders_gcg.c.

References GCGpricingVarGetNOrigvars(), GCGpricingVarGetOrigvars(), GCGvarIsPricing(), and LARGE_VALUE.

Referenced by createOriginalProblemSolution().

◆ setOriginalProblemMasterValues()

static SCIP_RETCODE setOriginalProblemMasterValues ( SCIP *  origprob,
SCIP *  masterprob,
SCIP_BENDERS *  benders,
SCIP_SOL *  origsol,
SCIP_VAR **  vars,
SCIP_Real *  vals,
int  nvars 
)
static

sets the master problem values for the original problem using the decomposed problem solution

Parameters
origprobthe SCIP instance of the original problem
masterprobthe Benders' master problem
bendersthe Benders' decomposition structure
origsolthe solution for the original problem
varsthe variables from the decomposed problem
valsthe solution values of the given problem, can be NULL
nvarsthe number of variables

Definition at line 216 of file benders_gcg.c.

References GCGmasterVarGetNOrigvars(), GCGmasterVarGetOrigvals(), GCGmasterVarGetOrigvars(), and GCGvarIsMaster().

Referenced by createOriginalProblemSolution().

◆ createOriginalProblemSolution()

static SCIP_RETCODE createOriginalProblemSolution ( SCIP *  masterprob,
SCIP_BENDERS *  benders,
SCIP_SOL *  sol,
SCIP_Bool  artificial 
)
static

creates an original problem solution from the master and subproblem solutions

Parameters
masterprobthe Benders' master problem
bendersthe Benders' decomposition structure
solthe solution passed to the Benders' decomposition subproblems.
artificialshould an artifical (possibly infeasible) solution be created to generate branching candidates

Definition at line 271 of file benders_gcg.c.

References GCGrelaxGetProbingheur(), setOriginalProblemMasterValues(), and setOriginalProblemPricingValues().

Referenced by SCIP_DECL_BENDERSPOSTSOLVE().

◆ mergeSubproblemIntoMaster()

static SCIP_RETCODE mergeSubproblemIntoMaster ( SCIP *  masterprob,
SCIP_BENDERS *  benders,
int  probnumber 
)
static

merge a single subproblem into the master problem

Parameters
masterprobthe Benders' master problem
bendersthe Benders' decomposition structure
probnumberthe index of the subproblem that will be merged

Definition at line 426 of file benders_gcg.c.

References GCGcopyPricingvarDataToMastervar().

Referenced by mergeSubproblemsIntoMaster().

◆ mergeSubproblemsIntoMaster()

static SCIP_RETCODE mergeSubproblemsIntoMaster ( SCIP *  masterprob,
SCIP_BENDERS *  benders,
int *  mergecands,
int  npriomergecands,
int  nmergecands,
SCIP_Bool *  merged 
)
static

performs a merge of subproblems into the master problem. The subproblems are merged into the master problem if the infeasibility can not be resolved through the addition of cuts. This could be because the appropriate cuts are not available in the Benders' decomposition framework, or that the subproblem has been infeasible for a set number of iterations.

Parameters
masterprobthe Benders' master problem
bendersthe Benders' decomposition structure
mergecandsthe subproblems that are merge candidates
npriomergecandsthe priority merge candidates, these should be merged
nmergecandsthe total number of merge candidates
mergedflag to indicate whether a subproblem has been merged into the master

Definition at line 473 of file benders_gcg.c.

References mergeSubproblemIntoMaster().

Referenced by SCIP_DECL_BENDERSPOSTSOLVE().

◆ SCIP_DECL_BENDERSFREE()

static SCIP_DECL_BENDERSFREE ( bendersFreeGcg  )
static

destructor of Benders' decomposition to free user data (called when SCIP is exiting)

Definition at line 520 of file benders_gcg.c.

◆ SCIP_DECL_BENDERSINITPRE()

static SCIP_DECL_BENDERSINITPRE ( bendersInitpreGcg  )
static

presolving initialization method of constraint handler (called when presolving is about to begin)

Definition at line 539 of file benders_gcg.c.

References GCGaddDataAuxiliaryVar().

◆ SCIP_DECL_BENDERSEXITSOL()

static SCIP_DECL_BENDERSEXITSOL ( bendersExitsolGcg  )
static

solving process deinitialization method of Benders' decomposition (called before branch and bound process data is freed)

Definition at line 559 of file benders_gcg.c.

◆ SCIP_DECL_BENDERSGETVAR()

static SCIP_DECL_BENDERSGETVAR ( bendersGetvarGcg  )
static

mapping method between the master problem variables and the subproblem variables of Benders' decomposition

Definition at line 579 of file benders_gcg.c.

References GCGlinkingVarGetPricingVars(), GCGmasterVarGetOrigvars(), GCGoriginalVarGetMastervars(), GCGoriginalVarGetNMastervars(), GCGoriginalVarGetPricingVar(), GCGoriginalVarIsLinking(), and GCGpricingVarGetOrigvars().

◆ SCIP_DECL_BENDERSPOSTSOLVE()

static SCIP_DECL_BENDERSPOSTSOLVE ( bendersPostsolveGcg  )
static

the post-execution method for Benders' decomposition

Definition at line 644 of file benders_gcg.c.

References createOriginalProblemSolution(), GCGrelaxUpdateCurrentSol(), and mergeSubproblemsIntoMaster().

◆ SCIP_DECL_BENDERSCREATESUB()

static SCIP_DECL_BENDERSCREATESUB ( bendersCreatesubGcg  )
static

the method for creating the Benders' decomposition subproblem. This method is called during the initialization 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 689 of file benders_gcg.c.

References GCGgetPricingprob(), and setSubproblemObjs().

◆ SCIPincludeBendersGcg()

SCIP_RETCODE SCIPincludeBendersGcg ( SCIP *  scip,
SCIP *  origprob 
)

creates the gcg Benders' decomposition and includes it in SCIP

Parameters
scipSCIP data structure
origprobthe SCIP instance of the original problem

Definition at line 719 of file benders_gcg.c.

References BENDERS_CUTLP, BENDERS_CUTPSEUDO, BENDERS_CUTRELAX, BENDERS_DESC, BENDERS_NAME, BENDERS_PRIORITY, and BENDERS_SHAREAUXVARS.

Referenced by SCIPincludeRelaxGcg().