Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

cloud branching rule

Author
Timo Berthold
Domenico Salvagnin

Branching rule based on muliple optimal solutions to the current LP relaxation. See
Cloud Branching
Timo Berthold and Domenico Salvagnin
Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2013, LNCS 7874
Preliminary version available as ZIB-Report 13-01.

Definition in file branch_cloud.c.

#include "blockmemshell/memory.h"
#include "scip/branch_allfullstrong.h"
#include "scip/branch_cloud.h"
#include "scip/branch_fullstrong.h"
#include "scip/pub_branch.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.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 "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.h>

Go to the source code of this file.

Macros

#define BRANCHRULE_NAME   "cloud"
 
#define BRANCHRULE_DESC   "branching rule that considers several alternative LP optima"
 
#define BRANCHRULE_PRIORITY   0
 
#define BRANCHRULE_MAXDEPTH   -1
 
#define BRANCHRULE_MAXBOUNDDIST   1.0
 
#define DEFAULT_USECLOUD   TRUE
 
#define DEFAULT_USEUNION   FALSE
 
#define DEFAULT_MAXPOINTS   -1
 
#define DEFAULT_MINSUCCESSRATE   0.0
 
#define DEFAULT_MINSUCCESSUNION   0.0
 
#define DEFAULT_MAXDEPTHUNION   65000
 
#define DEFAULT_ONLYF2   FALSE
 

Functions

static SCIP_DECL_BRANCHFREE (branchFreeCloud)
 
static SCIP_DECL_BRANCHINIT (branchInitCloud)
 
static SCIP_DECL_BRANCHEXECLP (branchExeclpCloud)
 
SCIP_RETCODE SCIPincludeBranchruleCloud (SCIP *scip)
 

Macro Definition Documentation

◆ BRANCHRULE_NAME

#define BRANCHRULE_NAME   "cloud"

Definition at line 65 of file branch_cloud.c.

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC   "branching rule that considers several alternative LP optima"

Definition at line 66 of file branch_cloud.c.

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY   0

Definition at line 67 of file branch_cloud.c.

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 68 of file branch_cloud.c.

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 69 of file branch_cloud.c.

◆ DEFAULT_USECLOUD

#define DEFAULT_USECLOUD   TRUE

should a cloud of points be used?

Definition at line 71 of file branch_cloud.c.

◆ DEFAULT_USEUNION

#define DEFAULT_USEUNION   FALSE

should the union of candidates be used?

Definition at line 72 of file branch_cloud.c.

◆ DEFAULT_MAXPOINTS

#define DEFAULT_MAXPOINTS   -1

maximum number of points for the cloud (-1 means no limit)

Definition at line 73 of file branch_cloud.c.

◆ DEFAULT_MINSUCCESSRATE

#define DEFAULT_MINSUCCESSRATE   0.0

minimum success rate for the cloud

Definition at line 74 of file branch_cloud.c.

◆ DEFAULT_MINSUCCESSUNION

#define DEFAULT_MINSUCCESSUNION   0.0

minimum success rate for the union

Definition at line 75 of file branch_cloud.c.

◆ DEFAULT_MAXDEPTHUNION

#define DEFAULT_MAXDEPTHUNION   65000

maximum depth for the union

Definition at line 76 of file branch_cloud.c.

◆ DEFAULT_ONLYF2

#define DEFAULT_ONLYF2   FALSE

should only F2 be used?

Definition at line 77 of file branch_cloud.c.

Function Documentation

◆ SCIP_DECL_BRANCHFREE()

static SCIP_DECL_BRANCHFREE ( branchFreeCloud  )
static

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

Definition at line 112 of file branch_cloud.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbranchruleGetData(), SCIPbranchruleSetData(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPfreeClock(), SCIPgetClockTime(), SCIPstatistic, and SCIPstatisticMessage.

◆ SCIP_DECL_BRANCHINIT()

static SCIP_DECL_BRANCHINIT ( branchInitCloud  )
static

initialization method of branching rule (called after problem was transformed)

Definition at line 154 of file branch_cloud.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetData(), and SCIPresetClock().

◆ SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpCloud  )
static

branching execution method for fractional LP solutions

Definition at line 178 of file branch_cloud.c.

References BMSclearMemoryArray, BMScopyMemoryArray, BRANCHRULE_NAME, FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_VARTYPE_INTEGER, SCIPallColsInLP(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPbranchVar(), SCIPceil(), SCIPchgRowLhsDive(), SCIPchgRowRhsDive(), SCIPchgVarLbDive(), SCIPchgVarObjDive(), SCIPchgVarUbDive(), SCIPcreateSol(), SCIPdebugMsg, SCIPendDive(), SCIPfloor(), SCIPfrac(), SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPBranchCands(), SCIPgetLPRows(), SCIPgetLPSolstat(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNLPBranchCands(), SCIPgetNLPRows(), SCIPgetRowActivity(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetVarRedcost(), SCIPgetVarsData(), SCIPinfinity(), SCIPisExactSolve(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPisFeasZero(), SCIPisIntegral(), SCIPisLPSolBasic(), SCIPisLT(), SCIPisZero(), SCIPlinkLPSol(), SCIPnodeGetLowerbound(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetRhs(), SCIPselectVarPseudoStrongBranching(), SCIPselectVarStrongBranching(), SCIPsolveDiveLP(), SCIPstartClock(), SCIPstartDive(), SCIPstopClock(), SCIPtrySolFree(), SCIPupdateNodeLowerbound(), SCIPvarGetName(), SCIPvarGetSol(), SCIPvarGetType(), SCIPwarningMessage(), and TRUE.