Detailed Description
GCG Benders' decomposition algorithm.
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 |
Definition at line 66 of file benders_gcg.c.
References GCGoriginalVarIsLinking(), and GCGpricingVarGetOrigvars().
Referenced by setSubproblemObjs().
◆ setSubproblemObjs()
|
static |
- Parameters
-
benders the benders' decomposition constraint handler probnumber the subproblem number
Definition at line 83 of file benders_gcg.c.
References GCGoriginalVarIsLinking(), GCGpricingVarGetOrigvars(), GCGvarGetBlock(), and varGetObj().
Referenced by SCIP_DECL_BENDERSCREATESUB().
◆ setOriginalProblemPricingValues()
|
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
-
origprob the SCIP instance of the original problem masterprob the Benders' master problem benders the Benders' decomposition structure origsol the solution for the original problem vars the variables from the decomposed problem vals the solution values of the given problem, can be NULL for an artificial solution nvars the number of variables success were 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 |
sets the master problem values for the original problem using the decomposed problem solution
- Parameters
-
origprob the SCIP instance of the original problem masterprob the Benders' master problem benders the Benders' decomposition structure origsol the solution for the original problem vars the variables from the decomposed problem vals the solution values of the given problem, can be NULL nvars the number of variables
Definition at line 216 of file benders_gcg.c.
References GCGmasterVarGetNOrigvars(), GCGmasterVarGetOrigvals(), GCGmasterVarGetOrigvars(), and GCGvarIsMaster().
Referenced by createOriginalProblemSolution().
◆ createOriginalProblemSolution()
|
static |
creates an original problem solution from the master and subproblem solutions
- Parameters
-
masterprob the Benders' master problem benders the Benders' decomposition structure sol the solution passed to the Benders' decomposition subproblems. artificial should 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 |
merge a single subproblem into the master problem
- Parameters
-
masterprob the Benders' master problem benders the Benders' decomposition structure probnumber the index of the subproblem that will be merged
Definition at line 426 of file benders_gcg.c.
References GCGcopyPricingvarDataToMastervar().
Referenced by mergeSubproblemsIntoMaster().
◆ mergeSubproblemsIntoMaster()
|
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
-
masterprob the Benders' master problem benders the Benders' decomposition structure mergecands the subproblems that are merge candidates npriomergecands the priority merge candidates, these should be merged nmergecands the total number of merge candidates merged flag 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 |
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 |
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 |
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 |
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 |
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 |
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
-
scip SCIP data structure origprob the 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().