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.8k
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 +...
- 279k
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.♦
- 166k
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 ...
- 401
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.♦
- 166k
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)|...
- 279k
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
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.♦
- 166k
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.♦
- 166k
2
votes
Accepted
Is there a linear programming method that is polynomial in the number of variables, constraints and bitlength of numbers?
Interior-point methods such as Khachiyan’s and Karmarkar’s are, indeed, polynomial in the size of the input, i.e., in the number of variables, constraints, and the bitlength of the coeficients. This ...
- 2,231
2
votes
Accepted
How can I model this optimization problem?
If we ignore the upper bound $m$, this is the problem of finding a maximum weight clique in a weighted graph. Delete all unavailable objects, and create a graph, where each object is a vertex, and ...
D.W.♦
- 166k
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,149
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.♦
- 166k
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,942
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
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.6k
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.♦
- 166k
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.♦
- 166k
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 ...
- 39.1k
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.♦
- 166k
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
Only top scored, non community-wiki answers of a minimum length are eligible