instances

Instances for Birkhoff-Decomposition (DSM-Dataset)

Format Description

Dataset with $n \times n$ (scaled) doubly stochastic matrices. Entries are non-negative and rows and columns sum to $s$. Each json file has 10 objects with the entries:

• n: Int with size of the (scaled) doubly stochastic matrix
• s: Int with the scale of the doubly stochastic matrix
• scaled_doubly_stochastic_matrix: Array{Int} of size $n^2$ with the scaled doubly stochastic matrix (columns stacked as a vector)
• weights: Array{Int}of length $n$ (sparse) or $n^2$ (dense). The array entries sum to $s$
• permutations: Array{Int} with $n$ (sparse) or $n^2$ (dense) permutation vectors stacked as a sigle vector. Each permutation vector has length $n$

File structure: qbench_n_sparse/dense.json where n is the size of the doubly stochstic matrix and sparse/dense indicates whether the doubly stochastic matrices are sparse or dense. Sparse and dense matrices are generated by sampling $n$ and $n^2$ permutations, respectively.

Instance Generation

The (scaled) doubly stochastic matrices are generated by sampling $k$ permutation matrices uniformly at random with the randperm function in the Random package in Julia.

For the weights, we draw $k - 1$ integers uniformly at random in the interval $[0, s]$ where $s = 10^d$ with $d = 2 + \text{number of digits} (k^2)$. Sort the $k-1$ integers in ascending order and add $0$ and $10^d$ to the list. Compute the differences between the integers. The weights are the difference between the integers.

Example for $k=4$:
$d$ is equal to $4$ and draw $3$ integers in the interval $[1,1000]$. Suppose the integers drawn are $[1000, 5000, 7000]$. Adding $0$ and $10000$ to the list we have $[0, 1000, 5000, 7000, 10000]$. The differences between the integers in the list are $[1000, 4000, 2000, 3000]$, which sum to $s$.