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)


$$\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?

  • $\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 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 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 at 18:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.