Optimization Online


Decentralized Online Integer Programming Problems with a Coupling Cardinality Constraint

Ezgi Karabulut(ezgi.karabulut***at***gatech.edu)
Shabbir Ahmed(shabbir.ahmed***at***isye.gatech.edu)
George L. Nemhauser(george.nemhauser***at***isye.gatech.edu)

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 item values. For any deterministic online algorithm for this problem, it has been shown that there exists a lower bound of $\Omega(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(\sqrt T)$ on the expected regret.

Keywords: distributed integer programming, online optimization, decentralized optimization

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: Georgia Institute of Technology - Atlanta, GA

Download: [PDF]

Entry Submitted: 09/11/2019
Entry Accepted: 09/11/2019
Entry Last Modified: 09/11/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society