Movatterモバイル変換

mwcsr

A package for solving maximum weight connected subgraph (MWCS)problem and its variants.

Supported MWCS variants are:

• classic (simple) MWCS, where only vertices are weighted;
• budget MWCS, where vertices are parametrized by costs and overallbudget is limited;
• generalized MWCS (GMWCS), where both vertices and edges areweighted;
• signal generalized MWCS (SGMWCS), where both vertices and edges aremarked with weighted “signals”, and a weight of a subgraph is calculatedas a sum of weights of its unique signals.

Currently, four solvers are supported:

• heuristic relax-and-cut solverrmwcs_solver for MWCSand Budget MWCS;
• heuristic relax-and-cut solverrnc_solver forMWCS/GMWCS/SGMWCS;
• heuristic simulated annealing solverannealing_solverfor MWCS/GMWCS/SGMWCS;
• exact (if CPLEX library is available) or heuristic (without CPLEX)solvervirgo_solver for MWCS/GMWCS/SGMWCS.

Installation

The package can be installed from GitHub usingdevtools:

library(devtools)install_github("ctlab/mwcsr")

Quick start

Loadmwcsr, as well asigraph package,which contains functions for graph manipulations.

library(mwcsr)library(igraph)

Let’s load an example instance of MWCS problem. The instance is asimpleigraph object withweight vertexattribute.

data("mwcs_example")print(mwcs_example)

## IGRAPH f86c56f UN-- 194 209 -- ## + attr: name (v/c), label (v/c), weight (v/n), label (e/c)## + edges from f86c56f (vertex names):##  [1] C00022_2--C00024_0  C00022_0--C00024_1  C00025_0--C00026_0 ##  [4] C00025_1--C00026_1  C00025_2--C00026_2  C00025_4--C00026_4 ##  [7] C00025_7--C00026_7  C00024_1--C00033_0  C00024_0--C00033_1 ## [10] C00022_0--C00041_0  C00022_1--C00041_1  C00022_2--C00041_2 ## [13] C00036_0--C00049_0  C00036_1--C00049_1  C00036_2--C00049_2 ## [16] C00036_4--C00049_4  C00037_1--C00065_0  C00037_0--C00065_1 ## [19] C00022_0--C00074_5  C00022_1--C00074_6  C00022_2--C00074_7 ## [22] C00024_0--C00083_0  C00024_1--C00083_1  C00026_1--C00091_0 ## + ... omitted several edges

summary(V(mwcs_example)$weight)

##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. ## -0.7379 -0.7379  1.9294  5.9667  7.2931 38.1546

Now let us initialize a heuristic relax-and-cut MWCS solver(Alvarez-Miranda and Sinnl, 2017):

rcsolver<-rmwcs_solver()

Now we can use this solver to solve the example instance:

m<-solve_mwcsp(rcsolver, mwcs_example)print(m$graph)

## IGRAPH 4fe8482 UN-- 162 164 -- ## + attr: name (v/c), label (v/c), weight (v/n)## + edges from 4fe8482 (vertex names):##  [1] C00022_0--C00024_1  C00022_0--C00041_0  C00022_0--C00074_5 ##  [4] C00022_0--C00149_0  C00022_1--C00041_1  C00022_1--C00074_6 ##  [7] C00022_1--C00149_2  C00022_2--C00024_0  C00022_2--C00041_2 ## [10] C00022_2--C00074_7  C00022_2--C00149_1  C00024_0--C00033_1 ## [13] C00024_0--C00222_0  C00024_1--C00033_0  C00024_1--C00222_2 ## [16] C00025_0--C00026_0  C00025_1--C00026_1  C00025_2--C00026_2 ## [19] C00025_4--C00026_4  C00025_7--C00026_7  C00026_0--C00091_1 ## [22] C00026_0--C00311_1  C00026_1--C00091_0  C00026_1--C00311_0 ## + ... omitted several edges

print(m$weight)

## [1] 1178.432

Using exact CPLEX-basedVirgo solver

Themwcsr package also provide and interface to exactCPLEX-based Virgo solver
(https://github.com/ctlab/virgo-solver) which can be usedto solve MWCS, GMWCS and SGMWCS instances to provable optimality.

To setup this solver CPLEX libraries has to be available. CPLEX canbe downloaded from the official web-site:https://www.ibm.com/products/ilog-cplex-optimization-studio.Free licence can be obtained for academic purposes.

First, initializecplex_dir variable to contain path toCPLEX libraries (for example, /opt/ibm/ILOG/CPLEX_Studio129/).

cplex_dir<-'<replace with path to cplex folder>'

Then initialize the solver:

vsolver<-virgo_solver(cplex_dir=cplex_dir)

And run it on the same MWCS instance:

m<-solve_mwcsp(vsolver, mwcs_example)print(m$graph)

## IGRAPH 9e2522d UN-- 164 166 -- ## + attr: name (v/c), label (v/c), weight (v/n), label (e/c)## + edges from 9e2522d (vertex names):##  [1] C00022_2--C00024_0  C00022_0--C00024_1  C00025_0--C00026_0 ##  [4] C00025_1--C00026_1  C00025_2--C00026_2  C00025_4--C00026_4 ##  [7] C00025_7--C00026_7  C00024_1--C00033_0  C00024_0--C00033_1 ## [10] C00022_0--C00041_0  C00022_1--C00041_1  C00022_2--C00041_2 ## [13] C00036_0--C00049_0  C00036_1--C00049_1  C00036_2--C00049_2 ## [16] C00036_4--C00049_4  C00037_1--C00065_0  C00037_0--C00065_1 ## [19] C00022_0--C00074_5  C00022_1--C00074_6  C00022_2--C00074_7 ## [22] C00026_1--C00091_0  C00042_2--C00091_0  C00026_0--C00091_1 ## + ... omitted several edges

While the solution is a bit different its weight is the same as foundbefore. The solutions differs only in zero-weight vertices.

get_weight(m$graph)

## [1] 1178.432

However, Virgo guarantees that the result is optimal, unless thesolver was interrupted on time limit.

m$solved_to_optimality

## [1] TRUE

Next, consider a GMWCS instance which additionally has edgeweights:

data("gmwcs_example")gmwcs_example

## IGRAPH f86c56f UNW- 194 209 -- ## + attr: name (v/c), label (v/c), weight (v/n), label (e/c), weight## | (e/n)## + edges from f86c56f (vertex names):##  [1] C00022_2--C00024_0 C00022_0--C00024_1 C00025_0--C00026_0 C00025_1--C00026_1##  [5] C00025_2--C00026_2 C00025_4--C00026_4 C00025_7--C00026_7 C00024_1--C00033_0##  [9] C00024_0--C00033_1 C00022_0--C00041_0 C00022_1--C00041_1 C00022_2--C00041_2## [13] C00036_0--C00049_0 C00036_1--C00049_1 C00036_2--C00049_2 C00036_4--C00049_4## [17] C00037_1--C00065_0 C00037_0--C00065_1 C00022_0--C00074_5 C00022_1--C00074_6## [21] C00022_2--C00074_7 C00024_0--C00083_0 C00024_1--C00083_1 C00026_1--C00091_0## [25] C00042_2--C00091_0 C00026_0--C00091_1 C00042_1--C00091_1## + ... omitted several edges

summary(E(gmwcs_example)$weight)

##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. ## -1.2715 -0.5762 -0.1060  0.5452  1.0458  8.5829

The same solver can be used to solve this instance:

m<-solve_mwcsp(vsolver, gmwcs_example)print(m$graph)

## IGRAPH c12fb8d UNW- 182 181 -- ## + attr: name (v/c), label (v/c), weight (v/n), label (e/c), weight## | (e/n)## + edges from c12fb8d (vertex names):##  [1] C00022_2--C00024_0  C00022_0--C00024_1  C00025_0--C00026_0 ##  [4] C00025_1--C00026_1  C00025_2--C00026_2  C00025_4--C00026_4 ##  [7] C00025_7--C00026_7  C00024_1--C00033_0  C00024_0--C00033_1 ## [10] C00022_0--C00041_0  C00022_1--C00041_1  C00022_2--C00041_2 ## [13] C00036_0--C00049_0  C00036_1--C00049_1  C00036_2--C00049_2 ## [16] C00036_4--C00049_4  C00037_1--C00065_0  C00037_0--C00065_1 ## [19] C00022_0--C00074_5  C00022_1--C00074_6  C00022_2--C00074_7 ## + ... omitted several edges

get_weight(m$graph)

## [1] 1296.41

Finally, let consider an SGMWCS instance. The weights of nodes andedges are defined not directly, but through thesignalsattribute:

data("sgmwcs_example")sgmwcs_example

## IGRAPH f86c56f UN-- 194 209 -- ## + attr: signals (g/n), name (v/c), label (v/c), signal (v/c), label## | (e/c), signal (e/c)## + edges from f86c56f (vertex names):##  [1] C00022_2--C00024_0 C00022_0--C00024_1 C00025_0--C00026_0 C00025_1--C00026_1##  [5] C00025_2--C00026_2 C00025_4--C00026_4 C00025_7--C00026_7 C00024_1--C00033_0##  [9] C00024_0--C00033_1 C00022_0--C00041_0 C00022_1--C00041_1 C00022_2--C00041_2## [13] C00036_0--C00049_0 C00036_1--C00049_1 C00036_2--C00049_2 C00036_4--C00049_4## [17] C00037_1--C00065_0 C00037_0--C00065_1 C00022_0--C00074_5 C00022_1--C00074_6## [21] C00022_2--C00074_7 C00024_0--C00083_0 C00024_1--C00083_1 C00026_1--C00091_0## [25] C00042_2--C00091_0 C00026_0--C00091_1 C00042_1--C00091_1## + ... omitted several edges

str(V(sgmwcs_example)$signal)

##  chr [1:194] "s1" "s1" "s1" "s2" "s3" "s4" "s4" "s4" "s4" "s4" "s5" "s5" ...

str(E(sgmwcs_example)$signal)

##  chr [1:209] "s103" "s104" "s105" "s106" "s107" "s108" "s109" "s110" "s110" ...

head(sgmwcs_example$signals)

##        s1        s2        s3        s4        s5        s6 ##  5.008879 -0.737898 -0.737898 20.112627 19.890279  2.069292

Again, we can solve this instance with Virgo solver:

m<-solve_mwcsp(vsolver, sgmwcs_example)print(m$graph)

## IGRAPH f81ae9a UN-- 40 39 -- ## + attr: signals (g/n), name (v/c), label (v/c), signal (v/c), index## | (v/n), label (e/c), signal (e/c), index (e/n)## + edges from f81ae9a (vertex names):##  [1] C00022_0--C00024_1  C00025_1--C00026_1  C00024_1--C00033_0 ##  [4] C00022_0--C00041_0  C00036_1--C00049_1  C00037_1--C00065_0 ##  [7] C00022_0--C00074_5  C00026_1--C00091_0  C00042_2--C00091_0 ## [10] C00042_2--C00091_51 C00111_6--C00118_2  C00117_6--C00119_4 ## [13] C00042_2--C00122_1  C00022_0--C00149_0  C00122_1--C00149_0 ## [16] C00036_1--C00149_1  C00122_1--C00149_1  C00111_6--C00184_0 ## [19] C00117_6--C00199_1  C00118_2--C00231_1  C00199_1--C00231_1 ## + ... omitted several edges

get_weight(m$graph)

## [1] 270.7676

Running Virgo heuristicswithout CPLEX

In case CPLEX is not available, Virgo solver can be run in theheuristic mode. Just setcplex_dir parameter toNULL:

vhsolver<-virgo_solver(cplex_dir=NULL)

While the results are not optimal, sometimes they can be enough forpractical applications:

m<-solve_mwcsp(vhsolver, mwcs_example)get_weight(m$graph)

## [1] 1174.737

m$solved_to_optimality

## [1] FALSE

m<-solve_mwcsp(vhsolver, gmwcs_example)get_weight(m$graph)

## [1] 1276.772

m<-solve_mwcsp(vhsolver, sgmwcs_example)get_weight(m$graph)

## [1] 227.3432