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: ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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{...
user avatar
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 ...
user avatar
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 ...
user avatar
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-...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
  • 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}...
user avatar
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. ...
user avatar
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
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible