# 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 ...
Accepted

### How do you proceed if your milp is not solvable

It's hard to specify one approach because it depends on your needs. From my experience I can suggest the following: Precision Typical solvers report solutions as "optimal" using gap parameters ...
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: ...
Accepted

### Binarization of Constraints

Introduce a new variable $Q$, whose domain is $\{0000,0001,0010,\dots,1111\}$. It represents the value of $C1,C2,C3,P$. For instance, if $Q=0001$, that means that $C1=0$, $C2=0$, $C3=1$, $P=0$. ...
Accepted

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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 ...
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.
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 (...
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 ...
1 vote

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

the 2d case of "graph embedding" is also known simply as "graph drawing" and there is a very wide variety of techniques. the most common is probably force directed graph drawing. however heres a basic ...
1 vote

### Help Understanding the Type and Complexity of my Programming Task

Divide this problem into two parts. I am attempting to design a program to optimize daily fantasy baseball rosters given certain information. The context here is that I will be designing rosters of ...
1 vote

### Isn't Domain of a variable nothing but a constraint?

Even though a domain may be considered just another type of constraint, there do exist good reasons to keep them separated, and it may be easier to think of them from a pure mathematical standpoint. ...

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