1
$\begingroup$

I am trying to find sorting networks having the optimal depth or optimal number of comparators by generating $2^n$ binary sequences where $n$ is the channel size.

The main variables in my model are as follows:

$L_{ijd} = 1$ if a comparator exists between indices $(i, j)$ at depth $d$ and $0$ otherwise.

$V_{idj}$ is the input value ($0$ or $1$) at index $i$, depth $d$ for the $j^{th}$ binary_sequence.

My model is based on section 2 of this paper. The issue I am finding with my model is that I've to input the value of depth $d$ that allows me to find the optimal depth. But that doesn't help in finding the optimal number of comparators.

Now I can just create depth as a variable but then it is used as an index. That's causing the issue. How can I change the model so that it allows the solver to find the depth?

$\endgroup$

1 Answer 1

1
$\begingroup$

Say $D$ is a set/list/dictionary/dataframe of all possible $d$ values, defined parameter. Define binary set $z_d'$ where $d'$ is indexed over $D$. Then using constraint
$ \sum_{d' \in D} z_{d'} = d$

Then use $ \sum_{d'} z_{d'}D_{d'} V_{ij}^{d'}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.