Santa's Optimization Challenge for this Christmas

We are approaching Christmas and Santa is getting ready to make the kids happy (as well as the math geeks busy).

He/She has bought 300 gifts with different values for this purpose.The value of each gift is known to Sant as displayed in following figure (the bigger the more valuable).

Santa is trying to maximise the number of happy kids by delivering these gifts. Santa will do this distribution so the value of gift that every kid receives is more than a min threshold. As a matter of fact, Santa had spent all the money in his/her pocket for purchasing the gifts so he/she does not have any money to pay for a commercial solver/tool. Santa decided to use an open source (and free) optimisation tool called #Pyomo to do this task. Here is the problem formulation:

Xi,j indicates if gift i goes to the kid j

Yj indicates if kid j receives any gift

The Pyomo code is here as well:

Once the Mixed Integer Linear Model is solved, the solution indicates which gift belongs to which kid as shown in this Figure.

After checking the solution, Santa realised that the number of gifts that some kids receive are more than the capacity of his/her bag. Santa decided to limit the number of items per kid (let's say 10) by adding an extra constrain as follows:

The problem is resolved and the solution is as follows:

Let's hope all the kids are happy all around the world, not only during the Christmas period but also all the times.

• The data is available upon the request.
• Other Pyomo models are available here

Subscribe and Follow #pyomo4all for the upcoming posts. #Share it with your network as a Christmas gift.

#optimization #supplychain #orms #innovation #futurism #inspiration