Differential Expression Analysis for CCC & Downstream Signalling Networks
Background
Cell-cell communication (CCC) events play a critical role in diseases, often experiencing deregulation. To identify differential expression of CCC events between conditions, we can build upon standard differential expression analysis (DEA) approaches, such as DESeq2. While dimensionality reduction methods like extracting intercellular programmes with MOFA+ and Tensor-cell2cell reduce CCC into sets of loadings, hypothesis-driven DEA tests focus on individual gene changes, making them easier to understand and interpret.
In this tutorial, we perform DEA at the pseudobulk level to assess differential expression of genes between conditions. We then translate the results into deregulated complex-informed ligand-receptor interactions and analyze their connections to downstream signaling events.
For further information on pseudobulk DEA, please refer to the Differential Gene Expression chapter in the Single-cell Best Practices book, as well as Decoupler’s pseudobulk vignette. These resources provide more comprehensive details on the subject.
Load Packages
Install mofa, decoupler, and omnipath via pip with the following commands:
pip install "decoupler>=0.1.4"
pip install "pydeseq2>=0.4.0"
[1]:
import numpy as np
import pandas as pd
import scanpy as sc
import plotnine as p9
import liana as li
import decoupler as dc
import omnipath as op
# Import DESeq2
from pydeseq2.dds import DeseqDataSet
from pydeseq2.ds import DeseqStats
/home/dbdimitrov/anaconda3/envs/spiana/lib/python3.10/site-packages/tqdm/auto.py:21: TqdmWarning: IProgress not found. Please update jupyter and ipywidgets. See https://ipywidgets.readthedocs.io/en/stable/user_install.html
Downloading data from `https://omnipathdb.org/queries/enzsub?format=json`
Downloading data from `https://omnipathdb.org/queries/interactions?format=json`
Downloading data from `https://omnipathdb.org/queries/complexes?format=json`
Downloading data from `https://omnipathdb.org/queries/annotations?format=json`
Downloading data from `https://omnipathdb.org/queries/intercell?format=json`
Downloading data from `https://omnipathdb.org/about?format=text`
[2]:
# Obtain TF regulons
net = dc.get_collectri()
Load & Prep Data
As a simple example, we will look at ~25k PBMCs from 8 pooled patient lupus samples, each before and after IFN-beta stimulation (Kang et al., 2018; GSE96583). Note that by focusing on PBMCs, for the purpose of this tutorial, we assume that coordinated events occur among them.
This dataset is downloaded from a link on Figshare; preprocessed for pertpy.
[3]:
adata = li.testing.datasets.kang_2018()
adata
[3]:
AnnData object with n_obs × n_vars = 24673 × 15706
obs: 'nCount_RNA', 'nFeature_RNA', 'tsne1', 'tsne2', 'condition', 'cluster', 'cell_type', 'patient', 'nCount_SCT', 'nFeature_SCT', 'integrated_snn_res.0.4', 'seurat_clusters', 'sample', 'cell_abbr'
var: 'name'
obsm: 'X_pca', 'X_umap'
layers: 'counts'
Define columns of interest from .obs
Note that we use cell abbreviations because MOFA will use them as labels for the views.
[4]:
sample_key = 'sample'
groupby = 'cell_abbr'
condition_key = 'condition'
Basic QC
Note that this data has been largely pre-processed & annotated, we refer the user to the Quality Control and other relevant chapters from the best-practices book for information about pre-processing and annotation steps.
[5]:
# filter cells and genes
sc.pp.filter_cells(adata, min_genes=200)
sc.pp.filter_genes(adata, min_cells=3)
Showcase the data
[6]:
# Show pre-computed UMAP
sc.pl.umap(adata, color=[condition_key, sample_key, 'cell_type', groupby], frameon=False, ncols=2)
... storing 'sample' as categorical
/home/dbdimitrov/anaconda3/envs/spiana/lib/python3.10/site-packages/scanpy/plotting/_tools/scatterplots.py:394: UserWarning: No data for colormapping provided via 'c'. Parameters 'cmap' will be ignored
/home/dbdimitrov/anaconda3/envs/spiana/lib/python3.10/site-packages/scanpy/plotting/_tools/scatterplots.py:394: UserWarning: No data for colormapping provided via 'c'. Parameters 'cmap' will be ignored
/home/dbdimitrov/anaconda3/envs/spiana/lib/python3.10/site-packages/scanpy/plotting/_tools/scatterplots.py:394: UserWarning: No data for colormapping provided via 'c'. Parameters 'cmap' will be ignored
/home/dbdimitrov/anaconda3/envs/spiana/lib/python3.10/site-packages/scanpy/plotting/_tools/scatterplots.py:394: UserWarning: No data for colormapping provided via 'c'. Parameters 'cmap' will be ignored
Differential Testing
First, we need to generate pseudobulk profiles for each cell type, and we do so using the `decoupler
package <https://decoupler-py.readthedocs.io/en/latest/notebooks/pseudobulk.html>`__.
[7]:
pdata = dc.get_pseudobulk(
adata,
sample_col=sample_key,
groups_col=groupby,
layer='counts',
mode='sum',
min_cells=10,
min_counts=10000
)
pdata
[7]:
AnnData object with n_obs × n_vars = 110 × 15701
obs: 'condition', 'cell_type', 'patient', 'sample', 'cell_abbr', 'psbulk_n_cells', 'psbulk_counts'
var: 'name', 'n_cells'
layers: 'psbulk_props'
We can plot the quality control metrics for each pseudobulk sample:
[8]:
dc.plot_psbulk_samples(pdata, groupby=[sample_key, groupby], figsize=(11, 4))
Next, now that we have generated the pseudobulk profiles, we can perform some edgeR-like filtering using decoupler-py, and then differential expression analysis using the `pydeseq2
package <https://pydeseq2.readthedocs.io/en/latest/>`__ - a re-implementation of the original DESeq2 method (Love et al., 2014).
Here, we perform DEA on the pseudobulk profiles for each cell type, for more info check this tutorial: https://decoupler-py.readthedocs.io/en/latest/notebooks/pseudobulk.html
[9]:
%%capture
dea_results = {}
quiet = True
for cell_group in pdata.obs[groupby].unique():
# Select cell profiles
ctdata = pdata[pdata.obs[groupby] == cell_group].copy()
# Obtain genes that pass the edgeR-like thresholds
# NOTE: QC thresholds might differ between cell types, consider applying them by cell type
genes = dc.filter_by_expr(ctdata,
group=condition_key,
min_count=5, # a minimum number of counts in a number of samples
min_total_count=10 # a minimum total number of reads across samples
)
# Filter by these genes
ctdata = ctdata[:, genes].copy()
# Build DESeq2 object
# NOTE: this data is actually paired, so one could consider fitting the patient label as a confounder
dds = DeseqDataSet(
adata=ctdata,
design_factors=condition_key,
ref_level=[condition_key, 'ctrl'], # set control as reference
refit_cooks=True,
quiet=quiet
)
# Compute LFCs
dds.deseq2()
# Contrast between stim and ctrl
stat_res = DeseqStats(dds, contrast=[condition_key, 'stim', 'ctrl'], quiet=quiet)
stat_res.quiet = quiet
# Compute Wald test
stat_res.summary()
# Shrink LFCs
stat_res.lfc_shrink(coeff='condition_stim_vs_ctrl') # {condition_key}_cond_vs_ref
dea_results[cell_group] = stat_res.results_df
This results in a wall of currently unavoidable verbose text and prints, as such I use %%capture
to hide it. One can use quiet
to some of the functions but not logfc_shrinkage
[10]:
# concat results across cell types
dea_df = pd.concat(dea_results)
dea_df = dea_df.reset_index().rename(columns={'level_0': groupby}).set_index('index')
dea_df.head()
[10]:
cell_abbr | baseMean | log2FoldChange | lfcSE | stat | pvalue | padj | |
---|---|---|---|---|---|---|---|
index | |||||||
AAED1 | B | 7.282872 | -0.134222 | 0.260852 | -0.605923 | 0.544566 | 0.747988 |
AAMP | B | 11.967019 | -0.436867 | 0.185711 | -2.523263 | 0.011627 | 0.047688 |
AARS | B | 5.797380 | 0.180074 | 0.272438 | 0.782374 | 0.433995 | 0.660342 |
AASDHPPT | B | 6.147571 | 0.184129 | 0.305030 | 0.741856 | 0.458175 | 0.679302 |
AATF | B | 9.567191 | -0.109027 | 0.254673 | -0.493000 | 0.622013 | 0.802867 |
DEA to Ligand-Receptor Interactions
Now that we have DEA results per gene, we can combine them into statistics of potentially deregulated ligand-receptor interactions.
To do so, liana provides a simple function li.multi.df_to_lr
that calculates average expression as well as proportions based on the passed adata
object, and combines those with the DEA results and a ligand-receptor resource. Since in this case we want to focus on gene statics relevant to the condition (stim), let’s subset the adata to those and normalize the counts.
[11]:
adata = adata[adata.obs[condition_key]=='stim'].copy()
[12]:
sc.pp.normalize_total(adata, target_sum=1e4)
sc.pp.log1p(adata)
Let’s combine the DEA results with the ligand-receptor interactions. We need to pass the names of the statistics from the DEA table in which we are interest to li.multi.df_to_lr
, here we will use the adjusted p-values and Wald test statistic.
[13]:
lr_res = li.multi.df_to_lr(adata,
dea_df=dea_df,
resource_name='consensus',
expr_prop=0.1, # calculated for adata as passed - used to filter interactions
groupby=groupby,
stat_keys=['stat', 'pvalue', 'padj'],
use_raw=False,
complex_col='stat', # NOTE: we use the Wald Stat to deal with complexes
verbose=True,
return_all_lrs=False,
)
Using resource `consensus`.
Using `.X`!
Converting to sparse csr matrix!
227 features of mat are empty, they will be removed.
/home/dbdimitrov/anaconda3/envs/spiana/lib/python3.10/site-packages/liana/method/_pipe_utils/_pre.py:150: ImplicitModificationWarning: Trying to modify attribute `.obs` of view, initializing view as actual.
0.75 of entities in the resource are missing from the data.
[14]:
lr_res = lr_res.sort_values("interaction_stat", ascending=False, key=abs)
lr_res.head()
[14]:
ligand | receptor | ligand_complex | receptor_complex | source | ligand_stat | ligand_pvalue | ligand_padj | ligand_expr | ligand_props | ... | receptor_pvalue | receptor_padj | receptor_expr | receptor_props | interaction_stat | interaction_pvalue | interaction_padj | interaction_expr | interaction_props | interaction | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
233 | CXCL11 | CCR5 | CXCL11 | CCR5 | CD14 | 26.172426 | 5.476439e-151 | 2.599815e-148 | 3.106561 | 0.899096 | ... | 9.797079e-47 | 3.410690e-45 | 0.601853 | 0.332369 | 20.264119 | 4.898540e-47 | 1.705345e-45 | 1.854207 | 0.615732 | CXCL11^CCR5 |
238 | CCL8 | CCR5 | CCL8 | CCR5 | CD14 | 25.720102 | 6.965891e-146 | 2.798145e-143 | 4.313416 | 0.894756 | ... | 9.797079e-47 | 3.410690e-45 | 0.601853 | 0.332369 | 20.037957 | 4.898540e-47 | 1.705345e-45 | 2.457634 | 0.613562 | CCL8^CCR5 |
252 | CCL8 | CCR1 | CCL8 | CCR1 | CD14 | 25.720102 | 6.965891e-146 | 2.798145e-143 | 4.313416 | 0.894756 | ... | 2.567490e-35 | 5.779065e-34 | 1.079367 | 0.552260 | 19.060759 | 1.283745e-35 | 2.889533e-34 | 2.696391 | 0.723508 | CCL8^CCR1 |
1062 | CXCL11 | CCR5 | CXCL11 | CCR5 | FGR3 | 16.919574 | 3.227547e-64 | 6.676057e-62 | 2.692778 | 0.826011 | ... | 9.797079e-47 | 3.410690e-45 | 0.601853 | 0.332369 | 15.637693 | 4.898540e-47 | 1.705345e-45 | 1.647316 | 0.579190 | CXCL11^CCR5 |
491 | CCL8 | CCR1 | CCL8 | CCR1 | CD14 | 25.720102 | 6.965891e-146 | 2.798145e-143 | 4.313416 | 0.894756 | ... | 2.993682e-07 | 2.388773e-06 | 0.384328 | 0.247232 | 15.421973 | 1.496841e-07 | 1.194386e-06 | 2.348872 | 0.570994 | CCL8^CCR1 |
5 rows × 22 columns
LIANA will filter lowly-expressed interactions, i.e. those for which any of the genes are not expressed in at least 0.1 of the cells (by default) in the AnnData object. This can be adjusted with the expr_prop
parameter.
Moreover, to deal with complexes for each cell type, as either source or target of the potential CCC events, LIANA will find and assign the subunit of a complex with the lowest gene expression (by default) as the subunit of interest, and will then use the stats for that subunit as the stats of the whole protein complex.
This is a simple heuristic also adapted by many other methods, but it is not perfect, as in some cases it might be over-conservative. For example, if the subunit with lowest expression is not the one that is differentially expressed, the complex will not be detected as deregulated.
To this end, we also provide the option to provide a complex_col
parameter, which will be used to assign the complex subunit of interest. This column should be a part of the stat_keys
. Note that the absolute minimum value is used (i.e. the value closest to 0 is thought to be the ‘worst’ result), so this will not work for statistics with ascending values (e.g. p-values).
Visualize the Results
interaction_*
columns returned by li.multi.dea_to_lr
are just the mean of the ligand and receptor columns of the corresponding statistic! Please use with caution as this is just a summary of the interaction that we can use to e.g. to sort the interactions as done above. Instead, we recommend to use the ligand and receptor statistics separately to filter and visualize the interactions.
Moreover, by averaging the statistics across the ligand and receptor, we are focusing on the interactions for which both the ligand and receptor are deregulated in the same direction, i.e. both up or both down. However, this might ignore interactions in which e.g. the the ligand is deregulated while the receptor is not, or such where they are deregulated in opposite directions. These could represent potential inhibitory mechanisms, but we leave this to the user to explore.
[15]:
# Let's visualize how this looks like for all interactions (across all cell types)
lr_res = lr_res.sort_values("interaction_stat", ascending=False)
lr_res['interaction_stat'].hist(bins=50)
[15]:
<Axes: >
Now that we have covered the basics, we can visualize our interactions in a few ways.
Let’s start with the top interactions according to their Wald statistic, and then plot the statistics for the ligands & receptors involved in those interactions across cell types, to do so LIANA+ provide li.pl.tileplot
:
[16]:
li.pl.tileplot(liana_res=lr_res,
fill = 'expr',
label='padj',
label_fun = lambda x: '*' if x < 0.05 else np.nan,
top_n=15,
orderby = 'interaction_stat',
orderby_ascending = False,
orderby_absolute = False,
source_title='Ligand',
target_title='Receptor',
)
/home/dbdimitrov/anaconda3/envs/spiana/lib/python3.10/site-packages/liana/plotting/_common.py:104: SettingWithCopyWarning:
A value is trying to be set on a copy of a slice from a DataFrame.
Try using .loc[row_indexer,col_indexer] = value instead
See the caveats in the documentation: https://pandas.pydata.org/pandas-docs/stable/user_guide/indexing.html#returning-a-view-versus-a-copy
/home/dbdimitrov/anaconda3/envs/spiana/lib/python3.10/site-packages/plotnine/layer.py:364: PlotnineWarning: geom_text : Removed 54 rows containing missing values.
Fontsize 0.00 < 1.0 pt not allowed by FreeType. Setting fontsize = 1 pt
[16]:
<Figure Size: (500 x 500)>
If you want to plot the expression values for ligand-receptor interactions without the DEA statistics, you can set the return_all_lrs
parameter to True
in the li.multi.dea_to_lr
function. This will return a dataframe with all the ligand-receptor interactions, where missing DEA stats will be set as nan
, while mean expression and proportions per cluster will be obtained via the AnnData object.
Ligand-Receptor Plot
We can also use visualize of the stats, summarized at the level of the interaction, to prioritize the interactions, or any subunit statistics using li.pl.dotplot
. For example, we can visualize the mean Wald statistic between the ligand & receptor, together with the pvalues for the ligand.
[17]:
plot = li.pl.dotplot(liana_res=lr_res,
colour='interaction_stat',
size='ligand_pvalue',
inverse_size=True,
orderby='interaction_stat',
orderby_ascending=False,
orderby_absolute=True,
top_n=10,
size_range=(0.5, 4)
)
# customize plot
(
plot
+ p9.theme_bw(base_size=14)
# fill cmap blue to red, with 0 the middle
+ p9.scale_color_cmap('RdBu_r', midpoint=0, limits=(-10, 10))
# rotate x
+ p9.theme(axis_text_x=p9.element_text(angle=90), figure_size=(11, 6))
)
/home/dbdimitrov/anaconda3/envs/spiana/lib/python3.10/site-packages/liana/plotting/_common.py:104: SettingWithCopyWarning:
A value is trying to be set on a copy of a slice from a DataFrame.
Try using .loc[row_indexer,col_indexer] = value instead
See the caveats in the documentation: https://pandas.pydata.org/pandas-docs/stable/user_guide/indexing.html#returning-a-view-versus-a-copy
/home/dbdimitrov/anaconda3/envs/spiana/lib/python3.10/site-packages/plotnine/scales/scale.py:143: PlotnineWarning: scale_color_cmap could not recognise parameter `midpoint`
/home/dbdimitrov/anaconda3/envs/spiana/lib/python3.10/site-packages/plotnine/scales/scales.py:50: PlotnineWarning: Scale for 'color' is already present.
Adding another scale for 'color',
which will replace the existing scale.
Fontsize 0.00 < 1.0 pt not allowed by FreeType. Setting fontsize = 1 pt
[17]:
<Figure Size: (1100 x 600)>
Now that we have identified a set of interactions that are potentially deregulated we can look into the downstream signalling events that they might be involved in.
One can also estimate ligand-receptor pathway activities, etc, these are covered multiple times in other tutorials, but also are applicable here.
Intracellular Signaling Networks
Cellular signaling networks govern the behavior of cells, allowing them to respond to external signals, including various cell-cell communication events. Thus, CCC events can be thought of as upstream perturbants of intracellular signaling networks that lead to deregulations of downstream signaling events. Such deregulations are expected to be associated with various conditions and disease. Thus, understanding intracellular signaling networks is critical to model the cellular mechanisms.
Here, we will combine several tools to identify plausible signalling cascades driven by CCC events.
Our approach includes the following steps:
Select a number of potentially deregulated ligand-receptor interactions (input nodes), in terms of summarized PyDESeq2 statistics.
Select a number of potentially deregulated TFs (output nodes). This is done via the use of Transcription factor (TF) activity inference. Carried out on differential gene expression data using TF regulon knowledge with decoupler
Obtain a prior knowledge network (PKNs), with signed protein-protein interactions from OmniPath.
Generate weights for the nodes in the PKN
Use CORNETO to identify a solution in the form of a causal (smallest sign-consistent signaling) network that explains the measured inputs and outputs
Import OmniPath
For this part OmniPath is required.
pip install omnipath
[18]:
# utily function to select top n interactions
def select_top_n(d, n=None):
d = dict(sorted(d.items(), key=lambda item: abs(item[1]), reverse=True))
return {k: v for i, (k, v) in enumerate(d.items()) if i < n}
Select Cell types of Interest
One limitation of using DEA to identify interactions of interest is that it tells us little about deregulation at the level of cell types. However, from dimensionality reductions on CCC, as done with Tensor-cell2cell & MOFA on the same dataset, we can see there is a potential deregulation of CCC that involve CD14 monocytes both as sources (senders) and targets (or receivers) of intecellular communication. Thus, we will focus on the interactions and downstream signalling within that cell type.
[19]:
source_label = 'CD14'
target_label = 'CD14'
# NOTE: We sort by the absolute value of the interaction stat
lr_stats = lr_res[lr_res['source'].isin([source_label]) & lr_res['target'].isin([target_label])].copy()
lr_stats = lr_stats.sort_values('interaction_stat', ascending=False, key=abs)
Select Receptors based on interaction stats
These will be used as the input or start nodes for the network. In this case, we will use interactions potentially involved in autocrine signalling in CD14 monocytes.
[20]:
lr_dict = lr_stats.set_index('receptor')['interaction_stat'].to_dict()
input_scores = select_top_n(lr_dict, n=10)
[21]:
input_scores
[21]:
{'CD40': 15.213890738775456,
'CD80': 11.672283052638337,
'SIRPA': 9.92679527367514,
'CCR1': 9.12729237916692,
'HLA-DPB1': 8.625121687728944,
'LILRB2': 8.250712282572682,
'CCR5': 6.024106443619973,
'PTPRC': 5.811339038637888,
'LILRB1': 5.586746654720494,
'CD47': 5.431274692175629}
Select Transcription Factors of interest
Before we select the transcription factors, we need to infer their activity. We will do so using decoupler with CollecTri regulons. Specifically, we will estimate TF activities using the Wald statistics (from PyDESeq2) for the genes in the regulons.
[22]:
# First, let's transform the DEA statistics into a DF
# we will use these to estimate deregulated TF activity
dea_wide = dea_df[[groupby, 'stat']].reset_index(names='genes').pivot(index=groupby, columns='genes', values='stat')
dea_wide = dea_wide.fillna(0)
dea_wide
[22]:
genes | A1BG | AAAS | AAED1 | AAGAB | AAK1 | AAMDC | AAMP | AAR2 | AARS | AARSD1 | ... | ZSCAN16 | ZSCAN16-AS1 | ZSCAN18 | ZSCAN32 | ZSWIM6 | ZSWIM7 | ZUFSP | ZW10 | ZYX | ZZZ3 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
cell_abbr | |||||||||||||||||||||
B | 0.000000 | 0.000000 | -0.605923 | 0.000000 | 0.000000 | 0.000000 | -2.523263 | 0.000000 | 0.782374 | 0.000000 | ... | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | -2.350376 | 0.000000 | 0.00000 | 0.000000 | 0.000000 |
CD14 | -2.993111 | 0.000000 | 10.129553 | 0.000000 | 1.085436 | 6.968489 | -3.097932 | 0.000000 | 0.000000 | 0.000000 | ... | 0.000000 | 0.000000 | 0.000000 | 0.000000 | -1.281381 | -4.154833 | 1.737279 | 0.00000 | -1.796965 | 0.000000 |
CD4T | -2.814957 | -1.995631 | 0.191978 | 1.144712 | -5.150155 | -0.081141 | -0.650599 | 2.032146 | 1.648662 | -0.270347 | ... | -0.218578 | -1.168355 | -1.515016 | -0.430795 | 0.000000 | -1.685312 | 3.455590 | -0.17713 | -1.399221 | -0.240491 |
CD8T | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | ... | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.00000 | 0.000000 | 0.000000 |
DCs | 0.000000 | 0.000000 | 3.883796 | 0.000000 | 0.000000 | 0.000000 | -1.620856 | 0.000000 | 0.000000 | 0.000000 | ... | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.00000 | -2.573142 | 0.000000 |
FGR3 | 0.000000 | 0.000000 | 2.836840 | 0.000000 | 0.000000 | 0.000000 | -3.248816 | 0.000000 | 0.000000 | 0.000000 | ... | 4.160610 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.00000 | -2.117717 | 0.000000 |
NK | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | -2.548184 | 0.000000 | 0.000000 | 0.000000 | ... | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.00000 | 0.000000 | 0.000000 |
7 rows × 7802 columns
[23]:
# Run Enrichment Analysis
estimates, pvals = dc.run_ulm(mat=dea_wide, net=net)
estimates.T.sort_values(target_label, key=abs, ascending=False).head()
[23]:
B | CD14 | CD4T | CD8T | DCs | FGR3 | NK | |
---|---|---|---|---|---|---|---|
STAT1 | 17.926670 | 13.178566 | 16.732069 | 17.533529 | 17.887823 | 15.023597 | 16.353252 |
IRF1 | 15.773025 | 10.694732 | 14.545148 | 13.118623 | 14.475640 | 11.968679 | 13.322178 |
STAT2 | 14.908431 | 9.841800 | 12.172835 | 13.719251 | 15.724816 | 12.524464 | 12.979574 |
IRF9 | 18.450977 | 8.841106 | 14.894291 | 19.616129 | 17.128387 | 13.703831 | 17.811499 |
NFKB1 | 6.898114 | 7.734655 | 8.250937 | 5.890799 | 9.258309 | 8.580269 | 7.130418 |
Select top TFs
Now that we have the potentially deregulated TFs, we focus on the top 10 TFs, based on their enrichment scores. In this case, we will look specifically at the top TFs deregulated in CD14 monocytes.
[24]:
tf_data = estimates.copy()
tf_dict = tf_data.loc[target_label].to_dict()
output_scores = select_top_n(tf_dict, n=5)
Generate a Prior Knowledge Network
Now we will obtain protein-protein interactions from OmniPath, filter them according to curation effort to ensure we only keep those that are of high quality, and convert them into a knowledge graph.
[25]:
# obtain ppi network
ppis = op.interactions.OmniPath().get(genesymbols = True)
ppis['mor'] = ppis['is_stimulation'].astype(int) - ppis['is_inhibition'].astype(int)
ppis = ppis[(ppis['mor'] != 0) & (ppis['curation_effort'] >= 5) & ppis['consensus_direction']]
input_pkn = ppis[['source_genesymbol', 'mor', 'target_genesymbol']]
input_pkn.columns = ['source', 'mor', 'target']
input_pkn.head()
[25]:
source | mor | target | |
---|---|---|---|
3 | CAV1 | 1 | TRPC1 |
6 | ITPR2 | 1 | TRPC1 |
9 | STIM1 | 1 | TRPC1 |
10 | TRPC1 | 1 | TRPC3 |
11 | TRPC3 | 1 | TRPC1 |
[26]:
# convert the PPI network into a knowledge graph
prior_graph = li.mt.build_prior_network(input_pkn, input_scores, output_scores, verbose=True)
Importing network...
done.
- Nodes x Edges: (3115, 6157)
- Provided inputs included in the prior network: 8/10
- Provided outputs included in the network: 5/5
Performing reachability analysis...
done.
- Selected inputs: 4/8.
- Selected outputs: 5/5.
- Final size of the prior graph: (530, 1988).
In this section we use Prior Knowledge Networks (PKNs) from OmniPath to generate network hypotheses based on the deregulated interactions considering both sign and direction. Specifically, we focus on highly curated protein-protein interactions, which often represent hubs in the network. Since such network approaches are highly dependent on prior knowledge, for a review on prior knowledge bias and similar network inference methods, including thier limitations, see Garrido-Rodriguez et al., 2022.
Calculate Node weights
Calculate gene expression proportions within the target cell type; we will use those as node weights in the network.
[27]:
temp = adata[adata.obs[groupby] == target_label].copy()
[28]:
node_weights = pd.DataFrame(temp.X.getnnz(axis=0) / temp.n_obs, index=temp.var_names)
node_weights = node_weights.rename(columns={0: 'props'})
node_weights = node_weights['props'].to_dict()
Find Causal Network
CORNETO (Rodriguez-Mier et al., In prep) generalizes biological network inference problems using convex and combinatorial optimization. Here, we use it to find the smallest sign-consistent network that explains the measured inputs and outputs, a network inference problem formulated in CARNIVAL.
CORNETO further generalizes the use of different solvers to find the network inference problems, as such it supports a wide range of supported free and commercial solvers. If no additional solver is installed (as done here), it will default to using the solver included in SCIPY. We refer the user to the CORNETO documentation for more details on how to use different solvers, specifically if they wish to solve more complex examples than the one presented here.
To run CORNETO, we need to first install it; it’s very lightweight and can be installed via pip:
pip install corneto cvxpy cylp
[29]:
import corneto as cn
cn.info()
|
[32]:
df_res, problem = li.mt.find_causalnet(
prior_graph,
input_scores,
output_scores,
node_weights,
# penalize (max_penalty) nodes with counts in less than 0.1 of the cells
node_cutoff=0.1,
max_penalty=1,
# the penaly of those in > 0.1 prop of cells set to:
min_penalty=0.01,
edge_penalty=0.1,
verbose=True,
max_runs=25, # NOTE that this repeats the solving either until the max runs are reached
stable_runs=5, # or until 3 consequitive stable runs are reached (i.e. no new edges are added)
solver='gurobi' # 'scipy' is available by default, but results in suboptimal solutions
)
Total positive/negative scores of the inputs and outputs:
- (-) input nodes: 0
- (+) input nodes: 85.66956224371147
- (-) output nodes: 0
- (+) output nodes: 50.29085922241211
- abs total (inputs + outputs): 135.9604214661236
Building CORNETO problem...
Solving with gurobi...
===============================================================================
CVXPY
v1.4.1
===============================================================================
(CVXPY) Apr 11 04:46:56 PM: Your problem has 9606 variables, 31 constraints, and 0 parameters.
(CVXPY) Apr 11 04:46:56 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Apr 11 04:46:56 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Apr 11 04:46:56 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Apr 11 04:46:56 PM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:46:56 PM: Compiling problem (target solver=GUROBI).
(CVXPY) Apr 11 04:46:56 PM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> GUROBI
(CVXPY) Apr 11 04:46:56 PM: Applying reduction CvxAttr2Constr
(CVXPY) Apr 11 04:46:56 PM: Applying reduction Qp2SymbolicQp
(CVXPY) Apr 11 04:46:56 PM: Applying reduction QpMatrixStuffing
(CVXPY) Apr 11 04:46:56 PM: Applying reduction GUROBI
(CVXPY) Apr 11 04:46:56 PM: Finished problem compilation (took 9.508e-02 seconds).
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:46:56 PM: Invoking solver GUROBI to obtain a solution.
Set parameter QCPDual to value 1
Set parameter QCPDual to value 1
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Model fingerprint: 0xf76d00ec
Model fingerprint: 0xf76d00ec
Variable types: 2535 continuous, 7071 integer (7071 binary)
Variable types: 2535 continuous, 7071 integer (7071 binary)
Coefficient statistics:
Coefficient statistics:
Matrix range [1e-03, 5e+02]
Matrix range [1e-03, 5e+02]
Objective range [5e-03, 2e+01]
Objective range [5e-03, 2e+01]
Bounds range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e-03, 5e+02]
RHS range [1e-03, 5e+02]
Presolve removed 24916 rows and 1156 columns
Presolve removed 24916 rows and 1156 columns
Presolve time: 0.14s
Presolve time: 0.14s
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Variable types: 2334 continuous, 6116 integer (6116 binary)
Variable types: 2334 continuous, 6116 integer (6116 binary)
Root relaxation: objective -8.344752e+01, 2370 iterations, 0.16 seconds (0.17 work units)
Root relaxation: objective -8.344752e+01, 2370 iterations, 0.16 seconds (0.17 work units)
Nodes | Current Node | Objective Bounds | Work
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -83.44752 0 65 - -83.44752 - - 0s
0 0 -83.44752 0 65 - -83.44752 - - 0s
H 0 0 -55.3928032 -83.44752 50.6% - 0s
H 0 0 -55.3928032 -83.44752 50.6% - 0s
H 0 0 -81.3146530 -83.44752 2.62% - 0s
H 0 0 -81.3146530 -83.44752 2.62% - 0s
0 0 -82.68413 0 152 -81.31465 -82.68413 1.68% - 0s
0 0 -82.68413 0 152 -81.31465 -82.68413 1.68% - 0s
H 0 0 -81.3246732 -82.66294 1.65% - 0s
H 0 0 -81.3246732 -82.66294 1.65% - 0s
0 0 -82.62043 0 125 -81.32467 -82.62043 1.59% - 1s
0 0 -82.62043 0 125 -81.32467 -82.62043 1.59% - 1s
0 0 -82.57058 0 130 -81.32467 -82.57058 1.53% - 1s
0 0 -82.57058 0 130 -81.32467 -82.57058 1.53% - 1s
0 0 -82.48925 0 90 -81.32467 -82.48925 1.43% - 1s
0 0 -82.48925 0 90 -81.32467 -82.48925 1.43% - 1s
0 0 -82.46940 0 85 -81.32467 -82.46940 1.41% - 1s
0 0 -82.46940 0 85 -81.32467 -82.46940 1.41% - 1s
0 0 -82.29410 0 167 -81.32467 -82.29410 1.19% - 1s
0 0 -82.29410 0 167 -81.32467 -82.29410 1.19% - 1s
0 0 -82.28608 0 185 -81.32467 -82.28608 1.18% - 1s
0 0 -82.28608 0 185 -81.32467 -82.28608 1.18% - 1s
0 0 -82.28565 0 186 -81.32467 -82.28565 1.18% - 1s
0 0 -82.28565 0 186 -81.32467 -82.28565 1.18% - 1s
0 0 -82.28562 0 186 -81.32467 -82.28562 1.18% - 1s
0 0 -82.28562 0 186 -81.32467 -82.28562 1.18% - 1s
0 0 -82.26867 0 223 -81.32467 -82.26867 1.16% - 1s
0 0 -82.26867 0 223 -81.32467 -82.26867 1.16% - 1s
0 0 -82.26867 0 108 -81.32467 -82.26867 1.16% - 2s
0 0 -82.26867 0 108 -81.32467 -82.26867 1.16% - 2s
0 0 -82.26867 0 131 -81.32467 -82.26867 1.16% - 2s
0 0 -82.26867 0 131 -81.32467 -82.26867 1.16% - 2s
H 0 0 -81.4286262 -82.26867 1.03% - 2s
H 0 0 -81.4286262 -82.26867 1.03% - 2s
0 0 -82.26867 0 194 -81.42863 -82.26867 1.03% - 2s
0 0 -82.26867 0 194 -81.42863 -82.26867 1.03% - 2s
0 0 -82.26867 0 180 -81.42863 -82.26867 1.03% - 2s
0 0 -82.26867 0 180 -81.42863 -82.26867 1.03% - 2s
0 0 -82.26867 0 192 -81.42863 -82.26867 1.03% - 2s
0 0 -82.26867 0 192 -81.42863 -82.26867 1.03% - 2s
0 0 -82.25773 0 185 -81.42863 -82.25773 1.02% - 2s
0 0 -82.25773 0 185 -81.42863 -82.25773 1.02% - 2s
0 0 -82.25462 0 154 -81.42863 -82.25462 1.01% - 2s
0 0 -82.25462 0 154 -81.42863 -82.25462 1.01% - 2s
0 0 -82.24890 0 176 -81.42863 -82.24890 1.01% - 2s
0 0 -82.24890 0 176 -81.42863 -82.24890 1.01% - 2s
0 0 -82.17678 0 184 -81.42863 -82.17678 0.92% - 2s
0 0 -82.17678 0 184 -81.42863 -82.17678 0.92% - 2s
0 0 -82.17124 0 204 -81.42863 -82.17124 0.91% - 2s
0 0 -82.17124 0 204 -81.42863 -82.17124 0.91% - 2s
0 0 -82.16960 0 200 -81.42863 -82.16960 0.91% - 2s
0 0 -82.16960 0 200 -81.42863 -82.16960 0.91% - 2s
0 0 -82.16952 0 199 -81.42863 -82.16952 0.91% - 2s
0 0 -82.16952 0 199 -81.42863 -82.16952 0.91% - 2s
0 0 -82.08210 0 203 -81.42863 -82.08210 0.80% - 2s
0 0 -82.08210 0 203 -81.42863 -82.08210 0.80% - 2s
0 0 -82.07915 0 198 -81.42863 -82.07915 0.80% - 2s
0 0 -82.07915 0 198 -81.42863 -82.07915 0.80% - 2s
0 0 -82.07915 0 206 -81.42863 -82.07915 0.80% - 2s
0 0 -82.07915 0 206 -81.42863 -82.07915 0.80% - 2s
0 0 -82.07221 0 171 -81.42863 -82.07221 0.79% - 3s
0 0 -82.07221 0 171 -81.42863 -82.07221 0.79% - 3s
0 0 -82.06224 0 174 -81.42863 -82.06224 0.78% - 3s
0 0 -82.06224 0 174 -81.42863 -82.06224 0.78% - 3s
0 0 -82.06224 0 186 -81.42863 -82.06224 0.78% - 3s
0 0 -82.06224 0 186 -81.42863 -82.06224 0.78% - 3s
0 0 -82.05077 0 174 -81.42863 -82.05077 0.76% - 3s
0 0 -82.05077 0 174 -81.42863 -82.05077 0.76% - 3s
0 0 -82.04690 0 179 -81.42863 -82.04690 0.76% - 3s
0 0 -82.04690 0 179 -81.42863 -82.04690 0.76% - 3s
0 0 -82.04690 0 180 -81.42863 -82.04690 0.76% - 3s
0 0 -82.04690 0 180 -81.42863 -82.04690 0.76% - 3s
0 0 -81.96217 0 172 -81.42863 -81.96217 0.66% - 3s
0 0 -81.96217 0 172 -81.42863 -81.96217 0.66% - 3s
0 0 -81.95649 0 164 -81.42863 -81.95649 0.65% - 3s
0 0 -81.95649 0 164 -81.42863 -81.95649 0.65% - 3s
0 0 -81.95624 0 163 -81.42863 -81.95624 0.65% - 3s
0 0 -81.95624 0 163 -81.42863 -81.95624 0.65% - 3s
0 0 -81.94043 0 152 -81.42863 -81.94043 0.63% - 3s
0 0 -81.94043 0 152 -81.42863 -81.94043 0.63% - 3s
0 0 -81.93802 0 163 -81.42863 -81.93802 0.63% - 3s
0 0 -81.93802 0 163 -81.42863 -81.93802 0.63% - 3s
0 0 -81.93802 0 166 -81.42863 -81.93802 0.63% - 3s
0 0 -81.93802 0 166 -81.42863 -81.93802 0.63% - 3s
0 0 -81.93802 0 162 -81.42863 -81.93802 0.63% - 3s
0 0 -81.93802 0 162 -81.42863 -81.93802 0.63% - 3s
0 0 -81.93802 0 179 -81.42863 -81.93802 0.63% - 3s
0 0 -81.93802 0 179 -81.42863 -81.93802 0.63% - 3s
0 0 -81.93139 0 173 -81.42863 -81.93139 0.62% - 4s
0 0 -81.93139 0 173 -81.42863 -81.93139 0.62% - 4s
0 0 -81.93139 0 173 -81.42863 -81.93139 0.62% - 4s
0 0 -81.93139 0 173 -81.42863 -81.93139 0.62% - 4s
0 2 -81.92634 0 171 -81.42863 -81.92634 0.61% - 4s
0 2 -81.92634 0 171 -81.42863 -81.92634 0.61% - 4s
Cutting planes:
Cutting planes:
Cover: 62
Cover: 62
Implied bound: 27
Implied bound: 27
Clique: 1
Clique: 1
MIR: 6
MIR: 6
Flow cover: 16
Flow cover: 16
Zero half: 6
Zero half: 6
Network: 4
Network: 4
RLT: 15
RLT: 15
Relax-and-lift: 2
Relax-and-lift: 2
Explored 81 nodes (19782 simplex iterations) in 4.91 seconds (3.18 work units)
Explored 81 nodes (19782 simplex iterations) in 4.91 seconds (3.18 work units)
Thread count was 12 (of 12 available processors)
Thread count was 12 (of 12 available processors)
Solution count 4: -81.4286 -81.3247 -81.3147 -55.3928
Solution count 4: -81.4286 -81.3247 -81.3147 -55.3928
No other solutions better than -81.4286
No other solutions better than -81.4286
Optimal solution found (tolerance 1.00e-04)
Optimal solution found (tolerance 1.00e-04)
Best objective -8.142862616577e+01, best bound -8.142862616577e+01, gap 0.0000%
Best objective -8.142862616577e+01, best bound -8.142862616577e+01, gap 0.0000%
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:01 PM: Problem status: optimal
(CVXPY) Apr 11 04:47:01 PM: Optimal value: 7.584e+00
(CVXPY) Apr 11 04:47:01 PM: Compilation took 9.508e-02 seconds
(CVXPY) Apr 11 04:47:01 PM: Solver (including time spent in interface) took 5.090e+00 seconds
Solution summary:
- Loss (unfitted inputs/output): [0.]
- Edge penalty error: 34.0
- Node penalty error: 4.024977342756888
Building CORNETO problem...
Solving with gurobi...
===============================================================================
CVXPY
v1.4.1
===============================================================================
(CVXPY) Apr 11 04:47:02 PM: Your problem has 9606 variables, 31 constraints, and 0 parameters.
(CVXPY) Apr 11 04:47:02 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Apr 11 04:47:02 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Apr 11 04:47:02 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Apr 11 04:47:02 PM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:02 PM: Compiling problem (target solver=GUROBI).
(CVXPY) Apr 11 04:47:02 PM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> GUROBI
(CVXPY) Apr 11 04:47:02 PM: Applying reduction CvxAttr2Constr
(CVXPY) Apr 11 04:47:02 PM: Applying reduction Qp2SymbolicQp
(CVXPY) Apr 11 04:47:02 PM: Applying reduction QpMatrixStuffing
(CVXPY) Apr 11 04:47:02 PM: Applying reduction GUROBI
(CVXPY) Apr 11 04:47:02 PM: Finished problem compilation (took 7.997e-02 seconds).
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:02 PM: Invoking solver GUROBI to obtain a solution.
Set parameter QCPDual to value 1
Set parameter QCPDual to value 1
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Model fingerprint: 0x675cb44e
Model fingerprint: 0x675cb44e
Variable types: 2535 continuous, 7071 integer (7071 binary)
Variable types: 2535 continuous, 7071 integer (7071 binary)
Coefficient statistics:
Coefficient statistics:
Matrix range [1e-03, 5e+02]
Matrix range [1e-03, 5e+02]
Objective range [5e-03, 2e+01]
Objective range [5e-03, 2e+01]
Bounds range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e-03, 5e+02]
RHS range [1e-03, 5e+02]
Presolve removed 24916 rows and 1156 columns
Presolve removed 24916 rows and 1156 columns
Presolve time: 0.15s
Presolve time: 0.15s
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Variable types: 2334 continuous, 6116 integer (6116 binary)
Variable types: 2334 continuous, 6116 integer (6116 binary)
Root relaxation: objective -8.344752e+01, 2395 iterations, 0.17 seconds (0.17 work units)
Root relaxation: objective -8.344752e+01, 2395 iterations, 0.17 seconds (0.17 work units)
Nodes | Current Node | Objective Bounds | Work
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -83.44752 0 65 - -83.44752 - - 0s
0 0 -83.44752 0 65 - -83.44752 - - 0s
H 0 0 -55.3928032 -83.44752 50.6% - 0s
H 0 0 -55.3928032 -83.44752 50.6% - 0s
H 0 0 -81.3146530 -83.44752 2.62% - 0s
H 0 0 -81.3146530 -83.44752 2.62% - 0s
0 0 -82.68413 0 155 -81.31465 -82.68413 1.68% - 1s
0 0 -82.68413 0 155 -81.31465 -82.68413 1.68% - 1s
H 0 0 -81.3246732 -82.66281 1.65% - 1s
H 0 0 -81.3246732 -82.66281 1.65% - 1s
0 0 -82.55335 0 115 -81.32467 -82.55335 1.51% - 1s
0 0 -82.55335 0 115 -81.32467 -82.55335 1.51% - 1s
0 0 -82.47886 0 114 -81.32467 -82.47886 1.42% - 1s
0 0 -82.47886 0 114 -81.32467 -82.47886 1.42% - 1s
0 0 -82.47886 0 119 -81.32467 -82.47886 1.42% - 1s
0 0 -82.47886 0 119 -81.32467 -82.47886 1.42% - 1s
0 0 -82.47886 0 117 -81.32467 -82.47886 1.42% - 1s
0 0 -82.47886 0 117 -81.32467 -82.47886 1.42% - 1s
0 0 -82.44284 0 179 -81.32467 -82.44284 1.37% - 2s
0 0 -82.44284 0 179 -81.32467 -82.44284 1.37% - 2s
H 0 0 -81.4146530 -82.25942 1.04% - 2s
H 0 0 -81.4146530 -82.25942 1.04% - 2s
0 0 -82.25942 0 111 -81.41465 -82.25942 1.04% - 2s
0 0 -82.25942 0 111 -81.41465 -82.25942 1.04% - 2s
0 0 -82.23806 0 95 -81.41465 -82.23806 1.01% - 2s
0 0 -82.23806 0 95 -81.41465 -82.23806 1.01% - 2s
0 0 -82.23806 0 160 -81.41465 -82.23806 1.01% - 2s
0 0 -82.23806 0 160 -81.41465 -82.23806 1.01% - 2s
0 0 -82.23806 0 160 -81.41465 -82.23806 1.01% - 2s
0 0 -82.23806 0 160 -81.41465 -82.23806 1.01% - 2s
0 0 -82.23806 0 170 -81.41465 -82.23806 1.01% - 2s
0 0 -82.23806 0 170 -81.41465 -82.23806 1.01% - 2s
0 0 -82.23806 0 105 -81.41465 -82.23806 1.01% - 2s
0 0 -82.23806 0 105 -81.41465 -82.23806 1.01% - 2s
0 0 -82.23806 0 111 -81.41465 -82.23806 1.01% - 3s
0 0 -82.23806 0 111 -81.41465 -82.23806 1.01% - 3s
H 0 0 -81.4286262 -82.23806 0.99% - 3s
H 0 0 -81.4286262 -82.23806 0.99% - 3s
0 0 -82.23806 0 73 -81.42863 -82.23806 0.99% - 3s
0 0 -82.23806 0 73 -81.42863 -82.23806 0.99% - 3s
0 0 -82.23806 0 52 -81.42863 -82.23806 0.99% - 3s
0 0 -82.23806 0 52 -81.42863 -82.23806 0.99% - 3s
0 0 -82.23806 0 46 -81.42863 -82.23806 0.99% - 3s
0 0 -82.23806 0 46 -81.42863 -82.23806 0.99% - 3s
0 0 -82.23806 0 56 -81.42863 -82.23806 0.99% - 3s
0 0 -82.23806 0 56 -81.42863 -82.23806 0.99% - 3s
0 0 -82.23806 0 52 -81.42863 -82.23806 0.99% - 3s
0 0 -82.23806 0 52 -81.42863 -82.23806 0.99% - 3s
0 0 -82.23754 0 60 -81.42863 -82.23754 0.99% - 3s
0 0 -82.23754 0 60 -81.42863 -82.23754 0.99% - 3s
0 0 -82.23235 0 151 -81.42863 -82.23235 0.99% - 3s
0 0 -82.23235 0 151 -81.42863 -82.23235 0.99% - 3s
0 0 -82.20956 0 164 -81.42863 -82.20956 0.96% - 3s
0 0 -82.20956 0 164 -81.42863 -82.20956 0.96% - 3s
0 0 -82.20423 0 140 -81.42863 -82.20423 0.95% - 3s
0 0 -82.20423 0 140 -81.42863 -82.20423 0.95% - 3s
0 0 -82.20423 0 140 -81.42863 -82.20423 0.95% - 3s
0 0 -82.20423 0 140 -81.42863 -82.20423 0.95% - 3s
0 0 -82.08249 0 138 -81.42863 -82.08249 0.80% - 4s
0 0 -82.08249 0 138 -81.42863 -82.08249 0.80% - 4s
0 0 -82.07861 0 138 -81.42863 -82.07861 0.80% - 4s
0 0 -82.07861 0 138 -81.42863 -82.07861 0.80% - 4s
0 0 -82.07861 0 141 -81.42863 -82.07861 0.80% - 4s
0 0 -82.07861 0 141 -81.42863 -82.07861 0.80% - 4s
0 0 -82.07337 0 181 -81.42863 -82.07337 0.79% - 4s
0 0 -82.07337 0 181 -81.42863 -82.07337 0.79% - 4s
0 0 -82.07111 0 184 -81.42863 -82.07111 0.79% - 4s
0 0 -82.07111 0 184 -81.42863 -82.07111 0.79% - 4s
0 0 -82.07087 0 183 -81.42863 -82.07087 0.79% - 4s
0 0 -82.07087 0 183 -81.42863 -82.07087 0.79% - 4s
0 0 -82.06883 0 139 -81.42863 -82.06883 0.79% - 4s
0 0 -82.06883 0 139 -81.42863 -82.06883 0.79% - 4s
0 0 -82.06826 0 172 -81.42863 -82.06826 0.79% - 4s
0 0 -82.06826 0 172 -81.42863 -82.06826 0.79% - 4s
0 0 -82.06706 0 153 -81.42863 -82.06706 0.78% - 4s
0 0 -82.06706 0 153 -81.42863 -82.06706 0.78% - 4s
0 0 -82.06639 0 169 -81.42863 -82.06639 0.78% - 4s
0 0 -82.06639 0 169 -81.42863 -82.06639 0.78% - 4s
0 0 -82.06632 0 129 -81.42863 -82.06632 0.78% - 4s
0 0 -82.06632 0 129 -81.42863 -82.06632 0.78% - 4s
0 0 -82.06620 0 170 -81.42863 -82.06620 0.78% - 4s
0 0 -82.06620 0 170 -81.42863 -82.06620 0.78% - 4s
0 0 -82.06246 0 173 -81.42863 -82.06246 0.78% - 4s
0 0 -82.06246 0 173 -81.42863 -82.06246 0.78% - 4s
0 0 -82.06246 0 176 -81.42863 -82.06246 0.78% - 4s
0 0 -82.06246 0 176 -81.42863 -82.06246 0.78% - 4s
0 0 -82.06246 0 173 -81.42863 -82.06246 0.78% - 4s
0 0 -82.06246 0 173 -81.42863 -82.06246 0.78% - 4s
0 2 -82.02715 0 170 -81.42863 -82.02715 0.74% - 4s
0 2 -82.02715 0 170 -81.42863 -82.02715 0.74% - 4s
19 5 -81.88002 5 52 -81.42863 -81.90671 0.59% 166 5s
19 5 -81.88002 5 52 -81.42863 -81.90671 0.59% 166 5s
Cutting planes:
Cutting planes:
Cover: 36
Cover: 36
Implied bound: 23
Implied bound: 23
MIR: 5
MIR: 5
Flow cover: 13
Flow cover: 13
Zero half: 9
Zero half: 9
Network: 1
Network: 1
RLT: 8
RLT: 8
Relax-and-lift: 1
Relax-and-lift: 1
Explored 68 nodes (18108 simplex iterations) in 5.55 seconds (2.90 work units)
Explored 68 nodes (18108 simplex iterations) in 5.55 seconds (2.90 work units)
Thread count was 12 (of 12 available processors)
Thread count was 12 (of 12 available processors)
Solution count 5: -81.4286 -81.4147 -81.3247 ... -55.3928
Solution count 5: -81.4286 -81.4147 -81.3247 ... -55.3928
No other solutions better than -81.4286
No other solutions better than -81.4286
Optimal solution found (tolerance 1.00e-04)
Optimal solution found (tolerance 1.00e-04)
Best objective -8.142862616577e+01, best bound -8.142862616577e+01, gap 0.0000%
Best objective -8.142862616577e+01, best bound -8.142862616577e+01, gap 0.0000%
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:07 PM: Problem status: optimal
(CVXPY) Apr 11 04:47:07 PM: Optimal value: 7.584e+00
(CVXPY) Apr 11 04:47:07 PM: Compilation took 7.997e-02 seconds
(CVXPY) Apr 11 04:47:07 PM: Solver (including time spent in interface) took 5.713e+00 seconds
Solution summary:
- Loss (unfitted inputs/output): [0.]
- Edge penalty error: 34.0
- Node penalty error: 4.024977342756888
Run 1 with seed 1338
Building CORNETO problem...
Solving with gurobi...
===============================================================================
CVXPY
v1.4.1
===============================================================================
(CVXPY) Apr 11 04:47:08 PM: Your problem has 9606 variables, 31 constraints, and 0 parameters.
(CVXPY) Apr 11 04:47:08 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Apr 11 04:47:08 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Apr 11 04:47:08 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Apr 11 04:47:08 PM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:08 PM: Compiling problem (target solver=GUROBI).
(CVXPY) Apr 11 04:47:08 PM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> GUROBI
(CVXPY) Apr 11 04:47:08 PM: Applying reduction CvxAttr2Constr
(CVXPY) Apr 11 04:47:08 PM: Applying reduction Qp2SymbolicQp
(CVXPY) Apr 11 04:47:08 PM: Applying reduction QpMatrixStuffing
(CVXPY) Apr 11 04:47:08 PM: Applying reduction GUROBI
(CVXPY) Apr 11 04:47:08 PM: Finished problem compilation (took 8.297e-02 seconds).
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:08 PM: Invoking solver GUROBI to obtain a solution.
Set parameter QCPDual to value 1
Set parameter QCPDual to value 1
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Model fingerprint: 0xa2237956
Model fingerprint: 0xa2237956
Variable types: 2535 continuous, 7071 integer (7071 binary)
Variable types: 2535 continuous, 7071 integer (7071 binary)
Coefficient statistics:
Coefficient statistics:
Matrix range [1e-03, 5e+02]
Matrix range [1e-03, 5e+02]
Objective range [5e-03, 2e+01]
Objective range [5e-03, 2e+01]
Bounds range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e-03, 5e+02]
RHS range [1e-03, 5e+02]
Presolve removed 24916 rows and 1156 columns
Presolve removed 24916 rows and 1156 columns
Presolve time: 0.19s
Presolve time: 0.19s
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Variable types: 2334 continuous, 6116 integer (6116 binary)
Variable types: 2334 continuous, 6116 integer (6116 binary)
Root relaxation: objective -8.343995e+01, 2038 iterations, 0.18 seconds (0.14 work units)
Root relaxation: objective -8.343995e+01, 2038 iterations, 0.18 seconds (0.14 work units)
Nodes | Current Node | Objective Bounds | Work
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -83.43995 0 69 - -83.43995 - - 0s
0 0 -83.43995 0 69 - -83.43995 - - 0s
0 0 -82.62368 0 118 - -82.62368 - - 0s
0 0 -82.62368 0 118 - -82.62368 - - 0s
H 0 0 -72.9188899 -82.58937 13.3% - 0s
H 0 0 -72.9188899 -82.58937 13.3% - 0s
H 0 0 -81.3969492 -82.58937 1.46% - 1s
H 0 0 -81.3969492 -82.58937 1.46% - 1s
0 0 -82.58937 0 112 -81.39695 -82.58937 1.46% - 1s
0 0 -82.58937 0 112 -81.39695 -82.58937 1.46% - 1s
0 0 -82.50646 0 188 -81.39695 -82.50646 1.36% - 1s
0 0 -82.50646 0 188 -81.39695 -82.50646 1.36% - 1s
0 0 -82.46819 0 194 -81.39695 -82.46819 1.32% - 1s
0 0 -82.46819 0 194 -81.39695 -82.46819 1.32% - 1s
0 0 -82.36505 0 121 -81.39695 -82.36505 1.19% - 1s
0 0 -82.36505 0 121 -81.39695 -82.36505 1.19% - 1s
0 0 -82.36505 0 60 -81.39695 -82.36505 1.19% - 1s
0 0 -82.36505 0 60 -81.39695 -82.36505 1.19% - 1s
0 0 -82.36505 0 136 -81.39695 -82.36505 1.19% - 1s
0 0 -82.36505 0 136 -81.39695 -82.36505 1.19% - 1s
0 0 -82.36505 0 131 -81.39695 -82.36505 1.19% - 2s
0 0 -82.36505 0 131 -81.39695 -82.36505 1.19% - 2s
0 0 -82.36298 0 110 -81.39695 -82.36298 1.19% - 2s
0 0 -82.36298 0 110 -81.39695 -82.36298 1.19% - 2s
0 0 -82.36093 0 120 -81.39695 -82.36093 1.18% - 2s
0 0 -82.36093 0 120 -81.39695 -82.36093 1.18% - 2s
0 0 -82.35928 0 120 -81.39695 -82.35928 1.18% - 2s
0 0 -82.35928 0 120 -81.39695 -82.35928 1.18% - 2s
0 0 -82.30727 0 152 -81.39695 -82.30727 1.12% - 2s
0 0 -82.30727 0 152 -81.39695 -82.30727 1.12% - 2s
0 0 -82.30126 0 158 -81.39695 -82.30126 1.11% - 2s
0 0 -82.30126 0 158 -81.39695 -82.30126 1.11% - 2s
0 0 -82.30126 0 161 -81.39695 -82.30126 1.11% - 2s
0 0 -82.30126 0 161 -81.39695 -82.30126 1.11% - 2s
0 0 -82.30126 0 157 -81.39695 -82.30126 1.11% - 2s
0 0 -82.30126 0 157 -81.39695 -82.30126 1.11% - 2s
0 0 -82.15235 0 173 -81.39695 -82.15235 0.93% - 2s
0 0 -82.15235 0 173 -81.39695 -82.15235 0.93% - 2s
0 0 -82.10662 0 179 -81.39695 -82.10662 0.87% - 2s
0 0 -82.10662 0 179 -81.39695 -82.10662 0.87% - 2s
0 0 -82.10228 0 144 -81.39695 -82.10228 0.87% - 2s
0 0 -82.10228 0 144 -81.39695 -82.10228 0.87% - 2s
0 0 -82.09393 0 172 -81.39695 -82.09393 0.86% - 2s
0 0 -82.09393 0 172 -81.39695 -82.09393 0.86% - 2s
0 0 -82.09114 0 189 -81.39695 -82.09114 0.85% - 2s
0 0 -82.09114 0 189 -81.39695 -82.09114 0.85% - 2s
0 0 -82.09114 0 189 -81.39695 -82.09114 0.85% - 2s
0 0 -82.09114 0 189 -81.39695 -82.09114 0.85% - 2s
0 0 -82.06353 0 211 -81.39695 -82.06353 0.82% - 2s
0 0 -82.06353 0 211 -81.39695 -82.06353 0.82% - 2s
0 0 -82.05648 0 211 -81.39695 -82.05648 0.81% - 2s
0 0 -82.05648 0 211 -81.39695 -82.05648 0.81% - 2s
0 0 -82.05648 0 211 -81.39695 -82.05648 0.81% - 2s
0 0 -82.05648 0 211 -81.39695 -82.05648 0.81% - 2s
0 0 -82.05648 0 218 -81.39695 -82.05648 0.81% - 2s
0 0 -82.05648 0 218 -81.39695 -82.05648 0.81% - 2s
0 0 -82.05501 0 216 -81.39695 -82.05501 0.81% - 2s
0 0 -82.05501 0 216 -81.39695 -82.05501 0.81% - 2s
0 0 -82.05501 0 216 -81.39695 -82.05501 0.81% - 2s
0 0 -82.05501 0 216 -81.39695 -82.05501 0.81% - 2s
0 0 -81.95658 0 228 -81.39695 -81.95658 0.69% - 3s
0 0 -81.95658 0 228 -81.39695 -81.95658 0.69% - 3s
0 0 -81.95545 0 228 -81.39695 -81.95545 0.69% - 3s
0 0 -81.95545 0 228 -81.39695 -81.95545 0.69% - 3s
0 0 -81.95264 0 227 -81.39695 -81.95264 0.68% - 3s
0 0 -81.95264 0 227 -81.39695 -81.95264 0.68% - 3s
0 0 -81.95264 0 229 -81.39695 -81.95264 0.68% - 3s
0 0 -81.95264 0 229 -81.39695 -81.95264 0.68% - 3s
H 0 0 -81.4109660 -81.95264 0.67% - 3s
H 0 0 -81.4109660 -81.95264 0.67% - 3s
0 0 -81.89571 0 235 -81.41097 -81.89571 0.60% - 3s
0 0 -81.89571 0 235 -81.41097 -81.89571 0.60% - 3s
0 0 -81.89571 0 232 -81.41097 -81.89571 0.60% - 3s
0 0 -81.89571 0 232 -81.41097 -81.89571 0.60% - 3s
0 0 -81.89571 0 221 -81.41097 -81.89571 0.60% - 3s
0 0 -81.89571 0 221 -81.41097 -81.89571 0.60% - 3s
H 0 0 -81.4182258 -81.89571 0.59% - 3s
H 0 0 -81.4182258 -81.89571 0.59% - 3s
0 2 -81.89418 0 220 -81.41823 -81.89418 0.58% - 3s
0 2 -81.89418 0 220 -81.41823 -81.89418 0.58% - 3s
Cutting planes:
Cutting planes:
Gomory: 1
Gomory: 1
Cover: 48
Cover: 48
Implied bound: 33
Implied bound: 33
Clique: 5
Clique: 5
MIR: 6
MIR: 6
Flow cover: 14
Flow cover: 14
GUB cover: 1
GUB cover: 1
Inf proof: 1
Inf proof: 1
Zero half: 11
Zero half: 11
Network: 2
Network: 2
RLT: 16
RLT: 16
Relax-and-lift: 3
Relax-and-lift: 3
Explored 60 nodes (18936 simplex iterations) in 4.48 seconds (2.60 work units)
Explored 60 nodes (18936 simplex iterations) in 4.48 seconds (2.60 work units)
Thread count was 12 (of 12 available processors)
Thread count was 12 (of 12 available processors)
Solution count 4: -81.4182 -81.411 -81.3969 -72.9189
Solution count 4: -81.4182 -81.411 -81.3969 -72.9189
No other solutions better than -81.4182
No other solutions better than -81.4182
Optimal solution found (tolerance 1.00e-04)
Optimal solution found (tolerance 1.00e-04)
Best objective -8.141822581299e+01, best bound -8.141822581299e+01, gap 0.0000%
Best objective -8.141822581299e+01, best bound -8.141822581299e+01, gap 0.0000%
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:13 PM: Problem status: optimal
(CVXPY) Apr 11 04:47:13 PM: Optimal value: 7.594e+00
(CVXPY) Apr 11 04:47:13 PM: Compilation took 8.297e-02 seconds
(CVXPY) Apr 11 04:47:13 PM: Solver (including time spent in interface) took 4.691e+00 seconds
Solution summary:
- Loss (unfitted inputs/output): [0.]
- Edge penalty error: 34.0
- Node penalty error: 4.023671669805017
Run 2 with seed 1339
Building CORNETO problem...
Solving with gurobi...
===============================================================================
CVXPY
v1.4.1
===============================================================================
(CVXPY) Apr 11 04:47:13 PM: Your problem has 9606 variables, 31 constraints, and 0 parameters.
(CVXPY) Apr 11 04:47:13 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Apr 11 04:47:13 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Apr 11 04:47:13 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Apr 11 04:47:13 PM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:13 PM: Compiling problem (target solver=GUROBI).
(CVXPY) Apr 11 04:47:13 PM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> GUROBI
(CVXPY) Apr 11 04:47:13 PM: Applying reduction CvxAttr2Constr
(CVXPY) Apr 11 04:47:13 PM: Applying reduction Qp2SymbolicQp
(CVXPY) Apr 11 04:47:13 PM: Applying reduction QpMatrixStuffing
(CVXPY) Apr 11 04:47:13 PM: Applying reduction GUROBI
(CVXPY) Apr 11 04:47:13 PM: Finished problem compilation (took 1.064e-01 seconds).
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:13 PM: Invoking solver GUROBI to obtain a solution.
Set parameter QCPDual to value 1
Set parameter QCPDual to value 1
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Model fingerprint: 0x7094fc5f
Model fingerprint: 0x7094fc5f
Variable types: 2535 continuous, 7071 integer (7071 binary)
Variable types: 2535 continuous, 7071 integer (7071 binary)
Coefficient statistics:
Coefficient statistics:
Matrix range [1e-03, 5e+02]
Matrix range [1e-03, 5e+02]
Objective range [5e-03, 2e+01]
Objective range [5e-03, 2e+01]
Bounds range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e-03, 5e+02]
RHS range [1e-03, 5e+02]
Presolve removed 24916 rows and 1156 columns
Presolve removed 24916 rows and 1156 columns
Presolve time: 0.19s
Presolve time: 0.19s
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Variable types: 2334 continuous, 6116 integer (6116 binary)
Variable types: 2334 continuous, 6116 integer (6116 binary)
Root relaxation: objective -8.344229e+01, 2123 iterations, 0.16 seconds (0.15 work units)
Root relaxation: objective -8.344229e+01, 2123 iterations, 0.16 seconds (0.15 work units)
Nodes | Current Node | Objective Bounds | Work
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -83.44229 0 65 - -83.44229 - - 0s
0 0 -83.44229 0 65 - -83.44229 - - 0s
0 0 -82.69675 0 150 - -82.69675 - - 0s
0 0 -82.69675 0 150 - -82.69675 - - 0s
H 0 0 -72.6255193 -82.65821 13.8% - 0s
H 0 0 -72.6255193 -82.65821 13.8% - 0s
H 0 0 -81.2100740 -82.65821 1.78% - 1s
H 0 0 -81.2100740 -82.65821 1.78% - 1s
0 0 -82.65821 0 150 -81.21007 -82.65821 1.78% - 1s
0 0 -82.65821 0 150 -81.21007 -82.65821 1.78% - 1s
0 0 -82.52719 0 170 -81.21007 -82.52719 1.62% - 1s
0 0 -82.52719 0 170 -81.21007 -82.52719 1.62% - 1s
0 0 -82.48950 0 170 -81.21007 -82.48950 1.58% - 1s
0 0 -82.48950 0 170 -81.21007 -82.48950 1.58% - 1s
H 0 0 -81.3100740 -82.48950 1.45% - 1s
H 0 0 -81.3100740 -82.48950 1.45% - 1s
0 0 -82.40373 0 169 -81.31007 -82.40373 1.35% - 1s
0 0 -82.40373 0 169 -81.31007 -82.40373 1.35% - 1s
0 0 -82.40373 0 169 -81.31007 -82.40373 1.35% - 1s
0 0 -82.40373 0 169 -81.31007 -82.40373 1.35% - 1s
0 0 -82.33198 0 125 -81.31007 -82.33198 1.26% - 1s
0 0 -82.33198 0 125 -81.31007 -82.33198 1.26% - 1s
0 0 -82.24227 0 124 -81.31007 -82.24227 1.15% - 1s
0 0 -82.24227 0 124 -81.31007 -82.24227 1.15% - 1s
0 0 -82.24227 0 52 -81.31007 -82.24227 1.15% - 2s
0 0 -82.24227 0 52 -81.31007 -82.24227 1.15% - 2s
H 0 0 -81.4100740 -82.24227 1.02% - 2s
H 0 0 -81.4100740 -82.24227 1.02% - 2s
0 0 -82.24227 0 93 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 93 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 90 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 90 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 148 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 148 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 100 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 100 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 100 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 100 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 94 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 94 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 150 -81.41007 -82.24227 1.02% - 2s
0 0 -82.24227 0 150 -81.41007 -82.24227 1.02% - 2s
0 0 -82.21235 0 158 -81.41007 -82.21235 0.99% - 2s
0 0 -82.21235 0 158 -81.41007 -82.21235 0.99% - 2s
0 0 -82.19809 0 159 -81.41007 -82.19809 0.97% - 3s
0 0 -82.19809 0 159 -81.41007 -82.19809 0.97% - 3s
0 0 -82.09974 0 176 -81.41007 -82.09974 0.85% - 3s
0 0 -82.09974 0 176 -81.41007 -82.09974 0.85% - 3s
0 0 -82.08210 0 154 -81.41007 -82.08210 0.83% - 3s
0 0 -82.08210 0 154 -81.41007 -82.08210 0.83% - 3s
0 0 -82.07891 0 179 -81.41007 -82.07891 0.82% - 3s
0 0 -82.07891 0 179 -81.41007 -82.07891 0.82% - 3s
0 0 -82.07842 0 193 -81.41007 -82.07842 0.82% - 3s
0 0 -82.07842 0 193 -81.41007 -82.07842 0.82% - 3s
H 0 0 -81.4286938 -82.07841 0.80% - 3s
H 0 0 -81.4286938 -82.07841 0.80% - 3s
0 0 -82.07841 0 194 -81.42869 -82.07841 0.80% - 3s
0 0 -82.07841 0 194 -81.42869 -82.07841 0.80% - 3s
0 0 -81.99868 0 95 -81.42869 -81.99868 0.70% - 3s
0 0 -81.99868 0 95 -81.42869 -81.99868 0.70% - 3s
0 0 -81.97528 0 172 -81.42869 -81.97528 0.67% - 3s
0 0 -81.97528 0 172 -81.42869 -81.97528 0.67% - 3s
0 0 -81.97528 0 167 -81.42869 -81.97528 0.67% - 3s
0 0 -81.97528 0 167 -81.42869 -81.97528 0.67% - 3s
0 0 -81.97528 0 173 -81.42869 -81.97528 0.67% - 3s
0 0 -81.97528 0 173 -81.42869 -81.97528 0.67% - 3s
0 0 -81.97528 0 210 -81.42869 -81.97528 0.67% - 4s
0 0 -81.97528 0 210 -81.42869 -81.97528 0.67% - 4s
0 0 -81.97528 0 211 -81.42869 -81.97528 0.67% - 4s
0 0 -81.97528 0 211 -81.42869 -81.97528 0.67% - 4s
0 0 -81.97528 0 223 -81.42869 -81.97528 0.67% - 4s
0 0 -81.97528 0 223 -81.42869 -81.97528 0.67% - 4s
0 0 -81.97528 0 224 -81.42869 -81.97528 0.67% - 4s
0 0 -81.97528 0 224 -81.42869 -81.97528 0.67% - 4s
0 0 -81.88779 0 220 -81.42869 -81.88779 0.56% - 4s
0 0 -81.88779 0 220 -81.42869 -81.88779 0.56% - 4s
0 0 -81.88127 0 202 -81.42869 -81.88127 0.56% - 4s
0 0 -81.88127 0 202 -81.42869 -81.88127 0.56% - 4s
0 0 -81.88127 0 196 -81.42869 -81.88127 0.56% - 4s
0 0 -81.88127 0 196 -81.42869 -81.88127 0.56% - 4s
0 0 -81.88127 0 204 -81.42869 -81.88127 0.56% - 4s
0 0 -81.88127 0 204 -81.42869 -81.88127 0.56% - 4s
0 0 -81.88012 0 207 -81.42869 -81.88012 0.55% - 4s
0 0 -81.88012 0 207 -81.42869 -81.88012 0.55% - 4s
0 0 -81.88012 0 211 -81.42869 -81.88012 0.55% - 4s
0 0 -81.88012 0 211 -81.42869 -81.88012 0.55% - 4s
0 0 -81.88012 0 211 -81.42869 -81.88012 0.55% - 4s
0 0 -81.88012 0 211 -81.42869 -81.88012 0.55% - 4s
0 2 -81.81408 0 211 -81.42869 -81.81408 0.47% - 5s
0 2 -81.81408 0 211 -81.42869 -81.81408 0.47% - 5s
Cutting planes:
Cutting planes:
Gomory: 1
Gomory: 1
Cover: 52
Cover: 52
Implied bound: 29
Implied bound: 29
Clique: 2
Clique: 2
MIR: 7
MIR: 7
Flow cover: 14
Flow cover: 14
GUB cover: 3
GUB cover: 3
Zero half: 9
Zero half: 9
Network: 5
Network: 5
RLT: 12
RLT: 12
Relax-and-lift: 2
Relax-and-lift: 2
Explored 43 nodes (18299 simplex iterations) in 6.50 seconds (2.78 work units)
Explored 43 nodes (18299 simplex iterations) in 6.50 seconds (2.78 work units)
Thread count was 12 (of 12 available processors)
Thread count was 12 (of 12 available processors)
Solution count 5: -81.4287 -81.4101 -81.3101 ... -72.6255
Solution count 5: -81.4287 -81.4101 -81.3101 ... -72.6255
No other solutions better than -81.4287
No other solutions better than -81.4287
Optimal solution found (tolerance 1.00e-04)
Optimal solution found (tolerance 1.00e-04)
Best objective -8.142869384455e+01, best bound -8.142869384455e+01, gap 0.0000%
Best objective -8.142869384455e+01, best bound -8.142869384455e+01, gap 0.0000%
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:20 PM: Problem status: optimal
(CVXPY) Apr 11 04:47:20 PM: Optimal value: 7.584e+00
(CVXPY) Apr 11 04:47:20 PM: Compilation took 1.064e-01 seconds
(CVXPY) Apr 11 04:47:20 PM: Solver (including time spent in interface) took 6.738e+00 seconds
Solution summary:
- Loss (unfitted inputs/output): [0.]
- Edge penalty error: 34.0
- Node penalty error: 4.024044927147559
Run 3 with seed 1340
Building CORNETO problem...
Solving with gurobi...
===============================================================================
CVXPY
v1.4.1
===============================================================================
(CVXPY) Apr 11 04:47:20 PM: Your problem has 9606 variables, 31 constraints, and 0 parameters.
(CVXPY) Apr 11 04:47:20 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Apr 11 04:47:20 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Apr 11 04:47:20 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Apr 11 04:47:20 PM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:20 PM: Compiling problem (target solver=GUROBI).
(CVXPY) Apr 11 04:47:20 PM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> GUROBI
(CVXPY) Apr 11 04:47:20 PM: Applying reduction CvxAttr2Constr
(CVXPY) Apr 11 04:47:20 PM: Applying reduction Qp2SymbolicQp
(CVXPY) Apr 11 04:47:21 PM: Applying reduction QpMatrixStuffing
(CVXPY) Apr 11 04:47:21 PM: Applying reduction GUROBI
(CVXPY) Apr 11 04:47:21 PM: Finished problem compilation (took 1.229e-01 seconds).
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:21 PM: Invoking solver GUROBI to obtain a solution.
Set parameter QCPDual to value 1
Set parameter QCPDual to value 1
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Model fingerprint: 0x61842000
Model fingerprint: 0x61842000
Variable types: 2535 continuous, 7071 integer (7071 binary)
Variable types: 2535 continuous, 7071 integer (7071 binary)
Coefficient statistics:
Coefficient statistics:
Matrix range [1e-03, 5e+02]
Matrix range [1e-03, 5e+02]
Objective range [5e-03, 2e+01]
Objective range [5e-03, 2e+01]
Bounds range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e-03, 5e+02]
RHS range [1e-03, 5e+02]
Presolve removed 24916 rows and 1156 columns
Presolve removed 24916 rows and 1156 columns
Presolve time: 0.18s
Presolve time: 0.18s
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Variable types: 2334 continuous, 6116 integer (6116 binary)
Variable types: 2334 continuous, 6116 integer (6116 binary)
Root relaxation: objective -8.345034e+01, 2360 iterations, 0.23 seconds (0.17 work units)
Root relaxation: objective -8.345034e+01, 2360 iterations, 0.23 seconds (0.17 work units)
Nodes | Current Node | Objective Bounds | Work
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -83.45034 0 65 - -83.45034 - - 0s
0 0 -83.45034 0 65 - -83.45034 - - 0s
H 0 0 -53.0883069 -83.45012 57.2% - 0s
H 0 0 -53.0883069 -83.45012 57.2% - 0s
H 0 0 -63.2256589 -82.70076 30.8% - 0s
H 0 0 -63.2256589 -82.70076 30.8% - 0s
0 0 -82.70076 0 151 -63.22566 -82.70076 30.8% - 0s
0 0 -82.70076 0 151 -63.22566 -82.70076 30.8% - 0s
H 0 0 -72.6326000 -82.66267 13.8% - 0s
H 0 0 -72.6326000 -82.66267 13.8% - 0s
H 0 0 -81.2324788 -82.66267 1.76% - 1s
H 0 0 -81.2324788 -82.66267 1.76% - 1s
0 0 -82.66267 0 165 -81.23248 -82.66267 1.76% - 1s
0 0 -82.66267 0 165 -81.23248 -82.66267 1.76% - 1s
H 0 0 -81.2348114 -82.50892 1.57% - 1s
H 0 0 -81.2348114 -82.50892 1.57% - 1s
H 0 0 -81.3301869 -82.50892 1.45% - 1s
H 0 0 -81.3301869 -82.50892 1.45% - 1s
0 0 -82.50892 0 179 -81.33019 -82.50892 1.45% - 1s
0 0 -82.50892 0 179 -81.33019 -82.50892 1.45% - 1s
0 0 -82.50198 0 170 -81.33019 -82.50198 1.44% - 1s
0 0 -82.50198 0 170 -81.33019 -82.50198 1.44% - 1s
0 0 -82.50198 0 170 -81.33019 -82.50198 1.44% - 1s
0 0 -82.50198 0 170 -81.33019 -82.50198 1.44% - 1s
0 0 -82.44503 0 163 -81.33019 -82.44503 1.37% - 2s
0 0 -82.44503 0 163 -81.33019 -82.44503 1.37% - 2s
0 0 -82.44183 0 163 -81.33019 -82.44183 1.37% - 2s
0 0 -82.44183 0 163 -81.33019 -82.44183 1.37% - 2s
0 0 -82.37595 0 169 -81.33019 -82.37595 1.29% - 2s
0 0 -82.37595 0 169 -81.33019 -82.37595 1.29% - 2s
0 0 -82.35582 0 162 -81.33019 -82.35582 1.26% - 2s
0 0 -82.35582 0 162 -81.33019 -82.35582 1.26% - 2s
0 0 -82.35335 0 161 -81.33019 -82.35335 1.26% - 2s
0 0 -82.35335 0 161 -81.33019 -82.35335 1.26% - 2s
0 0 -82.35335 0 161 -81.33019 -82.35335 1.26% - 2s
0 0 -82.35335 0 161 -81.33019 -82.35335 1.26% - 2s
0 0 -82.24777 0 165 -81.33019 -82.24777 1.13% - 2s
0 0 -82.24777 0 165 -81.33019 -82.24777 1.13% - 2s
0 0 -82.24777 0 57 -81.33019 -82.24777 1.13% - 3s
0 0 -82.24777 0 57 -81.33019 -82.24777 1.13% - 3s
H 0 0 -81.4154826 -82.24777 1.02% - 3s
H 0 0 -81.4154826 -82.24777 1.02% - 3s
0 0 -82.24777 0 125 -81.41548 -82.24777 1.02% - 3s
0 0 -82.24777 0 125 -81.41548 -82.24777 1.02% - 3s
0 0 -82.24777 0 138 -81.41548 -82.24777 1.02% - 3s
0 0 -82.24777 0 138 -81.41548 -82.24777 1.02% - 3s
0 0 -82.24777 0 170 -81.41548 -82.24777 1.02% - 4s
0 0 -82.24777 0 170 -81.41548 -82.24777 1.02% - 4s
0 0 -82.24777 0 146 -81.41548 -82.24777 1.02% - 4s
0 0 -82.24777 0 146 -81.41548 -82.24777 1.02% - 4s
0 0 -82.24777 0 146 -81.41548 -82.24777 1.02% - 4s
0 0 -82.24777 0 146 -81.41548 -82.24777 1.02% - 4s
0 0 -82.24777 0 167 -81.41548 -82.24777 1.02% - 4s
0 0 -82.24777 0 167 -81.41548 -82.24777 1.02% - 4s
0 0 -82.22879 0 165 -81.41548 -82.22879 1.00% - 4s
0 0 -82.22879 0 165 -81.41548 -82.22879 1.00% - 4s
0 0 -82.22879 0 165 -81.41548 -82.22879 1.00% - 4s
0 0 -82.22879 0 165 -81.41548 -82.22879 1.00% - 4s
0 0 -82.20482 0 132 -81.41548 -82.20482 0.97% - 4s
0 0 -82.20482 0 132 -81.41548 -82.20482 0.97% - 4s
H 0 0 -81.4301869 -82.19502 0.94% - 4s
H 0 0 -81.4301869 -82.19502 0.94% - 4s
0 0 -82.19502 0 157 -81.43019 -82.19502 0.94% - 4s
0 0 -82.19502 0 157 -81.43019 -82.19502 0.94% - 4s
0 0 -82.18681 0 185 -81.43019 -82.18681 0.93% - 4s
0 0 -82.18681 0 185 -81.43019 -82.18681 0.93% - 4s
0 0 -82.05096 0 164 -81.43019 -82.05096 0.76% - 5s
0 0 -82.05096 0 164 -81.43019 -82.05096 0.76% - 5s
0 0 -82.04386 0 183 -81.43019 -82.04386 0.75% - 5s
0 0 -82.04386 0 183 -81.43019 -82.04386 0.75% - 5s
0 0 -82.04081 0 173 -81.43019 -82.04081 0.75% - 5s
0 0 -82.04081 0 173 -81.43019 -82.04081 0.75% - 5s
0 0 -82.04011 0 174 -81.43019 -82.04011 0.75% - 5s
0 0 -82.04011 0 174 -81.43019 -82.04011 0.75% - 5s
0 0 -81.95340 0 144 -81.43019 -81.95340 0.64% - 5s
0 0 -81.95340 0 144 -81.43019 -81.95340 0.64% - 5s
H 0 0 -81.4348114 -81.94810 0.63% - 5s
H 0 0 -81.4348114 -81.94810 0.63% - 5s
0 0 -81.94810 0 156 -81.43481 -81.94810 0.63% - 5s
0 0 -81.94810 0 156 -81.43481 -81.94810 0.63% - 5s
0 0 -81.94810 0 154 -81.43481 -81.94810 0.63% - 5s
0 0 -81.94810 0 154 -81.43481 -81.94810 0.63% - 5s
0 0 -81.94766 0 102 -81.43481 -81.94766 0.63% - 5s
0 0 -81.94766 0 102 -81.43481 -81.94766 0.63% - 5s
0 0 -81.94000 0 163 -81.43481 -81.94000 0.62% - 5s
0 0 -81.94000 0 163 -81.43481 -81.94000 0.62% - 5s
0 0 -81.93783 0 216 -81.43481 -81.93783 0.62% - 5s
0 0 -81.93783 0 216 -81.43481 -81.93783 0.62% - 5s
0 0 -81.93759 0 200 -81.43481 -81.93759 0.62% - 5s
0 0 -81.93759 0 200 -81.43481 -81.93759 0.62% - 5s
0 0 -81.93172 0 184 -81.43481 -81.93172 0.61% - 6s
0 0 -81.93172 0 184 -81.43481 -81.93172 0.61% - 6s
0 0 -81.92808 0 180 -81.43481 -81.92808 0.61% - 6s
0 0 -81.92808 0 180 -81.43481 -81.92808 0.61% - 6s
0 0 -81.92800 0 202 -81.43481 -81.92800 0.61% - 6s
0 0 -81.92800 0 202 -81.43481 -81.92800 0.61% - 6s
0 0 -81.92796 0 205 -81.43481 -81.92796 0.61% - 6s
0 0 -81.92796 0 205 -81.43481 -81.92796 0.61% - 6s
0 0 -81.92483 0 208 -81.43481 -81.92483 0.60% - 6s
0 0 -81.92483 0 208 -81.43481 -81.92483 0.60% - 6s
0 0 -81.92483 0 214 -81.43481 -81.92483 0.60% - 6s
0 0 -81.92483 0 214 -81.43481 -81.92483 0.60% - 6s
0 0 -81.92483 0 214 -81.43481 -81.92483 0.60% - 6s
0 0 -81.92483 0 214 -81.43481 -81.92483 0.60% - 6s
0 0 -81.92483 0 211 -81.43481 -81.92483 0.60% - 6s
0 0 -81.92483 0 211 -81.43481 -81.92483 0.60% - 6s
0 2 -81.91435 0 209 -81.43481 -81.91435 0.59% - 6s
0 2 -81.91435 0 209 -81.43481 -81.91435 0.59% - 6s
Cutting planes:
Cutting planes:
Learned: 1
Learned: 1
Gomory: 1
Gomory: 1
Cover: 49
Cover: 49
Implied bound: 38
Implied bound: 38
Clique: 3
Clique: 3
MIR: 7
MIR: 7
Flow cover: 11
Flow cover: 11
GUB cover: 1
GUB cover: 1
Zero half: 11
Zero half: 11
Mod-K: 2
Mod-K: 2
Network: 4
Network: 4
RLT: 11
RLT: 11
Relax-and-lift: 2
Relax-and-lift: 2
Explored 76 nodes (21554 simplex iterations) in 8.64 seconds (3.09 work units)
Explored 76 nodes (21554 simplex iterations) in 8.64 seconds (3.09 work units)
Thread count was 12 (of 12 available processors)
Thread count was 12 (of 12 available processors)
Solution count 9: -81.4348 -81.4302 -81.4155 ... -53.0883
Solution count 9: -81.4348 -81.4302 -81.4155 ... -53.0883
No other solutions better than -81.4348
No other solutions better than -81.4348
Optimal solution found (tolerance 1.00e-04)
Optimal solution found (tolerance 1.00e-04)
Best objective -8.143481144440e+01, best bound -8.143481144440e+01, gap 0.0000%
Best objective -8.143481144440e+01, best bound -8.143481144440e+01, gap 0.0000%
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:30 PM: Problem status: optimal
(CVXPY) Apr 11 04:47:30 PM: Optimal value: 7.578e+00
(CVXPY) Apr 11 04:47:30 PM: Compilation took 1.229e-01 seconds
(CVXPY) Apr 11 04:47:30 PM: Solver (including time spent in interface) took 8.868e+00 seconds
Solution summary:
- Loss (unfitted inputs/output): [0.]
- Edge penalty error: 34.0
- Node penalty error: 4.024687672012542
Run 4 with seed 1341
Building CORNETO problem...
Solving with gurobi...
===============================================================================
CVXPY
v1.4.1
===============================================================================
(CVXPY) Apr 11 04:47:30 PM: Your problem has 9606 variables, 31 constraints, and 0 parameters.
(CVXPY) Apr 11 04:47:30 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Apr 11 04:47:30 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Apr 11 04:47:30 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Apr 11 04:47:30 PM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:30 PM: Compiling problem (target solver=GUROBI).
(CVXPY) Apr 11 04:47:30 PM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> GUROBI
(CVXPY) Apr 11 04:47:30 PM: Applying reduction CvxAttr2Constr
(CVXPY) Apr 11 04:47:30 PM: Applying reduction Qp2SymbolicQp
(CVXPY) Apr 11 04:47:30 PM: Applying reduction QpMatrixStuffing
(CVXPY) Apr 11 04:47:30 PM: Applying reduction GUROBI
(CVXPY) Apr 11 04:47:30 PM: Finished problem compilation (took 1.481e-01 seconds).
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:30 PM: Invoking solver GUROBI to obtain a solution.
Set parameter QCPDual to value 1
Set parameter QCPDual to value 1
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Model fingerprint: 0x02123258
Model fingerprint: 0x02123258
Variable types: 2535 continuous, 7071 integer (7071 binary)
Variable types: 2535 continuous, 7071 integer (7071 binary)
Coefficient statistics:
Coefficient statistics:
Matrix range [1e-03, 5e+02]
Matrix range [1e-03, 5e+02]
Objective range [5e-03, 2e+01]
Objective range [5e-03, 2e+01]
Bounds range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e-03, 5e+02]
RHS range [1e-03, 5e+02]
Presolve removed 24916 rows and 1156 columns
Presolve removed 24916 rows and 1156 columns
Presolve time: 0.53s
Presolve time: 0.53s
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Variable types: 2334 continuous, 6116 integer (6116 binary)
Variable types: 2334 continuous, 6116 integer (6116 binary)
Root relaxation: objective -8.344120e+01, 2356 iterations, 0.34 seconds (0.16 work units)
Root relaxation: objective -8.344120e+01, 2356 iterations, 0.34 seconds (0.16 work units)
Nodes | Current Node | Objective Bounds | Work
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -83.44120 0 65 - -83.44120 - - 1s
0 0 -83.44120 0 65 - -83.44120 - - 1s
H 0 0 -65.1158686 -83.44120 28.1% - 1s
H 0 0 -65.1158686 -83.44120 28.1% - 1s
H 0 0 -81.3117792 -82.78799 1.82% - 1s
H 0 0 -81.3117792 -82.78799 1.82% - 1s
0 0 -82.78799 0 152 -81.31178 -82.78799 1.82% - 1s
0 0 -82.78799 0 152 -81.31178 -82.78799 1.82% - 1s
H 0 0 -81.4117792 -82.75671 1.65% - 2s
H 0 0 -81.4117792 -82.75671 1.65% - 2s
0 0 -82.75671 0 152 -81.41178 -82.75671 1.65% - 2s
0 0 -82.75671 0 152 -81.41178 -82.75671 1.65% - 2s
0 0 -82.56802 0 125 -81.41178 -82.56802 1.42% - 3s
0 0 -82.56802 0 125 -81.41178 -82.56802 1.42% - 3s
0 0 -82.55779 0 107 -81.41178 -82.55779 1.41% - 3s
0 0 -82.55779 0 107 -81.41178 -82.55779 1.41% - 3s
0 0 -82.55687 0 110 -81.41178 -82.55687 1.41% - 3s
0 0 -82.55687 0 110 -81.41178 -82.55687 1.41% - 3s
0 0 -82.49418 0 171 -81.41178 -82.49418 1.33% - 3s
0 0 -82.49418 0 171 -81.41178 -82.49418 1.33% - 3s
0 0 -82.49418 0 171 -81.41178 -82.49418 1.33% - 3s
0 0 -82.49418 0 171 -81.41178 -82.49418 1.33% - 3s
0 0 -82.45349 0 167 -81.41178 -82.45349 1.28% - 4s
0 0 -82.45349 0 167 -81.41178 -82.45349 1.28% - 4s
0 0 -82.45349 0 165 -81.41178 -82.45349 1.28% - 4s
0 0 -82.45349 0 165 -81.41178 -82.45349 1.28% - 4s
0 0 -82.43325 0 167 -81.41178 -82.43325 1.25% - 4s
0 0 -82.43325 0 167 -81.41178 -82.43325 1.25% - 4s
0 0 -82.43325 0 58 -81.41178 -82.43325 1.25% - 5s
0 0 -82.43325 0 58 -81.41178 -82.43325 1.25% - 5s
0 0 -82.43325 0 90 -81.41178 -82.43325 1.25% - 5s
0 0 -82.43325 0 90 -81.41178 -82.43325 1.25% - 5s
0 0 -82.43325 0 96 -81.41178 -82.43325 1.25% - 6s
0 0 -82.43325 0 96 -81.41178 -82.43325 1.25% - 6s
0 0 -82.40353 0 171 -81.41178 -82.40353 1.22% - 6s
0 0 -82.40353 0 171 -81.41178 -82.40353 1.22% - 6s
0 0 -82.38450 0 173 -81.41178 -82.38450 1.19% - 6s
0 0 -82.38450 0 173 -81.41178 -82.38450 1.19% - 6s
0 0 -82.38450 0 180 -81.41178 -82.38450 1.19% - 6s
0 0 -82.38450 0 180 -81.41178 -82.38450 1.19% - 6s
0 0 -82.21994 0 166 -81.41178 -82.21994 0.99% - 7s
0 0 -82.21994 0 166 -81.41178 -82.21994 0.99% - 7s
H 0 0 -81.4321000 -82.19784 0.94% - 7s
H 0 0 -81.4321000 -82.19784 0.94% - 7s
0 0 -82.19784 0 191 -81.43210 -82.19784 0.94% - 7s
0 0 -82.19784 0 191 -81.43210 -82.19784 0.94% - 7s
0 0 -82.19740 0 203 -81.43210 -82.19740 0.94% - 7s
0 0 -82.19740 0 203 -81.43210 -82.19740 0.94% - 7s
0 0 -82.14623 0 197 -81.43210 -82.14623 0.88% - 7s
0 0 -82.14623 0 197 -81.43210 -82.14623 0.88% - 7s
0 0 -82.12614 0 159 -81.43210 -82.12614 0.85% - 7s
0 0 -82.12614 0 159 -81.43210 -82.12614 0.85% - 7s
0 0 -82.12463 0 162 -81.43210 -82.12463 0.85% - 7s
0 0 -82.12463 0 162 -81.43210 -82.12463 0.85% - 7s
0 0 -82.12430 0 199 -81.43210 -82.12430 0.85% - 7s
0 0 -82.12430 0 199 -81.43210 -82.12430 0.85% - 7s
0 0 -82.12430 0 199 -81.43210 -82.12430 0.85% - 7s
0 0 -82.12430 0 199 -81.43210 -82.12430 0.85% - 7s
0 0 -82.11330 0 207 -81.43210 -82.11330 0.84% - 7s
0 0 -82.11330 0 207 -81.43210 -82.11330 0.84% - 7s
0 0 -82.11097 0 220 -81.43210 -82.11097 0.83% - 8s
0 0 -82.11097 0 220 -81.43210 -82.11097 0.83% - 8s
0 0 -82.11097 0 225 -81.43210 -82.11097 0.83% - 8s
0 0 -82.11097 0 225 -81.43210 -82.11097 0.83% - 8s
0 0 -82.10574 0 225 -81.43210 -82.10574 0.83% - 8s
0 0 -82.10574 0 225 -81.43210 -82.10574 0.83% - 8s
0 0 -82.10497 0 222 -81.43210 -82.10497 0.83% - 8s
0 0 -82.10497 0 222 -81.43210 -82.10497 0.83% - 8s
0 0 -82.00935 0 213 -81.43210 -82.00935 0.71% - 8s
0 0 -82.00935 0 213 -81.43210 -82.00935 0.71% - 8s
0 0 -82.00760 0 194 -81.43210 -82.00760 0.71% - 8s
0 0 -82.00760 0 194 -81.43210 -82.00760 0.71% - 8s
0 0 -82.00760 0 238 -81.43210 -82.00760 0.71% - 8s
0 0 -82.00760 0 238 -81.43210 -82.00760 0.71% - 8s
0 0 -82.00631 0 173 -81.43210 -82.00631 0.71% - 8s
0 0 -82.00631 0 173 -81.43210 -82.00631 0.71% - 8s
0 0 -82.00413 0 209 -81.43210 -82.00413 0.70% - 8s
0 0 -82.00413 0 209 -81.43210 -82.00413 0.70% - 8s
0 0 -82.00413 0 216 -81.43210 -82.00413 0.70% - 9s
0 0 -82.00413 0 216 -81.43210 -82.00413 0.70% - 9s
0 0 -82.00413 0 232 -81.43210 -82.00413 0.70% - 9s
0 0 -82.00413 0 232 -81.43210 -82.00413 0.70% - 9s
0 0 -82.00413 0 231 -81.43210 -82.00413 0.70% - 9s
0 0 -82.00413 0 231 -81.43210 -82.00413 0.70% - 9s
0 0 -82.00413 0 230 -81.43210 -82.00413 0.70% - 9s
0 0 -82.00413 0 230 -81.43210 -82.00413 0.70% - 9s
0 0 -82.00396 0 90 -81.43210 -82.00396 0.70% - 10s
0 0 -82.00396 0 90 -81.43210 -82.00396 0.70% - 10s
0 0 -82.00396 0 169 -81.43210 -82.00396 0.70% - 10s
0 0 -82.00396 0 169 -81.43210 -82.00396 0.70% - 10s
0 0 -82.00396 0 175 -81.43210 -82.00396 0.70% - 11s
0 0 -82.00396 0 175 -81.43210 -82.00396 0.70% - 11s
0 0 -82.00396 0 171 -81.43210 -82.00396 0.70% - 11s
0 0 -82.00396 0 171 -81.43210 -82.00396 0.70% - 11s
0 0 -82.00396 0 173 -81.43210 -82.00396 0.70% - 11s
0 0 -82.00396 0 173 -81.43210 -82.00396 0.70% - 11s
0 0 -82.00396 0 209 -81.43210 -82.00396 0.70% - 11s
0 0 -82.00396 0 209 -81.43210 -82.00396 0.70% - 11s
0 0 -82.00396 0 193 -81.43210 -82.00396 0.70% - 11s
0 0 -82.00396 0 193 -81.43210 -82.00396 0.70% - 11s
0 0 -82.00396 0 166 -81.43210 -82.00396 0.70% - 12s
0 0 -82.00396 0 166 -81.43210 -82.00396 0.70% - 12s
0 0 -82.00396 0 190 -81.43210 -82.00396 0.70% - 12s
0 0 -82.00396 0 190 -81.43210 -82.00396 0.70% - 12s
0 0 -82.00363 0 194 -81.43210 -82.00363 0.70% - 12s
0 0 -82.00363 0 194 -81.43210 -82.00363 0.70% - 12s
0 0 -82.00290 0 195 -81.43210 -82.00290 0.70% - 12s
0 0 -82.00290 0 195 -81.43210 -82.00290 0.70% - 12s
0 0 -82.00290 0 215 -81.43210 -82.00290 0.70% - 12s
0 0 -82.00290 0 215 -81.43210 -82.00290 0.70% - 12s
0 0 -81.96087 0 162 -81.43210 -81.96087 0.65% - 12s
0 0 -81.96087 0 162 -81.43210 -81.96087 0.65% - 12s
0 0 -81.94659 0 191 -81.43210 -81.94659 0.63% - 13s
0 0 -81.94659 0 191 -81.43210 -81.94659 0.63% - 13s
0 0 -81.94526 0 201 -81.43210 -81.94526 0.63% - 13s
0 0 -81.94526 0 201 -81.43210 -81.94526 0.63% - 13s
0 0 -81.94265 0 233 -81.43210 -81.94265 0.63% - 13s
0 0 -81.94265 0 233 -81.43210 -81.94265 0.63% - 13s
0 0 -81.94252 0 218 -81.43210 -81.94252 0.63% - 13s
0 0 -81.94252 0 218 -81.43210 -81.94252 0.63% - 13s
0 0 -81.91279 0 183 -81.43210 -81.91279 0.59% - 13s
0 0 -81.91279 0 183 -81.43210 -81.91279 0.59% - 13s
0 0 -81.88618 0 199 -81.43210 -81.88618 0.56% - 14s
0 0 -81.88618 0 199 -81.43210 -81.88618 0.56% - 14s
0 0 -81.88445 0 185 -81.43210 -81.88445 0.56% - 14s
0 0 -81.88445 0 185 -81.43210 -81.88445 0.56% - 14s
0 0 -81.88394 0 184 -81.43210 -81.88394 0.55% - 14s
0 0 -81.88394 0 184 -81.43210 -81.88394 0.55% - 14s
0 0 -81.88386 0 186 -81.43210 -81.88386 0.55% - 14s
0 0 -81.88386 0 186 -81.43210 -81.88386 0.55% - 14s
0 0 -81.85676 0 175 -81.43210 -81.85676 0.52% - 14s
0 0 -81.85676 0 175 -81.43210 -81.85676 0.52% - 14s
0 0 -81.85607 0 182 -81.43210 -81.85607 0.52% - 14s
0 0 -81.85607 0 182 -81.43210 -81.85607 0.52% - 14s
0 0 -81.85360 0 210 -81.43210 -81.85360 0.52% - 14s
0 0 -81.85360 0 210 -81.43210 -81.85360 0.52% - 14s
0 0 -81.85085 0 210 -81.43210 -81.85085 0.51% - 14s
0 0 -81.85085 0 210 -81.43210 -81.85085 0.51% - 14s
0 0 -81.85085 0 214 -81.43210 -81.85085 0.51% - 14s
0 0 -81.85085 0 214 -81.43210 -81.85085 0.51% - 14s
0 0 -81.85085 0 212 -81.43210 -81.85085 0.51% - 15s
0 0 -81.85085 0 212 -81.43210 -81.85085 0.51% - 15s
0 2 -81.85085 0 212 -81.43210 -81.85085 0.51% - 16s
0 2 -81.85085 0 212 -81.43210 -81.85085 0.51% - 16s
Cutting planes:
Cutting planes:
Cover: 54
Cover: 54
Implied bound: 25
Implied bound: 25
MIR: 10
MIR: 10
Flow cover: 16
Flow cover: 16
GUB cover: 1
GUB cover: 1
Zero half: 8
Zero half: 8
Network: 4
Network: 4
RLT: 16
RLT: 16
Relax-and-lift: 2
Relax-and-lift: 2
Explored 56 nodes (25734 simplex iterations) in 17.44 seconds (4.26 work units)
Explored 56 nodes (25734 simplex iterations) in 17.44 seconds (4.26 work units)
Thread count was 12 (of 12 available processors)
Thread count was 12 (of 12 available processors)
Solution count 4: -81.4321 -81.4118 -81.3118 -65.1159
Solution count 4: -81.4321 -81.4118 -81.3118 -65.1159
No other solutions better than -81.4321
No other solutions better than -81.4321
Optimal solution found (tolerance 1.00e-04)
Optimal solution found (tolerance 1.00e-04)
Best objective -8.143210004534e+01, best bound -8.143210004534e+01, gap 0.0000%
Best objective -8.143210004534e+01, best bound -8.143210004534e+01, gap 0.0000%
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:48 PM: Problem status: optimal
(CVXPY) Apr 11 04:47:48 PM: Optimal value: 7.580e+00
(CVXPY) Apr 11 04:47:48 PM: Compilation took 1.481e-01 seconds
(CVXPY) Apr 11 04:47:48 PM: Solver (including time spent in interface) took 1.788e+01 seconds
Solution summary:
- Loss (unfitted inputs/output): [0.]
- Edge penalty error: 34.0
- Node penalty error: 4.023853381222087
Run 5 with seed 1342
Building CORNETO problem...
Solving with gurobi...
===============================================================================
CVXPY
v1.4.1
===============================================================================
(CVXPY) Apr 11 04:47:49 PM: Your problem has 9606 variables, 31 constraints, and 0 parameters.
(CVXPY) Apr 11 04:47:49 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Apr 11 04:47:49 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Apr 11 04:47:49 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Apr 11 04:47:49 PM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:49 PM: Compiling problem (target solver=GUROBI).
(CVXPY) Apr 11 04:47:49 PM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> GUROBI
(CVXPY) Apr 11 04:47:49 PM: Applying reduction CvxAttr2Constr
(CVXPY) Apr 11 04:47:49 PM: Applying reduction Qp2SymbolicQp
(CVXPY) Apr 11 04:47:49 PM: Applying reduction QpMatrixStuffing
(CVXPY) Apr 11 04:47:49 PM: Applying reduction GUROBI
(CVXPY) Apr 11 04:47:49 PM: Finished problem compilation (took 3.493e-01 seconds).
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:47:49 PM: Invoking solver GUROBI to obtain a solution.
Set parameter QCPDual to value 1
Set parameter QCPDual to value 1
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Model fingerprint: 0xf1542b06
Model fingerprint: 0xf1542b06
Variable types: 2535 continuous, 7071 integer (7071 binary)
Variable types: 2535 continuous, 7071 integer (7071 binary)
Coefficient statistics:
Coefficient statistics:
Matrix range [1e-03, 5e+02]
Matrix range [1e-03, 5e+02]
Objective range [5e-03, 2e+01]
Objective range [5e-03, 2e+01]
Bounds range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e-03, 5e+02]
RHS range [1e-03, 5e+02]
Presolve removed 24916 rows and 1156 columns
Presolve removed 24916 rows and 1156 columns
Presolve time: 0.24s
Presolve time: 0.24s
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Variable types: 2334 continuous, 6116 integer (6116 binary)
Variable types: 2334 continuous, 6116 integer (6116 binary)
Root relaxation: objective -8.344377e+01, 2222 iterations, 0.27 seconds (0.17 work units)
Root relaxation: objective -8.344377e+01, 2222 iterations, 0.27 seconds (0.17 work units)
Nodes | Current Node | Objective Bounds | Work
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -83.44377 0 69 - -83.44377 - - 0s
0 0 -83.44377 0 69 - -83.44377 - - 0s
H 0 0 -63.3189420 -82.78437 30.7% - 1s
H 0 0 -63.3189420 -82.78437 30.7% - 1s
0 0 -82.78437 0 144 -63.31894 -82.78437 30.7% - 1s
0 0 -82.78437 0 144 -63.31894 -82.78437 30.7% - 1s
H 0 0 -72.8291616 -82.75183 13.6% - 1s
H 0 0 -72.8291616 -82.75183 13.6% - 1s
H 0 0 -81.3321831 -82.75183 1.75% - 1s
H 0 0 -81.3321831 -82.75183 1.75% - 1s
0 0 -82.75183 0 172 -81.33218 -82.75183 1.75% - 1s
0 0 -82.75183 0 172 -81.33218 -82.75183 1.75% - 1s
0 0 -82.52171 0 166 -81.33218 -82.52171 1.46% - 1s
0 0 -82.52171 0 166 -81.33218 -82.52171 1.46% - 1s
0 0 -82.50121 0 131 -81.33218 -82.50121 1.44% - 2s
0 0 -82.50121 0 131 -81.33218 -82.50121 1.44% - 2s
0 0 -82.50121 0 139 -81.33218 -82.50121 1.44% - 2s
0 0 -82.50121 0 139 -81.33218 -82.50121 1.44% - 2s
0 0 -82.39138 0 174 -81.33218 -82.39138 1.30% - 2s
0 0 -82.39138 0 174 -81.33218 -82.39138 1.30% - 2s
0 0 -82.38727 0 172 -81.33218 -82.38727 1.30% - 2s
0 0 -82.38727 0 172 -81.33218 -82.38727 1.30% - 2s
0 0 -82.38727 0 178 -81.33218 -82.38727 1.30% - 3s
0 0 -82.38727 0 178 -81.33218 -82.38727 1.30% - 3s
0 0 -82.28223 0 193 -81.33218 -82.28223 1.17% - 3s
0 0 -82.28223 0 193 -81.33218 -82.28223 1.17% - 3s
0 0 -82.28223 0 60 -81.33218 -82.28223 1.17% - 4s
0 0 -82.28223 0 60 -81.33218 -82.28223 1.17% - 4s
0 0 -82.28223 0 150 -81.33218 -82.28223 1.17% - 4s
0 0 -82.28223 0 150 -81.33218 -82.28223 1.17% - 4s
0 0 -82.28223 0 95 -81.33218 -82.28223 1.17% - 5s
0 0 -82.28223 0 95 -81.33218 -82.28223 1.17% - 5s
0 0 -82.28089 0 121 -81.33218 -82.28089 1.17% - 5s
0 0 -82.28089 0 121 -81.33218 -82.28089 1.17% - 5s
0 0 -82.27911 0 157 -81.33218 -82.27911 1.16% - 5s
0 0 -82.27911 0 157 -81.33218 -82.27911 1.16% - 5s
0 0 -82.27857 0 159 -81.33218 -82.27857 1.16% - 5s
0 0 -82.27857 0 159 -81.33218 -82.27857 1.16% - 5s
0 0 -82.27775 0 144 -81.33218 -82.27775 1.16% - 5s
0 0 -82.27775 0 144 -81.33218 -82.27775 1.16% - 5s
0 0 -82.27390 0 147 -81.33218 -82.27390 1.16% - 5s
0 0 -82.27390 0 147 -81.33218 -82.27390 1.16% - 5s
0 0 -82.27390 0 147 -81.33218 -82.27390 1.16% - 5s
0 0 -82.27390 0 147 -81.33218 -82.27390 1.16% - 5s
0 0 -82.07322 0 172 -81.33218 -82.07322 0.91% - 6s
0 0 -82.07322 0 172 -81.33218 -82.07322 0.91% - 6s
0 0 -82.05015 0 162 -81.33218 -82.05015 0.88% - 6s
0 0 -82.05015 0 162 -81.33218 -82.05015 0.88% - 6s
0 0 -81.96375 0 113 -81.33218 -81.96375 0.78% - 6s
0 0 -81.96375 0 113 -81.33218 -81.96375 0.78% - 6s
0 0 -81.93033 0 164 -81.33218 -81.93033 0.74% - 6s
0 0 -81.93033 0 164 -81.33218 -81.93033 0.74% - 6s
0 0 -81.93033 0 164 -81.33218 -81.93033 0.74% - 6s
0 0 -81.93033 0 164 -81.33218 -81.93033 0.74% - 6s
0 0 -81.93033 0 223 -81.33218 -81.93033 0.74% - 7s
0 0 -81.93033 0 223 -81.33218 -81.93033 0.74% - 7s
0 0 -81.93033 0 222 -81.33218 -81.93033 0.74% - 7s
0 0 -81.93033 0 222 -81.33218 -81.93033 0.74% - 7s
0 0 -81.92471 0 156 -81.33218 -81.92471 0.73% - 7s
0 0 -81.92471 0 156 -81.33218 -81.92471 0.73% - 7s
0 0 -81.91289 0 184 -81.33218 -81.91289 0.71% - 7s
0 0 -81.91289 0 184 -81.33218 -81.91289 0.71% - 7s
0 0 -81.91289 0 184 -81.33218 -81.91289 0.71% - 7s
0 0 -81.91289 0 184 -81.33218 -81.91289 0.71% - 7s
0 0 -81.88139 0 176 -81.33218 -81.88139 0.68% - 7s
0 0 -81.88139 0 176 -81.33218 -81.88139 0.68% - 7s
H 0 0 -81.4144213 -81.87283 0.56% - 7s
H 0 0 -81.4144213 -81.87283 0.56% - 7s
0 0 -81.87283 0 176 -81.41442 -81.87283 0.56% - 7s
0 0 -81.87283 0 176 -81.41442 -81.87283 0.56% - 7s
0 0 -81.87283 0 187 -81.41442 -81.87283 0.56% - 7s
0 0 -81.87283 0 187 -81.41442 -81.87283 0.56% - 7s
0 0 -81.78099 0 156 -81.41442 -81.78099 0.45% - 8s
0 0 -81.78099 0 156 -81.41442 -81.78099 0.45% - 8s
0 0 -81.78099 0 156 -81.41442 -81.78099 0.45% - 8s
0 0 -81.78099 0 156 -81.41442 -81.78099 0.45% - 8s
0 0 -81.77866 0 156 -81.41442 -81.77866 0.45% - 8s
0 0 -81.77866 0 156 -81.41442 -81.77866 0.45% - 8s
0 0 -81.77866 0 158 -81.41442 -81.77866 0.45% - 8s
0 0 -81.77866 0 158 -81.41442 -81.77866 0.45% - 8s
0 0 -81.77866 0 179 -81.41442 -81.77866 0.45% - 8s
0 0 -81.77866 0 179 -81.41442 -81.77866 0.45% - 8s
0 0 -81.77866 0 179 -81.41442 -81.77866 0.45% - 8s
0 0 -81.77866 0 179 -81.41442 -81.77866 0.45% - 8s
0 0 -81.77550 0 188 -81.41442 -81.77550 0.44% - 8s
0 0 -81.77550 0 188 -81.41442 -81.77550 0.44% - 8s
0 0 -81.77286 0 205 -81.41442 -81.77286 0.44% - 9s
0 0 -81.77286 0 205 -81.41442 -81.77286 0.44% - 9s
0 0 -81.77282 0 208 -81.41442 -81.77282 0.44% - 9s
0 0 -81.77282 0 208 -81.41442 -81.77282 0.44% - 9s
0 0 -81.77197 0 214 -81.41442 -81.77197 0.44% - 9s
0 0 -81.77197 0 214 -81.41442 -81.77197 0.44% - 9s
0 0 -81.77186 0 226 -81.41442 -81.77186 0.44% - 9s
0 0 -81.77186 0 226 -81.41442 -81.77186 0.44% - 9s
H 0 0 -81.4310694 -81.77186 0.42% - 9s
H 0 0 -81.4310694 -81.77186 0.42% - 9s
0 0 -81.77186 0 225 -81.43107 -81.77186 0.42% - 9s
0 0 -81.77186 0 225 -81.43107 -81.77186 0.42% - 9s
0 0 -81.77076 0 229 -81.43107 -81.77076 0.42% - 9s
0 0 -81.77076 0 229 -81.43107 -81.77076 0.42% - 9s
0 0 -81.77059 0 221 -81.43107 -81.77059 0.42% - 9s
0 0 -81.77059 0 221 -81.43107 -81.77059 0.42% - 9s
0 0 -81.77028 0 221 -81.43107 -81.77028 0.42% - 9s
0 0 -81.77028 0 221 -81.43107 -81.77028 0.42% - 9s
H 0 0 -81.4321831 -81.76317 0.41% - 10s
H 0 0 -81.4321831 -81.76317 0.41% - 10s
0 2 -81.76317 0 221 -81.43218 -81.76317 0.41% - 10s
0 2 -81.76317 0 221 -81.43218 -81.76317 0.41% - 10s
Cutting planes:
Cutting planes:
Cover: 54
Cover: 54
Implied bound: 30
Implied bound: 30
Clique: 2
Clique: 2
MIR: 9
MIR: 9
Flow cover: 15
Flow cover: 15
Zero half: 12
Zero half: 12
Network: 2
Network: 2
RLT: 8
RLT: 8
Relax-and-lift: 1
Relax-and-lift: 1
Explored 111 nodes (19074 simplex iterations) in 11.85 seconds (3.16 work units)
Explored 111 nodes (19074 simplex iterations) in 11.85 seconds (3.16 work units)
Thread count was 12 (of 12 available processors)
Thread count was 12 (of 12 available processors)
Solution count 6: -81.4322 -81.4311 -81.4144 ... -63.3189
Solution count 6: -81.4322 -81.4311 -81.4144 ... -63.3189
No other solutions better than -81.4322
No other solutions better than -81.4322
Optimal solution found (tolerance 1.00e-04)
Optimal solution found (tolerance 1.00e-04)
Best objective -8.143218314121e+01, best bound -8.143218314121e+01, gap 0.0000%
Best objective -8.143218314121e+01, best bound -8.143218314121e+01, gap 0.0000%
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:48:02 PM: Problem status: optimal
(CVXPY) Apr 11 04:48:02 PM: Optimal value: 7.580e+00
(CVXPY) Apr 11 04:48:02 PM: Compilation took 3.493e-01 seconds
(CVXPY) Apr 11 04:48:02 PM: Solver (including time spent in interface) took 1.217e+01 seconds
Solution summary:
- Loss (unfitted inputs/output): [0.]
- Edge penalty error: 34.0
- Node penalty error: 4.023959569904854
Run 6 with seed 1343
Building CORNETO problem...
Solving with gurobi...
===============================================================================
CVXPY
v1.4.1
===============================================================================
(CVXPY) Apr 11 04:48:02 PM: Your problem has 9606 variables, 31 constraints, and 0 parameters.
(CVXPY) Apr 11 04:48:02 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Apr 11 04:48:02 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Apr 11 04:48:02 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Apr 11 04:48:02 PM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:48:02 PM: Compiling problem (target solver=GUROBI).
(CVXPY) Apr 11 04:48:02 PM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> GUROBI
(CVXPY) Apr 11 04:48:02 PM: Applying reduction CvxAttr2Constr
(CVXPY) Apr 11 04:48:02 PM: Applying reduction Qp2SymbolicQp
(CVXPY) Apr 11 04:48:02 PM: Applying reduction QpMatrixStuffing
(CVXPY) Apr 11 04:48:02 PM: Applying reduction GUROBI
(CVXPY) Apr 11 04:48:02 PM: Finished problem compilation (took 2.194e-01 seconds).
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:48:02 PM: Invoking solver GUROBI to obtain a solution.
Set parameter QCPDual to value 1
Set parameter QCPDual to value 1
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Optimize a model with 37357 rows, 9606 columns and 67371 nonzeros
Model fingerprint: 0x34bdaafe
Model fingerprint: 0x34bdaafe
Variable types: 2535 continuous, 7071 integer (7071 binary)
Variable types: 2535 continuous, 7071 integer (7071 binary)
Coefficient statistics:
Coefficient statistics:
Matrix range [1e-03, 5e+02]
Matrix range [1e-03, 5e+02]
Objective range [5e-03, 2e+01]
Objective range [5e-03, 2e+01]
Bounds range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e-03, 5e+02]
RHS range [1e-03, 5e+02]
Presolve removed 24916 rows and 1156 columns
Presolve removed 24916 rows and 1156 columns
Presolve time: 0.42s
Presolve time: 0.42s
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Presolved: 12441 rows, 8450 columns, 36719 nonzeros
Variable types: 2334 continuous, 6116 integer (6116 binary)
Variable types: 2334 continuous, 6116 integer (6116 binary)
Root relaxation: objective -8.344272e+01, 2167 iterations, 0.40 seconds (0.15 work units)
Root relaxation: objective -8.344272e+01, 2167 iterations, 0.40 seconds (0.15 work units)
Nodes | Current Node | Objective Bounds | Work
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -83.44272 0 65 - -83.44272 - - 1s
0 0 -83.44272 0 65 - -83.44272 - - 1s
H 0 0 -55.7982168 -83.44272 49.5% - 1s
H 0 0 -55.7982168 -83.44272 49.5% - 1s
H 0 0 -79.4242930 -83.44272 5.06% - 1s
H 0 0 -79.4242930 -83.44272 5.06% - 1s
0 0 -82.66703 0 158 -79.42429 -82.66703 4.08% - 1s
0 0 -82.66703 0 158 -79.42429 -82.66703 4.08% - 1s
H 0 0 -81.1293667 -82.64489 1.87% - 1s
H 0 0 -81.1293667 -82.64489 1.87% - 1s
H 0 0 -81.2890717 -82.64489 1.67% - 2s
H 0 0 -81.2890717 -82.64489 1.67% - 2s
0 0 -82.64489 0 162 -81.28907 -82.64489 1.67% - 2s
0 0 -82.64489 0 162 -81.28907 -82.64489 1.67% - 2s
0 0 -82.62034 0 81 -81.28907 -82.62034 1.64% - 3s
0 0 -82.62034 0 81 -81.28907 -82.62034 1.64% - 3s
0 0 -82.58725 0 169 -81.28907 -82.58725 1.60% - 3s
0 0 -82.58725 0 169 -81.28907 -82.58725 1.60% - 3s
H 0 0 -81.3204518 -82.45143 1.39% - 4s
H 0 0 -81.3204518 -82.45143 1.39% - 4s
0 0 -82.45143 0 113 -81.32045 -82.45143 1.39% - 4s
0 0 -82.45143 0 113 -81.32045 -82.45143 1.39% - 4s
0 0 -82.43281 0 168 -81.32045 -82.43281 1.37% - 4s
0 0 -82.43281 0 168 -81.32045 -82.43281 1.37% - 4s
0 0 -82.43281 0 168 -81.32045 -82.43281 1.37% - 4s
0 0 -82.43281 0 168 -81.32045 -82.43281 1.37% - 4s
0 0 -82.33936 0 120 -81.32045 -82.33936 1.25% - 5s
0 0 -82.33936 0 120 -81.32045 -82.33936 1.25% - 5s
0 0 -82.33936 0 120 -81.32045 -82.33936 1.25% - 5s
0 0 -82.33936 0 120 -81.32045 -82.33936 1.25% - 5s
0 0 -82.31463 0 169 -81.32045 -82.31463 1.22% - 5s
0 0 -82.31463 0 169 -81.32045 -82.31463 1.22% - 5s
0 0 -82.31463 0 172 -81.32045 -82.31463 1.22% - 5s
0 0 -82.31463 0 172 -81.32045 -82.31463 1.22% - 5s
0 0 -82.30970 0 173 -81.32045 -82.30970 1.22% - 5s
0 0 -82.30970 0 173 -81.32045 -82.30970 1.22% - 5s
0 0 -82.30213 0 124 -81.32045 -82.30213 1.21% - 5s
0 0 -82.30213 0 124 -81.32045 -82.30213 1.21% - 5s
0 0 -82.30213 0 57 -81.32045 -82.30213 1.21% - 6s
0 0 -82.30213 0 57 -81.32045 -82.30213 1.21% - 6s
H 0 0 -81.4293667 -82.30213 1.07% - 6s
H 0 0 -81.4293667 -82.30213 1.07% - 6s
0 0 -82.30213 0 172 -81.42937 -82.30213 1.07% - 6s
0 0 -82.30213 0 172 -81.42937 -82.30213 1.07% - 6s
0 0 -82.30213 0 179 -81.42937 -82.30213 1.07% - 6s
0 0 -82.30213 0 179 -81.42937 -82.30213 1.07% - 6s
0 0 -82.30213 0 179 -81.42937 -82.30213 1.07% - 6s
0 0 -82.30213 0 179 -81.42937 -82.30213 1.07% - 6s
0 0 -82.30213 0 179 -81.42937 -82.30213 1.07% - 6s
0 0 -82.30213 0 179 -81.42937 -82.30213 1.07% - 6s
0 0 -82.30213 0 104 -81.42937 -82.30213 1.07% - 7s
0 0 -82.30213 0 104 -81.42937 -82.30213 1.07% - 7s
0 0 -82.30213 0 109 -81.42937 -82.30213 1.07% - 7s
0 0 -82.30213 0 109 -81.42937 -82.30213 1.07% - 7s
0 0 -82.30213 0 107 -81.42937 -82.30213 1.07% - 7s
0 0 -82.30213 0 107 -81.42937 -82.30213 1.07% - 7s
0 0 -82.23457 0 154 -81.42937 -82.23457 0.99% - 7s
0 0 -82.23457 0 154 -81.42937 -82.23457 0.99% - 7s
0 0 -82.22430 0 122 -81.42937 -82.22430 0.98% - 7s
0 0 -82.22430 0 122 -81.42937 -82.22430 0.98% - 7s
0 0 -82.22430 0 124 -81.42937 -82.22430 0.98% - 7s
0 0 -82.22430 0 124 -81.42937 -82.22430 0.98% - 7s
0 0 -82.13515 0 127 -81.42937 -82.13515 0.87% - 8s
0 0 -82.13515 0 127 -81.42937 -82.13515 0.87% - 8s
0 0 -82.11836 0 190 -81.42937 -82.11836 0.85% - 8s
0 0 -82.11836 0 190 -81.42937 -82.11836 0.85% - 8s
0 0 -82.11836 0 190 -81.42937 -82.11836 0.85% - 8s
0 0 -82.11836 0 190 -81.42937 -82.11836 0.85% - 8s
0 0 -81.99809 0 188 -81.42937 -81.99809 0.70% - 8s
0 0 -81.99809 0 188 -81.42937 -81.99809 0.70% - 8s
0 0 -81.98478 0 168 -81.42937 -81.98478 0.68% - 8s
0 0 -81.98478 0 168 -81.42937 -81.98478 0.68% - 8s
0 0 -81.98376 0 183 -81.42937 -81.98376 0.68% - 8s
0 0 -81.98376 0 183 -81.42937 -81.98376 0.68% - 8s
0 0 -81.98376 0 184 -81.42937 -81.98376 0.68% - 8s
0 0 -81.98376 0 184 -81.42937 -81.98376 0.68% - 8s
0 0 -81.97177 0 156 -81.42937 -81.97177 0.67% - 9s
0 0 -81.97177 0 156 -81.42937 -81.97177 0.67% - 9s
0 0 -81.96997 0 227 -81.42937 -81.96997 0.66% - 9s
0 0 -81.96997 0 227 -81.42937 -81.96997 0.66% - 9s
0 0 -81.96997 0 227 -81.42937 -81.96997 0.66% - 9s
0 0 -81.96997 0 227 -81.42937 -81.96997 0.66% - 9s
0 0 -81.96632 0 184 -81.42937 -81.96632 0.66% - 9s
0 0 -81.96632 0 184 -81.42937 -81.96632 0.66% - 9s
0 0 -81.96512 0 199 -81.42937 -81.96512 0.66% - 9s
0 0 -81.96512 0 199 -81.42937 -81.96512 0.66% - 9s
0 0 -81.96512 0 203 -81.42937 -81.96512 0.66% - 9s
0 0 -81.96512 0 203 -81.42937 -81.96512 0.66% - 9s
0 0 -81.96211 0 198 -81.42937 -81.96211 0.65% - 9s
0 0 -81.96211 0 198 -81.42937 -81.96211 0.65% - 9s
0 0 -81.95989 0 219 -81.42937 -81.95989 0.65% - 9s
0 0 -81.95989 0 219 -81.42937 -81.95989 0.65% - 9s
0 0 -81.95989 0 235 -81.42937 -81.95989 0.65% - 9s
0 0 -81.95989 0 235 -81.42937 -81.95989 0.65% - 9s
0 0 -81.95715 0 235 -81.42937 -81.95715 0.65% - 10s
0 0 -81.95715 0 235 -81.42937 -81.95715 0.65% - 10s
0 0 -81.95715 0 235 -81.42937 -81.95715 0.65% - 10s
0 0 -81.95715 0 235 -81.42937 -81.95715 0.65% - 10s
0 0 -81.95715 0 235 -81.42937 -81.95715 0.65% - 10s
0 0 -81.95715 0 235 -81.42937 -81.95715 0.65% - 10s
0 0 -81.95715 0 238 -81.42937 -81.95715 0.65% - 10s
0 0 -81.95715 0 238 -81.42937 -81.95715 0.65% - 10s
0 0 -81.95715 0 231 -81.42937 -81.95715 0.65% - 10s
0 0 -81.95715 0 231 -81.42937 -81.95715 0.65% - 10s
0 2 -81.95653 0 231 -81.42937 -81.95653 0.65% - 11s
0 2 -81.95653 0 231 -81.42937 -81.95653 0.65% - 11s
Cutting planes:
Cutting planes:
Cover: 51
Cover: 51
Implied bound: 21
Implied bound: 21
Clique: 4
Clique: 4
MIR: 7
MIR: 7
Flow cover: 13
Flow cover: 13
Zero half: 12
Zero half: 12
Network: 4
Network: 4
RLT: 12
RLT: 12
Relax-and-lift: 5
Relax-and-lift: 5
Explored 97 nodes (21222 simplex iterations) in 12.99 seconds (3.35 work units)
Explored 97 nodes (21222 simplex iterations) in 12.99 seconds (3.35 work units)
Thread count was 12 (of 12 available processors)
Thread count was 12 (of 12 available processors)
Solution count 6: -81.4294 -81.3205 -81.2891 ... -55.7982
Solution count 6: -81.4294 -81.3205 -81.2891 ... -55.7982
No other solutions better than -81.4294
No other solutions better than -81.4294
Optimal solution found (tolerance 1.00e-04)
Optimal solution found (tolerance 1.00e-04)
Best objective -8.142936667131e+01, best bound -8.142936667131e+01, gap 0.0000%
Best objective -8.142936667131e+01, best bound -8.142936667131e+01, gap 0.0000%
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) Apr 11 04:48:16 PM: Problem status: optimal
(CVXPY) Apr 11 04:48:16 PM: Optimal value: 7.583e+00
(CVXPY) Apr 11 04:48:16 PM: Compilation took 2.194e-01 seconds
(CVXPY) Apr 11 04:48:16 PM: Solver (including time spent in interface) took 1.339e+01 seconds
Solution summary:
- Loss (unfitted inputs/output): [0.]
- Edge penalty error: 34.0
- Node penalty error: 4.024222388756216
Visualize the Inferred Network
Now that the solution has been found, we can visualize it using the cn.methods.carnival.visualize_network
function.
[33]:
cn.methods.carnival.visualize_network(df_res)
Warning: node 'PRKACA', graph '%3' size too small for label
Warning: node 'NFKB1', graph '%3' size too small for label
Warning: node 'GNAI2', graph '%3' size too small for label
Warning: node 'STAT2', graph '%3' size too small for label
Warning: node 'PDPK1', graph '%3' size too small for label
Warning: node 'PRKCZ', graph '%3' size too small for label
Warning: node 'STAT1', graph '%3' size too small for label
Warning: node 'IFNAR2', graph '%3' size too small for label
Warning: node 'AKT1', graph '%3' size too small for label
[33]:
We can see that the network above, largely captures a potential regulatory cascade with inhibitory (–|) and stimulatory (–>) interactions, related to JAK-STAT signalling. The network, in this case, starts from a receptor (triangle), coming from the top interactions, and ends with the deregulated TFs (square). The remainder of the nodes (circles) were inferred, taking their weights into account, and were not necessarily included in the input or output nodes.
In this example, we represent the directionality of signalling such that intracellular signalling is downstream of intercellular communication events. However, in biology cellular response is an admixture of both; thus such approaches are a simplification of biological reality.
Installing the Gurobi Solver: A Step-by-Step Guide
While in this small example the internal scipy solver works, for larger networks we recommend using a solver such as Gurobi.
Gurobi is a powerful optimization solver used in various mathematical programming problems. Here’s how you can install it:
1. Download Gurobi for Your Operating System:
Visit the Gurobi download page and select the version compatible with your OS.
2. Unzip and Update Path:
After downloading, unzip the file. Locate the /bin
folder inside the unzipped directory and add it to your system’s $PATH
variable. This step is crucial as it allows your system to recognize and run Gurobi from anywhere.
3. Register for an Academic License:
If you’re an academic user, you can obtain a free license. Register and request an academic license through the Gurobi portal. Follow the prompts to complete your registration.
4. Install Gurobi Python Interface:
Open your command prompt or terminal and run:
pip install gurobipy
This command installs the necessary Python interface to interact with Gurobi.
5. Configure the Solver:
In your code, ensure the solver
parameter is set to gurobi
to direct your program to use the Gurobi solver.
By following these steps, you should have Gurobi installed and ready to tackle complex optimization problems.