Scippy

SCIP

Solving Constraint Integer Programs

benderscut_opt.c File Reference

Detailed Description

Generates a standard Benders' decomposition optimality cut.

Author
Stephen J. Maher

Definition in file benderscut_opt.c.

#include "scip/benderscut_opt.h"
#include "scip/cons_linear.h"
#include "scip/pub_benderscut.h"
#include "scip/pub_benders.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_linear.h"
#include "scip/pub_var.h"
#include "scip/scip_benders.h"
#include "scip/scip_cons.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_var.h"
#include <string.h>

Go to the source code of this file.

Macros

#define BENDERSCUT_NAME   "optimality"
 
#define BENDERSCUT_DESC   "Standard Benders' decomposition optimality cut"
 
#define BENDERSCUT_PRIORITY   5000
 
#define BENDERSCUT_LPCUT   TRUE
 
#define SCIP_DEFAULT_ADDCUTS   FALSE /** Should cuts be generated, instead of constraints */
 

Functions

static SCIP_RETCODE polishSolution (SCIP *subproblem, SCIP_Bool *success)
 
static SCIP_RETCODE computeStandardOptimalityCut (SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_CONS *cons, SCIP_ROW *row, SCIP_Bool addcut, SCIP_Bool *success)
 
static SCIP_RETCODE addAuxiliaryVariableToCut (SCIP *masterprob, SCIP_BENDERS *benders, SCIP_CONS *cons, SCIP_ROW *row, int probnumber, SCIP_Bool addcut)
 
static SCIP_RETCODE generateAndApplyBendersCuts (SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result)
 
static SCIP_DECL_BENDERSCUTFREE (benderscutFreeOpt)
 
static SCIP_DECL_BENDERSCUTEXEC (benderscutExecOpt)
 
SCIP_RETCODE SCIPincludeBenderscutOpt (SCIP *scip, SCIP_BENDERS *benders)
 

Macro Definition Documentation

◆ BENDERSCUT_NAME

#define BENDERSCUT_NAME   "optimality"

Definition at line 46 of file benderscut_opt.c.

Referenced by SCIP_DECL_BENDERSCUTFREE(), and SCIPincludeBenderscutOpt().

◆ BENDERSCUT_DESC

#define BENDERSCUT_DESC   "Standard Benders' decomposition optimality cut"

Definition at line 47 of file benderscut_opt.c.

Referenced by SCIPincludeBenderscutOpt().

◆ BENDERSCUT_PRIORITY

#define BENDERSCUT_PRIORITY   5000

Definition at line 48 of file benderscut_opt.c.

Referenced by SCIPincludeBenderscutOpt().

◆ BENDERSCUT_LPCUT

#define BENDERSCUT_LPCUT   TRUE

Definition at line 49 of file benderscut_opt.c.

Referenced by SCIPincludeBenderscutOpt().

◆ SCIP_DEFAULT_ADDCUTS

#define SCIP_DEFAULT_ADDCUTS   FALSE /** Should cuts be generated, instead of constraints */

Definition at line 51 of file benderscut_opt.c.

Referenced by SCIPincludeBenderscutOpt().

Function Documentation

◆ polishSolution()

static SCIP_RETCODE polishSolution ( SCIP subproblem,
SCIP_Bool success 
)
static

in the case of numerical troubles, the LP is resolved with solution polishing activated

Parameters
subproblemthe SCIP data structure
successTRUE is the resolving of the LP was successful

Definition at line 70 of file benderscut_opt.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetIntParam(), SCIPgetLPSolstat(), SCIPinProbing(), SCIPsetIntParam(), SCIPsolveProbingLP(), and TRUE.

Referenced by SCIP_DECL_BENDERSCUTEXEC().

◆ computeStandardOptimalityCut()

static SCIP_RETCODE computeStandardOptimalityCut ( SCIP masterprob,
SCIP subproblem,
SCIP_BENDERS benders,
SCIP_SOL sol,
SCIP_CONS cons,
SCIP_ROW row,
SCIP_Bool  addcut,
SCIP_Bool success 
)
static

computes a standard Benders' optimality cut from the dual solutions of the LP

Parameters
masterprobthe SCIP instance of the master problem
subproblemthe SCIP instance of the subproblem
bendersthe benders' decomposition structure
solprimal CIP solution
consthe constraint for the generated cut, can be NULL
rowthe row for the generated cut, can be NULL
addcutindicates whether a cut is created instead of a constraint
successwas the cut generation successful?

Definition at line 102 of file benderscut_opt.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPaddCoefLinear(), SCIPaddVarToRow(), SCIPchgLhsLinear(), SCIPchgRowLhs(), SCIPconsGetDualsol(), SCIPconsGetLhs(), SCIPconsGetRhs(), SCIPdebugMsg, SCIPgetActivityLinear(), SCIPgetBendersMasterVar(), SCIPgetConss(), SCIPgetFixedVars(), SCIPgetLhsLinear(), SCIPgetNConss(), SCIPgetNFixedVars(), SCIPgetNVars(), SCIPgetRhsLinear(), SCIPgetRowSolActivity(), SCIPgetVarRedcost(), SCIPgetVars(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIProwGetLhs(), SCIProwGetRhs(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetSol(), SCIPvarGetUbLocal(), SCIPvarGetUnchangedObj(), and TRUE.

Referenced by generateAndApplyBendersCuts().

◆ addAuxiliaryVariableToCut()

static SCIP_RETCODE addAuxiliaryVariableToCut ( SCIP masterprob,
SCIP_BENDERS benders,
SCIP_CONS cons,
SCIP_ROW row,
int  probnumber,
SCIP_Bool  addcut 
)
static

Adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the auxiliary variable is first created and added to the master problem.

Parameters
masterprobthe SCIP instance of the master problem
bendersthe benders' decomposition structure
consthe constraint for the generated cut, can be NULL
rowthe row for the generated cut, can be NULL
probnumberthe number of the pricing problem
addcutindicates whether a cut is created instead of a constraint

Definition at line 329 of file benderscut_opt.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPaddCoefLinear(), SCIPaddVarToRow(), and SCIPbendersGetAuxiliaryVar().

Referenced by generateAndApplyBendersCuts().

◆ generateAndApplyBendersCuts()

static SCIP_RETCODE generateAndApplyBendersCuts ( SCIP masterprob,
SCIP subproblem,
SCIP_BENDERS benders,
SCIP_BENDERSCUT benderscut,
SCIP_SOL sol,
int  probnumber,
SCIP_BENDERSENFOTYPE  type,
SCIP_RESULT result 
)
static

generates and applies Benders' cuts

Parameters
masterprobthe SCIP instance of the master problem
subproblemthe SCIP instance of the pricing problem
bendersthe benders' decomposition
benderscutthe benders' decomposition cut method
solprimal CIP solution
probnumberthe number of the pricing problem
typethe enforcement type calling this function
resultthe result from solving the subproblems

Definition at line 363 of file benderscut_opt.c.

References addAuxiliaryVariableToCut(), computeStandardOptimalityCut(), FALSE, NULL, SCIP_BENDERSENFOTYPE_CHECK, SCIP_BENDERSENFOTYPE_LP, SCIP_BENDERSENFOTYPE_PSEUDO, SCIP_BENDERSENFOTYPE_RELAX, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTFIND, SCIP_FEASIBLE, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_SEPARATED, SCIP_STAGE_INITSOLVE, SCIP_STATUS_OPTIMAL, SCIPaddCons(), SCIPaddPoolCut(), SCIPaddRow(), SCIPbenderscutGetData(), SCIPbenderscutGetNFound(), SCIPcheckBendersSubproblemOptimality(), SCIPcreateConsBasicLinear(), SCIPcreateEmptyRowCons(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPfindConshdlr(), SCIPgetLPSolstat(), SCIPgetStage(), SCIPgetStatus(), SCIPinfinity(), SCIPreleaseCons(), SCIPreleaseRow(), SCIPsetConsDynamic(), SCIPsetConsRemovable(), SCIPsnprintf(), SCIPstoreBenderscutCons(), SCIPstoreBenderscutCut(), and TRUE.

Referenced by SCIP_DECL_BENDERSCUTEXEC().

◆ SCIP_DECL_BENDERSCUTFREE()

static SCIP_DECL_BENDERSCUTFREE ( benderscutFreeOpt  )
static

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

Definition at line 505 of file benderscut_opt.c.

References BENDERSCUT_NAME, NULL, SCIP_OKAY, SCIPbenderscutGetData(), SCIPbenderscutGetName(), SCIPbenderscutSetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_BENDERSCUTEXEC()