Fenchel-type duality for matroid valuations

The weighted matroid intersection problem has recently been extended to the valuated matroid intersection problem: Given a pair of valuated matroidsM_i = (V, _i, _i) (i = 1,2) defined on a common ground setV, find a common baseB _{1 2} that maximizes₁(B) + ₂(B). This paper develops a Fenchel-type duality theory related to this problem with a view to establishing a convexity framework for nonlinear integer programming. A Fenchel-type min max theorem and a discrete separation theorem are given. Furthermore, the subdifferentials of matroid valuations are investigated. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Part of this paper has been presented at fifth SIAM Conference on Optimization, Victoria, May 1996.This work was done while the author was at Forschungsinstitut für Diskrete Mathematik, Universität Bonn, 1994–1995.