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
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 ...
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
If I interpret the problem right, the task is to assign to each $j$ in the column index set $J$ of the distance matrix an index $x_j$ from the row index set $I$
such that the $x_j$ are all different and the $\sum_j d(x_j,j)$ is minimal.
This can be posed as a combinatorial constraint satisfaction problem to a number of constraint solvers. See, e.g.,
http://...
3
Suppose you have a permutation vector permVec. Then a permutation matrix should be calculated as follows (modulo some MATLAB syntax bugs, since it's been a while):
permMat = function permVecToMat(permVec)
n = length(permVec);
permMat = zeros(n,n);
for i = 1:n
permMat(i, permVec(i)) = 1
end
end
Then you just take the determinant, and ...
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\...
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 ...
2
You can find an implementation in Octave. The function is, as in Matlab, called nchoosek. Documentation is here. For the theory behind this type of algorithms, you can consult section 7.2.1 of Volume 4A of The Art Of Computer Programming by Donald Knuth.
2
You have what is called an integer optimization problem. Like Brian already mentioned, there are methods that use continuations of your objective function to all of ${\mathbb R}^n$ as part of the algorithm, but ultimately you will have to deal with the integer nature of your problem.
There are many text books on this topic. Find one in your local library to ...
2
In many cases it's possible to extend $f$ to a function that maps $R^{n}$ (actually $[0,2]^{n}$) to $R$. If that function is convex and preferably differentiable (so that it has a gradient), then you can use conventional continuous optimization techniques to minimize the extended function. However, rounding off the minimum of the extended function is not ...
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 ...
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 ...
1
You have a multi-objective optimization problem: you want to maximize the number of cities but also minimize the amount of time. This is, by itself, not a well posed problem since you need to say which of two solutions $(N_1,T_1)$ and $(N_2,T_2)$ is better if two paths visit $N_i$ cities and take $T_i$ time units. What you need to do, then, is to first ...
1
While this isn't a full algorithm, I think I can point you to a goal. Every piece has a specific number of spaces it can move in the greater 15x15 grid with itself at the center. Whenever you place a piece on the board, the spaces that it can move to become "unsafe". Your overall goal is to retain safe spaces for as long as possible so that you can ...
Only top voted, non community-wiki answers of a minimum length are eligible
