Question

In the equation SEND + MORE = MONEY each letter represents a different digit (0-9). The addition is done in the usual way from right to left, first adding D and E to obtain Y (possibly with a carry-over), then adding N and R, and so on. Solve this problem using linear programming with integer and binary variables. (No credit is given for a solution without the appropriate spreadsheet model in Excel.)

Answer 1

Solution of LP model using EXCEL SOLVER is following:

FORMULAS:

	0	1	2	3	4	5	6	7	8	9	SUM		Digit
S	0	0	0	0	0	0	0	1	0	0	=SUM(B2:K2)		=SUMPRODUCT($B$1:$K$1,B2:K2)
E	0	0	0	0	0	0	1	0	0	0	=SUM(B3:K3)		=SUMPRODUCT($B$1:$K$1,B3:K3)
N	0	0	0	0	1	0	0	0	0	0	=SUM(B4:K4)		=SUMPRODUCT($B$1:$K$1,B4:K4)		SEND +	MORE	- MONEY
D	0	0	0	1	0	0	0	0	0	0	=SUM(B5:K5)		=SUMPRODUCT($B$1:$K$1,B5:K5)		=N2*1000+N3*100+N4*10+N5	=+N6*1000+N7*100+N8*10+N3	=N6*10000+N7*1000+N4*100+N3*10+N9	=	=P5+Q5-R5
M	1	0	0	0	0	0	0	0	0	0	=SUM(B6:K6)		=SUMPRODUCT($B$1:$K$1,B6:K6)
O	0	0	0	0	0	0	0	0	1	0	=SUM(B7:K7)		=SUMPRODUCT($B$1:$K$1,B7:K7)
R	0	0	1	0	0	0	0	0	0	0	=SUM(B8:K8)		=SUMPRODUCT($B$1:$K$1,B8:K8)
Y	0	0	0	0	0	0	0	0	0	1	=SUM(B9:K9)		=SUMPRODUCT($B$1:$K$1,B9:K9)
SUM	=SUM(B2:B9)	=SUM(C2:C9)	=SUM(D2:D9)	=SUM(E2:E9)	=SUM(F2:F9)	=SUM(G2:G9)	=SUM(H2:H9)	=SUM(I2:I9)	=SUM(J2:J9)	=SUM(K2:K9)

Solution:

Letter	Digit
S	7
E	6
N	4
D	3
M	0
O	8
R	2
Y	9