EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
978. Uncertainty-affected graph problems solution through Bulk Optimization
Invited abstract in session TC-25: Graph and network optimization, stream Combinatorial Optimization.
Tuesday, 12:30-14:00Room: 011 (building: 208)
Authors (first author is the speaker)
| 1. | Paolo Paronuzzi
|
| DEI, University of Bologna | |
| 2. | Christoph Buchheim
|
| Fakultät für Mathematik, Technische Universität Dortmund | |
| 3. | Enrico Malaguti
|
| DEI, University of Bologna | |
| 4. | Michele Monaci
|
| DEI, University of Bologna |
Abstract
This work explores graph optimization problems, focusing on bulk optimization setting where potential link failures in different scenarios introduce uncertainty.
Bulk optimization, a recently introduced problem class in the literature, recognizes that in many practical cases, uncertainty affects only a small portion of the system. This contrasts with robust optimization, often considered overly conservative. Accordingly, the number of scenarios and the number of edges per scenario, although not necessarily low, are finite and limited.
Given a graph and a cost for each edge, our goal is to activate a subset of edges of minimum cost, ensuring that the resultant graph presents some desired structure (i.e., a perfect matching or a spanning tree) in each scenario.
Our study develops a Benders' decomposition approach where the master problem encapsulates variables determining which links to activate, while the subproblems verify the feasibility of the master solution in each scenario. The transformation of the subproblems into an efficiently solvable flow problems enhances computational tractability.
Although the bulk optimization paradigm has been studied for what concerns its theoretical properties, and some approximation algorithms have been proposed, we are not aware of any computational approach.
The proposed approach demonstrates promising results and applicability, offering a robust and scalable solution algorithm for graph problems in the presence of uncertainty.
Keywords
- Robust Optimization
- Graphs and Networks
- Programming, Integer
Status: accepted
Back to the list of papers