Maximization/Optimization

[agutts6]

Baseball question!

But if that's not your thing, feel free to think of it in terms of your favorite sport.

Let's say I have a typical roster of players. The cell values are their unit values, if they play each position (it's different for each player--if they play one position, they'll have more or less value than they do if they play another).

[TABLE="width: 500"]
<tbody>[TR]
[TD]Name[/TD]
[TD]First Base[/TD]
[TD]Second Base[/TD]
[TD]Third Base[/TD]
[TD]Shortstop[/TD]
[/TR]
[TR]
[TD]Sam
[/TD]
[TD]5[/TD]
[TD]4[/TD]
[TD]2[/TD]
[TD]1
[/TD]
[/TR]
[TR]
[TD]Tom[/TD]
[TD]5[/TD]
[TD]3[/TD]
[TD]3[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]Will[/TD]
[TD]2[/TD]
[TD]3[/TD]
[TD]3[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]Brian[/TD]
[TD]4[/TD]
[TD]3[/TD]
[TD]4[/TD]
[TD]4[/TD]
[/TR]
[TR]
[TD]Tod
[/TD]
[TD]5[/TD]
[TD]6[/TD]
[TD]2
[/TD]
[TD]6[/TD]
[/TR]
[TR]
[TD]Matt[/TD]
[TD]6[/TD]
[TD]3[/TD]
[TD]3[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]Ahmed[/TD]
[TD]2[/TD]
[TD]7[/TD]
[TD]1[/TD]
[TD]4[/TD]
[/TR]
[TR]
[TD]Billy[/TD]
[TD]3[/TD]
[TD]1[/TD]
[TD]3[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]Steve[/TD]
[TD]2[/TD]
[TD]3[/TD]
[TD]6[/TD]
[TD]6[/TD]
[/TR]
[TR]
[TD]Paul[/TD]
[TD]1[/TD]
[TD]4[/TD]
[TD]1[/TD]
[TD]4[/TD]
[/TR]
[TR]
[TD]Benjamin Netanyahu[/TD]
[TD]3[/TD]
[TD]3[/TD]
[TD]3[/TD]
[TD]3[/TD]
[/TR]
</tbody>[/TABLE]

How would I write an equation that solves for the optimal value of this configuration (who to put at which four positions, to maximize total value)?

It seems more complex to me than a standard optimization problem, because it involves things like "if you use Steve here, then he can't play there" or "if you use Ahmed at his second-best position, it allows Steve to play his best position" (and then of course those combinations compound with further iterations).

So it may be that it just requires higher optimization logic than I can easily conceive. Or maybe this is an iterative solve? I really don't know where to start, and would appreciate the help.

Thanks!

 

[sheetspread]

I don't recall having much luck with solver the last time someone asked about this type of problem, but I only have the basic version included with Excel. It's not difficult to print every possible combination of the 11 names, and they'll be plenty of repeats because of impossible combinations where multiple instances of the same name occur on a line:

Excel 2010
	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R
1	1	1	1	1		5	4	2	1		12			Name	First Base	Second Base	Third Base	Shortstop
2	1	1	1	2		5	4	2	3		14			Sam	5	4	2	1
3	1	1	1	3		5	4	2	3		14			Tom	5	3	3	3
4	1	1	1	4		5	4	2	4		15			Will	2	3	3	3
5	1	1	1	5		5	4	2	6		17			Brian	4	3	4	4
6	1	1	1	6		5	4	2	3		14			Tod	5	6	2	6
7	1	1	1	7		5	4	2	4		15			Matt	6	3	3	3
8	1	1	1	8		5	4	2	3		14			Ahmed	2	7	1	4
9	1	1	1	9		5	4	2	6		17			Billy	3	1	3	3
10	1	1	1	10		5	4	2	4		15			Steve	2	3	6	6
11	1	1	1	11		5	4	2	3		14			Paul	1	4	1	4
12	1	1	2	1		5	4	3	1		13			Benjamin	3	3	3	3
Sheet2

Cell Formulas
Range	Formula
A1	=MOD(ROUNDUP(ROW(A1)/1331,0)-1,11)+1
B1	=MOD(ROUNDUP(ROW(A1)/121,0)-1,11)+1
C1	=MOD(ROUNDUP(ROW(A1)/11,0)-1,11)+1
D1	=MOD(ROW(A1)-1,11)+1
F1	=INDEX($O$2:$R$12,A1,COLUMN(A1))
G1	=INDEX($O$2:$R$12,B1,COLUMN(B1))
H1	=INDEX($O$2:$R$12,C1,COLUMN(C1))
I1	=INDEX($O$2:$R$12,D1,COLUMN(D1))
K1	=SUM(F1:I1)

Copy down to row 14641 (11^4) and then paste as values, sort the sums to get:

Excel 2010
	A	B	C	D	E	F	G	H	I	J	K
14640	6	7	9	5		6	7	6	6		25
Sheet2 (2)

which your map tells us is:

Excel 2010
	N	O	P	Q	R
1	Name	First Base	Second Base	Third Base	Shortstop
2	Sam	5	4	2	1
3	Tom	5	3	3	3
4	Will	2	3	3	3
5	Brian	4	3	4	4
6	Tod	5	6	2	6
7	Matt	6	3	3	3
8	Ahmed	2	7	1	4
9	Billy	3	1	3	3
10	Steve	2	3	6	6
11	Paul	1	4	1	4
12	Benjamin	3	3	3	3
13
14		6	7	9	5
15		Matt	Ahmed	Steve	Tod
16		6	7	6	6
Sheet2 (2)

Cell Formulas
Range	Formula
O15	=INDEX($N$2:$N$12,O14)
P15	=INDEX($N$2:$N$12,P14)
Q15	=INDEX($N$2:$N$12,Q14)
R15	=INDEX($N$2:$N$12,R14)

This is much better to do in C++ or any OOP/scripting language where you print to the command prompt rather than a much slower graphics heavy worksheet like Excel's. Especially as the number of names and positions increases for instance. Excel's row count is limited so you might also write a macro that deletes the unneeded lines as they appear.

 

[agutts6]

Thanks, this is wonderful.

My fear here is I don't entirely follow the logic; the logic is sort of the operative value here for me, as I presented an abridged version.... in reality I'll have up to 20 names and 9 positions (depending on the instance) and I'm wondering if this is too customized to the problem--as in, if I want to expand from how it's set up here.

Do you know what the solver hangups would be, and/or how to overcome?

I found a similar set of issues here; I wonder about adapting this to my question: Excel Solver Using Strings - Stack Overflow

 

[sheetspread]

The logic is very simple, you're looking at every possible combination of numbers 1-11 arranged in groups of 4. It's an easy way to do it, but not the most efficient. An algorithm would be better. Or perhaps solver combined with VBA like Tushar Mehta's method to find numbers in a group whose total is known: Combination of numbers that sum or match a target value

I tried solver again on this problem, with no success:

Excel 2010
	A	B	C	D	E	F	G	H	I	J	K	L	M	N
1	Name	First Base	Second Base	Third Base	Shortstop									# unique
2	Sam	5	4	2	1			1.10003	1.10003	1.10003	1.10003			0
3	Tom	5	3	3	3			First Base	Second Base	Third Base	Shortstop	sum
4	Will	2	3	3	3			5	4	2	1	12
5	Brian	4	3	4	4
6	Tod	5	6	2	6
7	Matt	6	3	3	3
8	Ahmed	2	7	1	4
9	Billy	3	1	3	3
10	Steve	2	3	6	6
11	Paul	1	4	1	4
12	Benjamin	3	3	3	3
Sheet3

Cell Formulas
Range	Formula
N2	=SUMPRODUCT(--(COUNTIF($H$2:$K$2,$H$2:$K$2)=1))
H4	=INDEX(B$2:B$12,H2)
I4	=INDEX(C$2:C$12,I2)
J4	=INDEX(D$2:D$12,J2)
K4	=INDEX(E$2:E$12,K2)
L4	=SUM(H4:K4)

I'll try to post the screenshot of the constraints

 

[sheetspread]

 

[sheetspread]

The solver method is easy, I must've been tired before the above post:

 

[sheetspread]

(The Objective Cell is L4)