2
$\begingroup$

I created the following constraint (missing what exists in this context means)

For all a in A there exists a b in B so that for all c in C it holds 
that a variable x(a, b + c) is equal to a parameter m(a, c)

short:

$$\forall a \in A, \exists b \in B, \forall c \in C: x(a,b+c)=m(a,c)$$

What this constraint is trying to do is to ensure that for a given object a the values of a given tuple m(a,c) (both binary tuples) can be found in the same order. Of course that would mean that only |B|-1 constraints have to be true which is a problem (that I did not notice before). Can this be reformulated without the exists clause?

Therefore, m(a,c) is the given parameter of a smaller tuple for some object a. The constraint ensures that x for an object a starting at some position b contains the values of m(a,c) in the order of m(a,c). The tuples m(a,c) all have different sizes.

Therefore, with this and additional constraints I tried to solve a knapsack problem in which a set of different tuple have to be placed within a larger tuple. The tuple contains binary values representing 1 the position is used 0 the position is unused. Hence, if a position is not used (0) a different tuple can use it if it doesn't gets in conflict with the other assignments:

$$\forall b\in B: \sum_{a\in A} x(a,b)\leq 1$$

it doesn't matter whether for a object a in x positions b are marked as used even so they are not. It only matters to find whether for a tuple of a certain size the other tuples can be somehow fitted into.

Can the first constraint somehow reformulated to be linear? If not, what is the best I could do?

$\endgroup$
3
  • $\begingroup$ Your use of "tuple" is a bit confusing. For fixed $a$ and $c$, is $m(a,c)$ a scalar or a vector (in which case is $x(i,j)$ a vector for fixed $i$ and $j$)? What do you mean by "the tuples $m(a,c)$ all have different sizes"? $\endgroup$
    – prubin
    Jun 22, 2022 at 17:53
  • $\begingroup$ An ordered set, a vector - best is probably to see it as array. Basically I tried to describe a packaging problem in which I have arrays of different sizes that have to be put in a larger array (either in a way that they fit or that the larger arrays length is minimised). The 1 in the smaller arrays will mark a used field and the 0 an unused. The distance between 0 and 1 of a smaller array placed in a larger have to be maintained. If a field isn't used by one array it can be used by another. Hence arrays can overlap as long as each field is only used by one. $\endgroup$
    – baxbear
    Jun 22, 2022 at 17:58
  • $\begingroup$ The constraint shown above should have been the major constraint solving the placement until I noticed that (with my skills) if I implement the constraint there will always be |A|-|B|-1 constraints that will be false for each a in A. $\endgroup$
    – baxbear
    Jun 22, 2022 at 18:00

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.