Combinatorics (combinatorial analysis) is a branch of mathematics that studies the discrete objects, the set (a combination, permutation, deployment and transfer of elements) and the relationship to them (eg, partial order).

learn more… | top users | synonyms

4
votes
1answer
63 views

Algorithm to generate all vectors of integers with magnitude between $n\pm \delta$

I am working on an program to compute the structure factor of a given configuration of particles, and I need an efficient algorithm to generate all the possible vectors with integer coordinates and ...
0
votes
1answer
56 views

Picking n integers from n different sets summing to a given value

Given a set of integers $\{l_1,l_2,\ldots,l_n\}$, where each integer is associated with a set $m_k\in\{-l_k,-l_k+1,\ldots,l_k\}$, I need to find all combinations $\{m_1,m_2,\ldots,m_n\}$ that sum to a ...
3
votes
0answers
77 views

Striking examples of success of local search algorithms

In N queens problem https://en.wikipedia.org/wiki/Eight_queens_puzzle, trying to find solution by backtracking encounters difficulties quite fast (even for SWI-Prolog, http://swish.swi-prolog.org/...
0
votes
0answers
26 views

Generating Combinations

I'm trying to find and print all the combinations of specific sizes that are less than or equal to a max size by building an algorithm in Google Sheets. For example, I have four sizes: 2.75, 4, 5, and ...
1
vote
0answers
29 views

Optimal distribution of zeros and ones over matrix

I have the following problem: Given a matrix with n rows and m columns. Some elements of the matrix are unavailable. For each column, you have a set containing a number of zeros and ones which must ...
1
vote
0answers
23 views

Clustering by shared subsequence

I have a question that relates to the classical "longest common subsequence" problem. I'll give the background to the problem, but you could skip to the formulation below if you like Let's think of ...
0
votes
0answers
42 views

Pickup and delivery problem with time windows and container repositioning

Given a set of ships, harbors, batches, containers, and, a matrix of distances between harbors. At any given point in time a harbor has some number of containers which can either be available or used ...
0
votes
0answers
258 views

Looking for a C/C++ implementation of the Hungarian method for real-valued cost matrix

I am looking for a C/C++ implementation of the Hungarian method for solving the linear assignment problem with real-valued cost matrix. Some implementation I found, such as this one, only work for ...
4
votes
1answer
80 views

Sum of Inverse of Variables in an Optimization Problem

I have the following optimization problem: $$ \begin{array}{ll} \text{Minimize} & \frac{1}{x_1} + \frac{1}{x_2} + \ldots + \frac{1}{d_n} \\ \text{Subject to} & A x \leq b \end{array} $$ where ...
1
vote
1answer
63 views

Algorithm for generating the next m-tuple of integers, subject to constraints

I am looking for an algorithm with the following characteristics: It is used to generate the set of integer vectors $\mathbf k=(k_1,\ldots,k_m)$, where $k_i\leq K_i$, $k_i\geq 0$, and $K_i$ are ...
4
votes
1answer
54 views

Optimal partitioning of a graph

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I ...
0
votes
0answers
47 views

Solving an LP greedily

I have the following LP: $$ \begin{array}{ll} \text{Minimize} & \sum_{j=1}^n x_j \\ \text{Subject to} & \sum_{j=1}^n a_{ij} x_j \geq b_i,~~~i\in\{1,\ldots,M\} \\ & 0 \leq ...
3
votes
0answers
44 views

Graph optimization for parallel processing

Consider the following example structure of overlapping images marked A,B,C,D. The possible overlaps are marked by gray color: The structure can be represented by a weighted undirected graph (...
1
vote
0answers
59 views

Is this problem statement good for a GPU?

I am used to using GPU hardware for large scale matrix operations and vectorizing mathematical operations on a continuous space which has been discretized for numerical computation, but this is a ...
1
vote
1answer
86 views

Comparison of the time efficiency of an optimization problem formulated as a Network Flow model and Mixed Integer Programming

In combinatorial optimization, there are many problems that can be formulated as either Network Flow model or Mixed Integer Programming (MIP), e.g. supply chains, transportation, and graph-base ...
2
votes
1answer
134 views

enhancing a MIP formulation of Ising model [closed]

I want to construct a MIP formulation for Ising model. For simplicity, I will only include terms involving nearest-neighbor pairs and triangular terms. I propose one formulation and ask whether there ...
2
votes
0answers
79 views

About Convex Geometry

A consistency notion in constraint programming: Let $P = (X, D, C)$ be a CSP. Given a set of variables $Y \subseteq X$ with $|Y| = k -1$, a locally consistent instantiation $I$ on $Y$ is $k$-...
2
votes
3answers
2k views

calculate Binomial coefficient over $2^n$ in Matlab

I want to calculate ${n \choose k}/2^n$ for moderate $n$ and $k$. In Matlab, use nchoosek(n,k) with $n=60$ and $k=30$ will give a warning: "Warning: Result may not ...
4
votes
2answers
62 views

gradient for ternary functions?

I've got a function of form $$f: (\mathbb{Z}_3)^n \rightarrow \mathbb{R}$$ to optimize, where $n$ is relatively large (the order of hundreds). Is it there a gradient-like notion for these type of ...
2
votes
1answer
334 views

Evolutionary algorithm - Traveling Salesman -fitness function

I'm trying to solve this problem using genetic algorithms and am having difficulty choosing the fitness function. My problem is a little different than the original Traveling Salesman Problem, since ...
4
votes
1answer
178 views

What strategies one can use to keep maximum number of non attacking pieces on an $n \times n$ chess board? [closed]

What are the strategies one can use to keep maximum number of non attacking pieces (all pieces other than pawn) on an $n\times n$ board? It is like an $n$-queen problem but here instead of only queen ...
1
vote
1answer
439 views

How can I compute whether a sequence is an even or odd permutation of an increasing sequence? [closed]

Variants of this question have been crossposted to Stack Overflow and Mathematics Stack Exchange. Additional answers may be found at these other sites. Computational Science People: I originally ...
2
votes
1answer
386 views

Trying to implement a simple/efficient combinations function in MATLAB

So, recently, I have found myself in the position of having to implement a combinations function in MATLAB. What I mean by this is the following: I simply need to list all possible combinations for an ...
3
votes
0answers
69 views

Parallel algorithm to use in place of PORTA?

We currently use PORTA software to find the list of facet-defining inequalities (FDI) for polytopes that we work with. For certain polytopes, PORTA works fine. But because it is a serial algorithm (...
3
votes
1answer
73 views

Improve optimization over 'mapping' of indices

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like to associate the rows in the reference ...
4
votes
1answer
126 views

Generating lattice clusters/graphs in parallel

I'm trying to generate all graphs with n or fewer vertices that can be embedded in some lattice, eg square, triangular, Kagome. Do there exist algorithms to both enumerate and draw these graphs? What ...
6
votes
1answer
144 views

Algorithm for generating all cartesian products, without rotations

(Not sure if that's the right SX site? I don't need actual code, so…) I'm looking for an algorithm that generates all cartesian products for a list of sets, but skips tuples that are just rotations ...
4
votes
1answer
509 views

What is the probabilistic model behind sudoku grids?

I'm talking about the vanilla sudoku game, with 9x9 grids equally split into 9 regions. I've tried a few approaches to estimate the probability that a specific number is in a specific location, but I ...
5
votes
2answers
216 views

Enumerating hexahedral cell vertices and faces in arbitrary dimension

I have a Cartesian mesh in $d$ dimensions, and I would like to enumerate all the subcells of a given hexahedral cell. If I am just enumerating the vertices of a cell (or cells that contain a vertex) I ...