Uncertain multi-agent MILPs: A data-driven decentralized solution with probabilistic feasibility guarantees
We consider uncertain multi-agent optimization problems that are formulated as Mixed Integer Linear Programs (MILPs) with an almost separable structure. Specifically, agents have their own cost function and constraints, and need to set their local decision vector subject to coupling constraints due to shared resources. The problem is affected by uncertainty that is only known from data. We introduce a data-driven decentralized scheme for handling the combinatorial complexity of the resulting MILP, while providing a probabilistic feasibility certificate that depends on the size of the data-set. The proposed approach rests on a decentralized multi-agent MILP resolution algorithm recently introduced in the literature, which is extended here to an uncertain framework by using tools from statistical learning theory.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheorySimilar Papers 제목 키워드 기반
Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming
Cutting planes (cuts) play an important role in solving mixed-integer linear programs (MILPs), as they significantly tighten the dual bounds and improve the solving performance. A key problem for cuts is when to stop cut…
Decision MakingLearning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model
Cutting planes (cuts) are important for solving mixed-integer linear programs (MILPs), which formulate a wide range of important real-world applications. Cut selection -- which aims to select a proper subset of the candi…
Collision Avoidance Verification of Multiagent Systems with Learned Policies
For many multiagent control problems, neural networks (NNs) have enabled promising new capabilities. However, many of these systems lack formal guarantees (e.g., collision avoidance, robustness), which prevents leveragin…
Collision AvoidanceCAMBranch: Contrastive Learning with Augmented MILPs for Branching
Recent advancements have introduced machine learning frameworks to enhance the Branch and Bound (B\&B) branching policies for solving Mixed Integer Linear Programming (MILP). These methods, primarily relying on imitation…
Contrastive LearningImitation LearningOn Representing Mixed-Integer Linear Programs by Graph Neural Networks
While Mixed-integer linear programming (MILP) is NP-hard in general, practical MILP has received roughly 100--fold speedup in the past twenty years. Still, many classes of MILPs quickly become unsolvable as their sizes i…