Integer programming with binary variables in Solver - issue with constraint?

[tyedye4]

Hi all,

I am learning to use Excel Solver with no prior exposure. I thought I was starting to understand it, until I started working on a problem with binary variables. The objective is to maximize the number of customers reached by selecting one or more websites to advertise on. The constraint is that the budget cannot exceed $10,000. Additionally, each customer can only be counted once regardless of how many websites they visited.

The dataset I'm working with has 53 rows of customers and 10 columns for websites. A customer who has visited a website will have a 1 in the column, 0 otherwise. Without sharing the whole spreadsheet, the layout appears as so. I thought by adding across the columns I could set a mutually exclusive constraint in Solver to prevent it from counting one customer multiple times, but it does not appear that I have set it up correctly. Using the below as an example, the formula I'm using to add the values in the row is in F6. My constraint is $F$6:$F$9 = 1. If I remove this constraint, Solver can produce a solution, except it's counting each customer multiple times (based on what each column is adding up to) and that's not quite what I need to do.

I would be very grateful for advice in how to approach this problem. Please let me know if there's any additional information that would be helpful.

	B	C	D	E	F
Customer	1	2	3	4
1	0	0	1	0	=SUM(B2:B5)
2	1	1	0	0
3	0	1	0	1

 

[StephenCrump]

Welcome to the Forum!

Based on the limited data posted, website 2 looks optimum (before we factor in the relative costs) as it reaches 2 out of 3 customers.

This analysis involves adding up each column. It's not clear why you're adding across the columns? Is it relevant to the calculation?

 

[tyedye4]

Welcome to the Forum!

Based on the limited data posted, website 2 looks optimum (before we factor in the relative costs) as it reaches 2 out of 3 customers.

This analysis involves adding up each column. It's not clear why you're adding across the columns? Is it relevant to the calculation?

Thank you for the welcome.

I had it in my head that in order to force Solver to count each customer once and only once (even if they visited multiple websites, only one should be chosen), I would need to add across the row. The more I think about it, the more it doesn't make much sense and it doesn't seem to be working that way. I attached a preview of the full spreadsheet model.

 

[StephenCrump]

Here's what I think you're trying to do:

	A	B	C	D	E	F	G	H	I	J	K	L
1
2	Website		1	2	3	4	5	6	7	8	9	10
3	Cost		$5.00	$8.00	$3.50	$5.50	$7.00	$4.50	$6.00	$5.00	$3.00	$2.20
4	Pick?		0	0	0	0	0	1	0	0	1	1
5
6	Budget	$10.00
7	Total Cost	$9.70
8	Reach	20
9
10			8	11	5	10	13	7	10	7	6	7
11	Customer
12	1		1	0	0	0	1	1	1	0	0	0
13	2		0	0	0	1	1	0	1	1	0	1
14	3		0	1	0	0	1	0	1	1	0	0
15	4		0	1	0	1	1	0	0	1	1	0
16	5		0	1	0	0	1	0	1	0	0	0
17	6		0	0	0	1	1	0	0	0	0	1
18	7		0	0	0	0	1	1	0	0	0	0
19	8		1	0	1	0	1	0	1	0	0	0
20	9		1	1	0	1	1	1	0	0	0	0
21	10		0	0	1	1	0	0	0	0	1	0
22	11		1	0	0	1	1	0	1	0	0	0
23	12		1	1	1	1	1	1	1	0	0	0
24	13		0	1	0	0	0	0	0	0	0	0
25	14		0	1	1	1	0	1	0	1	1	0
26	15		0	0	1	0	0	0	1	0	1	0
27	16		0	1	0	0	1	0	1	1	1	0
28	17		1	1	0	1	0	0	0	1	1	1
29	18		1	1	0	1	1	0	0	1	0	0
30	19		1	0	0	0	0	1	0	0	0	1
31	20		0	1	0	0	0	1	1	0	0	0
Sheet1

Cell Formulas
Range	Formula
B7	B7	=SUMPRODUCT(C4:L4,C3:L3)
B8	B8	=SUMPRODUCT(C10:L10,C4:L4)
C10:K10	C10	=SUM(C12:C31)

Named Ranges
Name	Refers To	Cells
solver_adj	=Sheet1!$C$4:$L$4	B7:B8
solver_lhs2	=Sheet1!$C$4:$L$4	B7:B8

This is not the optimum solution - you can reach 20 with a lower spend. I could be wrong (I don't use Solver myself, so I'll be happy to be corrected) but I don't think it's possible to set major and minor objectives, i.e. in this case:

Major: Maximise Reach (subject to Spend <= Budget), and
Minor: Minimise Spend (within Budget)

But you can get there with a second step - the optimum solution is to advertise in 5 and 10 at cost $9.20 for a reach of 20.