7
votes
Accepted
Estimate the number of self-avoiding walks of length $n$
Background
The number of self-avoiding walks of length N on a square lattice is:
...
- 3,091
5
votes
Striking examples of success of local search algorithms
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 ...
- 8,287
5
votes
Accepted
calculate Binomial coefficient over $2^n$ in Matlab
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 ...
- 3,954
4
votes
calculate Binomial coefficient over $2^n$ in Matlab
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{...
- 29.8k
4
votes
Finding all valid combinations of numeric inputs and operators in a Reverse Polish Notation expression
I suspect it might be easier to only generate valid expressions if you start with an infix expression "tree" of your expression and convert that to RPN format if you really want to.
Each ...
- 646
3
votes
calculate Binomial coefficient over $2^n$ in Matlab
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 ...
- 8,553
3
votes
Algorithm to generate all vectors of integers with magnitude between $n\pm \delta$
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-...
- 714
3
votes
Accepted
Combinatorial Optimization Problem with Constraints
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 ...
- 159
3
votes
Complementary quadratic knapsack problem
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$ ...
- 131
3
votes
Accepted
Sum of Inverse of Variables in an Optimization Problem
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}...
- 1,763
2
votes
Optimal partitioning of a graph
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. ...
- 50.2k
2
votes
Looking for a C/C++ implementation of the Hungarian method for real-valued cost matrix
This one seems to work great for me:
https://github.com/mcximing/hungarian-algorithm-cpp
- 121
2
votes
tea bag flavors mixing algorithm
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 ...
- 8,553
2
votes
GPGPU/FPGA programming for Combinatorial Analysis
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 ...
- 121
2
votes
Accepted
Software for finding a minimum vertex cover for a hypergraph
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 ...
- 8,287
1
vote
Accepted
Picking n integers from n different sets summing to a given value
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 ...
- 3,673
1
vote
Accepted
Algorithm for generating the next m-tuple of integers, subject to constraints
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 ...
- 3,189
1
vote
Comparison of the time efficiency of an optimization problem formulated as a Network Flow model and Mixed Integer Programming
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 ...
- 29.8k
1
vote
enhancing a MIP formulation of Ising model
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 ...
- 29.8k
Only top scored, non community-wiki answers of a minimum length are eligible