Is the fastest route always the best? If your answer is yes, maybe this blogpost can give you a different perspective.

Normally there are multiple ways to tackle a given problem or task, and the optimization field is no different, as there are different approaches we can take in order to find an optimal solution. The choice of the best path to take may depend on the variables we are considering, the data we have available, the complexity of the system, the time required for reaching the best solution, etc.

In this blogpost we explore two well known approaches when it comes to optimization, Local Optimization and Global Optimization.

Besides discussing how they differ in terms of ideology, pros and cons, we will check their application in a real use case scenario: allocation of real estate agents to apartments for sale.

 

Local optimization vs Global optimization

 

Local optimization and global optimization techniques try to find the best solution possible using different routes.

Local optimization techniques normally are more “greedy”, as they prefer to follow the most promising path known until now, instead of exploring other search spaces. This type of optimization should be more suitable for simple systems where the number of variables to optimize are only a few and they are clearly identified. Furthermore, it can be used when we pretend to have an acceptable solution as quickly as possible.

On the other hand, global optimization focuses on finding the path to the best possible solution in the entire search space, even though it can take more time. This allows the creation of more reliable solutions, although it can take a bit more time to get there. This can be a good approach to follow if there is an unknown relationship between the different variables in the system, or we have a more complex or black-box system.

When training a machine learning model in AI, typically we try to prevent reaching a local optima (can be a good solution, but not the best one) as we hope to reach the global optima, which translates into a more robust and generalizable model. Although, in some cases where the time is an important factor, a greedy approach can be enough.

 

 

Next, we will apply both approaches to a specific use case: allocation of real estate agents to apartments for sale.

 

 

Use Case:

 

Assuming you are a real estate company, how could you optimize the allocations of apartments to the available real estate agents?

The first important aspect to consider is what variable(s) do we want to optimize. Is it time? Profit? Number of visits required? Diversity in the sales? A good assumption is to consider that we want to generate the maximum profit in the lowest time possible. Thus, a good metric to optimize might be the price per day (ratio between the profit and days required for the sale).

Data:

In terms of available data we assume we have the following information:

  • Apartment:
    • Number of  rooms
    • Area (M2)
    • Purchase price
    • Location
    • Features regarding infrastructures in the surrounding area
  • Real Estate Agent:
    • Inventory:
      • Number of  apartments to sell in total, based on location, price range, typology, area, etc
    • Historical sells:
      • Sells made in the past (for a specific time window) based on location, price range, typology, area, etc
  • Apartment vs Agent:
    • Predicted days in the market for a given (apartment, agent). That is, in how many days a given agent is capable of selling a given apartment.
      As this a more tricky information to have, an alternative can be to train a machine learning algorithm (based on the remaining data), that is able to predict the days in the market for a particular (apartment, agent)
  • Market:
    • Number of apartments sold in the past (x days)
    • Apartments currently available for sell

 

 

Applying Local optimization

 

Following the local optimization ideologies, a likely approach would be to start with the best matches between real estate agent and apartment, this means start by allocating the most suitable agents to the respective apartment first.

As we saw before, dollars/day is a good metric to take in consideration in the allocations, so the step 1 is to compute the dollars_per_day for every pair <Agent, Apartment>. Next, as this is a greedy approach, we rank the allocations (in descending order) by dollars_per_day value and start allocating the agents to the apartments with higher dollars_per_day metric.

Thus, the approach can be defined as follows:

  1. Compute dollars_per_day:
    1. Margin = agent valuation for a specific apartment – purchase price
    2. dollars_per_day = margin / prediction of days in market for (apartment, agent)
  2. Allocation process: ranking dollars_per_day (in descending order)

 

Applying Global optimization

 

Now using a global optimization approach, besides dollars per day, we can think of other metrics that may be relevant when measuring how suitable it is to allocate a given apartment to an agent.

  1. Selling_speed: if a given agent is good at selling a specific type of apartments, we should give him more apartments of that type
  2. Inventory: if a given agent already has similar apartments to sell, probably we should not allocate to him more apartments with those characteristics. An alternative is to define a maximum number of apartments assigned to a single agent.

(In this context, we assume that similar apartments have the same price range, area range and the same typology.)

Thus, there are 3 aspects to consider in the allocation model:

  • [maximize] dollars_per_day: profit/days, same as in local optimization approach
  • [maximize] Selling speed: percentage of similar apartments sold in the last X days
  • [minimize] Inventory: percentage of similar apartments in inventory

 

Using this information, we can define an objective function which our allocation model will try to maximize assuming we want to allocation n apartments to read estate agents.

 

     $$\frac{\sum_{}^{allocations} (\alpha * dollars\_per\_day + \beta * selling\_speed + \gamma * inventory)}{n}$$

 

This function corresponds essentially to a weighted average, in which, our allocation model will learn the best parameters for maximizing the objective function.

 

 

Comparison between solutions

 

Considering this specific use case, using a local optimization approach, we would be making the allocations sequentially (allocation by allocation), starting from the best allocations, without taking in consideration the impact of each allocation in the overall set of allocations. Therefore, we cannot assure that, in the end, we will reach the best solution, although it can get an acceptable solution in less time. If we apply a global optimization technique, globally, the allocations should be more accurate as we are thinking on the overall set of allocations, and not thinking allocation by allocation. This means that the performance should be better, although the the time to get the solution may be longer.

The fact that we may have multiple variables to optimize, depending on how we pretend to “measure” how good a given allocation is, is another factor that benefits the global approach instead of a local approach in this specific use case.

The amount of data available can also be an important decision factor when deciding the best approach. Typically, global optimization approaches require more data than local optimization approaches.

Finally, the type of data processing is also important, if the allocations are performed in batches, then, a global approach would determine the best allocations taking into account the entire system (set of all allocations). On the other hand, if the allocations are supposed to be delivered in a streaming fashion, then a greedy approach would be useful, as it does not need to take in consideration allocations of multiple apartments.

 

Conclusion

 

Going back to the first question, in the optimization field, the fastest and most promising path may not be the best to take after all, especially if it involves making several decisions along the way.

A local optimization approach may be more greedy in the way to find the best solution, which translates into a good solution, but not the best one. Using a more global optimization approach, it can take more time, and the obtained solution should be more trustable.

Did you use any of these approaches recently? Which one do you think is more appropriate to use? Feel free to get in touch with us, we would be happy to know your thoughts on this topic!

We also have a pre-order available for a Metaheuristics course on our website (https://learn.nilg.ai/courses/metaheuristics-theory-and-applications ), where you can get practical skills in combinatorial optimization using Metaheuristics, and learn more about alternative methods to solving issues such as allocations!