Thread Subject:

How to generate discrete combinations with fixed sum?

Good afternoon,

I am hoping someone in the community may be able to help me out with my problem.
I am using Matlab to generate combinations with constraints, as follows:

I have a fixed value, let's say 156, that I want to distribute amongst 20 slots in packages of 4. For each problem, I define the following constraints:
- the possible slots (out of the 20) amongst which these 156 may be distributed;
- the minimum amount of load on each slot
- the maximum amount of load on each slot

The problem is that I tried to generate all possible alternatives, then eliminate those that do not comply with the constraints. However, I get the OUT OF MEMORY error, so I really have to find a more efficient way of doing this.

Appreciate any kind of help!

Thanks,

JCF

"Jose " <zeca_ferrao@hotmail.com> wrote in message <i7amot$s7$1@fred.mathworks.com>...
> Good afternoon,
>
> I am hoping someone in the community may be able to help me out with my problem.
> I am using Matlab to generate combinations with constraints, as follows:
>
> I have a fixed value, let's say 156, that I want to distribute amongst 20 slots in packages of 4. For each problem, I define the following constraints:
> - the possible slots (out of the 20) amongst which these 156 may be distributed;
> - the minimum amount of load on each slot
> - the maximum amount of load on each slot
>
> The problem is that I tried to generate all possible alternatives, then eliminate those that do not comply with the constraints. However, I get the OUT OF MEMORY error, so I really have to find a more efficient way of doing this.
>
> Appreciate any kind of help!
>
> Thanks,
>
> JCF

The query isn't clear to me. What is a package? What is load?

Might help to show a few acceptable and unacceptable combinations

Ross

>
> The query isn't clear to me. What is a package? What is load?
>
> Might help to show a few acceptable and unacceptable combinations
>
> Ross

Ok, I'll try to explain it better.

I have 20 slots on which to distribute a given total load of 156 kg;
I have discretised my total load in packages of 4kg each;
I want to obtain all the possible combinations of package distributions amongst the 20 slots, subject to the following constraints:
- some of the slots cannot be used (they are identified by numbers)
- some of the slots have a minimum value of load
- some of the slots have a maximum value of load;

Ill give a rough example: imagine 5 slots on which I want to distribute 10 kg in packages of 2; some possible combinations without constraints) would be:
[2 2 2 2 2]
[4 0 2 2 2]
[4 0 0 4 2]

But, if I define that slot nr 2 cannot receive load, then the option [2 2 2 2 2] would not be considered.
On the other hand, if I define that slot 4 cannot handle more than 2 kg, then option [4 0 0 4 2] would also be discarded.

I think that the problem is not too complex, but the number of combinations that arise when working with 20 slots and more than 100 kg of load in small packages makes it impossible to calculate all the combinations and then eliminate the ones that do not comply with the constraints.

I was hoping that there'd be a way of calculating just the combinations that satisfy the constraints.

Thanks a lot for your help!

JCF

"Jose " <zeca_ferrao@hotmail.com> wrote in message <i7bc2f$qer$1@fred.mathworks.com>...
>
> >
> > The query isn't clear to me. What is a package? What is load?
> >
> > Might help to show a few acceptable and unacceptable combinations
> >
> > Ross
>
> Ok, I'll try to explain it better.
>
> I have 20 slots on which to distribute a given total load of 156 kg;
> I have discretised my total load in packages of 4kg each;
> I want to obtain all the possible combinations of package distributions amongst the 20 slots, subject to the following constraints:
> - some of the slots cannot be used (they are identified by numbers)
> - some of the slots have a minimum value of load
> - some of the slots have a maximum value of load;
>
> Ill give a rough example: imagine 5 slots on which I want to distribute 10 kg in packages of 2; some possible combinations without constraints) would be:
> [2 2 2 2 2]
> [4 0 2 2 2]
> [4 0 0 4 2]
>
> But, if I define that slot nr 2 cannot receive load, then the option [2 2 2 2 2] would not be considered.
> On the other hand, if I define that slot 4 cannot handle more than 2 kg, then option [4 0 0 4 2] would also be discarded.
>
> I think that the problem is not too complex, but the number of combinations that arise when working with 20 slots and more than 100 kg of load in small packages makes it impossible to calculate all the combinations and then eliminate the ones that do not comply with the constraints.
>
> I was hoping that there'd be a way of calculating just the combinations that satisfy the constraints.
>

There are an infinite number of combinations that meet the constraints.

"Jose " <zeca_ferrao@hotmail.com> wrote in message <i7bc2f$qer$1@fred.mathworks.com>...
>
> >
> > The query isn't clear to me. What is a package? What is load?
> >
> > Might help to show a few acceptable and unacceptable combinations
> >
> > Ross
>
> Ok, I'll try to explain it better.
>
> I have 20 slots on which to distribute a given total load of 156 kg;
> I have discretised my total load in packages of 4kg each;
> I want to obtain all the possible combinations of package distributions amongst the 20 slots, subject to the following constraints:
> - some of the slots cannot be used (they are identified by numbers)
> - some of the slots have a minimum value of load
> - some of the slots have a maximum value of load;
>
> Ill give a rough example: imagine 5 slots on which I want to distribute 10 kg in packages of 2; some possible combinations without constraints) would be:
> [2 2 2 2 2]
> [4 0 2 2 2]
> [4 0 0 4 2]
>
> But, if I define that slot nr 2 cannot receive load, then the option [2 2 2 2 2] would not be considered.
> On the other hand, if I define that slot 4 cannot handle more than 2 kg, then option [4 0 0 4 2] would also be discarded.
>
> I think that the problem is not too complex, but the number of combinations that arise when working with 20 slots and more than 100 kg of load in small packages makes it impossible to calculate all the combinations and then eliminate the ones that do not comply with the constraints.
>
> I was hoping that there'd be a way of calculating just the combinations that satisfy the constraints.
>

You will quickly find that the number of combinations
is quite large. But it IS simply done recursively.

Look at the first slot. Assume that it can take any of
these loads.

0,2,4,6,8,10

Now, simply compute the possible combinations for the
other slots, given what remains to be distributed for
each of those possibilities. At some point, there is either
nothing left to be distributed, or more than the remaining
slots can carry. In either case, you are done with that
thread of the recursion.

Simple recursion.

John

>
> You will quickly find that the number of combinations
> is quite large. But it IS simply done recursively.
>
> Look at the first slot. Assume that it can take any of
> these loads.
>
> 0,2,4,6,8,10
>
> Now, simply compute the possible combinations for the
> other slots, given what remains to be distributed for
> each of those possibilities. At some point, there is either
> nothing left to be distributed, or more than the remaining
> slots can carry. In either case, you are done with that
> thread of the recursion.
>
> Simple recursion.
>
> John

Ok, I'll do it recursively, it should work.
Thanks a lot for your help, John.

JCF

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <i7bd9s$eqv$1@fred.mathworks.com>...
> "Jose " <zeca_ferrao@hotmail.com> wrote in message <i7bc2f$qer$1@fred.mathworks.com>...
> >
> > >
> > > The query isn't clear to me. What is a package? What is load?
> > >
> > > Might help to show a few acceptable and unacceptable combinations
> > >
> > > Ross
> >
> > Ok, I'll try to explain it better.
> >
> > I have 20 slots on which to distribute a given total load of 156 kg;
> > I have discretised my total load in packages of 4kg each;
> > I want to obtain all the possible combinations of package distributions amongst the 20 slots, subject to the following constraints:
> > - some of the slots cannot be used (they are identified by numbers)
> > - some of the slots have a minimum value of load
> > - some of the slots have a maximum value of load;
> >
> > Ill give a rough example: imagine 5 slots on which I want to distribute 10 kg in packages of 2; some possible combinations without constraints) would be:
> > [2 2 2 2 2]
> > [4 0 2 2 2]
> > [4 0 0 4 2]
> >
> > But, if I define that slot nr 2 cannot receive load, then the option [2 2 2 2 2] would not be considered.
> > On the other hand, if I define that slot 4 cannot handle more than 2 kg, then option [4 0 0 4 2] would also be discarded.
> >
> > I think that the problem is not too complex, but the number of combinations that arise when working with 20 slots and more than 100 kg of load in small packages makes it impossible to calculate all the combinations and then eliminate the ones that do not comply with the constraints.
> >
> > I was hoping that there'd be a way of calculating just the combinations that satisfy the constraints.
> >
>
> You will quickly find that the number of combinations
> is quite large. But it IS simply done recursively.
>
> Look at the first slot. Assume that it can take any of
> these loads.
>
> 0,2,4,6,8,10
>
> Now, simply compute the possible combinations for the
> other slots, given what remains to be distributed for
> each of those possibilities. At some point, there is either
> nothing left to be distributed, or more than the remaining
> slots can carry. In either case, you are done with that
> thread of the recursion.
>
> Simple recursion.
>
> John

As I understand it, John's nice suggestion is related to an optimisation technique called dynamic programming, which the OP might like to read up on.

Dynamic programming could be used to search for an optimal assignment of packages to slots (e.g. most evenly balanced, or most profitable, or whatever objective function you want to use),

Ross

The function implemented here does something pretty close to what you asked
http://www.mathworks.com/matlabcentral/fileexchange/17818

You can use it as template to implement the recursive algorithm.

Bruno