Search code examples
pythonalgorithmoptimizationlinear-programmingmixed-integer-programming

Minimize number of shoppers used while buying all items

We have N shoppers with 100$ each and a list of M items that each cost [0-50$] (integer only) .

We need to buy all the items with the following requirements -

  1. Minimize the number of shoppers used
  2. If we need to use more than 1 shopper, minimize the variance in $ spent by the shoppers

Examples

  • 5 items costing [10,20,20,5,10]

    Solution = 1 shopper who buys all the items. Only use 1 shopper since total is $65 < $100 budget for a single shopper.

  • 5 items costing [50,15,30,30,10]

    Solution = Shopper 1 buys [50,15] and shopper 2 buys [30,30,10]

     We need to use 2 shoppers since total is > 100 & assign them so that the difference between the shoppers is minimal (only $5 here).

Pseudo code :

For n_shoppers in range(1,N) :

enter image description here

subject to constraints

![![Shopperi < 100

Break the loop as soon as the problem can be solved with a n_shoppers subset of the total shoppers (and thereby we have the minimum number of shoppers required, and the best assignments)

This is really slow and inefficient - any suggestions on how I can frame this problem better? I'm currently solving it using CVXPY.

Solution

  • One way is as follows.

    1. First solve the min shoppers model. Now you know the dimension of the model.
    2. Next solve the min variance model. As the number of shoppers is now constant, the mean is better defined (linear). The mean is difficult if the number of shoppers is not known. (An alternative would be to minimize the range: min UP-LO, UP>= shopper[i], LO <= shopper[i]).