New answers tagged

2

The standard way to create soft constraints in MaxSAT is to use label variables: For each $AMO_j$ constraint, create a new variable $l_j$. Then create an unit clause $(\lnot l_j)$ with weight $1$ and add the literal $l_j$ to every clause of the standard $AMO_j$ encoding that contains only hard (infinite weight) clauses. Now the label variable $l_j$ acts ...


2

You can use a binary variable z in {0,1}: x_1 <= x_2 x_1 <= x_3 x_1 >= x_2 - Mz x_1 >= x_3 -M(1-z) It gives you a PLNE. If you have one min inequality, it's better to use the previous answer.


0

This problem is NP-hard. The decision problem, whether a perfect allocation exists, it self is NP-hard. The decision variant is actually the same as the subset sums problem. Given a set of numbers $S$ and a target number $k$, is there a subset of $S$ that sum up to $k$. The problem itself is a variation of the Knapsack problem. However, the subset sum ...


3

Solve two linear programs. The first has the constraints $$ A \mathbf x = \mathbf b,\quad x_1 = x_2 \le x_3. $$ The second has the constraints $$ A \mathbf x = \mathbf b,\quad x_1 = x_3 \le x_2. $$ Choose whichever solution gives you a smaller value for $\mathbf c' \mathbf x$. This works for your particular situation. It doesn't scale to a case where you ...


3

This technique is called Lagrangian relaxation. The regular $DP$ approach, where $DP[a][b]$ represents the length of the longest increasing subsequence that ends in the $a$'th number and restarts at most $b$ times, is $\mathcal{O}(nk \log n)$. For convenience we'll assume the last number is the largest, and therefore $DP[n][k]$ is the value we are looking ...


3

The general $n \times m$ case is easily seen to be NP-hard by reduction from set cover. Add a column for each element; each row is the indicator function of a subset; set $t_j = 0$ for each column. A slightly more complicated reduction from subset sum shows that this is NP-hard even for $m = 2$. Suppose we are given a subset sum problem instance where we ...


Top 50 recent answers are included