5
The following paper
S. D. Prestwich, "Local search and backtracking vs non-systematic backtracking," in AAAI 2001 Fall Symp. Uncertainty Computation, 2001. Alternative link to a PDF.
has a thorough comparison of local search vs. backtracking-like algorithm.
In the introduction, it even features a question:
"What is the essential difference between local ...
5
If you have MATLAB's Symbolic Math Toolbox installed, then it is just a matter of writing:
evalin(symengine, 'binomial(60, 30) / 2^60')
Alternatively, you could write your own version of nchoosek (see this) using multiple precision arithmetic (available in MATLAB through third party toolboxes like this one). You may also consider writing your own code for ...
4
I'd take the log of your expression, calculate the log of your expression using built-in functions that are well-behaved (i.e., don't underflow or overflow), and then exponentiate at the end.
\begin{align}
{n \choose k} = \frac{n!}{k!(n-k)!}
\end{align}
so
\begin{align}
\log\left(\frac{{n \choose k}}{2^{n}}\right) = \log{n!} - \log{k!} - \log{(n - k)!} - ...
3
What about a simple nested loop to give you one octant of the solution, which can then be copied due to symmetry:
$i$ from 0 to $d+n$
$j$ from 0 to $\sqrt{(d+n)^2-i^2}$
$k$ from $\sqrt{(d-n)^2-i^2-j^2}$ to $\sqrt{(d+n)^2-i^2-j^2}$,
where the minimum bound is 0 if $i^2+j^2 > (d-n)^2$.
You have to round off to the 'smallest' integer range.
3
If utmost speed is not a concern, I'd go for rewriting nchoosek interspersing the divisions with the computation so that the temporary values stay bounded. What follows is a sample implementation.
function accumulator=dividedbinomial(n,k)
num=n; %factor to multiply at the numerator
den=k; %factor to multiply at the denominator
powers=n; %powers of 2 ...
3
Applying the transformation you suggested, we get:
$$\min_{y \in\{0,1\}^n} (\mathbf{1}-y)^TP(\mathbf{1}-y)$$
$$\mathrm{s.t.}\;\;w^T(\mathbf{1}-y)\geq c\, ,$$ where $n$ is the dimension where $x$ lives and $\mathbf{1}$ is a vector of $n$ ones.
Working with the objective function, $$ \begin{align*}
(\mathbf{1}-y)^T P(\mathbf{1}-y) & = \mathbf{1}^T P\...
3
For the discrete version, it can be cast as a mixed-integer linear program. You just have to note that every element $x_i$ can be written as $x_i = \sum_{j=1}^k \frac{\delta_{ij}}{j}$ where $\sum_{j=1}^k \delta_{ij} = 1$ where $\delta_{ij}$ is binary. Using the same binary variables the inverses are simply $x_{i}^{-1} = \sum_{j=1}^k j\delta_{ij}$
Here is ...
2
If all you're looking for is an approximate solution, I would suggest starting with one of the well-known graph partitioning packages, for example METIS. It allows you to attach weights to nodes. Partition it into $P$ groups and check whether your minimal weight sum condition is satisfied. If yes, try partitioning into $P+1$ groups and check again. Then ...
2
The first idea that would come to my mind naturally is: after each bag, choose with 50% probability one of the remaining two. Does this avoid "special" patterns such as ABABAB? No, they just have a low chance of appearing. And that's how it should be, in a true random number generator. Avoiding special patterns give the impression of randomness, but true ...
2
I am writing a general answer about porting a program running on a CPU to a GPU or FPGA.
Both GPU programs (using say CUDA) and CPU programs are written in high level languages like C, C++. Therefore it is much easier to port a CPU program to its equivalent on a GPGPU. The algorithm that you have presented seems suitable for porting to GPU. It is compute ...
2
I usually use SageMath for research work connected with graphs. However, I was not able to find there a ready-made algorithm to find a minimum vertex cover for a hypergraph (see subsection with the corresponding name).
Anyway, using Sage together with Python should simplify your life a lot as it will give access to a lot of convenient and tested data ...
1
You can write your entire system in matrix notation. For each feature, you have a system of linear equations $Ax=b$, with $A$ a matrix containing the amounts of products $a_{ij}=n_{ij}$, $x$ the vector of unknown features $f_j$, and $b$ the vector of respective sums $b_i$.
You can use classic linear algebra to solve that system, no optimization required;)
1
I thought this might be a fun problem to solve, so I cranked out a solution for it based on the comment I made in the problem statement. The class representing the solution, which is in C++, can be found via the following link:
Combinatorial Solution Class
The main.cpp file can be written with the following example code:
#include <stdio.h>
#include "...
1
This one seems to work great for me:
https://github.com/mcximing/hungarian-algorithm-cpp
1
Modulo an inessential detail, we are asked to generate mixed radix numbers with certain "digit" sums $k=k_1+\ldots+k_m$. In particular, given $\mathbf{k_i}$ satisfying the sum of components $k$, we are asked to find either the next larger representation having the same component sum, or if none exists, the smallest representation having component sum $k+1$, ...
1
Practically speaking, from the aspect of time efficiency, are there any significant differences between modelling as a mixed integer programming and modeling as a network problem? And why (other than sparsity)?
Yes. The reason network simplex is faster primarily has to do with exploiting the total unimodularity of network matrices -- basically, network ...
1
Generally speaking, you want to construct formulations such that the convex hull of the linear programming (LP) relaxation is as small as possible, while retaining all potentially optimal feasible solutions. (Of course, feel free to write constraints that exclude currently feasible solutions that are known to be suboptimal.) In the ideal case, this convex ...
Only top voted, non community-wiki answers of a minimum length are eligible