CODEWITHSUNDEEP
algorithmdistributionsetbin-packing
dfens
dfens

Reputation: 5515

Fair product distribution algorithm

Here is my problem:

Example:

We have 3 days to distribute products. Products of company A: a,a,a,a,a. Products of company B: b,b,b. Products of company C: c,c

Fair distribution: [aab,aabc,abc]

Invalid distribution: [aabc,aabc,ab] because on 1st day there are 4 products, on 3rd day 2 products (difference > 1)

Invalid distribution: [abc,aabc,aab] because on 1st day there is one product A, and on 2nd day there are 2 products A, so distribution of product A is not non-decreasing

EDIT if there is a case that makes fair distribution impossible please provide it with short description, I'll accept the answer

Upvotes: 6

Views: 865

Answers (4)

Zayenz
Zayenz

Reputation: 1964

Since I thought the problem was fun, I did a model for finding solutions using MiniZinc. With the Gecode backend, the initial example is shown to have 20 solutions in about 1.6 ms.

include "globals.mzn";

%%% Data
% Number of companies
int: n = 3;
% Number of products per company
array[1..n] of int: np = [5, 3, 2];
% Number of days
int: k = 3;

%%% Computed values
% Total number of products
int: totalnp = sum(np);
% Offsets into products array to get single companys products 
% (shifted cumulative sum).
array[1..n] of int: offset = [sum([np[j] | j in 1..i-1]) 
                          | i in 1..n];

%%% Predicates
predicate fair(array[int] of var int: x) =
      let { var int: low,
            var int: high
      } in
        minimum(low, x) /\
        maximum(high, x) /\
        high-low <= 1;
predicate decreasing_except_0(array[int] of var int: x) =
        forall(i in 1..length(x)-1) (
                 (x[i] == 0) \/
                 (x[i] >= x[i+1])
        );
predicate consecutive(array[int] of var int: x) =
        forall(i in 1..length(x)-1) (
             (x[i] == x[i+1]) \/
             (x[i] == x[i+1]-1)
        );

%%% Variables
% Day of production for all products from all companies
array[1..totalnp] of var 1..k: products 
          :: is_output;
% total number of products per day
array[1..k] of var 1..totalnp: productsperday 
        :: is_output;

%%% Constraints 
constraint global_cardinality(products, productsperday);
constraint fair(productsperday);
constraint
    forall(i in 1..n) (
         let { 
             % Products produced by company i
             array[1..np[i]] of var int: pi
                = [products[j] | 
                 j in 1+offset[i]..1+offset[i]+np[i]-1],
             % Products per day by company i
             array[1..k] of var 0..np[i]: ppdi
         } in
           consecutive(pi) /\
           global_cardinality(pi, ppdi) /\
           decreasing_except_0(ppdi)
    );

%%% Find a solution, default search strategy
solve satisfy;

The predicates decreasing_except_0 and consecutive are both very naive, and have large decompositions. To solve larger instances, one should probably replace them with smarter variants (for example by using the regular constraint).

Upvotes: 2

Matthieu M.
Matthieu M.

Reputation: 299740

It has been shown that the points 4 and 5 were incompatible:

  • 4: For any day j, for any company A, C(j,A) == 0 or C(j,A) >= C(j+1,A)
  • 5: For any days i and j, |C(i) - C(j)| <= 1

You thus need relaxing either constraint. Honestly, while I get a feeling of why 4 was put in place (to avoid delaying the distribution of one company indefinitely) I think it could be expressed otherwise to consider the first and last day of distribution as being special (since on the first day, you typically take what's left by the previous company and on last day you distribute what's left).

Point 3 does force the contiguity.

Mathematically:

For any company A, which has products, there exists two days i and j such that:

  • C(i,A) > 0 and C(j,A) > 0
  • for any day x such that x < i or x > j, C(x,A) = 0
  • for any day x such that i < x < j, C(x,A) = C(x)

Admittedly, the problem then becomes trivial to solve :)

Upvotes: 1

j_random_hacker
j_random_hacker

Reputation: 51226

Gareth Rees's comment on djna's answer is right -- the following counterexample is unsolvable:

  • 3 days, 7 items from company A and 5 items from company B

I tested this with the following dumbest-possible brute-force Perl program (which takes well under a second, despite being very inefficient):

my ($na, $nb) = (7, 5);
for (my $a1 = 0; $a1 <= $na; ++$a1) {
    for (my $a2 = 0; $a2 <= $na - $a1; ++$a2) {
        my $a3 = $na - $a1 - $a2;
        for (my $b1 = 0; $b1 <= $nb; ++$b1) {
            for (my $b2 = 0; $b2 <= $nb - $b1; ++$b2) {
                my $b3 = $nb - $b1 - $b2;
                if ($a1 >= $a2 && $a2 >= $a3 || $a1 == 0 && $a2 >= $a3 || $a1 == 0 && $a2 == 0) {
                    if ($b1 >= $b2 && $b2 >= $b3 || $b1 == 0 && $b2 >= $b3 || $b1 == 0 && $b2 == 0) {
                        if (max($a1 + $b1, $a2 + $b2, $a3 + $b3) - min($a1 + $b1, $a2 + $b2, $a3 + $b3) <= 1) {
                            print "Success! ($a1,$a2,$a3), ($b1,$b2,$b3)\n";
                        }
                    }
                }
            }
        }
    }
}

Please have a look and verify that I haven't made any stupid mistakes. (I've omitted max() and min() for brevity -- they just do what you'd expect.)

Upvotes: 3

djna
djna

Reputation: 55897

I don't think that you can always fulfil your requirements.

Consider 4 days, and 6 items from supplier A and 6 items from supplier B.

Upvotes: 0

Related Questions