2022 Developer Survey is open! Take survey.
7 votes
Accepted

Set the parameters of a Erdos-Renyi graph generator to get a specific mean degree

Average degree and mean degree are the same. In the $G(n,m)$ model, the average degree is $2m/n$. In the $G(n,p)$ model, the expected average degree is $np$. The actual average degree has normal ...
user avatar
5 votes
Accepted

Why arrival process of packets at a switch is not a Poisson Process?

"new flow arrivals" means "arrivals of new flows". A flow is a TCP connection (roughly); each individual TCP connection is a separate "flow". So, this is talking about new TCP connections, and the ...
user avatar
  • 140k
4 votes
Accepted

Requiring at least one alldiff constraint to be satisfied converted to SAT

If you want to model an alldiff() constraint in SAT, there are several options. Here are two different options you can try: One way is to expand $\text{alldiff}(x_1,\dots,x_n)$ into $n(n-1)/2$ ...
user avatar
  • 140k
4 votes
Accepted

How to impose Euclidean distance constraint in a constraint satisfaction problem without quadratic constraints?

You can't. You can't express this without using quadratic constraints. Your requirement is about Euclidean distance. The Euclidean distance is inherently quadratic. To be more precise about that: ...
user avatar
  • 140k
4 votes
Accepted

How to represent circles in x-y coordinates

This answer considers two cases: the overlapping relation between two disks, which is a very simple problem. the ovelapping or covering of a disk by a set of other disks, which is somewhat harder in ...
user avatar
  • 19.1k
4 votes

Converting reality to Petri net

I'm not sure how to approach your particular problem, but here is an attempt. Consider the recipe you are using as a collection of steps, some of which depend on others; for a salad you might have "...
user avatar
4 votes

Matching two people. One has 7% in common with the other. The other has 70% in common. What's a fair match score?

It seems you're looking for a symmetric set similarity measure. (Symmetric since, as you point out, $A$ should match $B$ as much as $B$ matches $A$. Set similarity since each person's preference is ...
user avatar
  • 1,682
3 votes

Boat riddle as a combinatorial optimization problem?

The river crossing problem using integer programming is solved by Börndorfer et al. in [1]. [1] Borndörfer, Ralf, Martin Grötschel, and Andreas Löbel. Alcuin's transportation problems and integer ...
3 votes
Accepted

Please explain linear programming as seen for this load balancing problem

How do you physically characterize the load of a processor, is it equivalent to CPU utilization? The program is modelling load like this. Whether you feel it's a good way to model load, and whether ...
user avatar
3 votes

Terminology needed for the computational solution to the Rubik's Cube

Kociemba wrote very nice algorithm, which is the fastest working algorithm returning optimal or almost optimal solution very efficiently. If you want to derive your own system, try in steps: 0) ...
user avatar
  • 9,325
3 votes
Accepted

Integer linear programming formulation of formula in DNF

You are looking for a four-dimensional convex polytope that contains all of the points $(x_1,x_2,x_3,x_4)$ that satisfy your condition, and but not any point $(x_1,x_2,x_3,x_4)$ that doesn't satisfy ...
user avatar
  • 140k
3 votes
Accepted

How can union-find algorithm be used with "real" data

Short answer: indirection. For instance, each object could have a field that contains an index into the id array. Or, you could use pointers. Standard union-find ...
user avatar
  • 140k
3 votes
Accepted

How to model references in an ontology

If you want to say something about an RDF triple (i.e., an rdf:Statement), you can use reification: ...
user avatar
  • 201
3 votes

Are objects appropriate for modeling the real world?

Object-oriented programming languages are designed to support programming. Whether they "properly" model the real world is beside the point and not the primary goal. So, when you ask "...
user avatar
  • 140k
2 votes

Terminology needed for the computational solution to the Rubik's Cube

have not heard of use of abstract languages to model the rubiks cube. however, there is a huge amount of group theory intrinsically associated with it, and there are natural ways to represent group ...
user avatar
  • 10.8k
2 votes

Terminology needed for the computational solution to the Rubik's Cube

It sounds like you want to compute the intersection of two languages. Depending upon what kind of languages you are looking at and how they're represented, you might look into the "product ...
user avatar
  • 140k
2 votes
Accepted

Modelling a dependency of multiple transitions on data in one place

I do not know if there is a variant of Petri nets that captures your intent exactly -- there probably is, there are so many -- but the feature can be expressed with regular Petri nets. Just add a ...
user avatar
  • 70.8k
2 votes
Accepted

Dynamic Shortest Path with Linear Programming

Our matrix is modelled as a graph $G = (V,E)$ with directed edges $E$ between cells $V$. We denote $V_{kl}$ as the set of nodes $j$ that respect $d_{jl} \leq k$. The edges $E$ exist between all nodes $...
user avatar
2 votes
Accepted

Efficient formulation for binary integer linear programming

Integer linear programming Let me suggest another way of formulating this with ILP that might be worth trying. Define combination to mean a list of all of the balls in a single box. For instance, ...
user avatar
  • 140k
2 votes

Finding a method to classify pixels according to how drastic their intensity change

One approach to distinguish between (1) vs (2)-or-(3) is to use a statistical hypothesis test. A statistical hypothesis test can tell you whether the amount of change is too large to be explained by ...
user avatar
  • 140k
2 votes

How to Determine Places, Transitions and Tokens in a Scenario when Modeling with Petri Nets?

Generally, the idea of a (normal) petri-net is to efficiently represent a system to model an arbitrary amount of 'agents' that change their state depending on certain transitions. (This would quite ...
user avatar
  • 6,978
2 votes
Accepted

Linear programming formulation for the single-source shortest path problem

Any optimal solution to the problem must satisfy $$ d_v = \min_{u\colon (u,v) \in E} (d_u + \ell_{uv}), $$ as well as $d_s = 0$, of course. Assuming the graph is connected, you can prove by induction ...
user avatar
2 votes

CNF form of variable assignment problem

If you only have to encode this (and don't have any other constraints on $x_i$), you can then use the following constraints: $x_1 < x_2 < \dots < x_{n-1} < x_n \leq k$ which is $n$ ...
user avatar
  • 521
2 votes

Scheduling N variable-time interdependent tasks across M workers

This can been seen as a variation of the job shop problem where you want to find the policy that yields the minimum makespan (time taken for all machines to process all jobs); as well as a variation ...
user avatar
  • 809
2 votes

How to Determine Places, Transitions and Tokens in a Scenario when Modeling with Petri Nets?

If you find it challenging to apply Petri Nets in modeling an application then it may help to consider the following mapping between the types of words found in a text description of an application ...
user avatar
2 votes
Accepted

Expressing a logical constraint in integer programming

Let $x \in [-10,10] \cap \mathbb Z$ and $y \in \{0,1\}$. Suppose that $$y = \begin{cases} 1 & \text{if } x \geq 3\\ 0 & \text{if } x \leq 2\end{cases}$$ To ensure that $y \neq 0$ when $x \...
user avatar
2 votes

Matching two people. One has 7% in common with the other. The other has 70% in common. What's a fair match score?

If you want to weight then cosine_similarity is an option. What this does is weight items that are not common in the population higher. Not sure how but I would base uniqueness on the two ...
user avatar
  • 431
2 votes

Integer linear programming formulation of formula in DNF

I will use a = 1, b = 2, etc... If a is set then c must be false and EITHER b or d must be true: 10a + c <= 10 10a + b + d <= 11 10a - b - d <= 9 ...
user avatar
  • 12.3k
2 votes

Modeling tiling problems as SAT problems

One example of a tiling problem that was successfully attacked by reducing it to a SAT instance was rectangular grid coloring. In "Extremely Complex 4-Colored Rectangle-Free Grids: Solution of Open ...
user avatar
  • 7,833
2 votes

How can union-find algorithm be used with "real" data

You don't say which union-find implementation you are talking about. On the abstract level, all is good; in the first quote, the authors already state that integers represent arbitrary objects! In ...
user avatar
  • 70.8k

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