3
$\begingroup$

I have a problem like this

$x_1 +x_2 +x_3 =10$ let's assume $0 \leq x_i \leq 10$

It is obvious that this problem has more than one solution For example :

Solution 1 : $x_1 =0 , x_2= 1 , x_3 =9$

Solution 2 : $x_1 =0 , x_2= 9 , x_3 =1$

Solution 3 : $x_1 =1 , x_2= 8 , x_3 =1$

As we can see, solution 1,2 are similar since they both use 0,1,9 but for different variables

How can we avoid these similarities while trying to find all possible solutions ?

My main question is regarding a real problem you can see in the picture we have 13 buckets (each has 4 numbers) The solution tells me what numbers are in each bucket. I forced the total value of each bucket Ascending look at the solution 2, bucket 6,7 have the same total value = 27 the next solution can easily swap the content of bucket 6,7 and create a new solution (which is not actually new) same can happen to bucket 8,9 or buckets 12,13

enter image description here

$\endgroup$

2 Answers 2

4
$\begingroup$

You can add a continuous variable $h_i$ for each bucket $i$ to contain its "hash value", then constrain the hash values to be in nondecreasing order ($h_1 \le h_2 \le \dots$). The hash function just needs to be a linear function of the bucket contents, say $h_i = \sum_j r_j x_{ij}$ where $x_{ij}$ is the model variable that represents the $j-th$ number in bucket $i$ and $r_j$ is a pseudorandom number you pick before solving the model. There's a theoretical chance two buckets could provide the same hash code (making them interchangeable), but it's sufficiently unlikely to happen that I personally would not lose any sleep over it.

$\endgroup$
7
$\begingroup$

you can order the variables:

$x_1 \le x_2 \le x_3$

$\endgroup$
1
  • $\begingroup$ Works in this example , thanks , Please also note the added comment in question if possible $\endgroup$ Commented May 29 at 12:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.