Scippy

SCIP

Solving Constraint Integer Programs

benderscut_feasalt.c File Reference

Detailed Description

Alternative feasibility cuts for Benders' decomposition.

Author
Stephen J. Maher

Definition in file benderscut_feasalt.c.

#include <assert.h>
#include <string.h>
#include "nlpi/exprinterpret.h"
#include "nlpi/pub_expr.h"
#include "nlpi/nlpi.h"
#include "scip/benderscut_feasalt.h"
#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_nlp.h"
#include "scip/pub_var.h"
#include "scip/scip_benders.h"
#include "scip/scip_cons.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_nonlinear.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_var.h"

Go to the source code of this file.

Macros

#define BENDERSCUT_NAME   "feasalt"
 
#define BENDERSCUT_DESC   "Alternative feasibility cuts for Benders' decomposition"
 
#define BENDERSCUT_PRIORITY   10001
 
#define BENDERSCUT_LPCUT   TRUE
 
#define SCIP_DEFAULT_DISPLAYFREQ   20
 
#define SLACKVAR_NAME
 

Functions

static SCIP_RETCODE freeNonlinearProblem (SCIP *scip, SCIP_BENDERSCUT *benderscut)
 
static SCIP_RETCODE solveFeasibilityNonlinearSubproblem (SCIP *scip, SCIP_BENDERSCUTDATA *benderscutdata, SCIP_Bool *success)
 
static SCIP_RETCODE createAuxiliaryNonlinearSubproblem (SCIP *masterprob, SCIP *subproblem, SCIP_BENDERSCUT *benderscut)
 
static SCIP_RETCODE updateAuxiliaryNonlinearSubproblem (SCIP *subproblem, SCIP_BENDERSCUT *benderscut)
 
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_BENDERSCUTEXIT (benderscutExitFeasalt)
 
static SCIP_DECL_BENDERSCUTFREE (benderscutFreeFeasalt)
 
static SCIP_DECL_BENDERSCUTEXEC (benderscutExecFeasalt)
 
SCIP_RETCODE SCIPincludeBenderscutFeasalt (SCIP *scip, SCIP_BENDERS *benders)
 

Macro Definition Documentation

◆ BENDERSCUT_NAME

#define BENDERSCUT_NAME   "feasalt"

Definition at line 55 of file benderscut_feasalt.c.

Referenced by SCIP_DECL_BENDERSCUTEXIT(), and SCIPincludeBenderscutFeasalt().

◆ BENDERSCUT_DESC

#define BENDERSCUT_DESC   "Alternative feasibility cuts for Benders' decomposition"

Definition at line 56 of file benderscut_feasalt.c.

Referenced by SCIPincludeBenderscutFeasalt().

◆ BENDERSCUT_PRIORITY

#define BENDERSCUT_PRIORITY   10001

Definition at line 57 of file benderscut_feasalt.c.

Referenced by SCIPincludeBenderscutFeasalt().

◆ BENDERSCUT_LPCUT

#define BENDERSCUT_LPCUT   TRUE

Definition at line 58 of file benderscut_feasalt.c.

Referenced by SCIPincludeBenderscutFeasalt().

◆ SCIP_DEFAULT_DISPLAYFREQ

#define SCIP_DEFAULT_DISPLAYFREQ   20

Definition at line 60 of file benderscut_feasalt.c.

Referenced by generateAndApplyBendersCuts().

◆ SLACKVAR_NAME

#define SLACKVAR_NAME
Value:
"##bendersslackvar" /** the name for the Benders' slack variables added to each
* constraints in the subproblems */

Definition at line 61 of file benderscut_feasalt.c.

Referenced by createAuxiliaryNonlinearSubproblem().

Function Documentation

◆ freeNonlinearProblem()

static SCIP_RETCODE freeNonlinearProblem ( SCIP scip,
SCIP_BENDERSCUT benderscut 
)
static

frees the non linear problem

Parameters
scipthe SCIP data structure
benderscutthe Benders' decomposition structure

Definition at line 88 of file benderscut_feasalt.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPbenderscutGetData(), SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPnlpiFreeProblem().

Referenced by createAuxiliaryNonlinearSubproblem(), and SCIP_DECL_BENDERSCUTEXIT().

◆ solveFeasibilityNonlinearSubproblem()

static SCIP_RETCODE solveFeasibilityNonlinearSubproblem ( SCIP scip,
SCIP_BENDERSCUTDATA benderscutdata,
SCIP_Bool success 
)
static

solves the auxiliary feasibility subproblem.

Note
: the variable fixings need to be setup before calling this function
Parameters
scipSCIP data structure
benderscutdataBenders' cut data
successreturns whether solving the feasibility problem was successful

Definition at line 130 of file benderscut_feasalt.c.

References FALSE, NULL, SCIP_CALL, SCIP_NLPPAR_TILIM, SCIP_NLPPAR_VERBLEVEL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPnlpiGetSolstat(), SCIPnlpiSetIntPar(), SCIPnlpiSetRealPar(), SCIPnlpiSolve(), and TRUE.

Referenced by generateAndApplyBendersCuts().

◆ createAuxiliaryNonlinearSubproblem()

static SCIP_RETCODE createAuxiliaryNonlinearSubproblem ( SCIP masterprob,
SCIP subproblem,
SCIP_BENDERSCUT benderscut 
)
static

builds the non-linear problem to resolve to generate a cut for the infeasible subproblem

Parameters
masterprobthe SCIP instance of the master problem
subproblemthe SCIP instance of the pricing problem
benderscutthe benders' decomposition cut method

Definition at line 177 of file benderscut_feasalt.c.

References FALSE, freeNonlinearProblem(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPbenderscutGetData(), SCIPblkmem(), SCIPcreateNlpiProb(), SCIPduplicateBlockMemoryArray, SCIPfreeBufferArray, SCIPgetNlpis(), SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapGetImageInt(), SCIPinfinity(), SCIPnlpiChgVarBounds(), SCIPnlpiCreateProblem(), SCIPnlpiSetObjective(), SCIPvarGetName(), and SLACKVAR_NAME.

Referenced by generateAndApplyBendersCuts().

◆ updateAuxiliaryNonlinearSubproblem()

static SCIP_RETCODE updateAuxiliaryNonlinearSubproblem ( SCIP subproblem,
SCIP_BENDERSCUT benderscut 
)
static

updates the non-linear problem that is resolved to generate a cut for the infeasible subproblem

Parameters
subproblemthe SCIP instance of the pricing problem
benderscutthe benders' decomposition cut method

Definition at line 253 of file benderscut_feasalt.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPbenderscutGetData(), SCIPinfinity(), SCIPnlpiChgVarBounds(), and SCIPupdateNlpiProb().

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 283 of file benderscut_feasalt.c.

References createAuxiliaryNonlinearSubproblem(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_DEFAULT_DISPLAYFREQ, SCIP_DIDNOTFIND, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIP_VERBLEVEL_NORMAL, SCIPbenderscutGetData(), SCIPbenderscutGetNFound(), SCIPdebugMsg, SCIPgenerateAndApplyBendersOptCut(), SCIPgetDualbound(), SCIPgetStage(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisInfinity(), SCIPisZero(), SCIPnlpiGetSolution(), SCIPprintDisplayLine(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarGetObj(), SCIPverbMessage(), solveFeasibilityNonlinearSubproblem(), TRUE, and updateAuxiliaryNonlinearSubproblem().

Referenced by SCIP_DECL_BENDERSCUTEXEC().

◆ SCIP_DECL_BENDERSCUTEXIT()

static SCIP_DECL_BENDERSCUTEXIT ( benderscutExitFeasalt  )
static

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

Definition at line 395 of file benderscut_feasalt.c.

References BENDERSCUT_NAME, freeNonlinearProblem(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPbenderscutGetName().

◆ SCIP_DECL_BENDERSCUTFREE()

static SCIP_DECL_BENDERSCUTFREE ( benderscutFreeFeasalt  )
static

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

Definition at line 408 of file benderscut_feasalt.c.

References NULL, SCIP_OKAY, SCIPbenderscutGetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_BENDERSCUTEXEC()