benderscut_int.c File Reference

Detailed Description

Generates a Laporte and Louveaux Benders' decomposition integer cut.

Author

Stephen J. Maher

Definition in file benderscut_int.c.

#include "scip/benderscut_int.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_paramset.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_sol.h"
#include <string.h>

Go to the source code of this file.

Macros
#define	BENDERSCUT_NAME   "integer"
#define	BENDERSCUT_DESC   "Laporte and Louveaux Benders' decomposition integer cut"
#define	BENDERSCUT_PRIORITY   0
#define	BENDERSCUT_LPCUT   FALSE
#define	SCIP_DEFAULT_ADDCUTS   FALSE /** Should cuts be generated, instead of constraints */
#define	SCIP_DEFAULT_CUTCONSTANT   -10000.0

Functions
static	SCIP_DECL_PARAMCHGD (paramChgdBenderscutintConstant)
static SCIP_RETCODE	createBenderscutData (SCIP *scip, SCIP_BENDERSCUTDATA *benderscutdata)
static void	updateSubproblemCutConstant (SCIP *masterprob, SCIP_BENDERS *benders, SCIP_BENDERSCUTDATA *benderscutdata, int probnumber)
static SCIP_RETCODE	computeStandardIntegerOptCut (SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_CONS *cons, SCIP_ROW *row, SCIP_Real cutconstant, int probnumber, 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	generateAndApplyBendersIntegerCuts (SCIP *masterprob, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result, SCIP_Bool initcons)
static	SCIP_DECL_BENDERSCUTFREE (benderscutFreeInt)
static	SCIP_DECL_BENDERSCUTEXIT (benderscutExitInt)
static	SCIP_DECL_BENDERSCUTEXEC (benderscutExecInt)
SCIP_RETCODE	SCIPincludeBenderscutInt (SCIP *scip, SCIP_BENDERS *benders)

Macro Definition Documentation

BENDERSCUT_NAME

#define BENDERSCUT_NAME   "integer"

Definition at line 55 of file benderscut_int.c.

BENDERSCUT_DESC

#define BENDERSCUT_DESC   "Laporte and Louveaux Benders' decomposition integer cut"

Definition at line 56 of file benderscut_int.c.

BENDERSCUT_PRIORITY

#define BENDERSCUT_PRIORITY   0

Definition at line 57 of file benderscut_int.c.

BENDERSCUT_LPCUT

#define BENDERSCUT_LPCUT   FALSE

Definition at line 58 of file benderscut_int.c.

SCIP_DEFAULT_ADDCUTS

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

Definition at line 60 of file benderscut_int.c.

SCIP_DEFAULT_CUTCONSTANT

#define SCIP_DEFAULT_CUTCONSTANT   -10000.0

Definition at line 61 of file benderscut_int.c.

Function Documentation

SCIP_DECL_PARAMCHGD()

static SCIP_DECL_PARAMCHGD ( paramChgdBenderscutintConstant  )

static

method to call, when the priority of a Benders' decomposition was changed

Definition at line 82 of file benderscut_int.c.

References NULL, SCIP_OKAY, and SCIPparamGetData().

createBenderscutData()

static SCIP_RETCODE createBenderscutData ( SCIP *  scip, SCIP_BENDERSCUTDATA *  benderscutdata  )

static

creates the Benders' decomposition cut data

Parameters

scip	the SCIP data structure
benderscutdata	the Benders' cut data

Definition at line 99 of file benderscut_int.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPbendersGetNSubproblems(), SCIPbendersGetSubproblemMasterVarsData(), and TRUE.

Referenced by SCIP_DECL_BENDERSCUTEXEC().

updateSubproblemCutConstant()

static void updateSubproblemCutConstant ( SCIP *  masterprob, SCIP_BENDERS *  benders, SCIP_BENDERSCUTDATA *  benderscutdata, int  probnumber  )

static

updates the cut constant for the given subproblem based upon the global bounds of the associated auxiliary variable

Parameters

masterprob	the SCIP instance of the master problem
benders	the benders' decomposition structure
benderscutdata	the Benders' decomposition cut data
probnumber	the index for the subproblem

Definition at line 143 of file benderscut_int.c.

References NULL, SCIPbendersGetAuxiliaryVar(), SCIPbendersGetSubproblemLowerbound(), SCIPisGT(), SCIPvarGetLbGlobal(), and TRUE.

Referenced by generateAndApplyBendersIntegerCuts().

computeStandardIntegerOptCut()

static SCIP_RETCODE computeStandardIntegerOptCut ( SCIP *  masterprob, SCIP_BENDERS *  benders, SCIP_SOL *  sol, SCIP_CONS *  cons, SCIP_ROW *  row, SCIP_Real  cutconstant, int  probnumber, SCIP_Bool  addcut, SCIP_Bool *  success  )

static

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

Parameters

masterprob	the SCIP instance of the master problem
benders	the benders' decomposition structure
sol	primal CIP solution
cons	the constraint for the generated cut, can be NULL
row	the row for the generated cut, can be NULL
cutconstant	the constant value in the integer optimality cut
probnumber	the number of the pricing problem
addcut	indicates whether a cut is created instead of a constraint
success	was the cut generation successful?

Definition at line 175 of file benderscut_int.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPaddVarToRow(), SCIPbendersGetSubproblemObjval(), SCIPbendersSubproblem(), SCIPchgLhsLinear(), SCIPchgRowLhs(), SCIPdebug, SCIPdebugMsg, SCIPgetActivityLinear(), SCIPgetBendersSubproblemVar(), SCIPgetBestSol(), SCIPgetLhsLinear(), SCIPgetNVars(), SCIPgetObjsense(), SCIPgetRowSolActivity(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetVars(), SCIPisFeasEQ(), SCIPisInfinity(), SCIProwGetLhs(), and TRUE.

Referenced by generateAndApplyBendersIntegerCuts().

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

masterprob	the SCIP instance of the master problem
benders	the benders' decomposition structure
cons	the constraint for the generated cut, can be NULL
row	the row for the generated cut, can be NULL
probnumber	the number of the pricing problem
addcut	indicates whether a cut is created instead of a constraint

Definition at line 300 of file benderscut_int.c.

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

Referenced by generateAndApplyBendersIntegerCuts().

generateAndApplyBendersIntegerCuts()

static SCIP_RETCODE generateAndApplyBendersIntegerCuts ( SCIP *  masterprob, SCIP_BENDERS *  benders, SCIP_BENDERSCUT *  benderscut, SCIP_SOL *  sol, int  probnumber, SCIP_BENDERSENFOTYPE  type, SCIP_RESULT *  result, SCIP_Bool  initcons  )

static

generates and applies Benders' cuts

Parameters

masterprob	the SCIP instance of the master problem
benders	the benders' decomposition
benderscut	the benders' decomposition cut method
sol	primal CIP solution
probnumber	the number of the pricing problem
type	the enforcement type calling this function
result	the result from solving the subproblems
initcons	is this function called to generate the initial constraint

Definition at line 334 of file benderscut_int.c.

References addAuxiliaryVariableToCut(), BENDERSCUT_NAME, computeStandardIntegerOptCut(), FALSE, generateAndApplyBendersIntegerCuts(), NULL, SCIP_BENDERSENFOTYPE_CHECK, SCIP_BENDERSENFOTYPE_LP, SCIP_BENDERSENFOTYPE_PSEUDO, SCIP_BENDERSENFOTYPE_RELAX, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTFIND, SCIP_FEASIBLE, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_STAGE_INITSOLVE, SCIPaddCons(), SCIPaddPoolCut(), SCIPaddRow(), SCIPbenderscutGetData(), SCIPbenderscutGetNFound(), SCIPbendersGetAuxiliaryVar(), SCIPcheckBendersSubproblemOptimality(), SCIPchgLhsLinear(), SCIPchgRowLhs(), SCIPcreateConsBasicLinear(), SCIPcreateEmptyRowConshdlr(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPfindConshdlr(), SCIPgetLhsLinear(), SCIPgetObjsense(), SCIPgetSolOrigObj(), SCIPgetStage(), SCIPinfinity(), SCIPinfoMessage(), SCIPisInfinity(), SCIPprintRow(), SCIPreleaseCons(), SCIPreleaseRow(), SCIProwGetLhs(), SCIPsetConsDynamic(), SCIPsetConsRemovable(), SCIPsnprintf(), SCIPvarGetLbGlobal(), TRUE, and updateSubproblemCutConstant().

Referenced by generateAndApplyBendersIntegerCuts(), and SCIP_DECL_BENDERSCUTEXEC().

SCIP_DECL_BENDERSCUTFREE()

static SCIP_DECL_BENDERSCUTFREE ( benderscutFreeInt  )

static

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

Definition at line 525 of file benderscut_int.c.

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

SCIP_DECL_BENDERSCUTEXIT()

static SCIP_DECL_BENDERSCUTEXIT ( benderscutExitInt  )

static

deinitialization method of Benders' decomposition cuts (called before transformed problem is freed)

Definition at line 546 of file benderscut_int.c.

References BENDERSCUT_NAME, NULL, SCIP_OKAY, SCIPbenderscutGetData(), SCIPbenderscutGetName(), and SCIPfreeBlockMemoryArray.

SCIP_DECL_BENDERSCUTEXEC()

static SCIP_DECL_BENDERSCUTEXEC ( benderscutExecInt  )

static

execution method of Benders' decomposition cuts

Definition at line 568 of file benderscut_int.c.

References BENDERSCUT_NAME, createBenderscutData(), FALSE, generateAndApplyBendersIntegerCuts(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_STATUS_OPTIMAL, SCIPbenderscutGetData(), SCIPbenderscutSetEnabled(), SCIPbendersSubproblem(), SCIPdebugMsg, SCIPgetStatus(), and SCIPinfoMessage().