Optimization When True Costs Are Unknown

Question

Here is a problem I thought of:

Suppose there is a car repair shop and 5 mechanics work there. Everyday, new cars arrive at the shop and each mechanic has to choose 3 cars to work on. In short, the mechanics ideally want to choose cars that they think will be both :

Easy to work on (i.e. require fewer hours)

Pay them well (e.g. suppose the mechanics are paid 50% of the total price the customer pays)

The only problem is: the mechanics have no idea how much time any given car will require for repair (let's assume that no one knows this information exactly), nor do they know the amount of money the customers were charged (e.g. let's assume that the owner of the repair shop and the owner of the car negotiate the price in private). When making a decision on which cars to work on, the mechanics only have access to the following information:

Total Mileage each car has driven

Price that the customer originally purchased the car for

However, the mechanics have access to historical data. The mechanics have a dataset that contains all 4 of these variables - for all cars that all mechanics at this shop have serviced since the shop has opened, they have: Total Mileage, Original Price of Car, Number of Hours that were required (can consider this as a "supervised label"), Total Bill that the customer was charged (can consider this as a "supervised label").

On first glance, this problem sort of looks like the "Knapsack Optimization Problem" (https://en.wikipedia.org/wiki/Knapsack_problem) - however, in the "Knapsack Problem", we know in advance the "value and cost" (i.e. the "labels") of each potential item we would like to consider for the knapsack. In this car mechanic problem, we do not know the "labels" - information that will eventually be used for defining/calculating the costs and utility function.

Question: Can the mechanics train two separate supervised models (e.g. regression, random forest) on the data that they have, e.g.

Model 1: hours_car_requires = f(mileage, original_price)

Model 2 : total_bill = g(mileage, original_price)

Then, if these models are able to perform well on the training data - they can then use them to predict the "total bill" and the "hours required" for each new car that comes to the repair shop. From here, they could then turn this problem into a "multi objective optimization task" and use optimization algorithms to select cars to work on?

Can someone please tell me if this approach that I have described makes sense? Or are there already well established algorithms designed for these kinds of problems? My analogy was that on some abstract level, the mechanics selecting desirable cars to work is the same as choosing portfolios with low risk and high return.

Answer 1

Your approach is sensible. Knapsack can be thought of as a multi-objective problem being solved by the $\epsilon$-constraint method and to uncover the complete pareto front you need to vary how much hours are interested in working.

Here are things to consider:

• If there are clearly preferable cars the workers might want to work on it exclusively. This is not possible. So you are left in a situation where have 2 (time spent and money earned) times 5 (workers) competing objectives you need to balance
• The workers are being assigned new cars every day, so you are solving the problem repeatedly and therefor need to assign cars such that assignments in total are seen as fair by the workers, otherwise one might leave since he only got unpreferable assignments.
• Since your estimate is uncertain, if you are able to construct a model of your estimates (for example a bayesian) that captures this uncertainty you could do robust optimization to distribute uncertainty such that no worker risk working many more hours than he wants to or getting paid an unpredictable amount.

Answer 2

You might be interested in the following paper, in which the authors bake a predictive component (regression or neural network model) for the objective function into an optimization model.

Bergman D, Huang T, Brooks P, Lodi A, Raghunathan AU (2019b) Janos: An integrated predictive and prescriptive modeling framework. arXiv preprint arXiv:1911.09461