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 ...
SamM's user avatar
  • 1,702
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 ...
D.W.'s user avatar
  • 159k
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 ...
D.W.'s user avatar
  • 159k
3 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 ...
John Frederick Chionglo's user avatar
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: ...
unor's 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 "...
D.W.'s user avatar
  • 159k
3 votes
Accepted

A voting scheme where votes are scriptable

Broad context First off, the field in which this sort of research would be carried out is called computational social choice (theory). Searching for papers or books in that field will give you exactly ...
ADdV's user avatar
  • 277
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 ...
Raphael's user avatar
  • 72.4k
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 $...
BlueMoon93's 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, ...
D.W.'s user avatar
  • 159k
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 ...
Yuval Filmus's 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$ ...
MotiNK's user avatar
  • 553
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 ...
GEL's user avatar
  • 829
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 ...
Discrete lizard's user avatar
  • 8,248
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 ...
orlp's user avatar
  • 13.4k
2 votes

Efficient encoding of sudoku puzzles

Here's a no-table method that combines a 75-bit encoding of the solution grid with an 81-bit encoding of which cells are clues to give a 156 bit fixed-length encoding for all puzzles ([edit] also see ...
53x15's user avatar
  • 121
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 ...
paparazzo's user avatar
  • 431
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 ...
Kyle Jones's user avatar
  • 8,091
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 ...
Raphael's user avatar
  • 72.4k
2 votes

Are objects appropriate for modeling the real world?

It sounds like you have already answered all of your own questions: objects are not meant to model the real world, although they have been marketed as such and perhaps that was an intention at some ...
Aaron Rotenberg's user avatar
1 vote
Accepted

What is a logical approach to developing an algorithm which can find the optimal parameters for a function which make it best fit a given data set?

The answer depends on what is your notion of "optimal parameters", and on the specific model you have in mind. Suppose your model is $f(x,\overline{p})$, where $p$ is the parameters vector, and you ...
Ariel's user avatar
  • 13.4k
1 vote

Develop a winning strategy for a game

The nature of a position in this game depends only on $n \bmod{11}$. If $n \equiv 0,2,4 \pmod{11}$ then $n$ is a losing position, otherwise it is a winning position. You can prove this by induction by ...
Yuval Filmus's user avatar
1 vote

Is this problem just an application of traveling salesman? If not is it some other already "solved" problem?

This problem comes down to a transportation problem (actually the Wikipedia article is not very good), although it is not exactly the problem you are stating. As David Richerby stated in the comments, ...
RoyPJ's user avatar
  • 156
1 vote
Accepted

How to convert two conflicting objective functions into a single objective function

To turn a maximisation problem into a minimisation one (or vice versa), simply multiply the value by -1. Hence you want w1 * f1 - w2 * f2, for some appropriate choice of weights w1, w2 (which could ...
NietzscheanAI's user avatar
1 vote

Modeling tiling problems as SAT problems

It's possible that you're talking about Wang tiles. Imagine that you have to fill up a matrix with tiles that cannot be rotated. Each side of each tile is a given color. If two tiles are placed ...
SamM's user avatar
  • 1,702
1 vote
Accepted

Set Cover and additional constraints

Once you've defined the variables $x_{ij},y_j,z_i$, all you need to do is add ILP constraints that enforce the domain requirements. The general approach is: write down the list of domain requirement, ...
D.W.'s user avatar
  • 159k
1 vote

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

When I use Petri nets or explain them to others, my general policy is to always name places and transitions and places by propositions of the form <subject> <predicate>. The subject is a ...
reinierpost's user avatar
  • 5,519
1 vote

Linear programming formulation for the single-source shortest path problem

The claim that "increasing any single $d_u$ never forces us to decrease some other $d_v$" can be seen from the constraint $d_v \leq d_u + l_{uv}$. Here, increasing $d_u$ will not cause a ...
xdavidliu's user avatar
  • 858

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