Decentralized online integer programming problems with a coupling cardinality constraint. (November 2021)

• Record Type: Journal Article
• Authors: Karabulut, Ezgi; Ahmed, Shabbir; Nemhauser, George
• Is Part Of: Computers & operations research. Volume 135(2021)
• Publication Date: 2021-11
• Subjects: Decentralized optimization -- Online optimization -- Distributed integer programming -- Resource allocation; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105421
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: We consider a problem involving a set of agents who need to coordinate their actions to optimize the sum of their objectives while satisfying a common resource constraint. The objective functions of the agents are unknown to them a priori and are revealed in an online manner. The resulting problem is an online optimization problem to optimally allocate the resource among the agents prior to observing the objective functions. For any deterministic online algorithm for this problem, it has been shown that there exists a lower bound of Ω ( T ) on regret. When the agents' integer programs satisfy a discrete concavity condition, we propose a randomized online algorithm that is decentralized and guarantees an upper bound of O ( K T ln m ) on the expected regret, where K is the total amount of resource to be shared and m is the number of agents. Highlights: Multiple agents tackle the online resource allocation problem in a decentralized way. State-of-the-art error bounds cannot be reached with deterministic algorithms. The solution is to apply randomized algorithms. We propose a decentralized randomized algorithm for online resource allocation.