PART A)

Give a Linear Integer Programming Model for the internet sites problem of deciding which customers gets a CD and at what price so that the total revenue is maximum. You can use the modeling tricks discussed in class. In taht case you need to decide values for two big-M type constants. Choose the smallest possible value as discussed in the lecture slides (hint: the upper bound on the difference between the LHS and RHS), and justify your choice. Notice that every CD must be assigned, but not every user can get a CD.

PART B)

Assume the valuations vij are random numbers from the uniform distribution U(1, 20). Code and solve your model in a solver of your choice for m = 10, n = 20 and m = 15 and n = 20 and m = 19, n = 20. Attach a brief output with results. Discuss the results with your observations

An internet site allows you to sell your classical music CD collection online. Your collection has m CDs. The selling procedure works as follows: every potential buyer i=1,,n sends online his/her valuations vij for every CD j=1,,m (e.g., v13=10 means customer 1 values CD 3 at 10 dollars). Having collected the valuations matrix V, the site decides which customer gets which CD, and what price he/she has to pay. The rule is that the CDs being rare collection items, every customer can only get one CD (or none at all since you do not want your entire CD collection transferred to another collecting person or store). The site is trying to maximize its total revenue (what is the objective function?). However, the following rules have to be observed: - If a customer i is assigned a CD j at a price pj then this must be one of the most advantageous CDs for him/her in terms of utility, i.e., vijpjvip,=j - If a customer i is assigned a CD j at price pj, then his/her utility must be non-negative. i.e., vijpj0. Assume n>m customers participate in the process. An internet site allows you to sell your classical music CD collection online. Your collection has m CDs. The selling procedure works as follows: every potential buyer i=1,,n sends online his/her valuations vij for every CD j=1,,m (e.g., v13=10 means customer 1 values CD 3 at 10 dollars). Having collected the valuations matrix V, the site decides which customer gets which CD, and what price he/she has to pay. The rule is that the CDs being rare collection items, every customer can only get one CD (or none at all since you do not want your entire CD collection transferred to another collecting person or store). The site is trying to maximize its total revenue (what is the objective function?). However, the following rules have to be observed: - If a customer i is assigned a CD j at a price pj then this must be one of the most advantageous CDs for him/her in terms of utility, i.e., vijpjvip,=j - If a customer i is assigned a CD j at price pj, then his/her utility must be non-negative. i.e., vijpj0. Assume n>m customers participate in the process