Maximizing Happiness in Child-Ice Cream Matching
In this problem scenario, we aim to find the optimal matching between children and ice cream flavors to maximize overall happiness based on individual preferences. The task involves assigning specific flavors to each child while ensuring everyone receives exactly one serving to ensure a fair distribution. By formulating and solving a linear programming model, we can achieve an ideal solution that balances the happiness of the children with their favorite flavors.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
A Matching Example Equal number of children and ice-cream servings, each of a different flavor A matching: a way of giving every child exactly one total serving (e.g. a child may get half banana-split, and half chocolate fudge) Happiness: we are given a happiness value for each child-flavor pair, based on how much that child likes the flavor (non-negative) Goal: find the matching that maximizes the total happiness of the children
Name your quantities N = number of children (and also the number of flavors) Ci,j= the happiness of the i-th child with the j-th flavor
Decision variables xi,j: the amount of matching between i-th child and j-th flavor or the amount of assignment of the j-th flavor to the i-th child Must have 0 x 1 Matching problems occur everywhere: school choice, customers to clients, Uber drivers to passengers, etc.
LP formulation Maximize i=1..N,j=1..NCi,jxi,j Subject to: For all i = 1..N: j=1..Nxi,j= 1 For all j = 1..N: i=1..Nxi,j= 1 x 0 [Interpretation: Every child gets one unit of ice-cream] [Interpretation: Every unit of ice-cream gets allocated]
Specific instance Happiness Gloria Harish Ivy Dipping-dots 1 0 0.5 Espresso 0.75 2 1 Fudge 0.5 2.5 1.5 A version of this with candidate-job pairs is in the supplement notes.
Specific instance The solution where Happiness Dipping- dots Gloria Harish Ivy x11 = x22 = x33 = 1, 1 0 0.5 and all other variables are 0 is an optimum solution Espresso 0.75 2 1 Objective function = 4.5 Fudge 0.5 2.5 1.5
Specific instance The solution where Happiness Dipping- dots Gloria Harish Ivy x11 = x23 = x33 = 1, 1 0 0.5 and all other variables are 0 is also an optimum solution Espresso 0.75 2 1 Objective function = 4.5 Fudge 0.5 2.5 1.5
Specific instance The solution where Happiness Dipping- dots Gloria Harish Ivy x11 = 1, x22 = x23 = x32 = x33 = , 1 0 0.5 Espresso 0.75 2 1 and all other variables are 0 is also an optimum solution Fudge 0.5 2.5 1.5 Objective function = 4.5
Concern? If children share ice-cream servings, is that likely to lead to spread of infectious diseases? But we observed that if we used Excel s LP solver, we only got integer solutions Claim: If we solve this LP with Excel s LP solver, then we will always find an integer solution Not true for all LPs this one has some special structure
Basic Feasible Solution A solution is basic feasible if it is not the average of two other feasible solutions Also known as extreme solutions , vertex solutions If an LP has a basic feasible solution and an optimum solutions, then There exist optimum solutions that are basic feasible Most LP solvers will return basic feasible optimum solutions
Exercise Which of the three optimum solutions x11 = x22 = x33 = 1, everything else 0 x11 = x23 = x33 = 1, everything else 0 x11 = 1, x22 = x23 = x32 = x33 = , everything else 0 can not be a basic feasible solution?
Example: Matchings In this example, every basic feasible solution is integral In general, for the problem of finding the highest total compatibility matching, every basic feasible solution is integral as you solve the problem as an LP => Excel s LP solver will always return an integer solution as long
