7
votes
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.4k
4
votes
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 ...
- 376
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: ...
D.W.♦
- 154k
4
votes
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$. ...
D.W.♦
- 154k
4
votes
Accepted
Is 2-SAT over Linear Real Arithmetic in P or NP?
You can express the fact that a variable $x_i$ is Boolean as follows:
$$
(0 \leq x_i \leq 1) \land ((x_i \leq 0) \lor (x_i \geq 1)).
$$
You can express the condition $x_i \lor x_j \lor x_k$ as
$$
x_i +...
- 274k
4
votes
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 ...
D.W.♦
- 154k
3
votes
Accepted
Maximum set of equalities, subject to some inequalities
Using your graph theoretic formulation, this problem can be restated as the multi-cut problem.
Given a graph $G = (V, E)$ and a set of pairs $(s_i, t_i) \in I$ find a set of edges $E' \subseteq E$ ...
- 3,857
3
votes
How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions
Let $\mathcal{C}(n,m)$ denote the set of sequences you are interested in, namely non-decreasing sequences of length $n$ consisting of integers from $\{0,\ldots,m\}$, and let $C(n,m) = |\mathcal C(n,m)|...
- 274k
3
votes
Accepted
How to know if a problem belongs to NP Class?
Make sure you use NP correctly. To say something belongs to NP doesn't really say anything, except that a right solution of the problem can be checked fast.
From my experience, it's more about the ...
- 185
2
votes
Finding infeasible sets of constraints (CSP)
If your system of constraints is expressed as a SAT instance, then this is known as the MAX-SAT problem. MAX-SAT is harder than SAT, but there are standard algorithms. The case of other discrete ...
D.W.♦
- 154k
2
votes
How to model equality in Integer Linear Programming
Use Cast to boolean, for integer linear programming, setting $x=a-b$ and $y=v$. This only works if you have a constant upper bound on $|a-b|$. Otherwise, I don't know how to express it in an ILP.
...
D.W.♦
- 154k
2
votes
Need recursive version of Conflict based backjumping
When a conflict is found during a recursive constraint satisfaction search there may be assignments and inferences in the call stack that have no connection to the conflict. Instead of backtracking ...
- 8,011
1
vote
Encoding "all-except" constraints in CNF
Let $[b]$ to denote $1$ if $b$ is true, $0$ if $b$ is false.
We have
$$
\begin{align}
& \bigwedge_{b \in B \setminus B_i} b \\
\iff & \sum_{b \in B \setminus B_i} [\neg b] = 0 \\
\iff & \...
- 2,205
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 ...
- 27.4k
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 ...
D.W.♦
- 154k
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 ...
- 27.8k
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 ...
D.W.♦
- 154k
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 ...
D.W.♦
- 154k
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 ...
D.W.♦
- 154k
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.
- 43
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 ...
D.W.♦
- 154k
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 ...
- 11k
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 ...
- 884
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