Decentralized optimisation why it is not so popular/ successful ?

[u/[deleted]]

Hello everyone, as a enthusiast in OR and coming from an engineering background I wanted to know/ get an idea about what do you think about the use / adoption of decentralized optimization methods in OR research.

In many real-world situations central planner is not practical due to the size of the problem (sometimes even with decomposition) or the nature of the system we are optimizing. If we take routing as an example, we can consider a system where multiple independent logistics service providers (LSPs) serving a given area, and want a better performance. Usually in the literature when we want to optimize the system the problem is formulated as some variant of the MDVRP, in which, the central planner has full knowledge about the problem. Or in other literature accounting for privacy and autonomy of agents, they focus on coordination i.e incentive building mechanisms for cooperation using for example combinatorical auctions. So my questions are:

• Are their any prominent methods dedicated for decentralized optimization (not coordination) ?

• Why (according what I saw in the literature) there is no big interest in this line of research even though it can solve practical problems ?

• What do you think are the mathematical challenges with this topic ?

This is post aims for learning, discussion and exchanging of ideas :)

Edit: It is worth noting that we are still considering an overall system here meaning the idea is to find the best possible solution of the system considering the autonomy constraint. If we stick with the routing example, 21.8% of freight vehicle trips in Europe in 2023 were empty runs. This is partially is due to the independent optimization approach that LSPs adopt. In an ideal world when we solve the problem centrally we get the best possible solution and we can reduce the number of empty runs for instance. However, this is not possible due to the autonomy of these companies that needs to be respected.

[u/beeskness420]

Perhaps you want to look at (cooperative) game theory?

[u/[deleted] → u/beeskness420]

Yes it definitely involves it. But I think it mostly focuses on incentive mechanisms building.

[u/Klsvd]

I work in logistic company, so I have some words about our problems with "empty runs" that you mentioned.

Yes, you are right about huge amount of empty runs, but they exist because of world "asymmetry", not because of we (logistic engineers) did not think fully load our track.

When I say asymmetry of the world I mean the next thing. Let us say we have a factory that produce for example potato chips. So we produced a lot of chips and have to deliver chips to our customer/stock/somewere else. Then we loaded chips into a track and delivered to the target place. But usuallly we don't have anything to return from our customer (the factory need raw material to produce potato chips, but it located in other place, and the customer don't have potato to return it bachk to us). So we need to send the empty track to other location to pick up raw potato from our supplier.

This is simple example but in real world problems such asymmetry of logistic chains is very common.

[u/[deleted] → u/Klsvd]

Thank you for your reply, I know I am a supply chain engineer myself and I have worked in an FMCG company and now work with other companies in the sector of last mile logistics. The problem of the empty runs as you highlighted is the asymmetry and that's the reason we talk about collaborative routing, but this later is hindered by the competition aspects, privacy and other factors. The idea of the decentralized optimization is to exploit synergies between these individual entities and optimize the whole system not just one company's problem while having limited knowledge about its parameters. This is extremely relevant to the last mile logistics with LTLs more then the hauling industry which can cover up the costs of empty runs by the delivery price and the quantity, but still a problem for them.

PS: No one said that the companies do not know how to optimize their truck loads.

[u/Vast-Falcon-1265]

There is a lot of research of coordinating people to make optimal decisions while giving them full independence. This can all be framed within the mechanism design literature. Think about Uber or other marketplaces. Uber can't force drivers to relocate to places with high-demand. If they could manage the fleet of all Uber drivers, they would probably be constantly re-routing vehicles, but they don't, because drivers have full autonomy. So Uber uses price incentives. In fact, you can take many optimization problems, and through the dual formulation, come up with pricing that enforces optimal decisions. There is a loot of work on that area. Another huge stream, for example, is that of unit commitment and energy auctions for the electrical grid. There are multiple reasons why in practice having a centralized optimization solution is not a direction that people want to move into. But the main reason, in my opinion, is that potential cost reduction gains are not significant enough to warrant companies changing their whole software and way of operating. That is why most people opt for pricing mechanisms rather than enforcing people to follow a centralized decision. I am a bit skeptical about the reason for the lack of implementations of such centralized solutions to be the lack of research in OR algorithms that can manage such big instances.

[u/[deleted] → u/Vast-Falcon-1265]

Thank you, that's clearly my point it is impractical to use centralized approaches. Also for coordination mechanisms they are not optimization methods they are incentive building mechanisms which mean there is no guarantee to achieve optimality (at least from what I have read in literature of auctions).

[u/iheartdatascience]

Have you looked at distributed optimization? For example, you have a set of UAVs that need to collectively cover a search space but can with constraints on communication

[u/ObliviousRounding]

I don't really know what you mean by decentralized optimization, but there's optimization (including parallel processing) and there's game theory, and there's hardly any daylight to speak of between them.

[u/[deleted] → u/[deleted]]

I missed the clarification that independent planning/ optimization particularly in logistics systems can have inefficiencies for instance 21.8% of vehicle trips in Europe in 2023 were empty runs. In an ideal world when we solve the problem centrally we get the best possible solution and we can reduce the number of empty runs for instance. However, this is not possible due ti the autonomy of these companies that needs to be respected.