zbMATH — the first resource for mathematics

Solution structure of some inverse combinatorial optimization problems. (English) Zbl 0932.90034
Summary: We consider some inverse combinatorial optimization problems, that is, for a given set of feasible solutions of an optimization problem, we wish to know: under what weight vectors (or capacity vectors) will these feasible solutions become optimal solutions? We analysed shortest path problem, minimum cut problem, minimum spanning tree problem and maximum-weight matching problem, and found that in each of these cases, the solution set of the inverse problem is characterized by solving another combinatorial optimization problem. The main tool in our approach is Fulkerson’s theory of blocking and anti-blocking polyhedra with some necessary revisions.

90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX Cite
Full Text: DOI