Scippy

SCIP

Solving Constraint Integer Programs

relax_stpdp.c File Reference

Detailed Description

Steiner tree relaxator.

Author
Daniel Rehfeldt

Definition in file relax_stpdp.c.

#include <assert.h>
#include <string.h>
#include "relax_stpdp.h"
#include "probdata_stp.h"
#include "solstp.h"
#include "dpterms.h"
#include "dpborder.h"
#include "substpsolver.h"

Go to the source code of this file.

Macros

#define RELAX_NAME   "stpdp"
 
#define RELAX_DESC   "DP relaxator for STP"
 
#define RELAX_PRIORITY   100000000
 
#define RELAX_FREQ   1
 

Enumerations

enum  DP_TYPE {
  dp_border,
  dp_terms
}
 

Functions

static SCIP_RETCODE solveWithDpBorder (SCIP *scip, GRAPH *graph, DPBORDER *dpborder, SCIP_Real *obj, SCIP_Bool *wasSolved)
 
static SCIP_RETCODE solveWithDpTerms (SCIP *scip, GRAPH *graph, SCIP_Real *obj, SCIP_Bool *wasSolved)
 
static SCIP_DECL_RELAXFREE (relaxFreeStpdp)
 
static SCIP_DECL_RELAXINITSOL (relaxInitsolStpdp)
 
static SCIP_DECL_RELAXEXITSOL (relaxExitsolStpdp)
 
static SCIP_DECL_RELAXEXEC (relaxExecStpdp)
 
SCIP_Bool SCIPStpDpRelaxIsPromising (SCIP *scip, GRAPH *graph)
 
SCIP_RETCODE SCIPStpDpRelaxActivate (SCIP *scip)
 
SCIP_Bool SCIPStpDpRelaxIsActive (SCIP *scip)
 
SCIP_RETCODE SCIPincludeRelaxStpdp (SCIP *scip)
 

Macro Definition Documentation

◆ RELAX_NAME

#define RELAX_NAME   "stpdp"

Definition at line 34 of file relax_stpdp.c.

Referenced by SCIPincludeRelaxStpdp().

◆ RELAX_DESC

#define RELAX_DESC   "DP relaxator for STP"

Definition at line 35 of file relax_stpdp.c.

Referenced by SCIPincludeRelaxStpdp().

◆ RELAX_PRIORITY

#define RELAX_PRIORITY   100000000

Definition at line 36 of file relax_stpdp.c.

Referenced by SCIPincludeRelaxStpdp().

◆ RELAX_FREQ

#define RELAX_FREQ   1

Definition at line 37 of file relax_stpdp.c.

Referenced by SCIPincludeRelaxStpdp().

Enumeration Type Documentation

◆ DP_TYPE

enum DP_TYPE
Enumerator
dp_border 
dp_terms 

Definition at line 39 of file relax_stpdp.c.

Function Documentation

◆ solveWithDpBorder()

static SCIP_RETCODE solveWithDpBorder ( SCIP scip,
GRAPH graph,
DPBORDER dpborder,
SCIP_Real obj,
SCIP_Bool wasSolved 
)
static

solves problem with border-FPT DP

Parameters
scipSCIP data structure
graphthe graph
dpborderDP border algorithm data structure
objpointer to the objective value (OUT)
wasSolvedpointer to mark whether problem was solved (OUT)

Definition at line 62 of file relax_stpdp.c.

References dpborder_solve(), GRAPH::edges, graph_printInfo(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPfreeMemoryArray, solstp_addSolToProb(), and solstp_getObj().

Referenced by SCIP_DECL_RELAXEXEC().

◆ solveWithDpTerms()

static SCIP_RETCODE solveWithDpTerms ( SCIP scip,
GRAPH graph,
SCIP_Real obj,
SCIP_Bool wasSolved 
)
static

solves problem with terminals-FPT DP

Parameters
scipSCIP data structure
graphthe graph
objpointer to the objective value (OUT)
wasSolvedpointer to mark whether problem was solved (OUT)

Definition at line 103 of file relax_stpdp.c.

References dpterms_solve(), GRAPH::edges, EQ, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPfreeMemoryArray, solstp_addSolToProb(), solstp_getObj(), and substpsolver_getObjFromGraph().

Referenced by SCIP_DECL_RELAXEXEC().

◆ SCIP_DECL_RELAXFREE()

static SCIP_DECL_RELAXFREE ( relaxFreeStpdp  )
static

destructor of relaxator to free user data (called when SCIP is exiting)

Definition at line 155 of file relax_stpdp.c.

References dpborder_free(), NULL, SCIP_OKAY, SCIPfreeMemory, SCIPrelaxGetData(), and SCIPrelaxSetData().

◆ SCIP_DECL_RELAXINITSOL()

static SCIP_DECL_RELAXINITSOL ( relaxInitsolStpdp  )
static

solving process initialization method of relaxator (called when branch and bound process is about to begin)

Definition at line 172 of file relax_stpdp.c.

References SCIP_OKAY.

◆ SCIP_DECL_RELAXEXITSOL()

static SCIP_DECL_RELAXEXITSOL ( relaxExitsolStpdp  )
static

solving process deinitialization method of relaxator (called before branch and bound process data is freed)

Definition at line 185 of file relax_stpdp.c.

References SCIP_OKAY.

◆ SCIP_DECL_RELAXEXEC()

static SCIP_DECL_RELAXEXEC ( relaxExecStpdp  )
static

◆ SCIPStpDpRelaxIsPromising()

SCIP_Bool SCIPStpDpRelaxIsPromising ( SCIP scip,
GRAPH graph 
)

is using the relaxator promising?

Parameters
scipSCIP data structure
graphgraph

Definition at line 239 of file relax_stpdp.c.

References dp_border, dp_terms, dpborder_init(), dpborder_probePotential(), dpterms_isPromisingPartly(), FALSE, SCIP_Bool, SCIP_CALL, SCIPfindRelax(), SCIPrelaxGetData(), and TRUE.

Referenced by SCIPprobdataCreateFromGraph().

◆ SCIPStpDpRelaxActivate()

SCIP_RETCODE SCIPStpDpRelaxActivate ( SCIP scip)

activates

Parameters
scipSCIP data structure

Definition at line 272 of file relax_stpdp.c.

References SCIP_CALL, SCIP_OKAY, SCIPfindRelax(), SCIPrelaxGetData(), SCIPsetIntParam(), and TRUE.

Referenced by SCIPprobdataCreateFromGraph().

◆ SCIPStpDpRelaxIsActive()

SCIP_Bool SCIPStpDpRelaxIsActive ( SCIP scip)

is active?

Parameters
scipSCIP data structure

Definition at line 293 of file relax_stpdp.c.

References SCIPfindRelax(), and SCIPrelaxGetData().

Referenced by SCIP_DECL_RELAXEXEC().

◆ SCIPincludeRelaxStpdp()

SCIP_RETCODE SCIPincludeRelaxStpdp ( SCIP scip)

creates the relaxator and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 307 of file relax_stpdp.c.

References dp_terms, FALSE, NULL, RELAX_DESC, RELAX_FREQ, RELAX_NAME, RELAX_PRIORITY, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPincludeRelaxBasic(), SCIPsetRelaxExitsol(), SCIPsetRelaxFree(), and SCIPsetRelaxInitsol().

Referenced by runShell(), and subscipSetupCallbacks().