NILG.AI

Is the fastest route always the best? This article may give you a different perspective if your answer is yes.

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 to find an optimal solution. The choice of the best path to take may depend on the variables we are considering, the available data, the system’s complexity, the time required to reach the best solution, etc.

In this article, 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: allocating real estate agents to apartments for sale.

Local optimization vs. Global optimization

Local and global optimization techniques try to find the best possible solution 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 is 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 (which 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 time is an important factor, a greedy approach can be enough.

Next, we will apply both approaches to a specific use case: allocating 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) we want to optimize. Is it time? Profit? The 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 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 can 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

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 apartment, we should give him more apartments of that type
2. Inventory: if a given agent already has similar apartments to sell, we should probably not allocate more apartments with those characteristics to him. 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 the 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 that our allocation model will try to maximize, assuming we want to allocation n apartments to real estate agents.

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 considering the impact of each allocation on the overall set of allocations. Therefore, we cannot assure that, in the end, we will reach the best solution, although we 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 about the overall set of allocations and not thinking about allocation by allocation. This means that the performance should be better, although 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 considering 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 consider allocations of multiple apartments.

Wrapping Up

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, where you can get practical skills in combinatorial optimization using Metaheuristics, and learn more about alternative methods to solving issues such as allocations!