A marketing company has derived the following data from a social network: For a certain product1 they want to advertise, they know a set I of potential influencers, and a set C of potential customers. For each influencer i I, they also identified a subset C(i) C of customers, which will buy the product if the influencer posts about it on the social network. Moreover, they have a marketing budget B and know the costs wi , which they have to pay to influencer i I to post about the product.

(a) The company has just hired you as their data analyst and wants to know which influencers they should pay to post about the product in order that the maximum number of customers buys the product. Thus, they ask you if the problem can be modeled as integer linear programming problem? (2 pts) Hint: You know this problem/the needed model already, we have used it in the course before. The input was encoded a little differently when we have seen it before.

(b) They also ask you to implement the model in Python using DoCPLEX to solve the instance homework11.py given in Moodle. What is the optimal solution and what is the optimal solution value? (2 pts)

(c) As you finished the Python code, the company now notifies you that they do not want to buy an integer programming solver software and they thus ask you to design and implement a greedy heuristic to generate good solutions to the problem and test it with the instance given in Moodle. What solution do you obtain? Please provide a Pseudocode of your greedy heuristic. (2 pts)

Py file:

#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ Created on Fri Jan 14 14:00:45 2022 @author: """ import random random.seed(43) #number of influencers nI=10 #number of customers nC=100 #cost for paying the influencer to post c=[] for i in range(nI): c.append(random.randint(1,100)) print(c) #budget B=int(sum(c)/5) print(B) #C(i) list of lists C=[[] for i in range(nI)] #populates the list for i in range(nC): numberOfInfluencers=random.randint(1,3) c=0 while c