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

1
vote
0answers
21 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
27 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
66 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 ...
3
votes
1answer
72 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
60 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
52 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
46 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
39 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 ...
0
votes
0answers
27 views

permutations sampling by probability matrix

I am looking for effective and reliable algorithm which is able to generate random samples of permutations by square doubly stochastic probability matrix $P$ (n x n) distribution ($\sum_{i}p_{i,j} = ...
1
vote
0answers
58 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
81 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
126 views

enhancing a MIP formulation of Ising model

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
78 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 ...
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
316 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
175 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
388 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
338 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
68 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
124 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
141 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
451 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
213 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 ...