Tagged Questions

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
1answer
39 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 ...
0
votes
0answers
13 views

Max weighted subset (max sum diversification)

Given a set of elements $V$, with known cost $\pi_S$ for each subset $S \subset V$ and a monotone increasing function on the subsets $f(S)$ . I'm wondering if there is a pseudo-polynomial algorithm ...
0
votes
0answers
20 views

Partitioning of a set w.r.t. injectivity

I have two disjoint sets A and B which are merged into a set C=A+B which is then partitioned. The number of such partitions is the nth Bell number. I want to filter out the partitions to be injective, ...
0
votes
1answer
69 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
61 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 ...
1
vote
3answers
459 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
166 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
151 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
231 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
238 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
57 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
68 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
102 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
135 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
261 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
196 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 ...