I don't think it is possible using solver...
Hi. Just 2 cents. Surprisingly, Solver can arrive at a solution fairly
quickly.
Solver can do about =SQRT(200), or 14, of these. The op is using 9, so
this is ok.
Instead of letters "a" thru "i", rename them numbers 1-9.
Ie instead of {e,c,a,d,b}, use {5,3,1,4,2}
For this example, fill a 9*9 square area with your choices. Each person
is picking only 5 out of 9, so this is a problem.
One "standard" method for those who don't bid enough choices is to fill
the remaining choices with those not selected in order.
For example, if one picks {2,4,6,8,9}, fill the remaining choices with
1,3,5,7. Applying the same rule to each person makes it a little more
"fair" to those who don't bid enough selections.
What you are now trying to do is make another 9*9 square of Solver Binary
constraints. ie Either 0 or 1.
Select a 9*9 area, fill it with 1's,, and name the range "Bin."
Select "Bin", and hold the shift key. Select the down arrow, and right
arrow to expand the selection by 1 row and 1 column.
Now, click the AutoSum button. This puts Sum formulas across the bottom
and side. Delete lower corner sum for clarity.
Your basic Solver problem is now:
Minimize =SUMPRODUCT(Input,Bin)
Subject to:
Lower row of Sum()'s) = 1
Verticle Column of Sum()'s = 1
"Bin" area is Bin for Binary.
The solution in the bin area will have only one "1" in each row, and each
column.
However, there is a problem at this point!!!
The first choice of 1 person could be the 4th choice of someone else.
The binary array will most likely be giving the same solution to multiple
people.
In other words, the first person could get his first choice, and the
second person could get his second choice, but they happen to be the same.
The solution is to go back to your input area, and rearrange the data.
You need to take what is known as the Inverse Permutation of each person's
choices.
For example, if the first person's choices are in this order {5,3,1,4,2},
change them to {3,5,2,4,1}
(As a quick check for myself...)
InversePermutation[{5,3,1,4,2}]
{3,5,2,4,1}
What this means is that my first choice is 5, so position 5 gets 1
Second choice is 3, so position 3 gets 2, ...etc.
After you take the Inverse Permutation of each persons choice, you can run
solver.
I like to use Conditional Formatting to highlight the cells that have a
corresponding 1 in the Bin area.
On my test example program, the upper right corner of Bin had a 1. This
tells me that I am to use the upper right corner of Input area.
this cell in Input area had a 1. This tells me that person 1 had his
first choice. It's in position 9, so first person's first choice was 9,
and he got it.
On my quick example, 5 people got their first choice, 2 people got their
second choice, and 1 person got their 3rd choice.
There is no person 9, so I filled in his choices with a high penalty value
of say 20.
Person 9 (who doesn't exist), got the left over position 8. But since
one location is unassigned, this is ok.
Be sure to set Solver's options to "Assume linear Model" to make it run
fast!!
Also note that you "may" have more than 1 optimal solution if two
selections are swapped.
--
Dana DeLouis
Peo Sjoblom said:
I don't think it is possible using solver, in fact unless someone writes a
large piece of VBA code I can't see how Excel is the best way for this
problem either. At least it is not really better than a pen and a paper
IMHO. I mean isn't this just variety of the problem where you have a
number of people placed at tables then rotate them to another table and
they cannot sit at the same table more than once and not with the same
people either etc There are quite a lot of these if you Google search on
"Can not sit at the same table twice" or something like that.
To me the question sounds as it is from a college class and not a real
life problem.
