Scippy

SCIP

Solving Constraint Integer Programs

probdata_cyc.c File Reference

Detailed Description

problem data for cycle clustering problem

Author
Leon Eifler

This file implements the problem data for the cycle clustering problem.

The problem data contains original transition matrix, the scaling parameter that appears in the objective function, and all variables that appear in the problem.

Definition in file probdata_cyc.c.

#include "probdata_cyc.h"
#include "scip/cons_nonlinear.h"
#include "scip/cons_linear.h"
#include "scip/cons_logicor.h"
#include "scip/var.h"
#include <assert.h>

Go to the source code of this file.

Functions

SCIP_Bool isPartition (SCIP *scip, SCIP_Real **solclustering, int nbins, int ncluster)
 
SCIP_RETCODE assignVars (SCIP *scip, SCIP_SOL *sol, SCIP_Real **clustering, int nbins, int ncluster)
 
int phi (int k, int ncluster)
 
int phiinv (int k, int ncluster)
 
static SCIP_RETCODE createVariables (SCIP *scip, SCIP_PROBDATA *probdata)
 
static SCIP_RETCODE createProbSimplifiedTest (SCIP *scip, SCIP_PROBDATA *probdata)
 
static SCIP_RETCODE createProbSimplified (SCIP *scip, SCIP_PROBDATA *probdata)
 
static SCIP_RETCODE createProbQP (SCIP *scip, SCIP_PROBDATA *probdata)
 
static SCIP_RETCODE createProbOnlyEdge (SCIP *scip, SCIP_PROBDATA *probdata)
 
static SCIP_DECL_PROBTRANS (probtransCyc)
 
static SCIP_DECL_PROBDELORIG (probdelorigCyc)
 
static SCIP_DECL_PROBDELTRANS (probdeltransCyc)
 
static SCIP_DECL_PROBCOPY (probcopyCyc)
 
SCIP_RETCODE SCIPcreateProbCyc (SCIP *scip, const char *name, int nbins, int ncluster, SCIP_Real **cmatrix)
 
SCIP_Real ** SCIPcycGetCmatrix (SCIP *scip)
 
int SCIPcycGetNBins (SCIP *scip)
 
int SCIPcycGetNCluster (SCIP *scip)
 
SCIP_VAR *** SCIPcycGetBinvars (SCIP *scip)
 
SCIP_Real SCIPcycGetScale (SCIP *scip)
 
SCIP_VAR **** SCIPcycGetEdgevars (SCIP *scip)
 
SCIP_VARgetEdgevar (SCIP_VAR ****edgevars, int state1, int state2, int direction)
 
SCIP_Bool edgesExist (SCIP_VAR ****edgevars, int *states, int nstates)
 
SCIP_DIGRAPHSCIPcycGetEdgeGraph (SCIP *scip)
 
SCIP_RETCODE SCIPcycPrintSolutionValues (SCIP *scip, SCIP_SOL *sol)
 

Function Documentation

◆ isPartition()

SCIP_Bool isPartition ( SCIP scip,
SCIP_Real **  solclustering,
int  nbins,
int  ncluster 
)

Check if the clustering has exactly one state in every cluster.

Parameters
scipSCIP data structure
solclusteringmatrix with the clustering
nbinsthe number of bins
nclusterthe number of clusters

Definition at line 57 of file probdata_cyc.c.

References FALSE, SCIP_Real, SCIPisEQ(), SCIPisIntegral(), SCIPisZero(), and TRUE.

Referenced by createSwitchSolution(), runCyckerlin(), SCIP_DECL_HEUREXEC(), and switchNext().

◆ assignVars()

SCIP_RETCODE assignVars ( SCIP scip,
SCIP_SOL sol,
SCIP_Real **  clustering,
int  nbins,
int  ncluster 
)

Assign the variables in scip according to the found clustering.

Parameters
scipSCIP data structure
solthe SCIP solution
clusteringthe matrix with the clusterassignment
nbinsthe number of bins
nclusterthe number of cluster

Definition at line 88 of file probdata_cyc.c.

References NULL, phi(), SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_MULTAGGR, SCIPcycGetBinvars(), SCIPcycGetEdgevars(), SCIPisEQ(), SCIPisGE(), SCIPisIntegral(), SCIPisLE(), SCIPsetSolVal(), SCIPvarGetLbGlobal(), SCIPvarGetStatus(), SCIPvarGetTransVar(), SCIPvarGetUbGlobal(), and SCIPvarIsTransformed().

Referenced by createSwitchSolution(), SCIP_DECL_HEUREXEC(), and SCIPcycAddIncompleteSol().

◆ phi()

int phi ( int  k,
int  ncluster 
)

function that returns the successive cluster along the cycle

Parameters
kthe cluster
nclusterthe number of clusters

Definition at line 181 of file probdata_cyc.c.

Referenced by assignVars(), createProbQP(), createProbSimplified(), and SCIPcycPrintSolutionValues().

◆ phiinv()

int phiinv ( int  k,
int  ncluster 
)

function that returns the predecessor-cluster along the cycle

Parameters
kthe cluster
nclusterthe number of clusters

Definition at line 193 of file probdata_cyc.c.

Referenced by createProbSimplified(), and getTempObj().

◆ createVariables()

static SCIP_RETCODE createVariables ( SCIP scip,
SCIP_PROBDATA probdata 
)
static

creates all the variables for the problem. The constraints are added later, depending on the model that is used

Parameters
scipSCIP data Structure
probdatathe problem data

Definition at line 209 of file probdata_cyc.c.

References NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OBJSENSE_MAXIMIZE, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPaddVar(), SCIPallocBlockMemoryArray, SCIPallocClearBlockMemoryArray, SCIPcreateVarBasic(), SCIPdigraphAddArc(), SCIPisZero(), SCIPsetObjsense(), and SCIPsnprintf().

Referenced by SCIPcreateProbCyc().

◆ createProbSimplifiedTest()

static SCIP_RETCODE createProbSimplifiedTest ( SCIP scip,
SCIP_PROBDATA probdata 
)
static

create the problem without variable amount of clusters, use simpler non-facet-defining inequalities

Parameters
scipSCIP Data Structure
probdatathe problem data

Definition at line 278 of file probdata_cyc.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPaddCoefLogicor(), SCIPaddCoefSetppc(), SCIPaddCons(), SCIPchgVarObj(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicLogicor(), SCIPcreateConsLinear(), SCIPcreateConsSetpart(), SCIPgetRealParam(), SCIPinfinity(), SCIPinfoMessage(), SCIPreleaseCons(), SCIPsnprintf(), and TRUE.

Referenced by SCIPcreateProbCyc().

◆ createProbSimplified()

static SCIP_RETCODE createProbSimplified ( SCIP scip,
SCIP_PROBDATA probdata 
)
static

create the problem without variable amount of clusters, using three edge-variables for each pair of states. This is the tested default version.

Parameters
scipSCIP Data Structure
probdataThe problem data

Definition at line 420 of file probdata_cyc.c.

References FALSE, NULL, phi(), phiinv(), SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_NORMAL, SCIPaddCoefLinear(), SCIPaddCoefLogicor(), SCIPaddCoefSetppc(), SCIPaddCons(), SCIPaddOrigObjoffset(), SCIPchgVarObj(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicLogicor(), SCIPcreateConsLinear(), SCIPcreateConsSetpart(), SCIPgetRealParam(), SCIPinfinity(), SCIPisZero(), SCIPreleaseCons(), SCIPsnprintf(), SCIPverbMessage(), and TRUE.

Referenced by SCIPcreateProbCyc().

◆ createProbQP()

static SCIP_RETCODE createProbQP ( SCIP scip,
SCIP_PROBDATA probdata 
)
static

◆ createProbOnlyEdge()

static SCIP_RETCODE createProbOnlyEdge ( SCIP scip,
SCIP_PROBDATA probdata 
)
static

create the problem with variable amount of clusters. Very large number of constraints not viable for large scale problems.

Parameters
scipSCIP Data Structure
probdataThe problem data

Definition at line 820 of file probdata_cyc.c.

References FALSE, MAX, MIN, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_NORMAL, SCIPaddCoefLinear(), SCIPaddCons(), SCIPchgVarObj(), SCIPcreateConsLinear(), SCIPgetRealParam(), SCIPinfinity(), SCIPreleaseCons(), SCIPsnprintf(), SCIPverbMessage(), and TRUE.

Referenced by SCIPcreateProbCyc().

◆ SCIP_DECL_PROBTRANS()

static SCIP_DECL_PROBTRANS ( probtransCyc  )
static

◆ SCIP_DECL_PROBDELORIG()

static SCIP_DECL_PROBDELORIG ( probdelorigCyc  )
static

◆ SCIP_DECL_PROBDELTRANS()

static SCIP_DECL_PROBDELTRANS ( probdeltransCyc  )
static

scip-callback to delete the transformed problem

Definition at line 1108 of file probdata_cyc.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPdigraphFree(), SCIPdigraphFreeComponents(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPreleaseVar().

◆ SCIP_DECL_PROBCOPY()

static SCIP_DECL_PROBCOPY ( probcopyCyc  )
static

◆ SCIPcreateProbCyc()

SCIP_RETCODE SCIPcreateProbCyc ( SCIP scip,
const char *  name,
int  nbins,
int  ncluster,
SCIP_Real **  cmatrix 
)

Create the probdata for an cyc-clustering problem

add callback methods to scip

Parameters
scipSCIP data structure
nameproblem name
nbinsnumber of bins
nclusternumber of cluster
cmatrixThe transition matrix

Definition at line 1303 of file probdata_cyc.c.

References createProbOnlyEdge(), createProbQP(), createProbSimplified(), createProbSimplifiedTest(), createVariables(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_NORMAL, SCIPABORT, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcreateDigraph(), SCIPcreateProbBasic(), SCIPgetCharParam(), SCIPsetProbCopy(), SCIPsetProbData(), SCIPsetProbDelorig(), SCIPsetProbDeltrans(), SCIPsetProbTrans(), and SCIPverbMessage().

Referenced by readCyc(), and SCIPapplyRedSize().

◆ SCIPcycGetCmatrix()

SCIP_Real** SCIPcycGetCmatrix ( SCIP scip)

Getter methods for the various parts of the probdata Returns the transition matrix

Parameters
scipSCIP data structure

Definition at line 1382 of file probdata_cyc.c.

References NULL, and SCIPgetProbData().

Referenced by runCyckerlin(), SCIP_DECL_HEUREXEC(), and SCIPapplyRedSize().

◆ SCIPcycGetNBins()

int SCIPcycGetNBins ( SCIP scip)

Returns the number of states

Parameters
scipSCIP data structure

Definition at line 1398 of file probdata_cyc.c.

References NULL, and SCIPgetProbData().

Referenced by getBranchCands(), getSolutionValues(), runCyckerlin(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_SEPAEXECLP(), SCIPapplyRedSize(), SCIPcycAddIncompleteSol(), and switchNext().

◆ SCIPcycGetNCluster()

int SCIPcycGetNCluster ( SCIP scip)

◆ SCIPcycGetBinvars()

SCIP_VAR*** SCIPcycGetBinvars ( SCIP scip)

Returns the state-variable-matrix

Parameters
scipSCIP data structure

Definition at line 1430 of file probdata_cyc.c.

References NULL, and SCIPgetProbData().

Referenced by assignVars(), branchOnBin(), getBranchCands(), getSolutionValues(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_HEUREXEC(), and SCIPcycAddIncompleteSol().

◆ SCIPcycGetScale()

SCIP_Real SCIPcycGetScale ( SCIP scip)

Returns the scaling parameter

Parameters
scipSCIP data structure

Definition at line 1447 of file probdata_cyc.c.

References NULL, and SCIPgetProbData().

Referenced by assignNextBin(), createSwitchSolution(), getTempObj(), SCIP_DECL_HEUREXEC(), SCIPapplyRedSize(), and switchNext().

◆ SCIPcycGetEdgevars()

SCIP_VAR**** SCIPcycGetEdgevars ( SCIP scip)

Returns the edge variables

Parameters
scipSCIP data structure

Definition at line 1463 of file probdata_cyc.c.

References NULL, and SCIPgetProbData().

Referenced by addPathCuts(), addSubtourCuts(), addTourCuts(), assignVars(), createPartitionCut(), and SCIP_DECL_SEPAEXECLP().

◆ getEdgevar()

SCIP_VAR* getEdgevar ( SCIP_VAR ****  edgevars,
int  state1,
int  state2,
int  direction 
)

return one specific edge variable

Parameters
edgevarsedgevar data structure
state1first state
state2second state
directiondirection, 0 = incluster, 1 = forward

Definition at line 1480 of file probdata_cyc.c.

References NULL.

Referenced by addPathCuts(), addSubtourCuts(), addTourCuts(), createPartitionCut(), and SCIP_DECL_SEPAEXECLP().

◆ edgesExist()

SCIP_Bool edgesExist ( SCIP_VAR ****  edgevars,
int *  states,
int  nstates 
)

check for an array of states, if all possible edge-combinations exist

Parameters
edgevarsedgevar data structure
statesstate array
nstatessize of state array

Definition at line 1496 of file probdata_cyc.c.

References FALSE, NULL, and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ SCIPcycGetEdgeGraph()

SCIP_DIGRAPH* SCIPcycGetEdgeGraph ( SCIP scip)

Returns the edge-graph

Parameters
scipSCIP data structure

Definition at line 1528 of file probdata_cyc.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_SEPAEXECLP().

◆ SCIPcycPrintSolutionValues()

SCIP_RETCODE SCIPcycPrintSolutionValues ( SCIP scip,
SCIP_SOL sol 
)

print the model-values like coherence in the clusters and transition-probabilities between clusters that are not evident from the scip-solution

Parameters
scipSCIP data structure
solThe solution containg the values

Definition at line 1548 of file probdata_cyc.c.

References NULL, phi(), SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_NORMAL, SCIPgetProbData(), SCIPgetSolVal(), and SCIPverbMessage().