Capacity Inverse Minimum Cost Flow Problem

In: The Forth Edition of ORP3 (Operational Research Peripatetic Post-Graduate Programme). 2007

Authors

• Cigdem Güler
• Horst W. Hamacher

Abstract

"Given a directed graph G=(N,A) with arc capacities and a minimum cost flow problem defined on G, the capacity inverse minimum cost flow problem is to find a new capacity vector for the arc set A such that a given feasible solution x° is optimal with respect to the modified capacities. Among all capacity vectors satisfying this condition, we would like to find one with minimum distance value.<br><br>We consider two distance measures rectilinear and chebyshev distances. By reduction from the feedback arc set problem we show that the capacity inverse minimum cost flow problem is NP-hard in the rectilinear case. On the other hand, it is polynomially solvable by a greedy algorithm for the chebyshev norm. In the latter case we also propose a heuristic for the bicriteria problem, where we minimize among all optimal solutions the number of affected arcs."

BibTeX

 
@InProceedings{ GuelerEtAl:cap_inverse, 
   title = { Capacity Inverse Minimum Cost Flow Problem }, 
   author = { Cigdem Güler and Horst W. Hamacher },   
   booktitle = { The Forth Edition of ORP3 (Operational Research Peripatetic Post-Graduate Programme) },              
   year = 2007, 
} 

---

This publication belongs to the project DeNDeMA.