The 2024 Developer Survey results are live! See the results

# Tag Info

Accepted

### Constraint Satisfaction: maximizing total value with no overlaps

You are looking for a maximum weight independent set in an interval graph, which can be solved in linear time (by a deterministic algorithm). By the way, the same is true also for a superclass of ...
• 22.7k
Accepted

### Graph coloring with fixed-size color classes

This problem is NP-hard: it is at least as hard as independent set. In particular, if you want to know whether there exists an independent set of size $N$, ask for a coloring with as many colors of ...
• 163k
Accepted

• 2,872
1 vote
Accepted

### If greater than or equal to zero then binary variable equals 1: integer linear program

Assuming that $L \le d_i < U$ with $L<0$ and $U>0$, you can add the following two constraints. The following encodes "if $d_i \ge 0$ then $v_i=1$": $$U v_i - d_i > 0.$$ The ...
• 29.6k
1 vote

### Encoding a binary sequence with shift in MILP

In constraint programming this particular type of constraint is known as a table constraint. It is generally said to be an existential constraint, since many other constraints can be encoded using a ...
• 111
1 vote
Accepted

### Constraint satisfaction problem: solve system, then evaluate whether many additional constraints are satisfied one at a time

If the constraints you have are of the form $a < b$ and $a=b$ (i.e., only unconditional inequality constraints), you can model them with a directed graph: each node represents a variable, and an ...
• 163k
1 vote

### Why N-Queens Problem is not used as experiment in CSP thesis?

n-queens problem can be solved quite efficiently with a very simple algorithm (finding all solutions takes ages, because the number grows exponentially). Getting anywhere near that efficiency with a ...
• 31.1k
1 vote
Accepted

### Algorithm to solve constraint satisfaction problems

Use an algorithm to find a perfect matching in a graph. Build a graph where each vertex represents a person, and draw an edge between each two people who don't share any characteristic, then look for ...
• 163k
1 vote
Accepted

### How to model a logical indicator when two inequalities hold in Integer Programming?

Your general approach is a good one. Use Boolean variable that captures whether an inequality holds to define $\delta_{i,j}^1$ and $\delta_{i,j}^2$. Then, use Express boolean logic operations in ...
• 163k
1 vote

### Which AC-3 algorithm is being used here?

The Fig. 5 in the question depicts AC-algorithm with backtracking. In fact, without backtracking, checking arc-consistency alone can hardly solve the 4-Queen problem. Unless it happens that choices ...
• 39k
1 vote

### Shift Organization algorithms (Constraint Programming + Marriage problem)

Turns out this problem is pretty hard to solve and is still under active research. This paper (2004) describes the state of the art.
• 121
1 vote
Accepted

### Checking large number of configurations with multiple constraints

Apparently, based on your comments, each condition is a linear inequality, you have a list of conditions, and you want to test whether an assignment satisfies all of the conditions, or find an ...
• 163k
1 vote

### CSP Forward checking with n-ary (and binary) constraints

Arc-Consistency algorithm only works on binary constraints.You have to use binary encoding and hidden variable encoding method.
• 53
1 vote

### CSP Forward checking with n-ary (and binary) constraints

Instead of forward checking, try arc consistency. You run arc consistency after every assignment to reduce backtracking. Another further improvement would be assigning a least constraining value (...
• 111
1 vote

### AC-3 Algorithms on CSP problem, What is happened when enocunter to an empty domain variable?

You've misunderstood the book. It's not describing the AC-3 algorithm; it's describing some other algorithm. The book is describing an algorithm that combines both guess-and-backtrack together with ...
• 163k

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